При использовании метода динамического программирования. Метод динамического программирования, как алгоритмическое выражение достаточно общей теории управления. I этап. Условная оптимизация

Двойственность в линейном программировании

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

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

Рассмотрим стандартную задачу ЛП с n переменными и m ограничениями в форме неравенств

f(x) = c1 x1 + c2 x2 + …+ cn xnmax,11 x1 + a12 x2 + … + a1n xn b1,21 x1 + a22 x2 + … + a2n xn b2,

…………………………………….……m1 x1 + am2 x2 + … + amn xn bm,j 0, j = 1, 2, …, n.

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

g(y) = b1 y1+ b2 y2 + …+ bm ym??min11 y1 + a21 y2 + … + am1 ym c112 y1 + a22 y2 + … + am2 ym c2

………………………….………………1n y1 + a2n y2 + … + amn ym cn

yi 0, i = 1, 2, …, m.

Выписывая матрицы условий для прямой и двойственной задачи

видим, что Адв = АTпр.

Следовательно, пара двойственных задач может быть записана в матричной форме:

< c, x > max; Ax ?b, x ?0.g(y) = < b, y > min; ATy ?с, y ?0.

2. Симметричная пара двойственных задач

Пара двойственных задач, в которых прямая задача - стандартная, называется симметричной парой двойственных задач.

Правила построения двойственной задачи к стандартной задаче ЛП.

·Число переменных двойственной задачи равно числу основных ограничений прямой задачи и наоборот.

·Если прямая задача есть задача на max при ограничениях «», то двойственная задача - задача на min при ограничениях «».

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

·Коэффициенты целевой функции прямой задачи - числа cj - становятся правыми частями ограничений двойственной задачи ЛП.

·j - й столбец матрицы условий прямой задачи превращается в j - ю строку матрицы условий двойственной задачи.

·Переменные прямой и двойственной задачи неотрицательны.

Пример. Рассмотрим стандартную задачу ЛП с двумя переменными, тремя ограничениями в форме неравенств и условиями неотрицательности.

f(x)=2x1-4x2max;1+ 3x2 8,

3x1+ x2 -7,

2x1 - 5x2 10,

x1, x2 0.

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

g(y)=8 y1-7y2+10 y3 min;1 - 3 y2+ 2 y3 2,

3y1+ y2 -5 y3 -4,1, y2 0.

Покажем, что двойственная к двойственной задаче ЛП совпадает с прямой задачей ЛП, для чего воспользуемся предыдущим примером.

Сначала приведем двойственную задачу к стандартному виду

g(y)= -8y1+7y2-10y3 max;1+ 3y2 - 2y3 -2,

3y1 - y2+ 5y3 4,1, y2 0.

Построим к ней двойственную задачу по правилам 1-6, обозначая двойственные переменные через x1, x2.

f(x)= - 2x1+ 4 x2 min;

x1 - 3x2 -8,

x1 - x2 7,

2x1+ 5x2 -10,

x1, x2 0.

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

Из вышесказанного следует, что если прямая задача имеет вид:

f(x) = < c, x > min; b, x 0,

то двойственной к ней будет задача

g(y) = < b, y > max;Ty с, y 0.

3. Экономический смысл двойственной задачи

Рассмотрим следующую производственную задачу.

Предприятие после выпуска основной продукции имеет излишки ресурсов двух типов: R1 - 10 единиц, R2 - 8 единиц. Существует два способа распорядиться этими ресурсами:

·организовать из них выпуск 3 новых видов продукции: P1, P2, P3.

·продать их.

Рассмотрим оба способа.

Исходные данные приведены в таблице:

РесурсыРасход ресурса на единицу продукцииЗапас ресурсовP1P2P3R112110R22138Удельная прибыль$6$4$4

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

Пусть xj - план выпуска продукции Pj.

Тогда целевая функция будет выглядеть следующим образом:

f(x)=6x1+4x2+4x3 max;

Ограничения по ресурсам:

1+2x2+x3 10,

x1+x2+3x3 8,j 0, j=1,2,3.

Получили стандартную задачу ЛП.

Рассмотрим второй способ использования ресурсов, а именно, их продажу.

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

В свою очередь покупатель заинтересован в приобретении ресурсов по таким ценам, при которых затраты на покупку будут минимальны.

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

Пусть y1 - цена одной единицы ресурса R1, y2 - цена одной единицы ресурса R2.

Интерес покупателя будет выражаться целевой функцией, равной суммарной стоимости приобретаемых ресурсов

