1.11. Методы получения 1-го опорного решения.

В рассмотренном нами примере (п. 1.7.) с самого начала каноническая задача линейного программирования имела симплексную форму. Рассмотрим теперь на примере, как для произвольной задачи ЛП получить первую симплекс-таблицу.

Пример №1. Найти решение задачи:

(1)

I-ый способ решения.

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

0	1	- 6	- 1	- 2	- 28
0	2	4	1	1	24	(2)
1	3	3	1	2	30

Первые две строки фактически содержат матрицу ограничений, а последняя, индексная, строка определение функции . Конечно, таблица (2) не является симплексной. Во-первых, столбец свободных членов содержит отрицательный элемент (–28) в первой строке. Чтобы этого не было, умножим первую строку на (–1):

0	- 1	6	1	2	28
0	2	4	1	1	24	(3)
1	3	3	1	2	30

Во-вторых, система ограничений не имеет разрешенного вида, то есть матрица ограничений в (3) не содержит единичной матрицы размера

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

0	- 1	6	1	2	28	28
0	2	4	1	1	24	24	(4)
1	3	3	1	2	30

Методом Гаусса преобразуем ведущий столбец в базисный. Для этого:

1. из первой строки вычтем ведущую (вторую)

2. из индексной строки (третьей) вычтем ведущую вторую).

Получим новую таблицу:

0	- 3	2	0	1	4
0	2	4	1	1	24	(5)
1	1	- 1	0	1	6

Теперь выберем ведущим столбец и найдем ведущую строку с минимальным допустимым отношением:

0	- 3	2	0	1	4	4	(6)
0	2	4	1	1	24	24
1	1	- 1	0	1	6

Преобразуем ведущий столбец в базисный. Для этого вычтем из второй и третьей строки ведущую (первую) строку. В результате получим таблицу:

0	- 3	2	0	1	4	(7)
0	5	2	1	0	20
1	4	- 3	0	0	2

которая является симплексной. Действительно, матрица системы содержит единичную (если переставить столбцы ( ) и ( )), подматрицу размера ; столбец неотрицателен; функция F зависит только от свободных переменных и , что видно из того, что в индексной строке в столбцах базисных переменных и стоят нули.

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

0	- 3	2	0	1	4	2
0	5	2	1	0	20	10
1	4	- 3	0	0	2
0		1	0		2		(8)
0	5	2	1	0	20
1	4	- 3	0	0	2
0		1	0		2	-
0	8	0	1	- 1	16	2
1		0	0		8
0		1	0		2
0	1	0			2
0		0	0		8
0	0	1			5
0	1	0			2
0	0	0			9

Последовательность операций.

1. Выбираем ведущим второй столбец по элементу (–3) в индексной строке.

2. Находим минимальное отношение .

3. Выбираем ведущей первую строку.

4. Делим ведущую строку на ключевой элемент 2 (в рамочке), стоящий в ведущей строке

5. Вычитаем из второй строки ведущую, умноженную на 2.

6. Прибавляем к индексной строке ведущую, умноженную на 3.

7. Выбираем ведущим первый столбец по элементу в индексной строке.

8. Определяем ведущую строку с минимальным допустимым отношением .

9. Делим ведущую строку на ключевой элемент 8.

10. Прибавляем к первой строке ведущую, умноженную на .

11. Прибавляем к индексной строке ведущую, умноженную на .

В результате всех операций 1-11 мы из первой симплекс-таблицы (7) получаем последнюю симплекс-таблицу:

0	0	1			5	(9)
0	1	0			2
0	0	0			9

и из первого опорного решения

, (10)

получаем последнее опорное решение:

, (11)

которое оказывается оптимальным, поскольку в индексной строке таблицы (9) нет отрицательных элементов.

Пример № 1 решен.

Ответ:

Изложенный выше метод получения первого опорного решения основан на методе Гаусса и теореме о минимальном допустимом отношении.

2-ой способ решения.

Метод искусственного базиса.

Запишем задачу (1) в виде:

(12)

Рассмотрим вспомогательную задачу:

Ясно, что, если система ограничений (12) совместна, то решение задачи (13) существует и Очевидно, верно и обратное, то есть, если задача (13) имеет оптиальное решение и то система ограничений (12) имеет решение, причем полученное решение задачи (12) является опорным.

Задачу (13) нетрудно решить симплекс-методом.

Условие: , заменим равносильным:

Дальнейшее решение запишем в виде таблицы.

0	- 1	6	1	2	1	0		28					Первая таблица (не симплексная)
0	2	4	1	1	0	1		24
1	0	0	0	0	1	1		0
0	- 1	6	1	2	1	0		28					Вторая таблица (не симплексная)
0	2	4	1	1	0	1		24
1	1	- 6	- 1	- 2	0	1		- 28
0	- 1	6	1	2	1	0		28					Третья таблица (симплексная)
0	2	4	1	1	0	1		24		4
1	- 1	- 10	- 2	- 3	0	0		- 52
0	- 3	2	0	1	1	- 1		4		4			Далее решаем симплекс-методом
0	2	4	1	1	0	1		24		24
1	3	- 2	0	- 1	0	2		- 4
0	- 3	2	0	1	1	- 1		4
0	5	2	1	0	- 1	2		20
1	0	0	0	0	1		1		0				(14)

Первая таблица не является симплексной, поскольку в базисных столбцах и в индексной строке вместо нулей стоят единицы. Вычитая из индексной строки сначала первую строку, а затем вторую строку, получаем третью таблицу, которая оказывается уже симплексной. Далее решаем задачу как обычно, симплекс-методом. Из последней симплекс-таблицы вспомогательной задачи находим оптимальное решение этой задачи:

Поскольку и , то равенства , , , дают нам первое опорное решение исходной задачи. Этому решению соответствует таблица:

0	- 3	2	0	1	4	(15)
0	5	2	1	0	20
0	3	3	1	2	30

Вычитая из последней (индексной) строки 1-ую строку, умноженную на 2, и 2-ую строку, получаем таблицу (7). Далее решение совпадает с изложенным ранее.