<<
>>

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

Задачу питания для случая двух продуктов и двух показателей их питательной ценности, рассмотренную в разделе 15.3, можно обобщить на случай т показателей питательной ценности и п продуктов.
В этом случае мы получаем общую форму линейного программирования, отвечающую различным экономическим и другим задачам. Простые примеры таких задач см. в работах Дорфмана, Солоу и Самуэльсона [7] и Кемени, Снелла и Томпсона [8].

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

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].

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:

  1. ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
  2. ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  3. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  4. 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
  5. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  6. 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  7. 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
  8. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  9. 15.8. СИМПЛЕКСНЫЙ МЕТОД
  10. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  11. 16.1. ВВЕДЕНИЕ. ОБЩЕЕ ЭКОНОМИЧЕСКОЕ РАВНОВЕСИЕ
  12. 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
  13. 16.7. ЦЕНЫ И ДВОЙСТВЕННАЯ ЗАДАЧА
  14. 16.9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ; МОДЕЛЬ РОСТА НЕЙМАНА
  15. 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
  16. 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  17. 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
  18. 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА
  19. 18.6. СПОСОБЫ ПОТРЕБЛЕНИЯ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  20. 18.7. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, КАСАЮЩАЯСЯ ТЕХНОЛОГИИ ПРОИЗВОДСТВА И ВКУСОВ ПОТРЕБИТЕЛЕЙ (СТРУКТУРЫ СПРОСА)