g(y) = 10 y1+ 8 y2 min.

Интерес продавца будет описываться ограничениями:

y1+2y2 6,

y1+y2 4,

y1+3y2 4,

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

Присоединяя естественные условия неотрицательности цен:

y1, y2, y3 0,

получаем двойственную задачу ЛП.

Таким образом, симметричной паре двойственных задач можно придать определенный экономический смысл.

Прямая задача Определить такой план выпуска продукции x =(x1, x2,…, xn), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.Двойственная задача Установить такой набор цен ресурсов y =(y1, y2,…, ym), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

Цены ресурсов y1, y2,…, ym носят названия теневых, неявных или внутренних цен. Эти названия отличают их от «внешних», заранее известных цен с1, с2,…, сn на выпускаемую продукцию. Цены y1, y2,…, ym на ресурсы определяются из решения двойственной задачи и характеризуют стоимость затрат на выпуск конкретных видов продукции, поэтому их часто называют двойственными оценками ресурсов.

4. Несимметричная пара двойственных задач

Пусть теперь исходная задача - каноническая, то есть имеет вид:

f(x) = < c, x > max;(4.1)Ax = b,(4.2)x 0.(4.3)

Здесь x = (x1,…, xn), c = (c1,…, cn), b = (b1,…, bm), так что число уравнений в системе (4.2) равно m.

Для построения двойственной задачи к задаче (4.1) - (4.3) сведем ее к стандартной форме.

Каждое равенство в (4.2) заменим парой неравенств

или, что то же самое

Получим стандартную задачу ЛП с 2m ограничениями.

f(x)=< c, x > max;b,

Построим к ней двойственную задачу ЛП по известным правилам.

Для этого введем двойственные переменные:

u = (u1,…, um) 0,

v = (v1,…, vm) 0.

Заметим, что, так как в прямой задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.

Целевая функция двойственной задачи примет вид:

g (u, v)=< b, u > + < - b, v > min,

а ограничения запишутся так:

ATu - ATv c,

Перепишем эту задачу более компактно:

g (u, v)=< b, u - v> min,T (u - v) c, 0, v 0.

Введем новый вектор двойственных переменных y = (y1, y2,…, ym) с координатами yi = ui - vi. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2-5= -3), то двойственные переменные yi не имеют ограничений по знаку.

Таким образом, двойственная задача к канонической будет иметь вид:

g(y) = < b, y > min;Ty 0,

Переменная любого знака !

5. Таблицы для построения двойственной задачи

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

Прямая задача линейного программированияДвойственная задача линейного программированияЦелевая функция< c, x > max< b, y > minЦелевая функцияТип i-го ограниченияi biyi 0Знак i-й переменнойi biyi 0i = biyij 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Прямая задача линейного ПрограммированияДвойственная задача линейного программированияЦелевая функция< c, x > min< b, y > ?maxЦелевая функцияТип i-го ограниченияi biyi ?0Знак i-ой переменнойi biyi 0i = biyi - любого знакаЗнак j-ой переменнойxj 0j cjТип j-го ограниченияxj 0j cjxj ? свободная переменнаяj = cj

Задание . Составить двойственные задачи к следующим задачам ЛП.

1. f(x) = 2x1 - 2x2+ 3x3 - 6x4 max

x1+ x2 - 2x3 + x4 = -101 - 5x2 - x3 + 2x4 = 35j 0, j=1,2,3,4

F(x) = - x1 - 3x2+ x3 min1+ x2+ x3 61 - x2+ x3 8j 0, j=1,2,3

F(x) = 9x1+ 2x2+ 3x3+ 2x4 min

x1+ x2+ 2x3 = 2

x1+ x2 - x3 - 4x4 = -1j 0, j=1,2,3,4

F(x) = x1 - 2x2 max1+ x2 4

x1 - x2 8

x1+ x2 0

x2 0

6. Связь между планами двойственных задач

Рассмотрим симметричную пару двойственных задач:

