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

Постановка задачи

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

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

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

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

Функция цели
maxF(x)=c×x

Ограничения
A×x≤b

Численные значения переменных:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1

Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.

Листинг решения прямой задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # загрузка библиотеки ЛП c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели b_ub = # список объёмов ресурсов A_ub = [, # матрица удельных значений ресурсов , , ] d=linprog(c, A_ub, b_ub) # поиск решения for key,val in d.items(): print(key,val) # вывод решения if key=="x": q=#использованные ресурсы print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов print("b_ub-A_ub*x", q1)

Выводы

1. Найден оптимальный план по видам продукции
2. Найдено фактическое использование ресурсов
3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
4. Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

Решение двойственной задачи о оптимальной производственной программе

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

C – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.

Функция цели
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Численные значения и соотношения для переменных:
с = ; A_ub_T transpose(A_ub); b_ub = .

Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.

Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Листинг решения двойственной задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,-40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Выводы

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

1. Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
2. Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
3. Прямая задача является задачей максимизации, а двойственная - задачей минимизации, и наоборот.
4. Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
5. Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
6. Знаки неравенств в ограничениях меняются на противоположные.
7. Матрица системы равенств транспонируется.

Лекция 6 . Теоремы двойственности. Двойственные оценки и их смысл.

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

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

Достаточный признак оптимальности.

Если и
– допус­тимые решения взаимно двойственных задач, для которых выполня­ется равенство

,

то
– оптимальное решение исходной задачи I, а – двойст­венной задачи II.

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

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

или
.

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

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

Экономический смысл первой теоремы двойственно­сти.

План производства
и набор цен (оценок) ресурсов
оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах
, равна затратам на ресурсы по "внутренним " (определяемым только из решения зада­чи) ценам
. Для всех же других планов Х и Y обеих задач прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

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

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

Пусть даны две взаимно двойственные задачи. Если каждую из этих задач решать сим­плексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I (в краткой записи
) следует ввести т неотрица­тельных переменных , а в систему ограничений задачи II (
) – n неотрицательных переменных , где
– номер неравенства, в которое введена дополнительная переменная
.

Системы ограничений каждой из взаимно двойственных задач примут вид:

.

Установим соответствие между первоначальными переменны­ми одной из двойственных задач и дополнительными перемен­ными другой задачи (таблица).

Теорема. Положительным (ненулевым) компонентам оптимально­го решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых
u
: если
, то
; если
, то
, и аналогично,

если
, то
; если
, то
.

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

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

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

4.5. Объективно обусловленные оценки и их смысл

Компоненты оптимального решения двойственной задачи называ­ются оптимальными (двойственными) оценками исходной задачи. Академик Л.В.Канторович назвал их объективно обусловленным» оценкам (в литературе их еще называют скрытыми доходами).

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

Таким образом, объективно обусловленные оценки ресурсов оп­ределяют степень дефицитности ресурсов: по оптимальному пла­ну производства дефицитные (т.е. полностью используемые) ре­сурсы получают ненулевые оценки, а недефицитные – нулевые оценки. Величина является оценкой -го ресурса. Чем больше значение оценки , тем выше дефицитность ресурса. Для недефицитного ресурса
.

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

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

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

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

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

Показателем дефицитности ресурсов и продукции.

Показателем влияния ограничений на значение целевой функции.

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

Инструментом сопоставления суммарных условных затрат и результатов.

С помощью данного онлайн-калькулятора можно получить:

• решение двойственной задачи линейного программирования через решений прямой задачи (симплексным методом, по теореме двойственности);
• оптимальный план двойственной задачи; оценки ресурсов (двойственные оценки);
• определение дефицитных и недефицитных (избыточных) ресурсов;
• изменение целевой функции при изменении параметров; обоснование эффективности оптимального плана;
• анализ устойчивости двойственных оценок (предельное изменение b i , c i); анализ субоптимальных вариантов плана.

Инструкция . Выберите количество переменных и количество ограничений прямой задачи линейного программирования, нажмите Далее. Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x i ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных x i неопределена, то можно использовать этот калькулятор .

Основная идея теории двойственности : для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с прямой. При этом:

• матрица ограничений двойственной задачи (ДЗ) есть транспонированная матрица прямой задачи;
• вектор "цен" для прямой задачи есть вектор правых частей ограничений задачи ДЗ и наоборот.

Пример . Определим максимальное значение целевой функции F(X) = 3x 1 +5x 2 +4x 3 при следующих условиях-ограничений.
0.1x 1 + 0.2x 2 + 0.4x 3 ≤1100
0.05x 1 + 0.02x 2 + 0.02x 3 ≤120
3x 1 + x 2 + 2x 3 ≤8000

Решим прямую задачу симплексным методом.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
0.1x 1 + 0.2x 2 + 0.4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0.05x 1 + 0.02x 2 + 0.02x 3 + 0x 4 + 1x 5 + 0x 6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,1100,120,8000)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.

Пример №2 . Для выполнения задания необходимо, чтобы одновременно взлетели 50 АК I-го вида, 30 АК 2-го вида и 45 АК 3-го вида. АК расположены на аэродромах I и II. В таблице представлено среднее время взлета (в секундах) с соответствующего аэродрома одного АК данного типа.

