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

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

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max f(X) = min g(Y).

2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.

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

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

Вторая теорема двойственности (теорема о дополняющей нежесткости)

Пусть   - допустимое решение прямой задачи (3.1)-(3.3), а   - допустимое решение двойственной задачи (3.4)-(3.6). Для того чтобы они были оптимальными решениями соответствующих взаимодвойсгвенных задач (3.1)-(3.3) и (3.4)-(3.6), необходимо и достаточно, чтобы выполнялись следующие соотношения:

 (3.7)

 (3.8)

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

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

Теорема об оценках (третья теорема двойственности)

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

 (3.9)

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

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

Пример 3.1 (задача оптимального использования ресурсов). Пусть для выпуска четырех видов продукции Р₁, Р₂, Р₃, Р₄ на предприятии используют три вида сырья S₁, S₂ и S₃. Объемы выделенного сырья, нормы расхода сырья и прибыль на единицу продукции при изготовлении каждого вида продукции приведены в табл. 3.1. Требуется определить план выпуска продукции, обеспечивающий наибольшую прибыль.

Решение. Составим экономико-математическую модель задачи оптимального использования ресурсов на максимум прибыли. В качестве неизвестных примем объем выпуска продукции j-го вида x_j (j = 1, 2, 3, 4).

Таблица 3.1

Исходные данные

Вид сырья	Запасы сырья	Вид продукции
		Р1	Р2	Р3	Р4
S1	35	4	2	2	3
S2	30	1	1	2	3
S3	40	3	1	2	1
Прибыль		14	10	14	11

Модель задачи по критерию "максимум прибыли":

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

1) покупающая организация старается минимизировать общую стоимость ресурсов;

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

Согласно первому условию общая стоимость сырья выразится величиной  . Согласно второму требованию вводятся ограничения: на единицу первого вида продукции расходуются четыре единицы первого ресурса ценой y₁, одна единица второго ресурса ценой у₂ и три единицы третьего ресурса ценой у₃. Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна   и должна составлять не менее 14, т.е. 

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

По экономическому смыслу цены неотрицательные:

Получили симметричную пару взаимодвойственных задач. В результате решения данной задачи симплексным методом получен оптимальный план  . На рис. 3.1 приведен результат решения задачи с использованием надстройки Поиск решения Excel. Жирным шрифтом выделены оптимальные значения   и  .

Экономический смысл первой теоремы двойственности следующий. План производства X и набор оценок ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции с₁, с₂,..., с₃, равна затратам на ресурсы но "внутренним" (определяемым только из решения задачи) ценам ресурсов у₁, у_2,…,у_т. Для всех же других планов   и   обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов: , т.е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит, величина   характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов.

Ячейки переменных
Ячейка	Имя	Окончательное значение	Приведенная стоимость	Целевая функция Коэффициент		Допустимое увеличение		Допустимое уменьшение
SBS1		0	-2	14	2				1Е+30
SCSI		5	0	10	4				0.666666667
SDS1		12,5	0	14	2				4
SES1		0	-10	11	10				1Е+30
Ограничения
Ячейка	Имя	Окончательное значение	Теневая цена	Ограничение Правая сторона	Допустимое увеличение				Допустимое уменьшение
SFS3		35	3	35	25				5
SFS4		30	4	30	5				12.5
$Н$5		30	0	40	1Е+30				10

Рис. 3.1. Отчет по устойчивости Microsoft Excel

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

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

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

если   (3.10)

если 

если   (3.11)

если 

Условия (3.10) можно интерпретировать так: если оценка у_i, единицы ресурса г-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью; если же ресурс используется не полностью, то его оценка равна нулю.

Из условия (3.11) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках не убыточен; если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

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

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

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

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

Свойство 1. Оценки как мера дефицитности ресурсов и продукции.

Свойство 2. Оценки как мера влияния ограничений на функционал.

Свойство 3. Оценки как инструмент определения эффективности отдельных вариантов.

Свойство 4. Оценки как инструмент балансирования суммарных затрат и результатов.

Пример 3.2 (задача о планировании выпуска тканей). Пусть некоторая фабрика выпускает три вида тканей, причем суточное плановое задание составляет не менее 90 м тканей первого вида, 70 м - второго и 60 м - третьего. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на один метр ткани представлен в табл. 3.2.

Таблица 3.2

Нормы расхода ресурсов

Ресурсы	Ткани
	I	II	III
Оборудование	2	3	4
Сырье	I	4	э
Электроэнергия	3	4	2

Цена за один метр ткани вида I равна 80 денежным единицам, II - 70 денежным единицам, III - 60 денежным единицам.

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

Решение. Составим модель задачи. Введем следующие обозначения. Неизвестными в задаче являются объемы выпуска ткани каждого вида:

x₁ - количество метров ткани вида I;

х₂ - количество метров ткани вида II;

х₃ - количество метров ткани вида III.

С учетом имеющихся данных модель примет вид:

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

 Плановое задание