f(x) = < c, x > max;(4.4)g(y) = < b, y > min;(4.7)Ax b(4.5)ATy c(4.8)x 0(4.6)(y 0(4.9)x = (x1,…, xn)y = (y1,…, ym)

Между решениями этих задач существует тесная связь, отражаемая следующими свойствами и теоремами.

7. Первая теорема двойственности

Кроме основного неравенства и достаточного признака оптимальности планов взаимно двойственных задач существуют и другие связи между их решениями. Важно установить, влияет ли наличие или отсутствие решения одной из пары задач на существование решения в другой. Ответ на этот вопрос дает следующая теорема, известная как первая теорема двойственности.

Теорема 1. Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем значения целевых функций на этих планах равны

(x*) = g(x*) или < c, x*> = < b, y*>.

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

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

Утверждение второй части теоремы легко доказывается от противного. Предположим, что в прямой задаче (4.4) - (4.6) целевая функция не ограничена сверху на множестве X, то есть max f(x) ¥ , xÎ X, но множество планов Y двойственной задачи не пусто - существует хотя бы одна точка yÎ Y. Тогда в силу основного неравенства теории двойственности: maxf(x) g(y), что противоречит неограниченности целевой функции прямой задачи. Таким образом, неограниченность сверху целевой функции исходной задачи влечет за собой несовместность ограничений двойственной задачи. Аналогично доказывается, что из неограниченности снизу двойственной целевой функции g(y) на множестве Y, следует пустота множества планов X прямой задачи.

Интересно, что обратное утверждение не верно. Из пустоты множества планов одной задачи еще не следует неограниченность целевой функции в двойственной к ней задаче. (Оба множества могут быть пусты).

Первая теорема двойственности позволяет исследовать любой заданный план на оптимальность.

8. Вторая теорема двойственности

Теорема 2.Планы x* = (x1*,…, xn*) и y* = (y1*,…, ym*) - оптимальны (каждый в своей задаче), тогда и только тогда, когда выполняются условия:

< Ax* - b, y* > = 0,(4.15)

< ATy* - c, x* > = 0,(4.16)

Доказательство.

Проведем доказательство для несимметричной пары двойственных задач.

Прямая задача ЛПДвойственная задача ЛПf(x) = < c, x > maxg(y) = < b, y > min(4.17) Ax = bATy cx 0

Необходимость.

Пусть x*, y* - оптимальные планы прямой и двойственной задач соответственно. Покажем, что условия (4.15), (4.16) выполняются.

Заметим, что при x = x* из (4.17) следует (4.15). Так как Ax* - b= 0, значит и скалярное произведение * - b, y* > тоже равно нулю. По первой теореме двойственности для оптимальных планов x*, y* выполняется равенство: < c, x* > = < b, y* >. Подставим сюда выражение для b из (14): b = Ax*. Используя правило перекидки, получим:

< c, x* > = < Ax*, y* >= < x*, ATy* > = < ATy*, x* >,

откуда следует < ATy* - c, x* > = 0. А это не что иное как условие (4.16)

Достаточность.

Пусть для допустимых планов x*, y* справедливо (4.15), (4.16). Докажем их оптимальность.

Условия (4.15) и (4.16) можно записать следующим образом

< Ax*, y* > = < b, y* >, < ATy*, x* > = < c, x* >.

По правилу перекидки < Ax*, y* > = < ATy*, x* >. Так как левые части условий равны, то равны и правые части:

< b, y* > = < c, x* >,

отсюда по свойству 2 заключаем, что x* - оптимальный план прямой задачи,* - оптимальный план двойственной задачи. Что и требовалось доказать.

. Условия равновесия

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

< Ax* - b, y* > = 0,(4.18)

< ATy* - c, x* > = 0. (4.19)

Прямая задача ЛПДвойственная задача ЛП f(x) = c1 x1 + … + cn xn maxg(y) = b1 y1+ …+ bm ym??minai1 x1 + … + ain xn bi, i =1,…, ma1j y1 + … + amj ym cj, j = 1,…, nxj 0, j = 1,…, nyi 0, i = 1,…, m

Раскрывая скалярные произведения, распишем условия (4.18) и (4.19) более подробно.

å (ai1 x1*+ … + ain xn* - bi) yi* = 0,(4.20)

å (a1j y1*+ … + amj ym* - cj) xj* = 0.(4.21)

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

(ai1 x1*+ … + ain xn* - bi) yi* = 0, i =1,…, m. (4.22)

двойственность неравенство равновесие линейный

В сумме (4.21) каждое слагаемое равно произведению разности левой и правой частей ограничения двойственной задачи на соответствующую переменную прямой задачи. Все слагаемые в этой сумме одного знака (0), так как разности в круглых скобках и переменные xj* неотрицательны. Для того, чтобы сумма равнялась нулю, любое слагаемое в сумме должно быть равно нулю.

(a1j y1*+ … + amj ym* - cj) xj* = 0, j = 1,…, n. (4.23)

Учитывая знаки сомножителей в произведении (4.22), из него можно получить пару условий

Если ai1 x1*+ … + ain xn* < bi, то yi* = 0. (4.22a)

Если yi* > 0, то ai1 x1*+ … + ain xn* = bi. (4.22b)

Аналогично, из (6) следует пара условий

Если a1j y1*+ … + amj ym* > cj, то xj* = 0. (4.23a)

Если xj* > 0, то a1j y1*+ … + amj ym* cj.(4.23b)

Таким образом, для пары двойственных задач

·если какое-либо ограничение одной задачи на оптимальном плане выполняется как строгое неравенство, то соответствующая координата оптимального плана другой задачи равна нулю (условия (4.22a) и (4.23a)).

·Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство (условия (4.22b) и (4.23b)).

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

. Геометрический смысл условий равновесия

Определение 1. Ограничение стандартной задачи линейного программирования

ai1 x1 + … + ain xn bi(4.24)

называется связным или активным на плане x", если на этом плане оно обращается в равенство

ai1 x1"+ … + ain xn" bi.

Определение 2 . Ограничение (4.24) называется несвязным (неактивным, пассивным) на плане x", если на этом плане оно выполняется как строгое неравенство

ai1 x1"+ … + ain xn" < bi.

Геометрически, ограничение, активное в точке x", проходит через эту точку, а неактивное - не проходит.

На рисунке в точке x" P1 и P3 - активные, связные ограничения; P2 - неактивное ограничение. В точке x» P1, P2 - активные ограничения; P3 - неактивное ограничение.

Теперь условиям равновесия можно придать геометрический смысл.

На оптимальных планах двойственных задач

·неактивному ограничению одной задачи соответствует нулевая переменная плана другой задачи.

·положительной переменной оптимального плана одной задачи соответствует активное ограничение другой задачи.

Литература

1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.

Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2009. - 354 с.

Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.

Доугерти Кристофер. Введение в эконометрику: Учебник для экон. спец. вузов / Пер. с англ. Е.Н. Лукаш и др. - М.: ИНФРА-М, 2007. - 402 с.

Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы: Учебник. - М.: Финансы и статистика, 2009. - 352 с.

Дуброва Т.А. Прогнозирование социально-экономических процессов. Статистические методы и модели: учеб. пособие / Т.А. Дуброва. - М.: Маркет ДС, 2007. - 192 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. -3-е изд., перераб. и доп. - М.: Дело, 2008. - 400 с.

Методы математической статистики в обработке экономической информации: учеб. пособие / Т.Т. Цымбаленко, А.Н. Баудаков, О.С. Цымбаленко и др.; под ред. проф. Т.Т. Цымбаленко. - М.: Финансы и статистика; Ставрополь: АРГУС, 2007. - 200 с.

Палий И.А. Прикладная статистика: Учебное пособие. - М.: Издательско-торговая корпорация «Дашков и К», 2008. - 224 с.

Порядина О.В. Эконометрическое моделирование линейных уравнений регрессии: Учебное пособие. - Йошкар-Ола: МарГТУ, 2006. - 92 с.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2007. - 344 с.

Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-у изд., испр. - Т. 2: Айвазян С.А. Основы эконометрики. - М.: ЮНИТИ-ДАНА, 2009. - 432 с.

Симчера В.М. Методы многомерного анализа статистических данных: учеб. пособие. - М.: Финансы и статистика, 2008. - 400 с.

Чураков Е.П. Прогнозирование эконометрических временных рядов: учеб. пособие / Е.П. Чураков. - М.: Финансы и статистика, 2008. - 208 с.

Эконометрика: учеб. / под ред. д-ра экон. наук, проф. В.С. Мхитаряна. - М.: Проспект, 2008. - 384 с.

Эконометрика: учеб. / под ред. И.И. Елисеевой. - М.: Проспект, 2009. - 288 с.

Эконометрика: Учебник/И.И. Елисеева, С.В. Курышева, Т.В. Костеева и др., Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 576 с.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

2. Теория двойственности в линейном программировании. Двойственный симплекс-метод

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

2.1. Определение и экономический смысл двойственной ЗЛП

Пусть прямая задача записана в каноническом виде:

https://pandia.ru/text/78/450/images/image005_76.jpg" width="23" height="25 src=">целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а векторправой части прямой задачи - вектором це­левой функции двойственной задачи.

5) Если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется, а ограничения имеют вид, и наоборот.

