Ненулевые параметры управления оптимального решения двойственной. Симплекс-метод решения злп

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

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

Прямая задача .
Максимизировать функцию

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

Двойственная задача .
Минимизировать функцию

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

Эти задачи обладают следующими свойствами:

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

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

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

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

1. Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла(то есть с одним и тем же знаком): если в исходной задаче ищется максимум функции цели (линейной формы) - они записываются со знаком "меньше или равно", если же минимум - со знаком "больше или равно". Для этого неравенства, в которых это требование не выполняется, умножают на минус единицу.
2. Выписывают матрицу A коэффициентов при переменных исходной задачи, полученых после преобразований, описанных в предыдущем пункте, и составляют матрицу A ", транспонированную относительно матрицы A .
3. Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы A ", а в качестве свободных членов - коэффициенты при переменных в функци цели исходной задачи и записывают неравенства противоположного смысла (то есть меняют знак) по сравнению с неравенствами, полученными в пункте 1.
4. Составляют функцию цели (линейную форму) двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в пункте 1.
5. Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум функции цели, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум.
6. Записывают условие неотрицательности переменных двойственной задачи.

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

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

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

,

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

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

1. Свободные члены в прямой задаче - коэффициенты функции цели в двойственной задаче.
2. Коэффициенты функции цели в прямой задаче - свободные члены в двойственной задаче.
3. Расширенная матрица в прямой задаче - транспонированная расширенная матрица в двойственной задаче.
4. j -й неизвестный в прямой задаче неотрицательный - j -е неравенство в двойственной задаче со знаком "больше или равно".
5. j -й неизвестный в прямой задаче без ограничения знака - j -е ограничение в двойственной задаче в виде уравнения.
6. j -й неизвестный в прямой задаче неположительный - j -е неравенство в двойственной задаче со знаком "меньше или равно".
7. i -е неравенство в прямой задаче со знаком "меньше или равно" - i -е неизвестный в двойственной задаче неотрицательный.
8. i -е ограничение в прямой задаче в виде уравнения - i -й неизвестный в двойственной задаче без ограничения знака.
9. i -е неравенство в прямой задаче со знаком "больше или равно" - i -й неизвестный в двойственной задаче неположительный.

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

Решение. Как видим, прямая задача записана в общей форме. Это будем учитывать при расстановке знаков в условиях двойственной задачи. А пока, как и в предыдущем примере, произведём универсальное действие - составим матрицу B прямой задачи и транспонированную матрицу B " двойственной задачи:

,

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

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

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

Теорема 1. Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. F max = Z min или F min = Z max . 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.

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

При решении симплекс-методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести m добавочных неотрицательных переменных (по числу неравенств в системе ограничений) x n+1 , x n+2 , ..., x n+i , ..., x n+m , где i = 1, 2, ..., m означает номер неравенства, в которое была введена добавочная переменная x n+i .

Система ограничений двойственной задачи состоит из n неравенств, содержащих m переменных. Если решать эту задачу симплекс-методом, то следует ввести n добавочных неотрицательных переменных y m+1 , y m+2 , ..., y m+j , ..., y m+n , где j = 1, 2, ..., n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная y m+j .

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

x 1 ↔ y m+1

x 2 ↔ y m+2

x j ↔ y m+j

x n ↔ y m+n

x n+1 ↔ y 1

x n+2 ↔ y 2

x n+i ↔ y i

x n+m ↔ y m

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

Иными словами, каждой первоначальной переменной исходной задачи x j (j = 1, 2, ..., n ) ставится в соответствие добавочная переменная y m+j , введённая в j -е неравенство двойственной задачи, а каждой добавочной переменной x n+i исходной задачи (i = 1, 2, ..., m ), введённой в i -е неравенство исходной задачи, - первоначальная переменная y i двойственной задачи.

Всё вышесказанное, как уже было отмечено, станет более понятным из примера 2, который будет вскоре после Теоремы 2.

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

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

Пример 3. На основании решений прямой и двойственной задач линейного программирования из примера 1 убедиться в справедливости теорем 1 и 2.

В примере 1 была дана исходная задача: найти максимум функции при ограничениях

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

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

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

а максимум целевой функции F max = 13 ,

Система ограничений двойственной задачи сводится к системе уравнений путём введения добавочных переменных y 5 , y 6 :

