Методы оптимизации транспортной задачи

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

- Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом;

- Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации.

По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы:

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

- В противном случае задачи называются задачами нелинейного программирования и используют для их решения соответствующие методы. В свою очередь из них выделяются две частные задачи:

1) если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования;

2) если , то имеют дело с задачей целочисленного (дискретного) программирования.

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

- прямые методы, требующие только вычислений целевой функции в точках приближений;

- методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

- аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

- численные методы;

- графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

- задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или четно;

- задачи целочисленного программирования - если X является подмножеством множества целых чисел;

- задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.

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

Кроме того, разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование. Математическое программирование используется при решении оптимизационных задач исследования операций. [5]

Таблица 3.1 – Методы оптимизации

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

1. Определение границ системы оптимизации

Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

2. Выбор управляемых переменных; «Замораживаем» значения некоторых переменных (неуправляемые переменные), а другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)

3. Определение ограничений на управляемые переменные (равенства и\или неравенства)

4. Выбор числового критерия оптимизации