Прямая задача Двойственная задача

https://pandia.ru/text/78/450/images/image009_48.jpg" width="288" height="272">

Пример 2.1. Составить задачу,двойственную следующей задаче:

при ограничениях:

Решение.

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

2. Составим расширенную матрицу системы

3. Найдем матрицу , транспонированную к А

4. Сформулируем двойственную задачу:

при ограничениях

6.1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

Ранее была рассмотрена задача об использовании ресурсов (эконо­мико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1)..jpg" width="48" height="23">- число единиц ресурса, потребляемого при производстве едини­цы продукции https://pandia.ru/text/78/450/images/image024_16.jpg" width="16" height="24 src=">- прибыль (выручка) от реали­зации единицы продукции (или цена продукции).

Предположим, что некоторая организация решила закупить ресурсы https://pandia.ru/text/78/450/images/image027_10.jpg" width="95" height="24">заинтересована в том, чтобы затраты на все ресурсы Z в количествахпо ценам соответственнобыли минимальны, т. е

Готовая продукция" href="/text/category/gotovaya_produktciya/" rel="bookmark">готовую продукцию . На изготовление единицы про­дукции P1 расходуется единиц ресурса , единиц ресурса единиц ресурса , ..., единиц ресурса по цене соответственно Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изго­товлении единицы продукции P1, должны быть не менее ее цены с1, т. е.

