Решение оптимизационных задач средствами EXCEL

 

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

 

1. Сформулируем экономико - математическую  модель задачи.

 

Обозначим через Х₁,  Х₂,  Х₃,  Х₄ количество ковров каждого типа.

 

Целевая функция  - это выражение, которое необходимо максимизировать  f(x) = 3Х₁ +4Х₂ +3Х₃ +Х₄

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

7Х₁ +2Х₂ +2Х₃ +6Х₄ 80

5Х₁ +8Х₂ +4Х₃ +3Х₄ 480

2Х₁ +4Х₂ +Х₃ +8Х₄ 130

Х₁, Х₂, Х₃, Х₄ 0

Решение

1. Указать адреса ячеек, в  которые будет помещен результат  решения (изменяемые ячейки).

 

Обозначьте через Х₁, Х₂, Хз, Х₄ количество ковров каждого типа. В нашей задаче оптимальные значения вектора Х =(Х₁, Х₂, Хз, Х₄) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции в ячейке F4.

2. Ввести исходные данные.

 

)Введем исходные данные в  созданную форму. В результате  получим (Рисунок 14):

 

Рисунок 14. Данные введены.

 

 

3 Введем  зависимость для целевой функции

• Курсор в F4.

• Курсор на кнопку Мастер функций.

На экране диалоговое окно Мастер функций шаг 1 из 2.

• Курсор в окно Категория  на категорию Математические.

 

 

Рисунок 15.  Вводится функция для вычисления целевой функции.

 

• Курсор в окно Функции на СУММПРОИЗВ.                                                             

• В массив 1 ввести³ В$3:E$3.

• В массив 2 ввести В4:E4.

• Готово. На экране: в F4 введена функция, как показано на Рисунке 15.

4. Введем  зависимость для левых частей  ограничений:

• Курсор в F4.

• Копировать в буфер.

• Курсор в F7.

• Вставить из буфера.

• Курсор в F8.

• Вставить из буфера.                   

• Курсор в F9.

• Вставить из буфера.

На этом ввод зависимостей закончен.

 

Запуск Поиска решения.

 

6. Назначение целевой функции (установить целевую ячейку).

• Курсор в поле Установить целевую ячейку.

• Ввести адрес $F$4.
• Ввести  направление целевой функции: Максимальному значению.

         Ввести  адреса искомых переменных:

• Курсор в поле Изменяя ячейки.
• Ввести адреса В$3:E$3.

5. Ввод ограничений.

Курсор в поле  Добавить. Появится диалоговое окно Добавление ограничения (Рисунок 16.).

 

 

Рисунок 16. Ввод правых и левых  частей ограничений.

 

· В окне Ссылка на ячейку ввести $F$7.

· Ввести знак ограничение  £..

· Курсор в правое окно.

·Вести $H$7.

· Добавить. На экране опять диалоговое окно Добавление ограничения. Ввести остальные ограничения.

· После ввода последнего ограничения ввести ОК.

 

На  экране появится диалоговое окно Поиск решения с введенными условиями (Рисунок 17).

 

 

 

Рисунок 17. Введены все условия для решения задачи.

 

8) Ввод параметров для  решения ЗЛП (Рисунок 18).

• Открыть окно Параметры поиска решения.
• Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.
• Установить флажок Неотрицательные значения.
• ОК (На экране диалоговое окно поиска решения).
• Выполнить (На экране диалоговое окно результаты поиска решения – Рисунок 19.).

 

Рисунок 18. Ввод параметров.

Рисунок 19. Решение найдено.

Полученное решение означает, что максимальный доход 150 тыс.  руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи  (ресурс сырье) будет использовано 280 кг.

Создание  отчета по результатам поиска решения

Excel позволяет представить результаты  поиска решения в форме отчёта. Существует три типа таких отчетов:                                  

• Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях
• Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках иди в формулах ограничений.                                  
• Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние   границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.

1. Отчет по результатам.

 

Отчет по результатам
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходно	Результат
	$F$4	коэф. в ЦФ ЦФ	0	150
Изменяемые ячейки
	Ячейка	Имя	Исходно	Результат
	$B$3	значение Х1	0	0
	$C$3	значение Х2	0	30
	$D$3	значение Х3	0	10
	$E$3	значение Х4	0	0
Ограничения
	Ячейка	Имя	Значение	Формула
	$F$7	труд левая часть	80	$F$7<=$H$7
	$F$8	сырье левая часть	280	$F$8<=$H$8
	$F$9	оборудование левая часть	130	$F$9<=$H$9

 

В отчете по результатам содержатся  оптимальные значения переменных Х₁, Х₂, Х₃, Х₄   , которые соответственно равны 0,10, 30,0;  значение целевой функции – 150,    а также левые части ограничений.

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

 

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

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

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

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

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

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

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

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

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

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

Модель исходной (прямой) задачи в  общем виде может быть записана следующим  образом:

 

                

                         

 

 

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

 

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

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

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

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

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

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

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

 

Экономический смысл первой теоремы двойственности следующий. План производства Х и  набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции  равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y_i. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:

f(X) < g(Y}, т. е.  ценность всей выпущенной продукции  не превосходит суммарной оценки  имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

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

 

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

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

Пусть X=(x₁,x₂,...x_n) - допустимое решение прямой задачи, а Y= (y₁,y₂,...y_m) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

      *

                        **

 

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

Из  второй теоремы двойственности в  данном случае следуют такие требования на оптимальную производственную программу X=(X₁,X₂,...,X_n) и оптимальный вектор оценок Y=(Y₁,Y₂,...,Y_m):

  (4)

  (5)

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

 

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

Теорема об оценках.

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

         

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

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

Пример. Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

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

f(x) = 3Х₁ +4Х₂ +3Х₃ +1Х₄

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

7Х₁ +2Х₂ +2Х₃ +6Х₄ 80

5Х₁ +8Х₂ +4Х₃ +3Х₄ 480

2Х₁ +4Х₂ +Х₃ +8Х₄ 130

Х₁, Х₂, Х₃, Х₄ 0

 

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

Y₁ – двойственная оценка ресурса труд, или «цена» труда;

Y₂ – двойственная оценка ресурса сырье, или «цена» сырья;

 

Y₃ – двойственная оценка ресурса оборудование, или «цена» оборудования.

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

g   = 80 ´Y₁ + 480´Y₂ + 130´Y₃  ® min

Необходимо  найти такие “цены” на ресурсы (Y_i), чтобы общая стоимость используемых ресурсов была минимальной.