<<
>>

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

Взаимодвойственные задачи. Рассмотрим задачу об использовании ресурсов. Пусть предприятие № 1 производит п видов продук-ции и использует т видов сырья. Известна прибыль, получаемая с единицы продукции CjJ = 1, п.
Известны технологические коэффи-циенты а-ф і = у = 1 , л. Требуется организовать производство так, чтобы предприятию была обеспечена максимальная прибыль. Сведем все исходные данные в табл. 7.22:

Таблица 7.22 Цены Запасы Продукция на ресурсы сырья Я, П2 пп «1 <*\\ <*\2 <*\п и2 ... ^22 <*2п ит Q ml Я ml <*тп Прибыль с Cl С2 сп единицы продукции

Запишем в общем виде экономико-математическую модель задачи об использовании ресурсов. Для этого введем переменные Хр у = 1 — количество продукции у-го вида. Тогда ограничения на сырье запишутся в виде

а\\х\ + а\2х2 + — +ах#л<>ах\

021*1 + «22*2 + - +*2ІЛІ ? «2; (7.55)

ат\х\ + *«2*2 + - +*І»І/Л, ^ ат• Целевая функция, определяющая максимум прибыли, имеет

вид

Zmax = с\х\ + С2Х2 + ••• + W (7-56)

xj>qj = т7л.

По этим же исходным данным сформулируем задачу по предприятию № 2.

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

общая стоимость ресурсов для предприятия № 2 должна быть минимальной;

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

Обозначим цены, по которым предприятие № 2 покупает ресурсы у предприятия № 1, через uh і = 1,/и. Запишем экономико- математическую модель для предприятия № 2 с учетом вышеуказанных условий 1) и 2).

Целевая функция, определяющая минимальную суммарную стоимость ресурсов, имеет вид

Апіп = <*\Щ + + - + атит- (7.57)

В соответствии с условием 2) запишем систему ограничений:

аххих + а2Хи2 + ...

+ ат1ит>сх;

ах2их + а22и2 + ... + ат2ит > с2;

а\пи\ + а2пи2 + ... + > Сравним математические модели задач (7.55), (7.56) и (7.57), (7.58):

число неизвестных одной задачи равно числу ограничений другой задачи;

матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;

неравенства в системах ограничений имеют противоположный смысл;

свободные члены системы ограничений одной из задач становятся коэффициентами целевой функции другой задачи, коэф-фициенты целевой функции превращаются в свободные члены ограничений;

целевые функции в задачах имеют противоположный смысл: в первой - шах, во второй - min.

Задачи линейного программирования, обладающие пятью указанными формальными признаками, называются симметричными. Одна из них называется основной, а другая — двойственной.

В линейном программировании кроме симметричных двойственных пар существуют несимметричные двойственные пары, которые имеют следующий вид:

основная задача

ахххх + ах2х2 + ... + аХпхп = Ьх; : (7.59)

ат\х\ + ат2*2 + — + атпхп = Ьт>

^шах = СХХХ + С&2 + ... + с„хЛ; (7.60)

xj > 0, j = Т77Ї;

двойственная задача

^тах = Ьхух + bjy2 + ... + Ь„ут; (7.61)

й\\У\ + а2\Уг + - + ^ С\>

: (7.62)

+ а2пУ2 + - + втпУт * сп-

ЭТИ задачи отличаются от симметричной пары двумя особенностями:

ограничения задачи (7.59)—(7.60) выражены уравнениями вместо неравенств;

в задаче (7.61)-(7.62) отсутствуют условия неотрицательности переменных yh і = I, т.

Общее правило построения двойственной пары. К пяти признакам, сформулированным ранее, необходимо добавить следующие:

в исходной задаче ограничения неравенства следует записывать со знаком >, если целевая функция стремится к min, и со знаком <, если целевая функция стремится к шах;

каждому ограничению неравенства исходной задачи соответ-ствует в двойственной задаче условие неотрицательности переменных у і > 0;

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

Пример 7.15.

Дана следующая система:

І*! +2х2 +*з [2хх +Х3 >4;

хх >0\х2> 0; х3 > 0;

^min = х1 + х2 + ху

Проверяем условие: целевая функция стремится к min, а знак неравенства должен быть >.

Исходная задача соответствует данному условию, и можно сразу приступить к построению симметричной двойственной пары.

Так как в прямой задаче в системе ограничений два неравенства, то в двойственной будет две переменных их и и2, причем их > 0, и2 > 0.

Целевая функция

^тах = 9их + 4W2.

Учитывая, что целевая функция на шах и в прямой задаче хх > 0; х2 > 0; х3 > 0, то система ограничений запишется в следующем виде:

щ+1и2<\\ 2их <1; их+и2<1.

Пример 7.16.

Имеем систему -2X2 +х3 +3^4 -2х5 = 6, 2Х] +3х2 "2*3 ~*4 +х5 ^ 4, +Зх3 -4х5 ? 8, хх >0;х3> 0; х5 > 0; х2 и х5 не имеют ограничения знака; Zmin = х\ - 2*2 + х3 - х4 + *5-