В результате решения задачи симплексным методом получен следующий оптимальный план: максимум общей стоимости продукции   = 19 075 ден. ед. достигается при

x₁ = 112,5 м - оптимальный объем выпуска ткани вида I;

x₂ = 70 м - оптимальный объем выпуска ткани вида II;

x₃ = 86,25 м - оптимальный объем выпуска ткани вида III.

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

y₁ - двойственная оценка ресурса "оборудование";

y₂ - двойственная оценка ресурса "сырье";

y₃ - двойственная оценка ресурса "электроэнергия";

y₄ - двойственная оценка ткани вида I;

y₅ - двойственная оценка ткани вида II;

y₆ - двойственная оценка ткани вида III.

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

Из соотношений второй теоремы двойственности вытекают следующие условия:

для каждого ресурса:

если  ;

если 

для задания по выпуску продукции:

если  , то  ;

если  , то  . (3.12)

Для нашего примера в этих соотношениях т = 3 (количество типов ресурсов).

Подставим значения x₁ = 112,5, x₂ = 70 и x₃ = 86,25 в ограничения прямой задачи:

Суточные ресурсы по оборудованию и электроэнергии использованы полностью. Сырье используется не полностью, имеется остаток в размере 850 - 823,75 = 26,25 (кг). План выпуска по тканям вида I и III перевыполнен.

Из второй теоремы двойственности вытекает, что y₂, y₄ и y₆ равны нулю. Остается найти значения y₁, y₃ и y₅. Так как x₁, x₂ и x₃ - больше нуля, то все три ограничения двойственной задачи выполняются как равенства:

Учитывая, что   имеем:

откуда  .

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

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

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

Ограничивают целевую функцию дефицитные ресурсы, в данном примере - оборудование и электроэнергия. Они полностью использованы в оптимальном плане. По условию (3.10) оценка таких ресурсов положительна (y₁ = 2,5; y₃ = 25). Рассмотрим теперь понятие дефицитности продукции. По условию (3.12) нулевую оценку (y₄ = 0, y₆ = 0) получает продукция, задания по выпуску которой в оптимальном плане перевыполняются. Очевидно, перевыполнение плана целесообразно по выгодной продукции (ткани I и III видов), т.е. такой, производство которой способствует достижению максимума критерия оптимальности. Размеры производства такой выгодной продукции определяются не величиной задания на выпуск (T_j) (в оптимальном плане они перекрыты), а ограниченностью дефицитных ресурсов. Эту продукцию выпускают как можно больше, пока хватит ресурсов. Выпуск выгодной продукции лимитируется не только фактом ограниченности дефицитных ресурсов, но и тем, что часть дефицитных ресурсов требуется выделить на обеспечение выпуска невыгодной продукции в соответствии с плановыми заданиями. По условию (3.12) отрицательную оценку (y₅ = -37,5) получает продукция, задания, по выпуску которой, не перевыполняются. Так как по условию задачи (X_j > T_j) плановые задания должны быть обязательно выполнены, то продукция делится на выгодную (виды 1 и III ткани) и невыгодную (вид II ткани).

Если в ограничение двойственной задачи, относящееся к виду II ткани,

подставить полученные значения двойственных оценок, то получаем

т.е. стоимость ресурсов, затраченных на один метр ткани вида II, составляет 107,5 денежной единицы, и это на 37,5 денежной единицы больше цены одного метра ткани этого вида. Таким образом, вид II ткани убыточен для фабрики: на каждом выпущенном метре ткани этого вида фабрика теряет 37,5 денежной единицы.

В соответствии с критерием оптимальности плана, в зависимости от того перевыполняется план выпуска или нет, выпуск ткани вида II поглощает часть дефицитных ресурсов, чем сдерживает рост выпуска выгодной продукции, а тем самым и рост целевой функции.

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

Влияние ограничений по выпуску продукции на критерий оптимальности противоположно влиянию ограничений по ресурсам. Если продукция невыгодна (вид II ткани, y₅ = -37,5), то увеличение плановых заданий по ее выпуску ведет к уменьшению выпуска выгодной продукции и ухудшает план. Наоборот, уменьшение плановых заданий по невыгодной продукции позволяет снизить ее выпуск, перебросить сэкономленные ресурсы на дополнительный сверхплановый выпуск выгодных видов продукции, что увеличивает значение целевой функции. Изменение плановых заданий по выгодной продукции не изменяет значения целевой функции.

Перейдем к анализу модели на чувствительность.

Пример 3.3. На основании информации, приведенной в табл. 3.3, составить план производства, максимизирующий объем прибыли.

Таблица 3.3

Ресурсы	Затраты ресурсов на единицу продукции			Наличие ресурсов
	А	А
Труд	2	4	2000
Сырье	4	1	1400
Оборудование	2	1	800
Прибыль на единицу продукции	40	60

Решение. Экономико-математическая модель задачи будет иметь вид:

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

