Задачи оптимизации пространственного расположения объектов

Тема: решение задач нелинейного программирования

Общая постановка задачи нелинейного программирования:

( ; ). (1)

Функция в (1) называется целевой функцией, а функции и - функциями ограничений. В общем случае целевая функция и функции ограничений могут быть нелинейными функциями.

Задача 1 может быть решена средствами Excel с помощью встроенной процедуры Solver («Поиск решения»). Однако при этом очень внимательно следует выбирать точку начального приближения. Это обстоятельство особенно важно для так называемых мультимодальных функций, имеющих более одного экстремума).

Пример. Функция Химмельблау

имеет четыре изолированные точки минимума.

Фрагмент рабочего листа Excel с найденными точками минимума:

Для того чтобы правильно выбрать точки начального приближения, рекомендуется предварительно провести аналитическое исследование функции на наличие и тип экстремумов. Если это затруднительно, можно протабулировать функцию на интересуемой области и построить ее график с помощью мастера диаграмм:

Заметим, что в случае, когда целевая функция имеет зависимость более чем от двух переменных, графическое исследование ее свойств затруднено. В любом случае желательно использовать аналитические методы.

Задачи оптимизации пространственного расположения объектов

Задача 1. В связи с реорганизацией служб здравоохранения г.Фомска по распоряжению администрации города должен быть создан городской Депозитарий (станция переливания) крови. Клиентами Депозитария будут четыре районных госпиталя г.Фомска, расположенные в различных частях города в точках с координатами, указанными в приведенной ниже таблице. В этой же таблице указано также среднее число обращений в сутки из госпиталей в Депозитарий за кровью:

Госпиталь	Расстояние от базовой точки (км)	Среднее число обращений в день
На восток	На север
«Кировский»
«Советский»
«Октябрьский»
«Ленинский»

Требуется определить координаты расположения Депозитария из критерия минимизации издержек на транспортировку запрашиваемой крови из него в госпитали города.

Решение. Обозначим: координаты i-го госпиталя; частота обращений в Депозитарий из i-го госпиталя; координаты Депозитария. Тогда расстояние от i-го госпиталя до Депозитария равно , следовательно, общая ежедневная средняя длина пути при транспортировке крови к i-му госпиталю равна . Таким образом, решение задачи состоит в определении координат , при которых общая средняя длина пути R при транспортировке крови во все госпитали минимальна:

Ограничений на координаты в данной задаче нет.

Ниже приведен фрагмент листа Excel с решением данной задачи.

Задача 3. Две деревни А и В расположены на берегу реки на расстоянии кмдруг от друга, третья деревня С находится на той же стороне реки и удалена от деревень А,В на расстояния соответственно и км. Русло реки в окрестностях деревень прямолинейно. Если пристань П построить на расстоянии x от от деревни А, то расстояния от пристани до деревень А,В,С будут выражаться соответственно формулами (проверить!)

В каком месте следует построить пристань, чтобы сумма расстояний от пристани П до деревень была бы наименьшей?

Ответ: пристань П следует построить между деревнями А и В на расстоянии км от деревни А.