Тема 19. Двойственность в решении задач лп.

С каждой задачей ЛП тесно связана другая линейная задача, называемая двойственной, первоначальная задача называется исходной или прямой. [32] Связь исходной и двойственной к ней задач заключается в частности в том, что решение одной из них может быть получено непосредственно из решения другой.

Каждая из задач двойственной пары фактически является самостоятельной задачей ЛП и может быть решена независимо от другой. Однако при определении симплекс-методом оптимального плана одной из задач находится решение и другой задачи.

Хорошо разработанный математический аппарат ЛП позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной задаче ЛП.

Таблица 4.7 [33] Задача I Задача I` (4.25’)

х1, х2, х3 ? 0 (4.24)

(4.25) а11х1 + а12х2 + а13х3 ? b1

а21х1 + а22х2 + а23х3 ? b2

f = c1х1 + c2х2 + c3х3

Найти max f при условиях (4.24) и (4.25)

у1, у2 ? 0 (4.24’)

а11y1 + а12y2 ? c1

а21y1 + а22y2 ? c2

а31y1 + а32y2 ? c3

j = b1y1 + b2y2

Найти min j при условиях (4.24’) и (4.25’)

Задачи I и I` будут являться двойственными друг другу. Смысл, вкладываемый в это название, состоит в следующем:

1) Если первая задача имеет размеры m x n, то вторая n x m. Так, в задаче I два ограничения с тремя неизвестными, а в задаче I` три ограничения с двумя неизвестными.

2) Матрицы их коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными.

3) В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.

4) В задаче I все ограничения представляют собой неравенства типа ?, причем в этой задаче требуется достичь максимума f. Напротив, в задаче I` все ограничения суть неравенства типа ?, причем требуется достичь минимума j.

Если ввести в рассмотрение матрицуА = а11 а12 а13

а21 а22 а23

х1

х2

х3

b1

b2

y1

y2 из коэффициентов при неизвестных в системе (4.24), а также матрицы (векторы) – столбцы

c1

c2

c3

Х = , В = , У = , С = ,

то получим другую (матрично-векторную) форму записи задач:

Таблица 4.8 [34]

Задача I Задача I?

Х ? 0

АХ ? В

f = CтХ ® max

Y ? 0

AтY ? C

j = BтY ® min

В таком виде может быть задана любая пара взаимно двойственных задач ЛП. При этом задача I может иметь произвольные размеры m x n, а задача I? соответственно размеры n x m.

Типичным примером двойственных задач будет являться задача об альтернативном использовании производственных ресурсов. [35]

На некотором предприятии после выполнения поставленного производственного плана осталось некоторое количество неиспользованного сырья. Существует 2 альтернативные возможности:

a) наладить производство из оставшегося сырья другой продукции;

b) реализовать сырье сторонней организации, нуждающейся в нем.

Будем считать, что имеются 2 вида сырья S1 и S2, остатки которого составляют 35 и 20 единиц. Из них можно изготовлять 3 вида товаров: Т1, Т2, Т3. От реализации единицы каждого из них получается прибыль: от Т1 – 7, от Т2 – 6, от Т3 – 18. Нормы расхода сырья на их производство вместе с данными о прибыли и записках даны в таблице:

Таблица 4.9 Вид товаров Сырье Прибыль от продажи единицы товара S1 S2 Т1 1 2 7 Т2 1 1 6 Т3 5 2 18 Запасы сырья 35 20

При исследовании возможности а) возникает вопрос о плане выпуска. Последний задается тремя числами х1, х2, х3, где хi - количество товара Тi, которое следует произвести (i = 1, 2, 3). Неизвестные х1, х2, х3 должны удовлетворять условиям:

х1, х2, х3 ? 0,

х1 + х2 + 5х3 ? 35,

2х1 + х2 + 2х3 ? 20.

Прибыль, которую получит предприятие от реализации плана (х1, х2, х3) выпуска товаров, составит, очевидно f = 7х1 + 6х2 + 18х3 .

В интересах предприятия максимизировать эту прибыль. Следовательно, чтобы наилучшим образом использовать первую возможность, нужно решить задачу ЛП: f ® max при вышеуказанных условиях.

Эта задача соответствует задаче I.

Вторая возможность – продать сырье. Обозначим цены продажи у1 и у2 (уi – цена единицы сырья Si, i = 1, 2). Разумеется,

у1, у2 ? 0.

