3 Двойственные задачи линейного

ПРОГРАММИРОВАНИЯ

3.1 Понятие о двойственных задачах

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

В качестве исходной задачи возьмем задачу производственного планирования. Формулировка ее такова. В распоряжении предприятия имеются видов ресурсов соответственно в количествах, равныхb₁, b₂, … , b_m. Эти ресурсы должны быть использованы для производстваn видов продукции, стоимость единицы которой известна и равнаc_j (j=1,2, … , n). Кроме того, известны нормыa_ij потребления каждого из ресурсов на производство единицы всех видов продукции. План производстваследует составить из условия максимизации общей стоимости продукции

(3.1)

при ограничениях на использование ресурсов

(3.2)

. (3.3)

По исходным данным задачи (3.1)-(3.3) сформулируем другую экономическую задачу. Для этого предположим, что нужно решить вопрос о том,

что выгоднее: продать имеющиеся на предприятии ресурсы или произвести из них продукцию согласно оптимальному плану задачи (3.1)-(3.3)? В связи с этим возникает необходимость вычислить оптимальные цены у₁, у₂, …, у_mна эти ресурсы, исходя из следующих соображений:

1) покупатель ресурсов стремится минимизировать их общую стоимость;

2) с другой стороны, предприятие за каждый вид ресурсов желает выручить сумму, не меньшую той, которую оно может получить, произведя из них продукцию.

Приведенная формулировка позволяет получить следующую математическую модель. Минимизировать общую стоимость всех ресурсов

(3.4)

при условиях (стоимость ресурсов, которые следует израсходовать, чтобы выпустить единицу j-й продукции не должна быть меньше цены на эту продукцию)

(3.5)

. (3.6)

Задача (3.4)-(3.6) является двойственной по отношению к задаче (3.1)-(3.3) и, наоборот, если исходной является задача (3.4)-(3.6), то двойственной к ней будет модель (3.1)-(3.3). Такие задачи называются симметричными.

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

1) коэффициенты c_j (j=1,2, … , n)целевой функции (3.1) прямой задачи служат свободными членами основных ограничений (3.5) двойственной задачи, а свободные членыb₁, b₂, … ,b_mосновных ограничений (3.2) исходной задачи являются коэффициентами целевой функции (3.4) двойственной задачи.

Итак, число переменных у₁, у₂, …, у_mв двойственной задаче равноm – числу основных ограничений исходной задачи, а число основных ограничений двойственной задачи равноn– числу переменных исходной задачи;

2) матрица коэффициентов основных ограничений двойственной задачи является транспонированной по отношению к матрицеАкоэффициентов при переменных в основных ограничениях исходной задачи;

3) неравенства основных ограничений исходной задачи имеют знак «», а неравенства двойственной задачи – «»;

4) целевая функция (3.1) исходной задачи – на максимум, а двойственной (3.4) – на минимум.

Если в исходной задаче ограничения выражены равенствами, то соответствующая ей двойственная задача будет иметь ограничения-неравенства. Такие задачи называются несимметричными:

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