Так как целевая функция на min, то в исходной задаче ограни-чения неравенства должны иметь знак >. Умножим второе неравенство системы на —1:

-2хх - За:2 + 2х3 + х4 - х5 > - 4.

В прямой задаче число ограничений равно 3, значит, в двойственной будет три переменных: их; и2\ и3. Так как и2 и ы3 соответствуют неравенствам, то и2 > 0; ы3 > 0. Параметр их соответствует равенству, поэтому их — переменная без ограничения знака.

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

целевая функция

^тах = - 4"2 + 8"3;

ограничения

их — 2и2 + ы3 < 1;

-2их - 3и2 = -2;

их + 2и2 + Зы3 < 1;

3 их + и2 = -1;

—2их — и2 — 4и3 < 1.

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

Теорема (первая теорема двойственности). Если одна из двойственных задач имеет оптимальное решение, то и другая его имеет. Причем экстремальные значения целевых функций совпа-дают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива.

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

ахххх + аХ2х2 + ...

+ аХпхп < ах\

: (7.63)

ат\*\ + ат&2 + - + amrPn ^ ат\

Zmax = СЛ + + ... + CJCn\

xt > 0; / = ГГл;

2) двойственная:

апих + a2lu2 + ... 4- amlum > cx\ \ (7.64)