Справедливое требование к ценам со стороны продавца состоит в следующем: выручка от продажи запасов сырья должна быть не меньше, чем прибыль от реализации готовых изделий – сырье, идущее на изготовление товара Тi при его продаже должно давать не меньшую прибыль, чем готовое изделие. Это требование выражается неравенствами

у1 + 2у2 ? 7,

у1 + у2 ? 6,

5у1 + 2у2 ? 18.

Других требований к ценам у1 и у2 предприятие – продавец предъявлять не может. Что же касается покупателя, то для него единственное пожелание заключается в сокращении до минимума расходов на покупку сырья, то есть величины

j = 35у1 + 20у2 .

Следовательно, необходимо решить задачу ЛП j ® min при описанных для цен на сырье условиях.

Эта задача соответствует задаче I?.

Относительно взаимно двойственных задач могут быть сделаны следующие основные утверждения, содержащиеся в двух теоремах. [36]

Первая теорема двойственности. Для взаимно двойственных задач ЛП имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения (более того, если оптимальное решение имеет одна из двойственных задач, то оно есть и у другой), причем значения целевых функций в точке оптимальности совпадает: max f = min j. Таким образом, если и – оптимальные решения двойственных задач, то критерием оптимальности решения каждой из них будет выполнение равенства

(4.26) f ( ) = j( ).

Экономический смысл может быть интерпретирован следующим образом: организации безразлично, производить ли продукцию по оптимальному плану и получить максимальную прибыль max f или продавать ресурсы по оптимальным ценам и возместить от продажи равные ей минимальные затраты на ресурсы min j.

2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху (max f = +?). При этом двойственной задачи окажется пустое допустимое множество решений.

3. В двойственной задаче допустимое множество решений не пусто, а целевая функция на этом множестве не ограничена снизу (min j = –?). При этом у прямой задачи множество допустимых планов оказывается пустым.

4. Обе рассматриваемые задачи имеют пустые множества допустимых решений.

(4.27) Вторая теорема двойственности (теорема о дополняющей нежесткости, теорема равновесия). Взаимно двойственные задачи вида (4.24), (4.25) и (4.24’), (4.25’) чтобы решать их симплекс-методом, необходимо привести к каноническому виду, а для этого в систему ограничений вида (4.24) следует ввести m неотрицательных переменных хn+1, xn+2, …, xn+m, а в систему вида (4.24’) – n переменных yn+1, yn+2, …, yn+m. Тогда системы ограничений каждой из двойственных задач примут вид:

i = 1, 2, …, m.

(4.28) j = 1, 2, …, m.

Установлено следующее соответствие между первоначальными и дополнительными переменными двойственных задач:

Таблица 4.10[37]

Переменные исходной задачи Первоначальные Дополнительные х1 х2 … хj … xn xn+1 xn+2 … xn+i … xn+m ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ym+1 ym+2 … ym+1 … ym+n y1 y2 … yi … ym Дополнительные Первоначальные Переменные двойственной задачи

Пусть – оптимальное решение прямой задачи, а – оптимальное решение двойственной задач. В этом случае, чтобы они действительно являлись оптимальными решениями взаимодвойственных задач I и I?, необходимо и достаточно, чтобы выполнялись соотношения:

(4.29) ;

.

В силу условия неотрицательности переменных каждое слагаемое в равенствах (4.29) должно равняться 0.

Выражения

(i = 1, 2, …, m )

и

(j = 1, 2, …, n )

называют невязки. [38]

Верным также является следующее утверждение, непосредственно вытекающее из теоремы о дополняющей нежесткости.

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

Эти условия устанавливают известное равновесие между задачами I и I? если в одной задаче нечто отлично от нуля, то в двойственной задаче нечто равно нулю. Отсюда еще одно название второй теоремы – «теорема равновесия».

Вышеозначенные условия имеют простой экономический смысл. Обратимся к производственной задаче об альтернативном использовании ресурсов. Предположим, что для некоторого номера i (1 или 2) выполняется условие уi ? 0 или, что то же

ai1x1 + ai2x2 + ai3x3 < bi .

Это означает, что расход сырья Si строго меньше его запаса – Si не является дефицитным. В этом случае мы должны иметь уi = 0, то есть продажная цена Si должна равняться нулю. Величина уi выступает в роли меры дефицита сырья Si. Отсюда и название для величин уi (элемент оптимального решения двойственной задачи) – объективно обусловленные оценки. [39]

Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной целевой функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. Это утверждение и называют второй теоремой двойственности.[40]

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