https://pandia.ru/text/78/450/images/image040_4.jpg" width="113" height="20 src=">. Экономико-математическая модель и содержательная интерпретация полученной та­ким образом двойственной задачи II приведены в правой части табл. 6.1.

Составить такой план выпуска продукции X = (*], х2, ..., х„), при котором прибыль (выручка) от реализации продукции будет мак­симальной при условии, что по­требление ресурсов по каждому виду продукции не превзойдет имеющихся запасов

Найти такой набор цен (оценок) ресурсов Y = (yh уъ ..., ут), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при произ­водстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

Цены ресурсов в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены..jpg" width="113" height="25 src=">являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их ча­ще называют оценками ресурсов.

2.2. Основные положения теории двойственности

https://pandia.ru/text/78/450/images/image048_0.jpg" width="47" height="37 src=">- планы соответственно прямой и двойственной ЗЛП, тогда

(2.12)

Теорема 2, Пусть- планы соответственно прямой и двойственной ЗЛП и

, тогдаhttps://pandia.ru/text/78/450/images/image051_0.jpg" width="195" height="32"> (2.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Замечание. Если в одной из взаимно двойственных задач нару­шается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное. Это связано с тем, что при нарушении единственности оптимального решения исходной задачи в выражении линейной функции ее опти­мального решения через неосновные переменные отсутствует хотя бы одна из основных переменных.

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

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

3. Целочисленные модели исследования операций

Целочисленное программирование ориентировано на решение задач математиче­ского программирования, в которых все или некоторые переменные должны принимать только целочисленные значения.

Задача называется полностью целочисленной, если условие целочиc-ленности на­ложено на все ее переменные; когда это условие относится лишь к некоторым перемен­ным, задача называется частично целочисленной. Если при этом целевая функция и функ­ции, входящие в ограничения, линейные, то задача является линейной целочисленной.

Значительная часть экономических задач , относящихся к задачам линейного про­граммирования, требует целочисленного решения. К ним относятся задачи, у которых пе­ременные величины означают количество единиц неделимой продукции, например, рас­пределение производственных заданий между предприятиями, раскрой материалов, загрузка оборудования, распределение судов по линиям, самолетов по рейсам, а также за­дачи по производству неделимой продукции. Если единица составляет малую часть всего объема производства, то оптимальное решение находят обычным симплексным методом, округляя его до целых единиц, исходя из смысла задачи. В противном случае округление может привести к решению, далекому от оптимального целочисленного решения.

Пример 3,2, В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19,3 м площади. На приобретение оборудования предприятие может израсходовать 10 тыс. у. е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у. е., а II вида - 3000 у. е. Приобре­тение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида - на 3 ед. Зная, что для установки одного комплекта оборудования 1 вида требуется 2 м2 площади, а оборудования II вида - 1https://pandia.ru/text/78/450/images/image053_0.jpg" width="19" height="17 src=">комплектов оборудования 1 вида икомплектов оборудования II ви­да. Тогда переменныеидолжны удовлетворять следующим неравенствам:

(3.11)

Если предприятие приобретет указанное количество оборудования, то общее уве­личение выпуска продукции составит

(3.12)

