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

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

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

/. Постановка взаимно двойственных задач

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

На некотором предприятии после выполнения годового плана возник вопрос: как поступить с остатками сырья? Некоторые заводские экономисты предложили наладить из оставшегося сырья производство изделий ширпотреба; другие же специалисты посоветовали продать сырье «на сторону» какой-нибудь нуждающейся в нем организации. Исследование этих двух возможностей поручили математикам. Вывод, к которому пришли математики, оказался неожиданным. Но прежде чем изложить их соображения, перечислим исходные данные задачи.

Для простоты будем считать, что имеются два вида сырья 5( и S2, остатки которого составляют соответственно 35 и 20 единиц. Из этого сырья можно наладить производство трех видов товаров: Т|, Т2, Тг. От реализации единицы каждого вида товара завод получит прибыль: от Г| — 7руб., Т2 — 6 руб., Тг— 18 руб. Нормы расхода сырья на производство товаров Тх, Т2, Тъ вместе с данными о прибыли и запасах представлены в следующей таблице.

Например, число 5 в этой таблице означает, что на производство единицы товара Г3 расходуется 5 единиц сырья S.

Проследим теперь за ходом мысли математиков. Как уже говорилось, им предстояло проанализировать две возможности.

При исследовании первой возможности (наладить выпуск товаров Г|, Т2, Г3) возникает вопрос о плане выпуска товаров. План

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

товара Tj, которое следует произвести (i = 1, 2, 3). Неизвестные

Х| х2 Ху должны удовлетворять условиям

*,><),

• *2>0, (9.1) хг > 0,

f х]+х2 + 5хг<35, j 2х, +х2 + 2х3<20.

Поясним смысл первого неравенства системы (9.2). В левой части записано количество сырья Sx, которое расходуется на выпуск хх единиц Т, х2 единиц Т2 и х3 единиц Г3. Это количество не должно превышать имеющегося запаса сырья 5], т. е. 35. Аналогичный смысл имеет второе неравенство системы (9.2).

Прибыль, которую получит предприятие от реализации плана (Х| х2 Ху) выпуска товаров, будет^ очевидно:

/= lx j + 6х2 + 18х3 руб.

В интересах предприятия максимизировать эту прибыль. Следовательно, чтобы наилучшим образом использовать первую возможность, нужно решить задачу линейного программирования:/-> max при условиях (9.1) и (9.2).

Назовем эту задачу задачей I.

Исследуем теперь вторую возможность (продать сырье другой организации). Здесь возникает вопрос: по каким ценам продавать сырье? Обозначим эти цены У,у2 (у, — цена единицы сырья S). Разумеется,

^, >0, >^2>0. (9.1')

Справедливое требование к ценам со стороны продающего предприятия состоит в следующем: если взять сырье, идущее на изготовление единицы товара 7}(i= 1,2, 3), то выручка от его продажи должна быть не меньше, чем прибыль от реализации готового изделия (в противном случае нет смысла продавать сырье — лучше изготовить из него товар и получить за него прибыль). Это требование приводит к неравенствам