1) обе задачи приводятся к каноническому виду;

2) устанавливается соответствие между переменными обеих задач;

3) с помощью симплекс-метода решается та задача, где свободные члены в выражениях для базисных неизвестных неотрицательны (предполагается, что одна из задач таким свойством обладает);

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

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

Таблица 4.11

Задача I Задача I?

х1, х2, х3 ? 0,

х1 + х2 + 5х3 ? 35,

2х1 + х2 + 2х3 ? 20.

f = 7х1 + 6х2 + 18х3 ® max

у1, у2 ? 0

у1 + 2у2 ? 7,

у1 + у2 ? 6,

5у1 + 2у2 ? 18.

j = 35у1 + 20у2 ® min

Приведем обе задачи к каноническому виду, чтобы иметь возможность решить их с помощью симплекс-метода:

Таблица 4.12

Задача I Задача I?

х1, х2, х3 ? 0,

х1 + х2 + 5х3 + х4 = 35,

2х1 + х2 + 2х3 + х5 = 20.

f = 7х1 + 6х2 + 18х3® max

у1, у2 ? 0

у1 + 2у2 – у3 = 7,

у1 + у2 – у4 = 6,

5у1 + 2у2 – у5 = 18.

j = 35у1 + 20у2 ® min

Установим соответствие между переменными задач:

Таблица 4.13

Переменные задачи I Первоначальные Дополнительные х1 х2 х3 x4 x5 ¦ ¦ ¦ ¦ ¦ у3 у4 y5 y1 у2 Дополнительные Первоначальные Переменные задачи I’

Теперь с помощью симплекс метода решим одну из двойственный задач, допустим, задачу I. Первоначально преобразуем целевую функцию так, чтобы данная задача стала задачей на минимум. С этой целью умножим ее на –1:

f = –7х1 – 6х2 – 18х3® min.

Приведем ее к виду (4.14):

f + 7х1 + 6х2 + 18х3 = 0 ® min.

Теперь нужно выделить первоначальный опорный план. Его составят переменные х4 и х5. Матрица параметров системы имеет вид:

1 1 5 1 0 35 2 1 2 0 1 20

Составим первую симплекс-таблицу:

Таблица 4.14

–7 –6 –18 0 0 0 Базисные переменные х1 х2 х3 х4 х5 Свободные члены 0 х4 1 1 5 1 0 35 0 х5 2 1 2 0 1 20 f 7 6 18 0 0 0

В последней строке таблицы нет ни одного отрицательного значения, значит данное базисное решение не оптимально. Чтобы определить столбец, в котором будет находиться разрешающий элемент, выберем столбец который содержит наибольшее значение на пересечении со строкой у. Это столбец х3, следовательно, в базис необходимо ввести х3. Переменную, которую нужно вывести из базиса, определяем, как и раньше. Это переменная х4 (35:5=7<10=20:2). Преобразуем исходную таблицу так, чтобы на месте х4 в базис вошла переменная х3:

Таблица 4.15

–7 –6 –18 0 0 0 Базисные переменные х1 х2 х3 х4 х5 Свободные члены –18 х3 1 0 7 0 х5 1 0 – 1 6 f 3 2 0 –3 0 –126

Во второй получившейся таблице в последней строке два положительных значения, что опять-таки говорит о неоптимальности решения. Наибольшее находится в столбце х1. Остается определить, какой из элементов этого столбца будет разрешающим элементом. Это элемент, находящийся в строке х5. Теперь нужно вывести из базиса неизвестное х5 и ввести в базис х1:

Таблица 4.16

–7 –6 –18 0 0 0 Базисные переменные х1 х2 х3 х4 х5 Свободные члены –18 х3 0 1 – 6 –7 х1 1 0 – 3 f 0 1 0 –2 –2 –138

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

Таблица 4.17

–7 –6 –18 0 0 0 Базисные переменные х1 х2 х3 х4 х5 Свободные члены –18 х3 – 0 1 – 5 –6 х2 2 1 0 – 1 10 f –3 0 0 –2 –4 –150

В этой таблице последняя строка не содержит положительных элементов, следовательно, найдено оптимальное решение задачи: = (0, 10, 5, 0, 0) (в исходной задаче х1 = 0, х2 = 10, х3 = 5, остатки х4 и х5 равны нулю).

Выраженная через независимые переменные системы целевая функция будет иметь вид

f – 3х1 – 2х4 – 4х5 = –150 ® min,

f = 3х1 + 2х4 + 4х5 – 150 ® min.

