Глава 3. Двойственные задачи линейного программирования

 

Важную роль в теории ЛП играют так называемые двойственные задачи. Установлено, что с каждой задачей ЛП тесно связана другая, тоже линейная, причем связь настолько тесная, что зная решение одной из них, можно легко получить решение другой. Эти задачи получили название двойственных, отношение двойственности взаимно: каждая из них является двойственной по отношению к другой. Неизвестные, получаемые в результате решения двойствен­ной задачи, играют важную роль при экономическом анализе исходной задачи. Кроме того, на теории двойственности основаны некоторые методы решения, например, двойственный симплекс-метод.

Рассмотрим в качестве примера задачу распределения ресурсов. Любое горное предприятие, выпуская продукцию, расходует различные ресурсы: материальные, трудовые и денежные. К материальным ресурсам относятся сырье и материалы, оборудование и топливо и т. д.

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

Чтобы составить математическую модель задачи, введем обозначения:

т - количество различных видов ресурсов;

i - индекс ресурсов ();

п - количество различных видов продукции, например сортов угля;

j - индекс продукции ();

 - запас ресурса i -го вида, т. е. максимальное количество этого ресурса, которое может быть израсходовано на производство продукции;

 - удельный расход i -го ресурса на продукцию j -го вида, т.е. количество единиц данного ресурса, которое затрачивается на производство одной единицы указанной продукции;

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

Величины т, п, , ,  обычно известны. Обозначим  -количество продукции j -го вида, планируемое к выпуску. Величины  должны быть подобраны так, чтобы обеспечить получение максимальной прибыли, а расход ресурсов не превышал их запаса. Это приводит к следующей математической задаче. Целевая функция - суммарная прибыль.

(3.1)

Ограничения:

а) по запасам ресурсов

.....................

(3.2)

б) по неотрицательности искомых величин

...

(3.3)

Поставим теперь задачу найти оценки ресурсов, объективно обу­словленные для данного производства. Очевидно, что эти оценки должны находиться из условий рентабельности производства. Это означает, что, во-первых, стоимость всех ресурсов должна быть минимальной и, во-вторых, стоимость всех ресурсов, расходуемых на выпуск единицы продукции, должна быть не ниже получаемой от нее прибыли.

Если обозначить через  оценку i -го ресурса, то указанные соображения приводят к следующей задаче ЛП. Целевая функция - суммарная стоимость всех ресурсов:

.

(3.4)

Ограничения:

а) по стоимости ресурсов, затраченных на выпуск единицы продукции

.....................

(3.5)

б) по неотрицательности оценок ресурсов

...

(3.6)

Задача (3.1) — (3.3) называется двойственной по отношению к задаче (3.4) — (3.6). Отметим следующие особенности двойственной задачи.

1. Коэффициентами ее целевой функции служат правые части основных ограничений исходной задачи.

2. Правыми частями в основных ограничениях двойственной задачи служат коэффициенты целевой функции исходной задачи.

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

4. В исходной задаче целевая функция максимизируется, а в двойственной - минимизируется, причем в основных ограничениях при максимизации целевой функции будут знаки неравенств «≤», а при минимизации «≥».

5. В обеих задачах присутствуют условия неотрицательности искомых величин.

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

Например, для задачи ЛП:

;

;

;

двойственной будет задача

;

;

;

;

.

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

ограничению-равенству исходной задачи в двойственной задаче соответствует переменная любого знака;

переменной любого знака в исходной задаче соответствует ограничение-равенство двойственной задачи.

В остальном действуют те же принципы, что и в симметричном случае. Например, для задачи

;

;

;

двойственной будет задача

;

;

;

;

.

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

Для канонической задачи ЛП

.....................

...

двойственной является задача

.....................

в которой искомые величины могут быть любого знака.

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

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

,	(3.7)
.	(3.8)

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

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

В теории двойственности доказано, что если одна из двойственных задач имеет оптимальный план, то и другая задача разрешима. Из этого следует, что существование оптимальных оценок ресурсов гарантирует и существование оптимального плана выпуска продукции.

Важную роль играют так называемые соотношения дополняющей нежесткости:

	(3.9)
	(3.10)

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

Для выяснения смысла этих утверждений допустим, что

