13. Нахождение исходного опорного решения.

1) Фиксируют уравнение с максимальным по модулю отрицательным свободным членом.

2) Почленно вычитают фиксированное уравнение из остальных уравнений с отрицательными свободными членами.

3) Обе части фиксированного уравнения умножают на «-1».

4) Остальные уравнения системы с неотрицательными свободными членами переписывают без изменений.

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

а) Все коэффициенты при неизвестных в фиксированном уравнении неположительны, т.е. опорных решений нет.

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

в) Разрешающий элемент не принадлежит фиксированному уравнению, тогда симплексные преобразования проводят до тех пор, пока не придут у случаю 1 или 2. При этом необходимо следить за тем, чтобы преобразования не повторялись.

14. Симплексный метод.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

∆ = 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