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

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

Решение

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

 

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

СП БП				C
		-1		-1
	-2			-2
T

 

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

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

СП БП				C
		-1		-1
	-2			-2
T

 

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

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

СП БП				C
		-1		-1
	-2			-2
T

 

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

1. Переходим к новой симплекс таблице по следующим правилам:
1. Меняем местами СП и БП соответствующие разрешающему элементу.

 

СП БП				C
T

 

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

СП БП				C
T

 

 

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

СП БП				C
			-1
T

 

 

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

СП БП				C
			-1
T

 

 

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

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

 

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

СП БП				C
				-2
			-1
T

 

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

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

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

СП БП				C
				-2
			-1
T

 

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

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

СП БП				C
				-2
			-1
T

 

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

1. Переходим к новой симплекс таблице по следующим правилам:
1. Меняем местами СП и БП соответствующие разрешающему элементу.

СП БП				C
T

 

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

СП БП				C
T

 

 

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

СП БП				C
T

 

 

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

СП БП				C
T

 

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

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

 

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

СП БП				C
T

 

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

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

 

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

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

 

СП БП			B
Z

 

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

 

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