Решение двойственной задачи симплекс-методом даёт следующий ответ:

а минимум целевой функции Z min = 13 ,

при этом сама целевая функция выражается как

Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причём Z min = F max = 13 .

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

x 1 ↔ y 5

x 2 ↔ y 6

x 3 ↔ y 1

x 4 ↔ y 2

x 5 ↔ y 3

x 6 ↔ y 4

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

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

Рассматривая коэффициенты при переменных y j в этой функции цели и учитывая их соответствие коэффициентам при переменных x i , получим решение (4; 1; 0; 5; 4; 0) , совпадающее с решением прямой задачи.

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

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

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

Пример 1.

Составить двойственную задачу

1. Приводим все неравенства системы ограничений исходной задачи к одному смыслу

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

3. Транспонируем матрицу

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

Исходная (прямая) задача	Двойственная задача

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

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

Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство f < z можно интерпретировать следующим образом:

Доход < Общая стоимость ресурсов

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

Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия о дополняющей нежесткости.

1. Если суммарная оценка i-го ресурса положительна

то этот ресурс в соответствии с оптимальным планом х* используется полностью

2. Если i-й ресурс используется не полностью

то его оптимальная оценка нулевая и i-е ограничение несущественно.

3. Если в соответствии с оптимальным планом х* j-я продукция производится

то это производство эффективно, так как цена единицы j-й продукции

равна затратам на ее производство в единицах

4. Если производство j-й продукции убыточно (приведенные издержки ненулевые

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

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

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

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

Прямая:

F(x)=c 1 x 1 + c 2 x 2 +…+ c n x n →max

a 11 x 1 + a 12 x 1 +…+ a 1n x n ≤b 1 ,

a 21 x 1 + a 22 x 1 +…+ a 2n x n ≤b 2 ,

………………………………

a k1 x 1 + a k2 x 1 +…+ a kn x n ≤b k ,

a k+1,1 x 1 + a k+1,2 x 1 +…+ a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 + a m2 x 1 +…+ a mn x n= b m ,

Двойственная:

F*(Y)=b 1 y 1 + b 2 y 2 +…+ b m y m →min

a 11 y 1 + a 21 y 2 +…+ a m1 y m ≥c 1 ,

a 12 y 1 + a 22 y 2 +…+ a m2 y m ≥c 2 ,

………………………………

a 1l y 1 + a 2l y 1 +…+ a ml y m ≤c l ,

a 1,l+1 y 1 + a 2,l+1 y 2 +…+ a m,l+1 y m =c l+1 ,

………………………………

a 1n y 1 + a 2n y 1 +…+ a mn y m= c m ,

Двойственная задача по отношению к исходной составляется согласно правилам:

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

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

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

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

5. Если переменная хj исходной задачи может принимать только лишь положительные значения, то j- e условие в системе ограничений двойственной задачи является неравенством вида "≥ ". Если же переменная хj может принимать и отрицательные значения, то j -e соотношение в двойственной задаче будет равенством. Если i -e соотношение в исходной задаче является неравенством, то і- я переменная двойственной задачи yi≥0. В противном случае yi может принимать как положительные, так и отрицательные значения.

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

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

Если основная задача линейного программирования имеет оптимальный план Х*, то Y*= C δ . является оптимальным планом двойственной задачи. Здесь C δ - вектор-строка коэффициентов целевой функции при базисных переменных оптимальной симплекс-таблицы прямой задачи, а - матрица обратная матрице, составленной из компонентов векторов, входящих в последний базис, при котором получен оптимальный план. Если прямая задача приведена к единичному базису при неотрицательных свободных членах уравнений, вычисление обратной матрицы не требуется, так как будет состоять из столбцов оптимальной симлекс-таблицы, полученных на месте единичных столбцов исходной таблицы.

Пример 1.

Задана прямая задача:

х 1 , х 2 ≥0

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

Решение:

Прежде всего третье ограничение умножим на "-1", так как оно имеет знак «≥». Это ограничение примет вид

-5х 1 +3х 2 -6х 3 ≤-19

Матрица из коэффициентов при неизвестных в ограничениях будет:

Запишем транспонированную к ней матрицу:

Тогда двойственная задача запишется:

у 1 , у 3 ≥0

Так как в прямой задаче второе ограничение имеет знак "=", то переменная y 2 не имеет ограничения на знак. Третье ограничение двойственной задачи имеет знак "=" так как переменная х 3 не имеет ограничения на знак.

Пример 2.

Прямая задача

х 1 , х 4 ≥0

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

	Баз. вект	С баз	А 0
	А 1	А 2	А 3	А 4	А 5
	А 3				-1
←	А 5						-1
		∆		-1	-5		-3

	Баз. вект	С баз	А 0
	А 1	А 2	А 3	А 4	А 5
←	А 3		14/3	10/3			8/3	1/3
	А 2		5/3	1/3			-1/3	1/3
		∆	34/3	5/3			-14/3	5/3

Баз. вект	С баз	А 0
А 1	А 2	А 3	А 4	А 5
А 4		7/4	5/4		3/8		1/8
А 2		9/4	3/4		1/8		3/8
	∆	78/4	15/2		7/4		9/4

Из последней таблицы получим оптимальный план:

Х опт =(0, 9/4, 0, 7/4);

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

Вектор С опт =(С 4 , С 2)=(6,4) . Матрица Ах состоит из векторов А 4 А 2 , взятых из ограничений по которым составляется двойственная задача:

А х =(А 4 А 2)=

Обратная матрица будет:

Тогда:

F min =

Примечание: Так как исходная задача приведена к единичному базису при неотрицательных свободных членах уравнений, то обратная матрица Ах -1 состоит из компонентов векторов А 3 и А 5 последней симплекс- таблицы.

3. Варианты заданий

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

1)	F=x 1 +x 2 →max		2)	F=3x 1 +x 2 →min
3)	F=3x 1 +3x 2 →min		4)	F=6x 1 -5x 2 →max
5)	F=8x 1 +2x 2 →max		6)	F=x 1 +2x 2 →max
7)	F=14x 1 +10x 2 +14x 3 +14x 4 →max		8)	F=2x 1 +3x 2 →min

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

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

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

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

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

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

