Замечание. 1. Любую задачу максимизации можно свести к задаче минимизации, умножив целевую функцию на (-1), и наоборот

1. Любую задачу максимизации можно свести к задаче минимизации, умножив целевую функцию на (-1), и наоборот.

2. При заполнении симплекс таблицы нужно обратить внимание на строку оценок: С₀ берется со своим знаком, а коэффициенты С_j - с противоположным знаком из целевой функции.

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

Алгоритм симплекс-метода

1. Заполняем симплекс-таблицу по данным задачи в каноническом виде (*).

2. Если выполнено условие оптимальности, то базисный план задачи оптимален и решение задачи получено.

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

4. Выбираем направляющий столбец S по наименьшему или наибольшему по модулю положительному (отрицательному) элементу строки оценок для задачи минимизации (максимизации).

5. Составляем отношения положительных элементов столбца свободных членов b к соответствующим положительным элементам направляющего столбца. Среди них выбираем наименьшее, т.е. если ; то r – направляющая строка, и элемент a_rs - это генеральный или ключевой элемент на данном шаге.

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

1) Элементы направляющей строки умножаются на 1/a_rs.

2) Все остальные элементы пересчитываются по правилу прямоугольника

7. Возвращаемся к пункту 2.

Пример. При условии предыдущего примера для решения применим симплекс-метод. Для задачи в основном виде

10x₁+20x₂≤100 10x₁+20x₂+x₃=100

20x₁+10x₂≤100 получим 20x₁+10x₂+x₄=100 - канонический

15x₁+15x₂≤90 15x₁+15x₂+x₅=90 вид

ƒ(x₁,x₂)= 20x₁+30x₂ →max

Строим симплекс-таблицу:

Т.к. все оценки последней симплекс-таблицы неотрицательны, то выполнено условие оптимальности, а, значит, получено оптимальное решение (см. столбец b последней симплекс-таблицы): α_опт (2;4;0;20;0), т.е. x₁=2; x₂=4; x₃=0; x₄=20; x₅=0. Экономический смысл переменных x₃, x₄, x₅ – остатки сырья каждого вида: сырье 1 и 3-го вида израсходовано полностью, а сырье 2-го вида использовано на 80 единиц из 100. Значения x₁=2; x₂=4 определяют оптимальное время использования 1-го и 2-го технологических способов, что позволит получить наибольшее количество произведенной продукции ƒ(α_опт)=160.