По своему экономическому содержанию переменные х\ и Х2 могут принимать лишь целые неотрицательные значения, т. е.,

(3..jpg" width="55" height="29 src=">, максимизирующий линейную форму

(З.1)

и удовлетворяющий условиям:

https://pandia.ru/text/78/450/images/image064_0.jpg" width="22" height="30 src=">- целочисленная переменная, значе­ниекоторой в оптимальном решении ослабленной задачи является дробным. Интервал

не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значениедолжно удовлетворять одному из неравенств

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

Затем каждая подзадача решается как задача линейного программирования (с це­левой функцией исходной задачи). Если полученный оптимум оказывается допустимым для целочисленной задачи, такое решение следует зафиксировать как наилучшее. При этом нет необходимости продолжать «ветвление» подзадачи, поскольку улучшить полу­ченное решение, очевидно, не удастся. В противном случае подзадача, в свою очередь, должна быть разбита на две подзадачи опять при учете условия целочисленности переменных, значения которых в оптимальном решении не являются целыми. Разумеется, как только полученное допустимое целочисленное решение одной из подзадач оказыва­ется лучше имеющегося, оно фиксируется вместо зафиксированного ранее. Процесс ветвления продолжается, насколько это возможно, до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения. В этом случае зафиксированное допустимое решение является оптимальным.

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

3.2. Задача коммивояжера

Имеется n городов, занумерованных числами 1,2,...,n..jpg" width="64" height="20">между ними..jpg" width="37" height="18 src=">- время переналадки при переходе от обработки детали i к обработке детали j . Требуется найти после­довательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программи­рования определим булевы переменные следующим образом: , если коммивояжер переезжает и i-го города в j-й; https://pandia.ru/text/78/450/images/image075.jpg" width="33" height="28 src=">удовлетворяющих следующим соотношениям:

Водохранилище" href="/text/category/vodohranilishe/" rel="bookmark">водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем чтобы она учитывала перевозку нескольких видов продукции.

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

В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции из исходных пунк­тов в пункты назначения. Эту задачу можно видоизменить, включив в нее ограничения сверху на пропускные способности транспортных коммуникаций . Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.

Рассмотрим построение экономико-математической модели транспортной задачи на примере.

Пример 4.1. Построить экономико-математическую модель следующей задачи. Имеются три поставщика и четыре потребителя. Мощ­ность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик - потре­битель" сведены в таблицу поставок (табл. 7.1).

https://pandia.ru/text/78/450/images/image078.jpg" width="33" height="19">-клетки (i - номер

строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика

https://pandia.ru/text/78/450/images/image080.jpg" width="491" height="79 src=">

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу).

На множестве неотрицательных решений системы ограничений (7.1) и (7.2) найти такое решениеhttps://pandia.ru/text/78/450/images/image082.jpg" width="17" height="18 src=">.jpg" width="16" height="17 src=">в количестве единиц. Известна стоимость cij перевозки еди­ницы груза от i-ro поставщика к j-му потребителю.

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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

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

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

Теорема об оценках . Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b i в системе ограничений прямой задачи на величину целевой функции :

(2.8)

Компоненты оптимального решения двойственной задачи принято называть двойственными оценками . Часто употребляется также термин «объективно обусловленные оценки».

На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.

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

Формулировка прямой (исходной) задачи:

y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0.

В результате решения получим следующие оптимальные планы:

= (24, 4); = (1/3, 1/3, 0).

Легко убедиться, что при подстановке оптимальных планов в целевые функции задач оба получаемых значения равны 64.

Перейдем к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

Последнее утверждение легко подтвердить, подставив и в ограничения исходной задачи:

4ּ24 + 6ּ4 = 120, 2ּ24 + 6ּ4 = 72, 4 < 10.

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

Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса . Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3ּ12).

Свойство 3. Оценки как инструмент определения эффективности отдельных хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δ j) вычисляется как:

(2.9)

В том случае, если Δ j ≤ 0, вариант производства является выгодным, если Δ j > 0 – вариант невыгоден.

Вернемся к нашему примеру. Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ j по формуле (2.9):

Δ j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ j < 0, значит производить бейсбольные биты выгодно.

Свойство 4. Оценки как мера относительной заменяемости ресурсов с точки зрения конечного эффекта. Например, отношение / показывает, сколько единиц k-го ресурса может быть высвобождено при увеличении объема i-го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне; или наоборот, сколько единиц k-го ресурса необходимо дополнительно ввести при уменьшении на единицу объема i-го ресурса, если мы хотим, чтобы значение целевой функции не изменилось.

