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].
Еще по теме 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:
- ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
- ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
- 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
- 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
- 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
- 15.8. СИМПЛЕКСНЫЙ МЕТОД
- 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 16.1. ВВЕДЕНИЕ. ОБЩЕЕ ЭКОНОМИЧЕСКОЕ РАВНОВЕСИЕ
- 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
- 16.7. ЦЕНЫ И ДВОЙСТВЕННАЯ ЗАДАЧА
- 16.9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ; МОДЕЛЬ РОСТА НЕЙМАНА
- 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
- 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
- 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА
- 18.6. СПОСОБЫ ПОТРЕБЛЕНИЯ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
- 18.7. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, КАСАЮЩАЯСЯ ТЕХНОЛОГИИ ПРОИЗВОДСТВА И ВКУСОВ ПОТРЕБИТЕЛЕЙ (СТРУКТУРЫ СПРОСА)