alnu{ + a2nu2 + ... + amnum > cn\

Lmin = Wi + + - + amum\ Uj > 0, / = 1,/w.

Преобразуем задачи (7.63) и (7.64) к виду, допускающему применение симплекс-алгоритма. Для этого введем выравнивающие переменные ypj = 1,/и в прямую задачу и v,, / = 1,« — в двойственную задачу:

прямая:

ух = а{ - (апх{ + а12х2 + ... + а1пхп); I (7.630

Ут = от - (ат1хх + ат2х2 + ... + атпхп);

Zmax = 0 - (~C\Xi - <%> - ... - cjcn);

двойственная:

vi = —с\ - (-ацЩ - а21и2 - ... - ат1ит)'9 : (7.640

vn = ~~сп - (~а\пи\ - а2пи2 - ... - атпит)\ Lmm = 0 " (-«1^1 - Wl " - ~ <*mUm).

Построим для задач (7.63') и (7.64') общую симплекс-таблицу (табл. 7.23), причем эта таблица имеет дополнительные столбец и строку для двойственной задачи:

Таблица 7.23 Двойственная Vl v2 v„ Anin задача С *2 свободные Б члены -"і аХ2 -«2 У2 а}х ар «2 я а? Ут <*т\ ^/пя 7

^т ах ~С\ -С2 -с* 0

Задачи, представленные в общей симплекс-таблице (табл. 7.23), решаются обычным симплекс-методом, алгоритм которого приведен выше.

Сформулируем признаки оптимальности двойственной пары задач:

планы X— (хх, х2, хп) и ?/= (uXi w2, ит) оптимальны, если Zmax(X) = Lmln(U);

решения Х= (xb х2, ..., хп) и t/ = (wj, w2, ..., wm) оптимальны, если все произведения сопряженных условий для этих решений равны 0.

Запишем следующие сопряженные условия:

группа:

(ах - ахххх - аХ2х2 - ... - аХпхп) их = 0;

(<*т ~ <>т 1*1 ~ Я/я2*2 - - ~ "т =

группа получается, если умножить нахь х2, ..., хп выражения для базисных переменных двойственной задачи:

(аххих + а2Хи2 + ... + атХит - сх) X! = 0;

(ахпих + а2пи2 + ... + атпит - сп) хп = 0.

Пример 7.17. По исходной задаче построить двойственную и найти оптимальное решение обеих задач.

Zmax = ~~3*1 + 5Х2 + Х3 + Х4;

Зх! + 8Х2 + х3 + х4 < 50;

5хх — 4Х2 — х3 + х4 > 14;

ху>0,у=ГТ4.

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

3их + 5и2 > -3; 8их - 4и2 > 5; их- и2 > 1; их + и2 > 1;

Anin = 50«! + 14W2; их и и2 > 0.

Решим задачи в единой симплекс-таблице.

Для этого представим их в виде, позволяющем применить симплекс-метод:

прямая задача:

вводим выравнивающие переменные х5, х6:

х5 = 50 — (3xj + 8*2 + *з + x4)i х6 = 14 — (5xj - 4х2 - + х4);

^тах = 0 — (3xj — 5х2 — х3 — х4);

двойственная задача:

вводим в левую часть ограничений выравнивающие перемен-ные Vj, v2, v3, v4 со знаком «—»:

V! = 3 - (-3их -5w2); v2 = - 5- (-8«! +4k2); v3 = - 1 - (-ні + к2); v4 = -1 - (u{ - w2);

^rnin = 0 - (—50wj - 14w2).

Итак, составим таблицу, внешний контур которой образует двойственную задачу, внутренний - прямую задачу (табл. 7.24):

Таблица 7.24 Б* Vl v2 v3 V4 -^min С** С

Б *2 *з х4 свободные члены -щ -и2 *5 *6 3 5 1

-1 1 1 50 14 Свобод-ные члены z 3 -5 -1 -1 0 *Б - базисные переменные. **С — свободные переменные. Т

Будем работать по симплекс-методу, но так как записанная в последней строчке функция стремится к максимуму, то в этой строчке мы будем искать наименьший отрицательный элемент. Построим итоговую таблицу (табл. 7.25): Б* Vl Щ v3 V4 Lmin С* С

Б *5 *3 Х4 свободные члены -v2 -w2 *2 *6 3/8 1/8 1/8 1/8 52/8 4/8 -4/8 12/8 50/8 39 Свобод-ные члены z 39/8 5/8 -3/8 -3/8

Т 250/8

Б* Vl V2 v4 ^rnin С* С

Б Хь *2 Х4 свободные члены -v3 -w2 *3 *б 3 18 1 8 1 4 | 2 1 50 64 Свобод-ные члены 7

^тах 6 13 0

Т 50

Б* Vl Щ V2 "2 Lmin С* С

Б *1 Х2 *6 свободные члены -v3 -v4 *3

х4 -1 1/2 6 -1/2 4 1/2 2 1/2 18 32 Свобод-ные члены 7

^тах 6 13 0 50

Итак, мы получили итоговую таблицу (табл. 7.25), в последней строчке которой нет отрицательных элементов, следовательно, за-дачи решены:

прямая задача X = (0; 0; 18; 32), Zmax = 50; двойственная задача U ~ (1; 0), Zmin = 50.

Проверим полученное решение на оптимальность: условие 1) выполнено: Z (X) = L (U) = 50. Для выполнения условия 2) составим произведения сопряжен-ных условий:

XjVJ = X! (3 - (-3их - 5и2)) = 0 (3 - (-3 -1-50» = 0;

X2V2 = х2 (- 5 - (-Щ + 4и2)) = 0 (- 5 - (-8 • 1 + 4 • 0)) = 0;

x3v3 = х3 (-1 - (~их + и2)) = 18 (-1 - (-1 + 0)) = 0;

X4V4 = х4 (-1 - (~их - и2)) = 18 С— 1 — (-1 - 0)) ^ 0;

ихх5 = их (50 - (Зх! + 8х2 + х3 + х4)) = 1 (50 - (3 • 0 + 8 • 0 + 18 + + 32)) = 0;

"2*6 = и2 О - (5*1 ~ 4х2 - х3 + х4)) = 0 (14 - (5 • 0 - 4 .

0 - 18 + + 32)) = 0.

Итак, оба условия выполняются, значит, полученный план — оптимальный.

Рассмотренную задачу примера 7.17 можно решить иначе. Для этого необходимо:

решить прямую задачу обычным симплекс-методом. Решение получим следующее: Zmax = 50; X = (0; 0; 18; 32);

составить произведение сопряженных условий и приравнять их 0:

xxvx = хх (3 - (-3их - 5и2))\ x2v2 = х2 (- 5 - (-8их + 4и2))\

X3V3 = х3 (- 1 - (~их + и2))\ X4V4 = х4 (- 1 - (-их - и2))\

иххЗ = их (50 - (Зхх + 8Х2 + х3 + х4)); w2*6 = w2 (14 - (5хх - 4Х2 - х3 + х4)).

Подставим вектор X в записанные условия, тогда будем иметь:

18 • (— 1 — ( —их + и2)) = 0; 32 . (-1 _ (-их - и2)) = 0.

После преобразований получим:

1 + U{ + и2) = о; \ + (- их- и2) = 0.

Откуда их = 1; и2 = 0, Lmln = 50, так как Zmax = Z,min, значит, задача решена верно.

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 7.8. Двойственные задачи линейного программирования:

  1. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  2. 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 1.Метод линейного программирования.
  4. 7.1. Задачи линейного программирования
  5. 7.2. Построение экономико- математических моделей задач линейного программирования
  6. 7.3. Графическое решение задачи линейного программирования
  7. 7.6. Методы нахождения опорного решения задачи линейного программирования
  8. 7.7. Экономическая интерпретация решения задачи линейного программирования
  9. 7.8. Двойственные задачи линейного программирования
  10. Транспортные задачи линейного программирования
  11. 10.1. Геометрическая интерпретация задач нелинейного программирования
  12. 10.4. Многоцелевые задачи линейного программирования
  13. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  14. § 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом
  15. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
  16. ПАРАМЕТРИЧЕСКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  17. Линейное программирование с параметром в целевой функции
  18. Дробно–линейное программирование
  19. Приложение 3В. Линейное программирование