Соответствующий отчет об устойчивости решения представлен на рис. 3.2.

Ячейки переменных
Ячейка	Имя	Окончательное значение	Приведенная стоимость	Целевая функция Коэффициент		Допустимое увеличение	Допустимое уменьшение
$A$2		200	0	40	80			10
$B$2		400	0	60	20			40
Ограничения
Ячейка	Имя	Окончательное значение	Теневая цена	Ограничение Правая сторона	Допустимое увеличение			Допустимое уменьшение
$С$4		2000	13.3333333337	2000	1200			600
$С$5		1200	0	1400	1E+30			200
$С$6		800	6.6666666667	800	85.71428571			300

Рис. 3.2. Отчет об устойчивости

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

1. Увеличение объемов какого вида ресурсов наиболее выгодно?

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

3. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

4. Целесообразность включения в план новых изделий.

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

54. В основной модели будем полагать наличие дефицита. Это означает, что при отсутствии запасаемого продукта, т.е. при J(t) =0 спрос сохраняется с той же интенсивностью r(t) = b, но потребление запаса отсутствует – b(t) = 0, вследствие чего накапливается дефицит со скоростью b. График изменения уровня запаса в этом случае представлен на рис. 3. Убывание графика ниже оси абсцисс в область отрицательных значений в отличие от графика на рис. 13 характеризует накопление дефицита. Рисунок 3 – Уровень запасов в модели управления запасами с дефицитом Каждый период "пилы" Т = n / b разбивается на два временных интервала, т.е. Т = Т1 + T2 , где Т1 – время, в течение которого производится потребление запаса, T2 – время, когда запас отсутствует и накапливается дефицит, который будет перекрыт в момент поступления следующей партии. Необходимость покрытия дефицита приводит к тому, что максимальный уровень запаса s в момент поступления каждой партии меньше на величину дефицита (п – s), накопившегося за времяT2. Из геометрических соображений легко установить, что                                                             (11) В данной модели в функцию суммарных затрат С наряду с затратами С1 (на пополнение запаса) и С2 (на хранение запаса) необходимо ввести затраты С3 – штраф из-за дефицита, т.е. общие издержки равны С = С1 + С2 + С3. Затраты С1, находят по формуле (4). Затраты С2 при линейном расходе запаса равны затратам на хранение среднего запаса, который за время потребления Т1 равен sT1 / 2; поэтому затраты С2 составят                                                                   (12) При расчете затрат С3 считают, что штраф за дефицит составляет в единицу времени с3 на каждую единицу продукта. Средний уровень дефицита за период T2 равен (п – s)T2 / 2, штраф за этот период T2 составит 1\2(c3(n – s)T2 , а за весь период θ:                                                                    ( 13) Суммарные затраты равны                                                                    ( 14) Рассматриваемая задача управления запасами сводится к отысканию такого объема партии n и максимального уровня запаса s, при которых функция С (14) принимает минимальное значение. Другими словами, необходимо исследовать функцию двух переменных С(n, s) на экстремум. Приравнивая частные производные ∂С / ∂n, ∂C / ∂s к нулю, получим после преобразований систему уравнений:                                                ( 15) Величина:                                                                    ( 16) называется плотностью убытков из-за неудовлетворенного спроса и играет важную роль в управлении запасами. Заметим, что 0 < ρ < 1. Если значение с3 мало по сравнению с c2, то величина ρ близка к нулю: когда с3 значительно превосходит с2, то ρ близка к 1. Недопустимость дефицита равносильна предположению, что с3 = ∞ или ρ = 1. Решая систему, получаем формулы наиболее экономичного объема партии  ~n0 и максимального уровня запаса s0 для модели с дефицитом:                                    ( 17)                                              ( 18) Следует учесть, что в силу (16) и (18)     и                             ( 19) Поэтому утверждение о том, что плотность убытков из-за неудовлетворенного спроса равна ρ, означает, что в течение (1 – ρ) 100 % времени от полного периода T запас продукта будет отсутствовать. Из сравнения формул (17) и (18) следует, что оптимальные объемы партий для задач с дефицитом и без дефицита при одинаковых параметрах связаны соотношением                                                                    ( 20) откуда следует, что оптимальный объем партии в задаче с дефицитом всегда больше, чем в задаче без дефицита. Детерминированные методы управления запасами, основанные на вычислении экономического объема заказа обладают существенным недостатком. Этот недостаток связан с ограничениями, накладываемыми самим понятием "детерминированный экономический процесс", а также введением ограничений, связанных с методом вычисления величины экономического объема заказа. 55.  Сущность транспортной задачи линейного программирования    

В различных местах оправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза отправляется из каждого пункта и сколько груза должно поступить в пункт назначения. Причём безразлично, какой именно отправитель будет доставлять груз тому или иному получателю. Требуется так организовать перевозки, чтобы обеспечить минимальный общий пробег груза, т. е. минимизировать затраты на транспортировку. Экономико-мате­ма­тическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.

 

Таблица 2.1