Анализ результатов решения. При упорядочении найденного решения получаем, что в качестве оптимального плана
При упорядочении найденного решения получаем, что в качестве оптимального плана данной задачи найдены две цепочки (петли) переходов. Они отмечены стрелками на рисунке с результатом поиска решения. Следовательно, найденное решение не удовлетворяет условиям задачи ввиду наличия в нем подциклов (петель).
1. Введите дополнительное ограничение, исключающее наличие найденных в плане петель. Для этого выполните следующие действия:
· В любой ячейке, например, D25 подсчитайте сумму найденных переходов =СУММ(E9;B10;F11;C12;G13;D14), которая равна 6.
· Проведите повторный поиск решения, добавив новое ограничение D25 ≤ 5.
2. Найденный план задает план переходов между городами, не содержащий петель, представленный на Рис. 49.
3. Сохраните задачу в виде книги Excel с именем «Задача-о-назначениях.xls».
Рис. 49. Результат поиска решения без «петель».
Особенностью задач о назначениях является то, что переменные (значения изменяемых ячеек) являются булевыми переменными, т.е. могут принимать значение «0» либо «1».
Задача нелинейного программирования .
Задача оптимального управления
Рассматриваемая задача относится к задачам с нелинейной моделью.
Содержательная постановка задачи
При застройке нового микрорайона требуется определить месторасположение нового торгового центра. Для обеспечения удобства жителей района необходимо так разместить торговый центр, чтобы суммарное расстояние переходов от него до жилых массивов было минимальным. Координаты жилых массивов приведены в Таблице 10.
Таблица 10
Исходные данные
Математическая модель – представлена в таблице 11.
Таблица 11
Математическая модель
Оптимизационное моделирование
Построение модели
1. На рабочий лист Excel введите:
· исходные данные – координаты жилых массивов – ячейки B3:B6; C3:C6;
· изменяемые ячейки – координаты торгового центра – ячейки B8 и C8;
· формулы для расчета расстояний между торговым центром и жилыми массивами – ячейки D3:D6;
· формулу для расчета ЦФ - суммарного расстояния между торговым центром и жилыми массивами (min) – ячейка D7.
2. Результаты ввода данных в числовом и формульном режимах представлены на Рис. 50. и Рис. 51.
Рис. 50. Фрагмент рабочего листа в символьном режиме.
Рис. 51. Фрагмент рабочего листа в режиме формул.
Исследование модели
1. Выполните поиск решения ЦФ (min), не задавая ограничений (Рис.52).
Рис. 52. Настройка окна ПОИСК РЕШЕНИЯ без ограничений
2. Результат поиска решения и план застройки представлен на Рис.53.
3. Для построения плана застройки в качестве исходных выберите диапазон данных с координатами жилых массивов B3:C6 и координаты торгового центра B8:C8. Чтобы выделить несмежные ячейки, необходимо удерживать клавишу Ctrl. Тип диаграммы – «Точечная».
Рис. 53. Фрагмент рабочего листа с результатами поиска решения
Изменение модели
Допустим, на застраиваемой жилыми массивами территории расположен парк с координатами из Таблицы 12.
Таблица 12
Координаты парка
Исследование модели
1. Добавьте ограничения, учитывающие парковую зону, и снова выполните процедуру поиска решения (Рис. 54).
Рис.54. Настройка окна ПОИСК РЕШЕНИЯ с ограничениями
2. Результаты представлены на Рис. 55.
Рис. 55. Фрагмент рабочего листа с результатами поиска решения.
3. Сохраните задачу в виде книги Excel с именем «Жил-массив.xls».