На этом шаге решим задачу линейного программирования М-методом.
Минимизировать z = 4x1 + x2.
При условиях:
3x1 + x2 = 3,
4x1 + 3x2 ≥ 6,
x1 + 2x2 ≤ 4,
x1, x2 ≥ 0.
Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной x3 во второе неравенство и дополнительной (остаточной) переменной x4 в третье неравенство. Эта задача в стандартной форме:
Минимизировать z = 4x1 + x2.
При условиях:
3x1 + x2 = 3,
4x1 + 3x2 - x3 = 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4 ≥ 0.
В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MR1 + MR2. В результате получим следующую задачу линейного программирования:
Минимизировать z = 4x1 + x2 + MR1 + MR2.
При условиях:
3x1 + x2 + R1 = 3,
4x1 + 3x2 - x3 + R2= 6,
x1 + 2x2 + x4 = 4,
x1, x2, x3, x4, R1, R2 ≥ 0.
В этой модифицированной задаче переменные R1, R2, x4 можно использовать в качестве начального допустимого базисного решения. Получим следующую симплекс-таблицу:
Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. Значение функции z, соответствующее начальному базисному решению R1 = 3, R2 = 6, x4 = 4, должно равняться 3M + 6M + 0 = 9M, а не 0. Это несоответствие связано с тем, что переменным R1 и R2 соответствуют ненулевые коэффициенты (-М,-М) в строке z. Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк R1 и R2 на величину М, и затем сложить эти строки с z-строкой (если бы коэффициенты в строках R1 и R2 были бы отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты):
Новая z-строка = Старая z-строка + М * R1-строка + М * R2-строка
Выполним эту операцию в данном примере:
Измененная симплекс-таблица:
Таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости (см. шаг 28). Т.к. нужно минимизировать целевую функцию, то находим наибольший положительный коэффициент в z-строке. Наибольший коэффициент -4+7М соответствует переменной x1, которая будет вводимой. Условие допустимости указывает на переменную R1 в качестве исключаемой. Воспользуемся методом Гаусса-Жордана для вычисления новой симплекс-таблицы. Выполните действия самостоятельно! В результате получим следующую таблицу.
Первая итерация исключила из базисного решения искусственную переменную R1, что является результатом включения штрафа в целевую функцию.
Последняя таблица показывает, что следующими, вводимой и исключаемой, переменными будут х2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет х1 = 2/5, х2 = 9/5, х3 = 1 и z = 17/5.
На следующем шаге рассмотрим применение и реализацию с помощью TORA М-метода решения задач ЛП.
