Составление новой симплекс таблицы.

· Имена всех базисных переменных сохраняются за исключением имени генеральной строки. Оно заменяется именем переменной генерального столбца.

· Элементы генеральной строки делятся на генеральный элемент, и полученные значения заносятся в новую таблицу. В частности, на месте генерального элемента записывается единица.

· Остальные элементы генерального столбца заменяются нулями.

· Для элемента исходной таблицы находятся соответствующий ему элемент генеральной строки и элемент генерального столбца. На месте этого элемента в новой таблице пишется

, (13)

где – генеральный элемент.

Компактно это преобразование таблицы можно записать в виде формулы:

Пример 7. Решить следующую каноническую задачу линейного программирования симплекс-методом.

,

при ограничениях

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

Таблица 3. Таблица 4.

–5

··

4*

–3

–3/4

1/4

·

Эта таблица не порождает оптимальное базисное решение, так как в последней строке стоят два положительных числа. Возьмем одно из них, например 7. Следовательно, первый столбец будет генеральным. Найдем теперь отношения свободных членов к положительным элементам генерального столбца: . Наименьшее из этих отношений оказалось во второй строке. Пометим генеральный элемент символом *.

Переменную введем вместо в число базисных. На месте генерального элемента запишем число 1, вместо остальных элементов генерального столбца запишем нули, все остальные элементы генеральной строки поделим на генеральный элемент, число 4. В результате мы получим таблицу 4.

Заполним клетку помеченную символом (·). Соответствующие элементы генеральной строки и столбца будут равны: , , поэтому в этой клетке следует написать (по формуле 13). В клетке, помеченной знаком (··), напишем . Аналогично заполняются оставшиеся клетки Таблицы 4. (Таблица 5.)

Таблица 5. Таблица 6.

9/4

5/4

23/13

-9/13

–3/4

1/4

1/13

3/13

13/4*

-3/4

-3/13

4/13

29/4

-7/4

-35

-1/13

-29/13

-64

Таблица 5 порождает следующее базисное решение задачи:

, , , , .

Значение целевой функции будет . То есть на новом базисном плане оно меньше на 35 единиц, чем на первоначальном.

Найденное нами базисное решение не оптимально, так как в последней строке Таблицы 5 есть положительные элементы. Для нахождения следующего базисного плана выберем базисный столбец симплекс-таблицы 5. Так как в последней строке положительный элемент только один, то за такой столбец следует взять столбец .

Как и ранее вычислим отношения свободных членов к положительным элементам генерального столбца. У нас получатся следующие отношения: . Наименьшим из этих отношений оказалось третье и, следовательно, генеральной строкой будет третья строка. Таким образом, генеральным элементом таблицы 5 будет число .

Выполним преобразование таблицы 5 и составим таблицу 6. Составление этой таблицы удобно начинать с последней строки, так как именно по ней определяется оптимальность получаемого решения. Так как все элементы последней строки оказались отрицательными, то порождаемое этой таблицей базисное решение

, , , ,

будет оптимальным, а минимальное значение целевой функции .

Построение допустимого плана с помощью искусственного базиса

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

В этом параграфе мы покажем, как симплекс-методом можно найти базисное допустимое решение или доказать, что система ограничений канонической задачи несовместна.

Предположим, что в системе уравнений (12) значения свободных членов отрицательны. Умножим эти уравнения на –1 и составим новую систему уравнений:

(14)

В этой системе искусственные переменные можно взять за базисные, тогда все компоненты базисного решения будет неотрицательны.

Составим новую задачу:

при ограничениях (14) и .

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

Если же минимальное значение вспомогательной функции положительно, то система (12) не имеет базисного решения с неотрицательными компонентами.

Пример 8. Решить следующую задачу линейного программирования симплекс методом.

(15)

при ограничениях

. (16)

Решение. Введем дополнительные переменные

и перейдем к канонической задаче линейного программирования.

, (17)

при ограничениях

(18)

.

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

Введем искусственную переменную в третье уравнение:

и составим вспомогательную целевую функцию:

,

в записи которой базисная переменная выражена через свободные. Составим вспомогательную задачу.

при ограничениях

.

Для этой задачи составим симплекс-таблицу 7. В эту таблицу мы включили первоначальную целевую функцию , которая будет преобразовываться по тем же правилам, что и вся симплекс-таблица.

Таблица 7. Таблица 8.

11/5

1/5

-1/5

-3/5

2/5

-2/5

5*

-1

4/5

-1/5

1/5

7/5

2/5

-2/5

-8

-1

-1

За генеральный столбец в таблице 7 мы возьмем столбец . Отношения свободных членов к элементам этого столбца будут соответственно равны . Поэтому генеральный элемент будет в третьей строчке и равен 5. После преобразований у нас получиться таблица 8.

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

, , , , .

Заметим, что значение целевой функции на этом решение равно –8. Симплекс таблица для первоначальной задачи получается из таблицы 8 вычеркиванием столбца и последней строки . У нас получиться симплекс-таблица 9.

Таблица 9. Таблица 10.

11/5

1/5

5/2*

-1/2

-3/5

2/5*

-3/2

5/2

4/5

-1/5

1/2

1/2

7/5

2/5

-8

-1

-20

В этой таблице выберем генеральный элемент и выполним преобразование таблицы. У нас получиться Таблица 10. В этой таблице значение целевой функции равно –20, что меньше чем в таблице 9. Снова применим алгоритм симплекс метода. У нас получится Таблица 11.

Таблица 11.

	0
			-4/5	-3/5		-36

Все элементы последней строки отрицательны. Следовательно эта таблица порождает оптимальное базисное решение задачи (17, 18). А именно,

, , , , .

При этом минимальное значение функции равно –36.

Минимальное значение функции задачи(25, 16) равно также –36 и оно достигается в точке с координатами , .