15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общая прямая и двойственная задачи линейного программирования описываются следующими соотношениями:

I Минимизировать z = р1х1 + />2я2+ . .. + рпхп

при условии

449

29 Р. Аллен

а11х1 + а12х2 + . . . + % пХп > ^21Х1 ^22Х2 "ІГ • • • ~ї~ &2пХп ^ '

ат1х1 ~Т ат2Х2 +... +

II Максимизировать при условии

®тпХп ®т'> ХГ > О, Х2 > 0, . . . , Хп> 0.

+ «аіБа + • • • + атЛш< Pit

й12І1 + «22^2 + • • • + аш2Іт< ^2'

alrJ=>l a2rJ*2 • • • ~t~ атгЛт

Єі>0, g2>0, lm>0.

Задача питания —лишь один пример применения таких систем; тогда коэффициенты а суть «технологические показатели» т питательных свойств для п продуктов, Ь — потребности в каждом из т питательных свойств, р — цены каждого из п продуктов, х — переменные количества покупаемых продуктов и z — минимизируемая стоимость. В других] задачах истолкование постоянных и переменных величин будет иным.

Более сжатая запись задач линейного программирования достигается при использовании матричных обозначений: Минимизировать Максимизировать

2 = р'х 1 = Ъ'1

при условии при условии

Ах> Ь, А'|<р,

х>0. 1>0.

При такой формулировке заданными являются следующие элементы условий:

r = 1, 2, . . т 5=1, 2, ..., п

А = [ars] матрица технологических коэффициентов тхп

Ь = {йг} вектор ттг-го порядка;

p = {ps} вектор иг-го порядка.

Транспонированные элементы соответственно обозначаются А', Ь' и р'* Решением прямой задачи является вектор х тг-го порядка, а двойственной — вектор I 771-ГО порядка. Для всех допустимых решений выполняются ограничения (неравенства); в оптимальных допустимых решениях удовлетворяются также условия максимума (или минимума).

Результаты, полученные выше при анализе простого примера в разделе 15.3, дают основание ожидать, что прямая и двойственная ей задача имеют одно и то же решение, то есть что минимум z совпадает с максимумом Это действительно так, если только исключена возможность отсутствия решения. Следовательно, основная теорема двойственности формулируется следующим образом:

Прямая и двойственная задачи линейного программирования либо имеют общее решение, либо вовсе не имеют решения. Математическое доказательство этой теоремы вовсе не легко; частный очень простой пример из раздела 15.3 является не более, чем ее иллюстрацией. Одно из доказательств теоремы, которое принадлежит Гейлу, Куну и Таккеру, приведено в [9, гл. XIX]; это доказательство основано на теории игр и разработано применительно даже к более широкому классу задач линейного программирования, чем приведенные в настоящем разделе. Другой способ доказательства, принадлежащий Чарнесу приведен в книге Чарнеса, Купера и Гендерсона [2, лекция VIII]; это доказательство базируется на работах Данцига и симплексном методе решения задач линейного программирования (см. 15.8). Вероятно, простейшее из существующих доказательств предложено Дано [4].