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

Симплексный метод позволяет путем ряда преобразований, состоящих в переходе от одного опорного решения к другому (причем так, что значение целевой функции все время возрастает (max) или убывает (min)), находить оптимальное решение за конечное число шагов, либо показать неразрешимость исходной задачи.

Подготовка к решению задачи симплексным методом:

1) приведение задачи к каноническому виду

2) приведение системы уравнений к единичному базису

3) нахождение исходного опорного решения

Решение симлекс-методом:

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Исходный опорный план проверить на оптимальность, в результате чего может иметь место один из 3 случаев:

а) если Δj≥0, то исходный опорный план является оптимальным.

б) если Δj<0 и все элементы соответствующего столбца ≤0, то целевая функция не огранична сверху на множестве ее плана.

в) Δj<0 и для каждого такого j по крайней мере одно aij положительное, то можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции возрастает.

4. Найти разрешающий столбец и разрешающую строку. Разрешающий столбец определяется наибольшей по абсолютной величине отрицательной оценкой Δj. Разрешающая строка определяется минимальным отношением свободных членов к положительным элементам разрешающего столбца.

5. Сделать соответствующие замены в столбцах Вб и Сб и проделать один шаг метода Ж. Гауса с найденный разрешающим элементом. Пересчитать элементы в строке Δ.

6. Проверить найденный опорный план на оптимальность. Если план неоптимален и необходимо пререйти к новому опорному плану, то возвращаемся к пункту 2, а в случае получения оптимального плана или усановления неразрешимости задачи решение задачи заканчивают.

Приращение целевой функции

Приращение – разность между последующей и предыдущей функциями

∆ = Z2 – Z1 >0

X1 àZ(X1) =Z1

| | |

X2 àZ(X2) =Z2

Z2=(z1aij-∆jbi) \ aij=Z1 - ∆jbi\aij

∆ = Z1 - ∆jbi/ aij – Z1 = -∆jbi/ aij > 0

∆j < 0

Критерии оптимальности

Теорема 1: Опорный план Х*=(х1*, х2*, 0,…, 0) задачи (1) – (3) является оптимальным, если ∆j ≥0, j = 1, n.

Теорема 2: Если ∆k< 0 для некоторого j=k и среди чисел aik нет положительных (aik ≤ 0), то целевая функция (1) задачи (1) – (3) не ограничена на множестве ее планов.

Теорема 3: Если ∆k < 0 и опорный план Х задачи (1) – (3) не вырожден, но среди чисел aik есть положительные (не все aik ≤ 0), то существует опорный план Х’ такой что Z(X’) >Z(X)

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

Поиск по сайту: