Тема 2.8 Решение задачи линейного программирования

Полагая переменные (свободные) , ...,x_n равными нулю, получим первое базисное решение (a , a ,…, a 0...,0) и первое значение f целевой функции, соответствующее этому решению. Первый базисный план и первое значение целевой функции образуют последний правый столбец таблицы 2.2. В верхней нулевой строке таблицы 2.2 записаны все переменные задачи ЛП, в левом нулевом столбце записаны базисные переменные. Будем рассматривать задачу на максимум функции f.

Переход ко второй симплекс-таблице осуществляется следующим образом: выбираем j -й столбец (разрешающий) таблицы 2.2 из условия, что является наибольшим по модулю отрицательным индексом и хотя бы один из элементов a >0;

выбираем i -ю строку (разрешающую) из условия, что:

a / a =для a >0,

принимая a в качестве разрешающего элемента, производим преобразование коэффициентов таблицы

(в том числе элементов индексной строки) так, как это делается при решении системы уравнений методом Жордана-Гаусса:

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

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

Если в очередной симплекс-таблице:

1) найдется хотя бы один отрицательный индекс и в каждом столбце с отрицательным индексом окажется хотя бы один положительный элемент, то план можно улучшить, перейдя к следующей симплекс-таблице;

2) найдется хотя бы один отрицательный индекс и все элементы в столбце, содержащем этот индекс отрицательные, то

fmax =+

3) нет ни одного отрицательного индекса, то достигнут оптимальный план.

Пример. Найти наибольшее значение функции

f = 5 x + 2 x , если x , x неотрицательные и удовлетворяют системе неравенств:

Решение. Вводим балансовые переменные х₃, x , x и получаем систему уравнений:

Целевую функцию представим в форме:

f = 0 - (-5x - 2х ). Составляем первую симплекс-таблицу 2.3:

Таблица 2.3

Б.п.						с.к.
	-2
		-1
f	-5	-2

В качестве разрешающего столбца выбираем первый столбец, ибо = -5-наибольший по модулю отрицательный индекс. В качестве разрешающей выбираем третью строку, так как min.

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

где

i = 3, j =1, k 3, p 1.

Формулу эту называют «правилом прямоугольника», ибо ее легко запомнить, пользуясь прямоугольником: