Основы теории двойственности

С каждой задачей линейного программирования

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

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

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

1) если целевая функция исходной задачи формулируется намаксимум, то целевая функция двойственной задачи — на минимум(и наоборот), при этом в задаче на максимум все неравенства в функциональных ограничениях со знаками« », в задаче на минимум — со знаками « »;

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

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений всистеме двойственной задачи — числу переменных в исходной;

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

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

Переменные двойственной задачи y_iв экономической литературе получили различные названия: теневые цены, объективно обусловленные оценки, двойственные оценки (илицены) ресурсов. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен на продукцию, известных, как правило, до начала производства, цены ресурсов являются внутренними, так как они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

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

Прямая задача: какое количество продукции каждого вида надо произвести, чтобы при заданных значениях стоимости единицы продукции с_j (j = 1, …, n), объемах имеющихся ресурсов b_i (i = 1, m)и нормах их расходовa_ijмаксимизировать выпуск продукции в стоимостном выражении при условии, что потребление ресурсов каждого вида не превзойдет имеющихся запасов.

Двойственная задача: какова должна быть минимальная оценка единицы каждого из ресурсов , чтобы при заданных величинахb_i, с_j, и a_ij минимизировать общую оценку затрат ресурсов на всю произведенную продукцию при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции?

Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может бытьрешена независимо от другой задачи. Вместе с тем, при решении прямой ЗЛП в «Поиске решений» в Excel формируется «Отчет по устойчивости», в котором содержатся значения двойственных оценок в колонке «Теневая цена» (см. рис. 2). Подробнее с содержанием отчета по устойчивости можно познакомиться в пособии [5].

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

MicrosoftExcel 14.0 Отчет об устойчивости

Лист: [Книга1]Лист1

Отчет создан: 08.07.2016 11: 17: 58

Ячейки переменных

Ячейка

Имя

Окончательное

Приведенн.

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

Допустимое

значение

стоимость

Коэффициент

Увеличение

Уменьшение

$A$1

Х1

-7

1E+30

$B$1

Х2

$C$1

Х3

1.75

$D$1

Х4

-9.666666667

9.666666667

1E+30

Ограничения

Ячейка

Имя

Окончательное

Теневая

Ограничение

Допустимое

Левая часть

значение

цена

Правая часть

увеличение

уменьшение

$E$4

Труд

1.333333333

$E$5

Сырье

1E+30

$E$6

Оборудование

0.333333333

Рисунок 2. Отчет по устойчивости

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

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

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

и набор цен (оценок) ресурсов

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

равна затратам на ресурсы по «внутренним» (определяемым только из решения двойственной задачи) ценам

Основная теорема устанавливает также наличие баланса (равенства) между результатами производстваF_maxи совокупными затратами Z_minна него.

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

(1)

(2)

Условия (1) и (2) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи (см. пример ниже).

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

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

Замечания

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

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

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

Следствия и уточнения

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

2) двойственные оценки представляют собой оценки влияния свободных членов b_iсистемы ограничений (неравенств) прямой задачи на величину прибыли (выручки) F

;

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

;

4) данная теорема справедлива при незначительных (малых) изменениях запасов ресурсов; эти допустимые изменения определяются интервалами устойчивости двойственных оценок, которые находят специальным образом или в «Отчете по устойчивости» (рис. 2, последние два столбца второй таблицы).

Пример. Сформулировать экономико-математическую модель двойственной задачи к задаче о коврах (см. пункт 1.1).Найти ее оптимальное решение с помощью теорем двойственности. Сделать выводы экономического характера.

Решение:

Исходная задача:

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

Исходная задача решена в предыдущем разделе. Для решения двойственной задачи воспользуемся второй теоремой двойственности. Подставим оптимальные значения переменных исходной задачи в ее систему ограничений

Так как второе ограничение оказалось строгим, то, во-первых, второй ресурс «Сырье» недефицитный (использован при производстве неполностью), а во-вторых, согласно условий (1) второй теоремы, .

Остальные две переменные двойственной задачи найдем с помощью условия (2) второй теоремы двойственности.

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

Таким образом, получаем оптимальное решение двойственной задачи, которое совпадает с представленным в отчете по устойчивости (см. рис. 2):

Согласно первой теореме двойственности, оптимальное решение найдено правильно, т.к. .

Экономические выводы:

1. Так как , то ресурсы первого и третьего видов дефицитны. Минимальная цена (оценка) 1 ед. первого ресурса – , второй ресурс недефицитный (остался после производства), так как , минимальная цена (оценка) 1 ед. третьего ресурса – .

2. Согласно теореме об оценках, при увеличении запасов 1-го и 2-го ресурсов на 1 ед. общая стоимость продукции увеличится соответственно на усл. ед.и усл.ед., а при увеличении запасов 2-го ресурса на 1 ед. общая стоимость продукции не изменится.

3. Общие затраты на ресурсы по теневым ценам будут минимальны и составят 150 усл. ед.

Материал, изложенный в данном пункте, позволяет определить следующие свойства двойственных оценок (далее ДО) ресурсов:

1. ДО устанавливают баланс(равенство) между результатами производства и совокупными затратами на него. Это свойство вытекает из первой теоремы двойственности.

2. ДО являются характеристикой дефицитности ресурсов (вторая теорема двойственности).

3. ДО выступают, как мера ценности каждой дополнительной единицы ресурса (вторая теорема двойственности).

4. ДО позволяют определить целесообразность включения в план производства новых видов изделий. Это свойство ранее не рассматривалось. Разберем его прямо сейчас.

Пусть планируется выпуск нового изделия j, стоимость единицы которого , затраты ресурсов на производство единицы планируемого к производству изделия соответственно . Вывод о целесообразности производства изделия зависит от знака разности

При производство выгодно, так как стоимость превышает затраты ресурсов, при затраты превышают стоимость – производство невыгодно.

Так, в нашей задаче о коврах выпуск нового вида продукции ценой за единицу 2 тыс. руб. и нормах затрат ресурсов соответственно 5, 2, 9 не будет выгодным, т.к.

Задачи для самостоятельного решения

Задание 1. Решить графическим методом задачу линейного программирования. Найти максимум и минимум функции f(X) при заданных ограничениях.

Варианты 1.1 – 1.10
1.1.	1.2.
1.3.	1.4.
1.5.	1.6.
1.7.	1.8.
1.9.	1.10.

Задание 2. Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам. Получить решение графическим методом. Проверить решение средствами Excel. Сделать выводы экономического характера.

Варианты 2.1 – 2.10

2.1.Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед.

Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?

2.2. Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:

Корма Питат. вещества	Количество питательных веществ в 1 кг корма

А В
Цена 1 кг корма, тыс.руб.	0, 2	0, 3

2.3.Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

2.4.На имеющихся у фермера 400 гектарах земли он планирует посеять кукурузу и сою. Сев и уборка кукурузы требует на каждый гектар 200 ден. ед. затрат, а сои – 100 ден. ед. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. ден. ед.. Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей – 60 центнеров. Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 3 ден. ед., а каждый центнер сои – 6 ден. ед. Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.

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

2.5.Продукция двух видов (краска для внутренних (I) и наружных (Е) работ) поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно. Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

Исходный продукт	Расход исходных продуктов на тонну краски, т	Максимально возможный запас, т
Краска Е	Краска I
А В

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

2.6. Финансовый консультант фирмы «АВС» консультирует клиента по оптимальному инвестиционному портфелю. Клиент хочет вложить средства (не более 25000$) в два наименования акций крупных предприятий в составе холдинга «Дикси».Анализируются акции «Дикси-Е» и «Дикси-В». Цены на акции: «Дикси-Е» – 5$ за акцию; «Дикси-В» – 3$ за акцию.

Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при этом акций одного из наименований должно быть не более 5000 штук.По оценкам «АВС» прибыль от инвестиций в эти две акции в следующем году составит: «Дикси-Е» – 1, 1$; «Дикси-В» – 0, 9$.

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

2.7. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей Х и Y. Завод располагает фондом рабочего времени в 4000 чел.-ч в неделю. Для производства одной детали типа Х требуется 1 чел.-ч, а для производства одной детали типа Y – 2 чел.-ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ден. ед., а от производства одной детали типа Y – 40 ден. ед.?

2.8. Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁S₂ и S₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
I	II
S₁ S₂ S₃

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.

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

2.9. При производстве двух видов продукции используется 4 типа ресурсов. Норма расхода ресурсов на производство единицы продукции, общий объем каждого ресурса заданы в таблице

Ресурсы	Норма затрат ресурсов на товары	Общее количество ресурсов
1-го вида	2-го вида

Прибыль от реализации одной единицы продукции первого вида составляет 2 ден. ед., второго вида – 3 ден. ед.

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

2.10.Фирма производит два широко популярных безалкогольных напитка – «Лимонад» и «Тоник». Фирма может продать всю продукцию, которая будет произведена. Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0, 02 ч работы оборудования, а для производства 1 л «Тоника» – 0, 04 ч. Расход специального ингредиента составляет 0, 01 кг и 0, 04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно и распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0, 10 ден. ед. за 1 л «Лимонада» и 0, 30 ден. ед. за 1 л «Тоника». Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли?

Задание 3. Решить симплекс-методом задачи линейного программирования.

Варианты 3.1 – 3.10
3.1.1.	3.1.2.
3.2.1.	3.2.2.
3.3.1.	3.3.2.
3.4.1.	3.4.2.
3.5.1.	3.5.2.
3.6.1.	3.6.2.
3.7.1.	3.7.2.
3.8.1.	3.8.2.
3.9.1.	3.9.2.
3.10.1.	3.10.2.

Задание 4. Построить экономико-математическую модель задачи линейного программирования. Решить ЗЛП симплексным методом. Сформулировать двойственную задачу и найти ее оптимальное решение с помощью теорем двойственности. Сделать выводы экономического характера. Провести проверку полученного решения взаимно двойственных задач средствами Excel, используя надстройку «Поиск решений» и «Отчет по устойчивости».

Варианты 4.1 – 4.10

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
А	Б	В	Г
I II III
Цена изделия

Требуется:

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

2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

3) Пояснить нулевые значения переменных в оптимальном плане.

4) На основе свойств двойственных оценок и теорем двойственности:

- проанализировать использование ресурсов в оптимальном плане исходной задачи;

- определить, как изменятся выручка и план выпуска продукции при увеличении запасов сырья I и II вида на 4 и 3 единицы соответственно и уменьшении на 3 единицы сырья III вида;

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

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
А	Б	В	Г
I II III
Цена изделия

Требуется:

2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

3) Пояснить нулевые значения переменных в оптимальном плане.

4) На основе свойств двойственных оценок и теорем двойственности:

- проанализировать использование ресурсов в оптимальном плане исходной задачи;

- определить, как изменятся выручка и план выпуска продукции при увеличении запасов сырья II и III вида на 120 и 160 единиц соответственно и уменьшении на 60 единиц запасов сырья I вида;

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

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
А	Б	В	Г
I II III
Цена изделия

Требуется:

2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

3) Пояснить нулевые значения переменных в оптимальном плане.

4) На основе свойств двойственных оценок и теорем двойственности:

- проанализировать использование ресурсов в оптимальном плане исходной задачи;

- определить, как изменятся выручка от реализации продукции и план ее выпуска при увеличении запасов сырья I и II вида на 8 и 10 единиц соответственно и уменьшении на 5 единиц запасов сырья III вида;

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

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
А	Б	В
I II III
Цена изделия

Требуется:

2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

3) Пояснить нулевые значения переменных в оптимальном плане.

4) На основе свойств двойственных оценок и теорем двойственности:

- проанализировать использование ресурсов в оптимальном плане исходной задачи;

- определить, как изменятся выручка от реализации продукции и план ее выпуска при увеличении запасов сырья I и III вида на 4 единиц каждого;

- оценить целесообразность включения в план изделия " Г" ценой 13 ед., на изготовление которого расходуется соответственно 1, 3 и 2ед. каждого вида сырья и изделия " Д" ценой 12ед., на изготовление которого расходуется по две единицы каждого вида сырья.

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

⇐ Предыдущая 1 2 345 6 7 8 9 Следующая ⇒