В нашем примере двойственные оценки первого и второго ресурсов равны. Это означает, что, например, при уменьшении фонда времени на участке А на 1 н-час необходимо увеличить фонд времени на участке В на 1 н-час, чтобы общая получаемая предприятием прибыль осталась неизменной.

Завершая рассмотрение вопроса, отметим, что применение теорем двойственности (а именно, соотношений (2.6) и (2.7)) позволяет, зная оптимальное решение одной из взаимно двойственных задач, без труда отыскать оптимальное решение другой задачи.

Проиллюстрируем это утверждение примером .

Для производства четырех видов изделий А 1 , А 2 , А 3 и А 4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.

Технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) и прибыль от реализации единицы каждого изделия приведены в таблице 2.12.

Таблица 2.12 - Исходные данные задачи о четырех видах изделий

Требуется, зная решение данной задачи, решить задачу, двойственную ей.

Сформулируем исходную ЗЛП.

Основные утверждения о взаимно двойственных задачах содержатся в следующих теоремах.

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

Если же у одной из этих задач целевая функция не ограничена, то двойственная ей задача не имеет допустимых решений. Наконец, если одна из этих задач не имеет допустимых решений, то двойственная ей задача либо также не имеет допустимых решений, либо имеет неограниченную целевую функцию.

Вторая теорема двойственности. Для того, чтобы два допустимых решения
иУ =(у 1 , у 2 , …, у m ) пары двойственных задач были оптимальными необходимо и достаточно, чтобы они удовлетворяли так называемым «условиям дополняющей нежесткости»:

1)

2)

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

Третья теорема двойственности (теорема об оценках). Значения переменныху i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов ограничений исходной задачи на экстремальное значение ее целевой функции Z max , т.е.

.

3.3 Экономическая интерпретация двойственных задач

В разделе 3.1 приведен один из возможных вариантов экономической интерпретации двойственных задач. В случае рассмотрения задачи планирования работы предприятия, производящего n видов продукции с использованиемm видов ресурсов, решением исходной задачи является план производства
, а решением двойственной задачи – совокупность цен (двойственных оценок) ресурсовУ =(у 1 , у 2 , …, у m ), соответствующих этому плану.

Существует тесная связь между решениями пары двойственных задач.

Согласно третьей теореме двойственности оценки ресурсовУ =(у 1 , у 2 , …, у m ) выступают как мера влияния объемов ресурсов на величину максимума товарной продукции (Z max ). Они показывают: на сколько увеличится значение целевой функции при приращении данного ресурса наединицу . Следовательно, еслиi -й ресурс увеличится на
единиц, то целевая функция соответственно возрастет на
ден. ед. Однако надо помнить, что это справедливо только для таких приращений ресурса, которые не вызовут изменение базиса исходной задачи.

Чтобы определить предел увеличения ресурса, не приводящий к изменению базиса в оптимальной симплекс-таблице, рассматривают коэффициенты таблицы, принадлежащие столбцу соответствующей ресурсу дополнительной переменной. Эти коэффициенты показывают на сколько увеличатся (если коэффициент больше 0), и на сколько уменьшатся (если коэффициент меньше 0) значения базисных переменных, если в задачу вводится дополнительная единица ресурса. Предел увеличения ресурса находится из условия неотрицательности новых значений базисных переменных. Поэтому его вычисляют как минимум модуля отношений значений базисных переменных к отрицательным коэффициентам столбца дополнительной переменной. Например, для ресурса с индексом j предел увеличения равен

для коэффициентов
.

Пример расчета предела увеличения ресурса для задачи 2.1 приведен в разделе 2.2. В этой задаче при увеличении ресурса 2, не превышающем 6000 ед., справедлива его оценка y 2 , являющаяся решением двойственной задачи.

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

.

Из второй теоремы двойственности следует, что если оценкау i единицы ресурса положительна, то при оптимальном плане производства этот ресурс используется полностью, т.е. является по определению дефицитным, ау i называетсястепенью дефицитности . Если же ресурс используется не полностью, то его оценка равна0. Аналогично, еслиj -я продукция используется в производстве, т.е.
, то она в оптимальных двойственных оценках неубыточна (рентабельна), если же она убыточна (нерентабельна), то в производстве не используется (
). Двойственная оценкау j такой продукции называетсястепенью нерентабельности .

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