Запишем задачу ЛП в стандартной форме:

,

,

i=1,..,m; j=1,..,n.

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

,

i=1,..,m; j=1,..,n.

Проанализировав задачи, можно сделать следующие выводы:

1. Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2. Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

4. Вид экстремума двойственной задачи противоположен виду экстремума прямой задачи;

5. Векторы В и С в прямой и двойственной задачах меняются местами;

6. Матрица A двойственной задачи получается путем транспонирования матрицы А прямой задачи;

7. Все ограничения двойственной задачи имеют вид для задачи максимизации и вид для задачи минимизации линейной формы.

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

Для случая несимметричной задачи:

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

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

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

Пример Дана задача линейного программирования (слева от каждого ограничения стоит ассоциированная с ним двойственная переменная). Данная задача относится к несимметричной.

,

Сформулируем для этой задачи двойственную задачу. Целевая функция двойственной задачи представляет собой линейную форму, полученную как произведение вектора b=(10,20,60,80) на вектор переменных двойственной задачи Y =(). Кроме того, поскольку в прямой задаче целевая функция максимизируется, в двойственной она минимизируется. С учетом сделанных замечаний получим,

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

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

Рассуждая аналогично, получим второе ограничение двойственной задачи: . Отсутствие переменной в этом ограничении связано с тем обстоятельством, что во втором ограничении прямой задачи нет переменной .

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

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

Пример Дана задача линейного программирования в нестандартной форме

,

,

,

Не ограничена в знаке, .

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

,

.

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

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

,

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

.

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

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

Рассмотрим смешанную задачу.

Двойственная для нее задача будет иметь вид:

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

Каноническая форма задачи имеет вид:

Двойственная задача будет иметь вид:

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

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

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

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

.

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

Пример Решим симметричную задачу. Пусть исходная задача имеет вид

Решив задачу графическим методом, получим

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

Так целевые функции в точке оптимума равны, то

Так как переменные
, то соответствующие им ограничения в двойственной задаче содержат знак равенства. Данные ограничения имеют вид

Подставим в ограничения значения . Получим

.

В данной системе только первое неравенство является строгим. Следовательно, . Другие значения переменных найдем из системы уравнений

.

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

Решим ту же задачу, однако считая, что известно решение

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

.

Решая данную систему уравнений, получим

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

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

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

То двойственные переменные показывают, как изменится целевая функция при изменении ресурса на единицу

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

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

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

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

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

,

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

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

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

или
.

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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