Задача на максимум будет выглядеть

f = 150 – 3х1 – 2х4 – 4х5 ® max,

и при найденном базисном решении fmax = 150.

Тогда согласно первой теореме двойственности ?min решение двойственной задачи тоже равно 150.

В таблице 4.13 было установлено некоторое соответствие между переменными исходной и двойственной задач. Тогда с учетом этого соответствия оптимальное решение двойственной задачи I’ = (2, 4, 3, 0, 0), то есть вместо производства товаров сырье можно реализовать по указанным ценам, при чем что касается сырья для производства товара Т1, то от простой продажи его по данным ценам получится даже большая прибыль, чем от продажи одного готового изделия (превышение равно у3 = 3).

Математические модели пары двойственных задач могут быть симметричными и несимметричными. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными. В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.[41]

Всегда имеется возможность выбора: решать прямую задачу или двойственную, использовать прямой или двойственный симплекс-метод. Выбирают ту модификацию задачи, которую, проще решать. Например, если исходная задача содержит переменные, на которые не наложено условие неотрицательности, то бывает удобнее решать двойственную задачу. Прежде чем записать двойственную задачу, полезно в исходной освободиться от ограничений в виде равенств, поскольку в двойственной задаче они будут порождать переменные, которые могут иметь любой знак. То есть привести несимметричные задачи ЛП к симметричному виду.

--------------------------------------------------------------------------------

[1] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999. – С. 58

[2] Немчинов В.С. Экономико-математические методы и прикладные модели. – М.: Мысль, 1965. – С. 80

[3] см., например, Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. –С. 127

[4] Математика. БЭС / Гл. ред. Ю.В. Прохоров.- 3-е изд.- М.: Большая Российская энциклопедия, 1998.- С. 248

[5] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 21

[6] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 128

[7] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 21

[8] Грешилов А.А. Как принять наилучшее решение в реальных условиях. – М.: Радио и связь, 1991. – С. 25

[9] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 129

[10] см., например: Канторович Л. В., Горстко А.Б. Оптимальные решения в экономике. – М.: Наука, 1972. – 231 с.

[11] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999. – С. 58

[12] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 25

[13] Солодовников А.С., Бабайцев В.А., Браилов А.В., Шандра И.Г. Математика в экономике. В 2-х ч. Ч. 1. – М.: Финансы и статистика, 1999. – С. 134

[14] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 26

[15] Солодовников А.С., Бабайцев В.А., Браилов А.В., Шандра И.Г. Математика в экономике. В 2-х ч. Ч. 1. – М.: Финансы и статистика, 1999. – С. 134

[16] из: Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999. – С. 60

[17] То есть наряду с любыми двумя своими точками содержит и отрезок, их соединяющий.

[18] Грешилов А.А. Как принять наилучшее решение в реальных условиях. – М.: Радио и связь, 1991. – С. 54

[19] см. Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999. – С. 62 – 64

[20] Грешилов А.А. Как принять наилучшее решение в реальных условиях. – М.: Радио и связь, 1991. – С. 53

[21] Там же.

[22] Математика. БЭС / Гл. ред. Ю.В. Прохоров.- 3-е изд.- М.: Большая Российская энциклопедия, 1998. – С. 543

[23] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 156

[24] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999. – С. 66

[25] Математическая экономика на персональном компьютере/ пер. с яп.: Под ред. М. Кубонива: Под ред и с предисл. Е.З. Демиденко – М.: Финансы и статистика, 1991. – С. 222

[26] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 158

[27] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 166

[28] Там же, С. 168

[29] см. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 169 – 171.

[30] см., например, Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 172 – 179; Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 61 – 64; Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. – М.: ЮНИТИ, 2000. – С. 94 – 97.

[31] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 176

[32] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 67

[33] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 191

[34] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 191

[35] Там же, С. 187-189

[36] Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 70

[37] Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. – М.: ЮНИТИ, 2000. – С. 108.

[38] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 194

[39] Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 196

[40] Кремер Н.Ш., Путко Б.А., Тришин И.М., Фридман М.Н. Исследование операций в экономике: Учебное пособие для ВУЗов/ под ред. проф. Кремера Н.Ш. – М.: ЮНИТИ, 2000. – С. 110.

[41] см., например, Экономико-математические методы и прикладные модели/ Под. ред. Федосеева В.В. – М.: ЮНИТИ, 1999. – С. 69; Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. В 3-х ч. Ч. 1. – М.: Финансы и статистика, 1998. – С. 215 – 218.