<<
>>

15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА

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

Требуется минимизировать zx = 6хх + 21яа при условии хх + 2х2 > 3,

(і)

хх + 4х2 > 4, хх>09 я2>0.

, С формально алгебраической точки зрения всякая задача подобного рода на нахождение минимума двойственна — ей соответствует задача на нахождение максимума. Составить двойственную задачу очень важно, хотя она, несомненно, вовсе не является очевидной90. Для задачи (1) двойственная ей задача получается следующим образом. Пусть из хлеба и сыра необходимо составить суточный рацион питания, калорийность которого 3000 калорий, а содержание белка 100 г. Примем те же, что и раньше, единицы измерения (1000 калорий и 25 г белка); пусть и ?2 — наша оценка (в пенсах за единицу) полезности каждого из этих показателей. Тогда общая (условная) оценка рациона питания равна ? = 3%х + 4g2; мы будем стремиться максимизировать Однако стоимость 1 фунта каждого продукта не может превышать рыночной его цены (для хлеба — 6 пенсов, для сыра — 21 пенс). Если 1 фунт хлеба содержит 25 г белка и 1000 калорий, то оценка его питательного содержания, то есть + |2, не может превышать 6 пенсов. Аналогично этому для сыра оценка питательных веществ, равная 2%х + 4|2, не может превышать 21 пенса. Следовательно, двойственную задачу можно сформулировать таким образом:

Найти такие оценки единицы питательных веществ ^ и чтобы

? = 3^ + 4^ = max

при условии

(2)

6i + E«<6, +4g2 < 21, Еі>0, |2>0. л

Задача питания имеет двойственные формы (1) и (2). Связь между этими задачами проста и легко распространяется на задачи линейного программи- рования всех других типов. В задаче (1) минимизируется z, и ограничивающие соотношения переменных входят в форме «больше или равны» (>); в задаче (2) максимизируется и ограничивающие соотношения переменных представлены в форме «меньше или равны» (<) некоторой величине.

В условиях обеих задач имеется матрица технологических коэффициентов

Г 1 21

(показателей питательной ценности продуктов) , однако в ограни

чениях задачи (2) коэффициенты транспонированы по сравнению с задачей (1). В задаче (1) цены (6 и 21) являются коэффициентами минимизируемой функции, а показатели потребности (3 и 4) — ограничивающими соотношениями; в задаче (2) положение обратное.

Нам остается лишь показать, что обе двойственные задачи имеют одно и то же решение — в том смысле, что минимум функции z в задаче (1) равен максимуму функции ? в задаче (2). Решение задачи (1) следующее: 1 1

я1 = 2; #2— у» 2 = 22 у (минимальная стоимость рациона питания).

Графически или тем же методом, что в упражнении 1, находится следующее решение задачи (2):

3 9 1

^ = у; ?2 =5 у; ? = 22 у (максимальная оценка заданного питательного

рациона).

Один и тот же расход, а именно 22г/2 пенса в сутки, мы получаем как при оптимальном ассортименте покупаемых продуктов (2 фунта хлеба и 1/2 фунта сыра), так и при оптимальной оценке полезности единицы питательных веществ (Iі/2 пенса за 1000 калорий и 4г/2 пенса за 25 г белка).

Все вышесказанное вытекает из чисто алгебраических соображений. Однако прямая и двойственная ей задача линейного программирования должны иметь и экономическое истолкование; в самом деле, существование экономической двойственности легко обнаружить и в общем случае. Так, в задачах на распределение ограниченных ресурсов в производстве функцию издержек производства можно получить (при заданных ценах ресурсов), либо минимизируя издержки для заданной программы, либо максимизируя выпуск при заданной общей сумме издержек. Двойственными аспектами одной и той же задачи являются распределение ресурсов и оценка их. Если для ресурсов не существует рыночных цен, то необходимо их создать, ввести систему условных или расчетных цен. Этому указанию придется следовать в дальнейшем.

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

Оценки питательного содержания не устанавливаются, хотя именно они (а не продукты) лежат в основе задачи. Введем теперь условные оценки показателей питательной ценности: ^ пенсов за 1000 калорий и пенсов за 25 г белка. Тогда возникает двойственная задача (2), где требуется максимизировать условную оценку рациона заданной питательной ценности при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были возможно более дешевыми, удовлетворяя вместе с тем? требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи — втом, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный.

Задачи и упражнения

1. Решить двойственную задачу (2) графическим "методом (см. рис. 50) и указать основные различия между геометрическими методами решения прямой и двойственной задач.

Н . 2. Исследовать характер изменений графического' решения задачи (2), если мы будем менять цены так как это делалось в упражнениях 1—3 предыдущего раздела. 3.

Составить и истолковать двойственную задачу, приведенную в упражнении 6 раздела 15.1. Решить ее графически (на плоскости) и показать, что добавление третьего* продукта не вносит ничего нового по сравнению с решением задачи 1 данного раздела. 4.

Объяснить, почему нельзя решить графически на плоскости двойственную задачу 5 раздела 15.1. Показать, что эта двойственная задача аналогична прямой задаче 6 раздела 15.1. 5.

Показать, что двойственную транспортную задачу 7 раздела 15.1 можно сформулировать следующим образом:

Найти неотрицательные и |2> максимизирующие функцию

при условии

^ ht la <

Дать экономическое истолкование этой двойственной задаче.

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

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

  1. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  2. 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
  3. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  4. 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  5. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  6. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  7. 16.7. ЦЕНЫ И ДВОЙСТВЕННАЯ ЗАДАЧА
  8. 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  9. 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
  10. 17.7. ПАРАДОКС РИКАРДО
  11. 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА