Двойственность и двойственные оценки при оптимальном планировании

Содержание

 

 

Введение

 

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

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

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

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

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

 

 

 

Глава I  . Двойственность и двойственные оценки при оптимальном планировании

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

 

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Cj минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции xj(j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях Cj (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов bi(i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.

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

F=c1x1+c2x2+…cnxn

при условиях

 

   

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

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

2. Матрица

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

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

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

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

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cj функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве bi (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aij ед. t-гo ресурса, ее стоимость составляет Cj ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

Z=C1x1+C2x2+… +Cnxn

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

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

 

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

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

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

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

Сформулируем двойственную задачу. Необходимо определить матрицу-строку Y=(y1, y2,…, ym), которая максимизирует линейную функцию f=YB и удовлетворяет ограничениям

YiAi>Сi (1.1)

Сформулируем исходную задачу. Определить матрицу-столбец X=(x1, x2,…, xn), которая минимизирует линейную функцию Z=СХ и. удовлетворяет ограничениям

AjXj=Bj,

Хj>0 (1.2)

Как в исходной так и в двойственной задачах А=(aij) – матрица коэффициентов системы ограничений, A0=(b1, b2,…, bm) – матрица-столбец, C=(c1, c2,…, cn) – матрица-строка. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач.

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

Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Тогда получаем, что Z(X)+Y. Это выражение также лишено смысла, поэтому исходная задача не имеет решений.

 

1.3 Виды математических моделей  двойственных задач

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

• Симметричные задачи

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

 

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

                                     

• Несимметричные задачи

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

Zmin=CX;                                          fmax=Y Bi;

AiXi=Bi;                                            YJAJ=СJ

X>0

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

Zmax=CX;                                           fmin=Y Bi;

AiXi=Bi;                                             YJAJ=СJ

Xi>0

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

1.4 Двойственный симплексный метод

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

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

bi являются оценками плана двойственной задачи. Сj являются оценками плана исходной задачи.

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

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

Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A0, Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA0 при YA>С. Пусть определен следующий базис D=(A1, А2,…, Аi,…, Аm), причем в нем хотя бы одна из компонент вектора Х=D-1A0=(x1, x2,…, xi,…, xm) отрицательная. Для всех векторов Aj используется следующее соотношение Zj–Cj >0 (i=1,2,…, n).

Пользуясь теоремой двойственности, Y=СбазD-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.

Поэтому, следует исключить из базиса исходной задачи вектор Аi, который соответствует компоненте xi<0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.

Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет xij<0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.

В противном случае для столбцов, имеющих отрицательные значения, определяем q0j=min(xi/xij)>0. Также находим вектор, который соответствует minq0j(Zj–Cj) при решении исходной задачи на максимум, а также maxq0j(Zj–Cj) при значении исходной задачи на минимум.

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

Допустим, что q0j=min(xi/xij)=0, т.е. xi=0, тогда xij выбирается как разрешающий элемент, но лишь тогда, когда xij>0.

Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается.

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

Используя при решении, алгоритм двойственного симплексного метода условие Zj–Cj>0 допускается не учитывать, пока не будут исключены все хi<0.

Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все хi<0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q0j=max(xi/xij)>0.

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

 

 

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

Для проведения содержательной интерпретации двойственной задачи (II) свяжем переменные двойственной задачи

Пусть L* - максимальное значение дохода в задаче (I). Если запасы ресурсов , i=1,...,m изменить, то может измениться и максимальный доход L*. Это означает, что L* является функцией от ресурсов , i=1,...,m, т.е.

Рассмотрим отношение приращения дохода  к приращению i-го ресурса       ;  

 Тогда по определению частной  производной функции 

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

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

Пусть L*- максимальное значение дохода в задаче (I),

Тогда, изменяя i-й ресурс на единицу, получим новое значение максимального дохода по формуле

или более общий вид

    

Двойственные переменные

называются оценками (теневыми ценами, ценностями) соответствующих ресурсов i=1,..., m, и характеризуют меру эффективности использования соответствующих ресурсов.

1.6 Экономическая интерпретация ограничений двойственной задачи.

Рассмотрим j-е ограничение задачи (II)   

Вектор   является j-м столбцом матрицы А и характеризует технологический процесс производства j-й продукции, а именно,  - это количество i-го ресурса i=1,..., m, необходимого для производства единицы j-й продукции.  Поскольку     - оценка единицы i-го ресурса, i=1,..., m, то сумма

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

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

производство j-й продукции убыточно.

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

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

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

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

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

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

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

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

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

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

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

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

 

Глава II  Практическая часть

2.1 Словесная модель задачи

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

Тип сырья	Нормы сырья на одно изделие			Запасы ресурсов
	I	II	III
Труд	3	6	4	2000
Сырье 1	20	15	20	15000
Сырье 2	10	15	20	7400
Оборудование	0	3	5	1500
Цена	6	10	9

Требуется

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

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

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

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

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

Определить, как изменятся выручка и план выпуска продукции  при увеличении запасов сырья  I вида на 24

Оценить целесообразность включения в план изделия 4-го вида ценой 11 ед., на изготовление которого расходуется по 8, 4, 20 и 6 единиц сырья соответственно.

 

 

2.2 Математическая модель задачи

Составим экономико-математическую модель задачи. Для этого введем переменные:

Пусть

- количество выпущенной продукции  I вида

- продукции II вида

- продукции III вида.

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

F=

Составим систему ограничений по запасу ресурсов:

2.3 Решение  прямой задачи симплексным  методом

 

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

 

Преобразуем математическую модель к каноническому виду:

Введем дополнительные переменные :

Применим симплекс-метод:

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

:

Б0(0,0,0,2400,15000,1500) FБ0=0

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

Возьмём x2 в качестве базисной переменной

     

Выразим x2 из 1-го уравнения, тогда  x4 выходит из базиса

Итак,

Б1(0;333,33;0;0;10000;2400;500) FБ0=-10000/3

Из целевой функции  видно, что её наибольшее уменьшение будет если x3 будет уменьшаться

Возьмём x3 в качестве базисной переменной

Выразим из 4-го уравнения , тогда выходит из базиса

         Б2(0;     FБ2=-33500/9

Из целевой функции  видно, что её наибольшее уменьшение будет если x1 будет уменьшаться

Возьмём x1 в качестве базисной переменной

Выразим из 3-го уравнения , тогда выходит из базиса

 Б3(     FБ3=-106220/27

Из целевой функции  видно, что её наибольшее уменьшение будет если x7 будет уменьшаться

Возьмём x7 в качестве базисной переменной

Выразим из 1-го уравнения, тогда выходит из базиса

Итак, Б4(520;0;110;0;2400;0,950) FБ4=4110

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

Возвращаясь к исходному условию задачи, получим:

Оптимальное решение:

2.4 Решение задачи средствами MS Excel

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

1. Введем все необходимые данные в таблицу:

 

2. Решение: пропишем все необходимые формулы для подсчета:

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

4. Получим результаты:

 

 

 

2.5 Двойственная задача. Решение двойственной задачи

 

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

Имеем

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

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

Z=2000y1+15000y2+7400y3+1500y4 => min

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

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

y4 ≥ 0

Подставим  ; ;      в ограничение задачи

Из второй теоремы двойственности   (т.к в 2-ой и 4-ой строках не выполняется строгого равенстра «<»);

т.к >0; и >0, то ограничения запишем как равенства; 
Итак

       

т.к =0 ,и то ( ) будет иметь вид :

 

Решая её, получим 

 Подставим найденные значения  в целевую функцию двойственной задачи.

Проверим выполняется ли условие F( )=G( )

Итак, Fmax=Zmin, значит это условие выполняется,

 Подставим оптимальное решение Y(1.5;0;3/20;0) в систему ограничений

 Так как Y2=0 и Y4=0 рассмотрим 1-е и 3-е уравнение первоначальной системы. Во втором ограничении равенство не выполняется, значит Х2 =0

Откуда

Итак, max функции (т.е max общей стоимости выпускаемой продукции) равен 4110 при выпуске:

520 единиц продукции 1-го вида

0 единиц продукции 2-го вида

110 единиц продукции 3-го вида

Ответ: Максимум прибыли от общей стоимости выпускаемой продукции составляет 4110 д.ед., при 520 единицах продукции 1-го вида и 110 единицах продукции 3-го вида

 

 

Глава III Аналитическая часть

3.1 Анализ использования ресурсов в оптимальном плане

 

В оптимальном плане прямой задачи имеем х2=0, потому что затраты на выпуск этого изделия превышает их цену на 1,25 единиц.

сырьё №1 и №3 полностью используются в оптимальном плане и являются дефицитным, т.е. сдерживающим рост целевой функции.  Сырье №2 используется не полностью, поэтому имеет нулевую двойственную оценку и не влияет на план выпуска продукции.

По двойственным оценкам сделаем вывод, что сырьё №2 недефицитно, остро дефицитный ресурс №1, т.к. у1=1,5, и менее дефицитный ресурс №3, т.к. у3=0,15

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

Z=2024*1,5+7400*3/20=4146(ден.ед) Т.е прибыль  увеличится на 46 единиц, поэтому  этот проект будет выгодным.

Решим новую задачу средствами Ms Excel, получили что прибыль составит 4146ден.ед, т.е. увеличится на 46 единиц, поэтому этот проект будет выгодным.

Рассмотрим эффективность включения в план изделия IV –го вида с ценой 11 ед, и затратами 8,4,20 и 6 ед каждого ресурса

8*у1+4у2+20у3+6у4-11=8*1,5+0+20*0,15+0-11=4 получили, что данный проект невыгодный.

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

 Отчет по устойчивости

В отчете по результатам отображается решение двойственной задачи в столбце «Теневая цена». Как мы видим из данного отчета решение двойственной задачи составляет у1=1,5;у2=0,15, что совпадает с нашим решением, полученным с помощью двойственных оценок.