Двойственные задачи и их решение

Каждой задаче линейного программирования ставят в соответствие другую задачу, построенную на основе тех же данных по определенным правилам.

Эти правила сводятся к следующему:

§ все ограничения исходной задачи приводят к одному виду: в случае ограничения должны иметь вид неравенств типа “ ”, в случае - типа “ ”. Неравенства, не соответствующие этому условию, умножают на (- 1);

§ выписывают матрицу коэффициентов при неизвестных и транспонируют ее ;

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

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

Например, для задачи, решенной симплексным методом, составим двойственную, исходя из приведенных правил.

Переход от любой задачи к двойственной можно выполнить, используя табличную схему:

	- 1	- 2	- 4
	- 5	- 1	- 5
	- 1
	- 2

Запись одной задачи идет по строкам, другой – по столбцам.

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

Например, в рассмотренной задаче имели:

-строка		-8/3				-1/6	-7/6

Дополнительными были столбцы , , , поэтому получаем:

.

Рассмотрение двойственных задач очень полезно, т.к. они имеют самостоятельный экономический смысл и позволяют изучать экономический процесс с разных сторон.