2.7 Задача 4

Для заданной задачи линейного программирования составить двойственную задачу Линейного программирования и решить ее Симплекс методом:

Решение

1. Для заданной задачи Линейного программирования Двойственная Задача Линейного программирования выглядит следующим образом:

2. Строим симплекс таблицу для заданной двойственной задачи Линейного программирования

СП БП				C
	3	-1	3	-1
	-2	2	2	-2
T	6	4	12	0

2. Выбираем разрешающую строку k , соответствующую наименьшему отрицательному элементу в С столбце

Следовательно, k=2.

СП БП				C
	3	-1	3	-1
	-2	2	2	-2
T	6	4	12	0

3. Выбираем разрешающий столбец l, который соответствует наименьшему положительному из отношений элементов T-строки на соответствующие элементы разрешающей строки:

Следовательно, l=2.

СП БП				C
	3	-1	3	-1
	-2	2	2	-2
T	6	4	12	0

4. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом : 2

5. Переходим к новой симплекс таблице по следующим правилам:

   1. Меняем местами СП и БП соответствующие разрешающему элементу.

СП БП				C
T

2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

СП БП				C
T

3. Все элементы разрешающей строки делятся на разрешающее число с обратным знаком, включая элемент последнего столбца:

СП БП				C
	1		-1	1
T

4. Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки:

СП БП				C
	1		-1	1
T		2

5. Все остальные элементы матрицы вычисляются по формулам:

Например, вычислим некоторые элементы таблицы :

Полученная СТ2 следующая:

СП БП				C
	2		4	-2
	1		-1	1
T	10	2	8	4

6. В С столбце есть отрицательные элементы ( -2), поэтому оптимальное решение не найдено и необходимо сделать еще одно симплекс преобразование.

7. Выбираем разрешающую строку k , соответствующую наименьшему отрицательному элементу в С столбце

Следовательно, k=1.

СП БП				C
	2		4	-2
	1		-1	1
T	10	2	8	4

8. Выбираем разрешающий столбец l, который соответствует наименьшему положительному из отношений элементов T-строки на соответствующие элементы разрешающей строки:

Следовательно, l=3.

СП БП				C
	2		4	-2
	1		-1	1
T	10	2	8	4

9. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом :

10. Переходим к новой симплекс таблице по следующим правилам:

    1. Меняем местами СП и БП соответствующие разрешающему элементу.

СП БП				C
T

2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

СП БП				C
T

3. Все элементы разрешающей строки делятся на разрешающее число с обратным знаком, включая элемент последнего столбца:

СП БП				C
T

4. Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки:

СП БП				C
T			2

5. Все остальные элементы матрицы вычисляются по формулам:

Например, вычислим некоторые элементы таблицы :

Полученная СТ3 следующая:

СП БП				C
T	6	3	2	8

11. Все элементы С столбца положительные, следовательно оптимальное решение найдено.

12. Введем соответствие между СП и БП Прямой и Двойственных задач Линейного программирования

СП							БП
↕	↕	↕				↕		↕
БП							СП

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

СП БП			B
			2
Z			8

Таким образом, оптимальное решение – максимум целевой функции Z =8 - достигается при , Это полностью совпадает с результатом решения прямой задачи Линейного Программирования ( см. Задачу 1)

Ответ: Z_max=8 при этом ,