Симплекс-метод с искусственным базисом (М-метод).

М-метод заключается в применении правил симплекс- метода к так называемой М-задаче.

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки Дj теперь будут зависеть от «буквы М». Для сравнения оценок нужно помнить, что М— достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

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

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

L. Пример 8. Найти максимум целевой функции: тах/(Х) = = 3*, + 2х2 + х3 при условиях

2*i + *2 = 8, *1 + х2 + *3 = 6, *1 > 0,х2 > О, *3 > 0.

Решение. Матрица условий содержит только один единичный вектор, добавим еще один искусственный вектор (искусственную неотрицательную переменную У\ в первое ограничение):

Получим следующую М-задачу: найти максимум целевой функции max f(X) = 3*х + 2х2 + х3 - Му1 при условиях

2*i + *2 + у\ = 8, *1 + *2 + *3 = 6, *1 > 0, *2 > о, *з > О, У1 > 0.

М-задачу решаем симплекс-методом.

Таблица 2.3 Номер симплекс-таблицы ч Базис в 3 2 1 -м Q Pi 0 -м <-?Pi 8 1 2 | 1 0 1 4 1 м 6 1 1 і 0 6 - -8М+6 -2М-2 -М-1 0 0 - I 3 1 Аз 4 2 1 0 0,5 0,5 0 X - 14 0 0 0 В начальной таблице наименьшее Дj соответствует вектору А\ — он вводится в базис, а искусственный вектор Pi из базиса выводится, так как ему отвечает наименьшее Q. Столбец, соответствующий Pi, из дальнейших симплексных таблиц вычеркивается.

Полученный новый опорный план является опорным планом исходной задачи. Для него все Ду > 0, поэтому он является и оптимальным. Таким образом получен оптимальный план исходной задачи (4,0,2), и максимальное значение

целевой функции ДХ*) = 14. Л

L Пример 9. Решить ЗЛП: min f(X) = 10*! - 5*2 при условиях:

2*i - *2 > 3, *1 + *2 > 2, *! + 2*2 > "І, *1>2 ? 0.

Приведем ЗЛП к каноническому виду, перейдя к задаче «на максимум»: max/j(X) = -10* і + 5*2 при условиях:

2*х - *2 - *з = 3, *! + *2 - *4 = 2, -*! - 2*2 + *5 = 1, Xj > О, j = ^5 .

Для нахождения опорного плана переходим к М-задаче: maxg(X,Y) = -10*! + 5*2 - М(уі + у2) при условиях:

2*і - *2 - х3 + г/1 = 3, *1 + *2 - *4 + у2 = 2, -*1 - 2*2 + *5 = 1, ^1,2,3,4,5 ^ °'У 1,2 ^ 0-

Дальнейшее решение проводим в симплекс-таблицах (табл. 2.4).

Таблица 2.4 Номер

симплекс-

таблиц X Базис В -10 5 0 0 0 -м -м Q А Ai Az As А, А5 Pi Ря -м 3 1 2 1 -1 -1 0 0 1 0 3/2 0 -м 2 1 1 0 -1 0 0 1 2 0 А5 1 -1 -2 0 0 1 0 0 - - - А/ -5М -ам+ю -в" м м 0 0 0 -10 3/2 і -1/2 -1/2 0 0 V 0 - I -м 4-Р* 1/2 0 1 3/2 1 1/2 -1 0 л 1 1/3 0 Ац 5/2 0 -5/2 -1/2 0 1 / \ 0 - - N -М/2-15 0 -ЗМ/2 -М/ 2+5 м 0 0 -10 А, 5/3 і 0 -1/3 -1/3 0 V V II 5 ->а2 1/3 0 1 1/3 -2/3 0 л X 0 А5 10/3 0 0 0 -5/3 1 / \ /\ - - А/ -15 0 0 5 0 0 В симплекс-таблице II получен опорный план исходной ЗЛП; поскольку все оценки A j > 0, j = 1,5, то этот план является и оптимальным, т.е. х{ = 5/3, х\ = 1/3 (исходные переменные), = 10/3, = 0, х\ = 0 (дополнительные переменные), при этом min f(X) = - max Д(Х) = -(-15) = 15 .

Вопросы и задания 1.

В чем суть принципа оптимальности в планировании и управлении? 2.

Сформулируйте общую постановку задачи линейного программирования. Каковы особенности канонической формы записи этой задачи? 3.

Дайте общую характеристику метода Жордана-Гаусса исследования систем линейных уравнений. 4.

В чем заключается геометрическая интерпретация задачи линейного программирования? 5.

Каковы основные этапы графического метода решения задач линейного программирования? 6.

В чем суть симплекс-метода? На каких свойствах задач линейного программирования он основан? 7.

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

Когда возникает необходимость использования симплекс-метода с искусственным базисом (М-метода)? В чем суть этой модификации симплекс-метода?

Упражнения a) maxf(X)= -*i + х2 б) min f(X)= -2*i - Sx2

+ x2 < 15 3*! + 3*2 ^ 15

*1 + *2 < 3 *i + 3*2 < 9

*2 ^ 6 *i < 4

хъх2>0; *l,*2>0;

в) min f{X)=2xi - 3*2

2*i - *2 - *з > 3 *1 - *2 + *3 2; 2 *1,*2, *3^ 0.

4. Для выпуска четырех видов продукции требуются затраты сырья, рабочего времени и оборудования. Исходные данные приведены в таблице: Тип Нормы затрат ресурсов на единицу продукции Наличие ресурса 1 2 3 4 ресурсов Сырье 3 5 2 4 60 Рабочее время 22 14 18 30 400 Оборудование 10 14 8 16 128 Прибыль на еди ницу продукции 30 25 8 16 Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции.