002. ЛЕКЦИИ 1-6 (ОПУТ) (МТП) (курсант) / Лекции / лекция 6 / лекция 6

Принцип двойственности. Правило построения двойственно-сопряженной задачи

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

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

Рассмотрим снова задачу про предприятие, выпускающее n видов продукции. При изготовлении этой продукции предприятие использует m видов ресурсов, объемы которых заданы в количествах b₁, b₂…b_m. Также заданы расходы (a_ij) i-го вида ресурсов (i=1…m) на производство единицы продукции j-го вида (j=1…n). Кроме того известна стоимость единицы продукции - c_ij.

Необходимо определить объем производства продукции, при котором достигается максимальный доход от реализации, при условии, что вся продукция найдет сбыт.

Целевая функция примет вид:

(4.4)

Система ограничений:

(4.5)

Для построения задачи, которую называют двойственно-сопряженной к задаче рассмотренной выше, представим следующую ситуацию. Пусть некоторая организация предлагает предприятию продать весь запас ресурсов m. Какие цены следует установить за единицу каждого из ресурсов?

Обозначим эти цены через u₁, u₂,…u_m (ден. ед.). Тогда набор ресурсов, расходуемых при выпуске одного изделия будет оценен в a_1ju₁+a_2ju₂+…+a_mju_m (ден. ед.), т.к. предприятие при затрате такого набора ресурсов может получить доход c_j (ден. ед.), то, очевидно, при продаже оно будет стремиться получить за каждый такой набор не меньшую сумму, чем c_j, т.е. оно назначит цены так, чтобы удовлетворялось неравенство:

Таким образом, цены u₁, u₂…u_m будут назначены так, чтобы удовлетворялись совместно неравенства:

Чтобы соблюсти такие неравенства, можно было бы просто назначить большие цены, но покупающая организация с этим не согласится. Во избежание необоснованного завышения цен покупающая организация предъявит предприятию такое дополнительное требование: при соблюдении указанных выше неравенств общая сумма за весь запас всех ресурсов должна быть минимальной. Эта сумма будет составлять величину . Таким образом, получена новая задача линейного программирования:

(4.6’)

(4.7’)

Данная задача (4.6’) - (4.7’) является задачей, двойственно-сопряженной с задачей (4.4) - (4.5).

Отсюда вытекает правило построения двойственно-сопряженной задачи:

1. исходная задача (4.4) - (4.5) является задачей на максимум, а сопряженная задача (4.6’) - (4.7’) - задача на минимум;

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

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

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

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

Пример:

Исходная задача:

Сопряженная задача примет вид:

Как видно, составление сопряженной задачи не представляет труда. Но следует иметь в виду, что не всегда двойственно-сопряженные задачи имеют смысл. Здесь возможны различные варианты, а именно:

1. исходная задача допустима – она имеет планы, удовлетворяющие ограничениям, а сопряженная задача недопустима – она не имеет планов, удовлетворяющих ее ограничениям (как показано в примере выше);

2. исходная задача недопустима, а сопряженная зада допустима:

3. обе задачи недопустимы:

4. обе задачи допустимы: