Решение задачи линейного программирования симплекс-методом (стр. 5 из 6)

3. Получение

- строки для СТ (0). Приведём целевую функцию к виду

.

Получим из (2):

, из (3):

4. Формирование симплекс – таблицы на первом шаге:

Начальный базис

СТ (0) РС

								ПЧ
	1	-1-4M	3+3M	-3M-3	M	0	0	0	-12M
	0	1	2	-2	0	1	0	0	4
	0	3	-4	4	0	0	1	0	12
	0	1	1	-1	-1	0	0	1	0

5. Определение разрешающего столбца.

При решении задачи максимизации выбираем в

- строке максимально отрицательный коэффициент: - включаемая переменная.

6. Определение разрешающей строки:

– исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

, где В(0) - матрица перехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) на условие оптимальности:

СТ(1)

z								ПЧ
z	1	0	4+7M	-7M-4	-3M-1	0	0	1+4M	-12M
	0	0	1	-1	1	1	0	-1	4
	0	0	-7	7	3	0	1	-3	12
	0	1	1	-1	-1	0	0	1	0

СТ(2)

z								ПЧ
z	1	0	0	0	5/7	0	M+4/7	M-5/7	48/7
	0	0	0	0	10/7	1	1/7	-10/7	40/7
	0	0	-1	1	3/7	0	1/7	-3/7	12/7
	0	1	0	0	-4/7	0	1/7	4/7	12/7

СТ(2) – оптимальная, т. к. коэффициенты при НБП

.

, , .

3. Решение задачи линейного программирования симплекс-методом.

Двойственная задача.

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:

Прямая задачаДвойственная задача

(1)

(2)

Итак, получено:

, , .

2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки:

.

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

(3)

(4)

3. Решим ДЗ симплекс методом:

Из (3): выразим

Из (4) выразим:

СТ(0)

W								ПЧ
W	1	-4-M	7M-12	12-7M	0	-M	0	0	4M
	0	1	3	-3	-1	-1	1	0	1
	0	-2	4	-4	1	0	0	1	3

СТ(1)

W								ПЧ
W	1	-10/3M	0	0	7/3M-4	4/3M-4	-7/3M+4	0	5/3M+4
	0	1/3	1	-1	-1/3	-1/3	1/3	0	1/3
	0	-10/3	0	0	7/3	4/3	-4/3	1	5/3