Решение. Обозначим через:
x 11 - АК 1-го типа на первом аэродроме,
x 12 - АК 1-го типа на втором аэродроме,
x 21 - АК 2-го типа на первом аэродроме,
x 22 - АК 2-го типа на втором аэродроме,
x 31 - АК 3-го типа на первом аэродроме,
x 32 - АК 3-го типа на втором аэродроме,

Ограничения
4x 11 + 6x 12 = 50
10x 21 + 8x 22 = 30
10x 31 + 20x 32 = 45
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 ≥ 0
x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 -целые числа

Целевая функция
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → min

После найденного решения, ответом на первый вопрос будут значения переменных x 11 , x 12 , x 21 , x 22 , x 31 ,x 32 . Информация об ответе на второй вопрос будет расположена в разделе Интервалы устойчивости коэффициентов целевой функции.

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

при условиях

(33)

(34)

Определение 1. Задача, состоящая в нахождении минимального значения функции

при условиях

(36)

(37)

называется двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум.

2. Матрица

(38)

составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица

(39)

в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче (35) – (37) равно числу ограничений в системе (33) исходной задачи (32) – (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи.

5. Если переменная x j исходной задачи (32) – (34) может принимать только лишь положительные значения, то j –е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “? ”. Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i –я переменная двойственной задачи . В противном случае переменная у j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Пример 1. Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

(40)

при условиях

(41)

Решение. Для данной задачи

и

Число переменных в двойственной задаче равно числу уравнений в системе (41), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (41), т.е. числа 12, 24, 18.

Целевая функция исходной задачи (40) – (42) исследуется на максимум, а система условий (41) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (40) – (42) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “? ”. Следовательно, для задачи (40) – (42) двойственная задача такова: найти минимум функции при условиях

Пример 2. Для задачи, состоящей в максимизации функции

при условиях

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

Решение. Для данной задачи

,

В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: найти минимум функции при условиях

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

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

при условиях

(44)

Двойственная задача: найти минимум функции

при условиях

(47)

Каждая из задач двойственной пары (43) – (45) и (46), (47) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении оптимального плана одной из задач тем самым находится решение и другой задачи.

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

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

Лемма 2. Если для некоторых планов X * и Y * задач (43) – (45) и (46), (47), то X * – оптимальный план исходной задачи, а Y * – оптимальный план двойственной задачи.

Теорема 8 (первая теорема двойственности). Если одна из задач двойственной пары (43) – (45) или (46), (47) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

Если же целевая функция одной задачи из двойственной пары неограничена (для исходной (43) – (45) – сверху, для двойственной (46), (47) – снизу), то другая задача вообще не имеет планов.

Теорема 9 (вторая теорема двойственности). План задачи (43) – (45) и план задачи (46), (47) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

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

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

Пример 3.

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

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

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

Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х * = (2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y * =(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.

Из рис . 7 видно, что при всяком плане исходной задачи значение целевой функции не больше 46. Одновременно, как видно из рис . 8, значение целевой функции двойственной задачи при любом ее плане не меньше 46. Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при ее произвольном плане.

Пример 4.

Найти решение двойственной пары задач.

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

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

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

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

Нахождение решения двойственных задач. Рассмотрим пару двойственных задач – основную задачу линейного программирования (43) – (45) и двойственную к ней задачу (46), (47).

Предположим, что с помощью симплексного метода найден оптимальный план X * задачи (43) – (45) и этот план определяется базисом, образованным .

Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (43) задачи (43) – (45), а через – матрицу, обратную матрице Р , составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.

Теорема 10. Если основная задача линейного программирования имеет оптимальный план X * , то является оптимальным планом двойственной задачи.

Таким образом, если найти симплексным методом оптимальный план задачи (43) – (45), то, используя последнюю симплекс–таблицу , можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (46), (47).

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

Сказанное выше имеет место и для симметричной пары двойственных задач. При этом так как система ограничений исходной задачи содержит неравенства вида “ ”, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m +1)–й строки последней симплекс–таблицы решения исходной задачи. Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.

Пример 15. Для задачи, состоящей в определении максимального значения функции при условиях

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

Решение. Двойственная задача по отношению к исходной состоит в нахождении минимума функции при условиях

Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Оно приведено в таблице 12. Из последней симплекс-таблицы видно, что двойственная задача имеет решение

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

Таблица 12

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

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

Пример 6. Для производства трех видов изделий А , В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице 13.

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

Таблица 13

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

(52)

Как видно, задачи (48) – (50) и (51) – (53) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A , В и С , а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (48) – (50) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.

Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно, что оптимальным решением двойственной задачи является

Таблица 14

Переменные и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75= 1345,75 руб. При этом числа, стоящие в столбце вектора таблицы 14, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.

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

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

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

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

Так как есть три единичных вектора, то
можно сразу записать опорный план
Х=(0,0,0,360,192,180).
Составим нулевую симплекс-таблицу

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

23.

24.

25.

26.

27.

28.

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

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

31.

32.

33. Решение симметричных двойственных задач

34. Экономическое содержание первой теоремы двойственности

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

36.

37.

38.

39. Пример.

40.

41.

42. Рассмотрим последнюю таблицу исходной задачи

43.