Методы оптимизации

Задача выбора оптимального решения относится к классу задач математического программирования, в основе которых лежит поиск безусловного и условного экстремума. Так, задачи максимизации прибыли в экономике, или минимизации ущерба при стихийном бедствии, или выбора кратчайшего маршрута при мини­мизации транспортных потерь и т. д. - все в конечном итоге сводятся к макси­мизации (или минимизации) целевых функций при условии заданных ограни­чений.

Таким образом, задачи поддержки принятия решений, относящиеся к одним из основных при моделировании в ГИС, в той или иной степени связаны с выбором целевых функций и математическим программированием.

2.1. Линейное программирование

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

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