yt + 2y2>l, • у1+ у2>6, (9-2') 5у{ + 2у2> 18.

Например, первое из написанных неравенств означает, что выручка от продажи единицы сырья Sx и двух единиц S2 (именно такое количество сырья расходуется на изготовление единицы Tj) не меньше, чем прибыль, которую могло бы получить предприятие от продажи единицы товара Т1( если бы оно отказалось от идеи продать сырье и занялось изготовлением из него товаров Тх, Т2, Ту Аналогичный смысл имеют остальные два неравенства.

Других требований к ценам УУ2 предприятие-продавец предъявлять не вправе. Что же касается покупателя, то для него единственное пожелание заключается в сокращении до минимума расходов на покупку сырья, т. е. величины

Ф = Ъ5у{ + 20у2.

Следовательно, для справедливого использования второй возможности необходимо решить задачу линейного программирования: Ф -» при условиях (9. Г), (9.2').

Назовем эту задачу задачей Г.

Задачи I и Г называются двойственными друг другу. Смысл, который вкладывается в это название, состоит в следующем.

Если первая задача имеет размеры тхп (т ограничений с п неизвестными), то вторая — размеры пх т. Так, в задаче I два ограничения с тремя неизвестными, а в задаче Г — три ограничения с двумя неизвестными.

Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными. Так, в задаче I матрица из коэффициентов при хх х2 *з есть

в то время как в задаче Г матрица из коэффициентов при ух у2 есть

О том, как решается поставленный выше «производственный» вопрос (какую из двух возможностей для реализации остатков сырья следует выбрать) , будет сказано позднее, в § 9.3. А сейчас запишем двойственные задачи 1 и Г в более общей форме, заменив в них конкретные числа буквенными величинами:

Задача Г

Таблица 1

х, £0, х2>0, х3£0,

Задача 1

(9.1)

(9.2')

(9.2)

аих]+а]2х2 + апхг<Ь1, л21 Х| + а12 х2 + а2і х3 £ b2,

/= с,х, + CjX2 + с3х3.

Найти max/ при условиях (9.1), (9.2)

аиУі+агУ2*с\< апУ+аггУг*сг< аіУ+агьУг*сь

<Р = Ь, У + ^2Найти min <р при условиях (9.1'), (9.2')

Если ввести в рассмотрение матрицу

а22

'21

°13 а23

из коэффициентов при неизвестных в системе (9.2) , а также матрицы-столбцы

х2 *3

(

В задаче I все ограничения представляют собой неравенства типа < , причем в этой задаче требуется достичь максимума / Напротив, в задаче Г все ограничения суть неравенства типа > , причем требуется достичь минимума ф.

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

II. Основное неравенство для двойственных задач

Теорема (основное неравенство). Пусть X—какое-нибудь допустимое решение задачи I, т. е. любое решение системы (9.1), (9.2), а У— какое-нибудь допустимое решение задачи Г —любое решение системы (9. Г), (9.2'). Тогда справедливо неравенство

f(X)<<p(Y). (9.3)

Применительно к указанным ранее задачам размеров 2 х 3 и 3 х 2 написанное неравенство означает

ci*i + с2*2 + сзх1 £ ЬУ + ЬугДоказательство неравенства (9.3). Имеем А Х< В, откуда следует (АХ)Т<ВТили ХТАТ<ВТ. Умножив обе части этого

неравенства справа на матрицу Y > 0*, получим (ХТА Т) У£ЯГУ или, ввиду ассоциативности умножения матриц,

ХТ(АТ Y)<BTY=q>(Y) (9.4)

Аналогично имеем A TY > С; умножив обе части слева на матрицу

т

X > 0, будем иметь

ХТ(АТ Y)>XTC=f(X). (9.5)

Соединяя два полученных неравенства (9.4) и (9.5), можем записать

ЛХ)<ХТАТ У<Ф(У), (9.6)

откуда и следует основное неравенство (9.3). Заметим, что полученное нами попутно двойное неравенство (9.6) будет использовано далее.

После умножения обеих частей неравенства на матрицу Y> 0 знак неравенства сохраняется, действительно, обозначив левую и правую части соответственно через PvQ, будем иметь Я 2: Q=> РQ> О =>(/*Q)Y> 0=> PYZ QY.

Следствие 1 (достаточный признак оптимальности). Если для

о о

каких-то допустимых решений X и Y задач I и Г выполняется равенство

/(*)-№. <9Л)

о о то X есть оптимальное решение задачи I , a Y — оптимальное

решение задачи Г.

Действительно, для любого допустимого решения X задачи I имеем согласно неравенству (9.3),

Д*)*ф(к),

а значит,

f(X)<f(x), о

что и доказывает оптимальность X. Аналогично доказывается опти-о

мальность Y.

Следствие 2. Если в одной из задач I и Г целевая функция не ограничена с соответствующей стороны (т. е. тах/= « в задаче I или min ф = оо в задаче Г), то другая задача не имеет допустимых решений.

Действительно, пусть, например, тах/=<» в задаче I. Если бы

о

существовало допустимое решение Y задачи Г, то ввиду (9.3) все числа f(X) (где X — любое допустимое решение задачи I) были бы

ограничены сверху одним и тем же числом ф (у), что противоречит условию max/ = оо.