Решение двойственной задачи получается в последней симплексной таблице исходной задачи (3.1)-(3.3), в (М+1)-й строке.

Если в качестве исходной задачи служит модель (3.4)-(3.6), то решение двойственной к ней (3.1)-(3.3) получается умножением на (-1) соответствующих элементов (М+1)-й строки последней симплекс-таблицы задачи (3.4)-(3.6).

Для того чтобы правильно выписать из симплекс-таблицы решение двойственной задачи, необходимо установить соответствие переменных прямой и двойственной задач, исходя из их канонической формы:

– основным переменным прямой задачи соответствуют дополнительные переменные двойственной;

– дополнительным переменным исходной соответствуют основные переменные двойственной модели.

Значения основных переменных двойственной задачи расположены в столбцах дополнительных переменных (М+1)-й строки симплекс-таблицы прямой задачи, а значения дополнительных переменных – в столбцах основных переменных той же строки.

Рассмотрим оптимальный план задачи 2.1 (таблица 3.1).

Запишем соответствие переменных прямой и двойственной задач.

Исходная задача	х 1	х 2	х 3	х 4	х 5	х 6
Двойственная задача	у 4	у 5	у 6	у 1	у 2	у 3

В таблице 3.1 скопирована последняя симплекс-таблица задачи 2.1 и подписаны обозначения двойственных переменных, значения которых получаются одновременно с решением исходной задачи.

Таблица 3.1 – Расположение оптимального плана двойственной

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

		х 1	х 2	х 3	х 4	х 5	х 6
х 4 х 3 х 6
Двойственные переменные		у 4	у 5	у 6	у 1	у 2	у 3

Оптимальный план:

,
,
.

,
,
,

.

Оптимальный план двойственной задачи:

,
,
,

,

.

.

Именно по двойственным переменным был проведен экономический анализ решения задачи линейного программирования в разделе 2.2.

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования­ – двойственную. Решая одну из них, автоматически решается и другая задача. Такие задачи называют взаимно двойственными. Двойственные задачи имеют важный экономический смысл, теория двойственности позволяет найти некоторые экономические характеристики производственных процессов, провести анализ на чувствительность.

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

Задача 8 (о плане). Предприятие располагает тремя видами сырья и намеревается выпускать четыре вида продукции. Технологические коэффициенты в таблице (табл.2.12) указывают затраты соответствующего вида сырья на 1 единицу определенного вида продукции, а также прибыль от реализации 1 единицы продукции и общие запасы ресурсов. Найти оптимальный план производства продукции, при котором будет обеспечена максимальная прибыль.

Таблица 2.12

Составим математическую модель. Пусть количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:

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

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

Запишем задачу в таблицу, предварительно выписав ее каноническую форму.

.

I этап. Эта задача специального вида, базис составляют переменные , правые части уравнений неотрицательны, опорный план допустимый. Он соответствует симплекс-таблице (табл.2.13).

Таблица 2.13

свободные базис					правые части
		0,4		0,5
					100
	-3	-5	-4	-5

II этап . Проверим план на оптимальность. Так как в индексной F–строке есть отрицательные элементы, то план не оптимален, переходим к III этапу.

III этап. Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, могли выбрать и второй, т.к. в обоих – 5. Выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум отношений . С разрешающим элементом проводим преобразование таблицы по правилам 3.1–3.5 (табл.2.14).

Таблица 2.14

свободные базис					правые части
	4,5	0,4	1,5	-0,5
	-1		-1	-1	200
		-5

Полученный план опять не оптимален, т.к. в строке есть отрицательный элемент –5, этот столбец разрешающий. В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять «внутренность» таблицы. Результаты запишем в таблицу 2.15.

Таблица 2.15

свободные базис					правые части

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап. Базисные переменные принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план и

Действительно, Т.е. для получения максимальной прибыли в 700 руб., предприятие должно выпускать изделия II вида в количестве 40 штук, IV вида в количестве 100 штук, изделия I, III видов производить невыгодно. При этом напомним смысл дополнительных переменных – это излишки сырья, следовательно, сырье 2–го и 3–го видов будет израсходовано полностью, а сырья 1-го вида останется 334 единицы, т.к. .

Сформулируем правила построения двойственной задачи.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной (без учета неравенств неотрицательности).

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

3. Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной и наоборот.

4. Целевая функция в одной задаче максимизируется, в другой минимизируется.

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

При записи задач их следуетужно располагать рядом друг с другом, точно определяя соответствие неравенств (показано стрелочками).