т.е. в оптимальном плане выпуска продукции i-й вид ресурса расходуется не полностью, тогда из формулы (3.10) следует, что . Это значит, что оценки недефицитных ресурсов равны нулю. С другой стороны, из условия  следует, что

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

Аналогичное истолкование можно дать и соотношению (3.9).

Действительно, пусть

т. е. суммарная стоимость ресурсов, затраченных на выпуск единицы продукции j -го вида, больше прибыли от ее выпуска, Тогда для обращения в нуль произведения необходимо, чтобы , что означает нецелесообразность выпуска продукции этого вида. С другой стороны, если , то

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

Отметим еще одну важную роль двойственных оценок. Из формул (3.1), (3.4), (3.8) следует

(3.11)

Рассматривая запас i -го ресурса как переменную величину, получаем

(3.12)

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

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

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

Трудность решения задач ЛП симплекс-методом в большей степени возрастает с увеличением числа основных ограничений и в меньшей - с увеличением числа переменных. Поэтому, если в исходной задаче количество ограничений велико по сравнению с числом неизвестных, то сначала легче получить решение двойственной задачи.

 

Планирование оптимального объема добычи

Три шахты, входящие в объединение, поставляют энергетический и коксующийся угли. Добыча этих видов угля в целом по объединению с учетом круга потребителей не должна превышать 40 тыс. и 15 тыс. т. соответственно. Известно, что энергетический уголь в общем объеме добычи по шахтам составляет соответственно 60, 80. и 30 %, а величина прибыли 4,8; 3,2; 4,2 руб. в расчете на 1 т угля.

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

Составим математическую модель задачи, обозначив через , ,  - искомые объемы добычи трех шахт.

Целевая функция - суммарная прибыль по объединению.

Ограничения:

а) по добыче энергетического угля

б) по добыче коксующегося угля

в) по неотрицательности искомых величин

.

Пусть  - оценка стоимости 1 т энергетического угля, а  - коксующегося. Тогда можно составить следующую двойственную задачу.

Целевая функция - суммарная оценка всего добываемого угля

Ограничения:

а) по рентабельности добычи на каждой шахте

б) по неотрицательности оценок:

Оптимальный план двойственной задачи находим с помощью инструмента Поиск решения. Сначала создаем исходную таблицу, вносим в нее исходные данные и необходимые формулы (рис.3.1).

Рис.3.1. Ввод исходных данных и формул

 

Указав в окне параметров соответствующие ограничения, получим решение (рис.3.2).

Рис. 3.2. Решение двойственной задачи

Оценки стоимости энергетического и коксующегося углей, объективно обусловленные для данного объединения, равны соответственно  = 1,6 руб/т,   = 9,6 руб/т. Суммарная минимальная оценка всего добываемого по объединению угля составляет

Решение исходной задачи находим таким же образом (рис.3.3).

 

Рис. 3.3. Решение исходной задачи

 

Получаем, , , .

Следовательно, в данных условиях объединению выгодно до­бывать с первой и второй шахт соответственно 20 тыс. и 35 тыс. т угля. Вести добычу на третьей шахте нецелесообразно. Такое планирование позволяет получить объединению максимально возможную прибыль в размере

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

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

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

Пусть, например, потребность в энергетическом угле возрастает на 1000 т. Тогда максимальная прибыль увеличится на  т.е. на . Прирост на 1000 т потребности в коксующемся угле при оптимальном планировании добычи вызовет увеличение прибыли по объединению на , т. е. на .

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

Это будет означать недефицитность спроса для соответствую­щего вида углей: увеличение спроса на него не приводит к уве­личению прибыли объединения, поскольку уголь и так находит полный сбыт, а потребности данного круга потребителей удовле­творяются не полностью.

Следует отдельно остановиться на том, что в соответствии с полученным решением, по третьей шахте добыча угля не должна планироваться совсем. Если шахты — проектируемые, то такое решение не вызывает особых возражений, если же шахта — действующая, то это означает ее фактическое закрытие, что на практике может оказаться неприемлемым с учетом факторов, не при­нятых во внимание при постановке данной задачи. Это свидетельствует о том, что получаемые математическими методами решения являются оптимальными только в пределах условий рассмотренных при постановке задачи.

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