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

 
 

Кафедра сертификации и менеджмента 
 
 
 
 

«Решение  оптимизационных  задач линейного  программирования в  среде EXCEL». 
 
 
 

                                                                             Выполнила: студент

              группы УК-52-07

                                  Проверил: С. В.И.  
 
 
 
 
 
 
 
 
 

2010

      Условие задачи:

Мебельная фабрика  производит комоды и шкафы. Цена одного изделия: шкаф – 8000 руб., комод – 6000 руб. Расход ресурсов на производство одного изделия  и общее количество имеющихся ресурсов приведены в табл.

 

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

Экономико-математическая модель задачи.

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

      Обозначим через х1, х2, вид выпускаемой продукции.

Целевая функция – это выражение, которое необходимо максимизировать:

f (Х)=8000х1++6000х2→max

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

0,1х1+0,2х2≤40

0,3х1+0,1х2≤45

1, 5х1+1,2х2≤360

х1, х2,≥0

Решение.

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

   Обозначаем  через х1, х2 вид выпускаемой продукции. В моей задаче оптимальные значения вектора Х= (х1, х2), будут помещены в ячейках А2:В2, оптимальные значения целевой функции – в ячейке С3.

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

Рис.1. Ввод искомых данных.

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

• Помещаем курсор в ячейку «С3», произойдет выделение ячейки.
• Помещаем курсор на кнопку Мастер функций, расположенную на панели инструментов.
• Ввести Enter. На экране появляется диалоговое окно Мастер функций шаг 1 из 2.
• В окне категория выбираем категорию Математические.
• В окне Функции выбираем строку СУММПРОИЗВ. На экране появляется диалоговое окно СУММПРОИЗВ.
• В строку Массив 1 вводим А2:В2.
• В строку Массив 2 вводим А3:В3.

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

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

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

• Помещаем курсор в ячейку C3.

• На панели инструментов кнопка Копировать в буфер.

• Поместить курсор в ячейку С4.
• На панели инструментов кнопка Вставить из буфера.
• Поместить курсор в ячейку С5.
• На панели инструментов кнопка Вставить из буфера. (Содержимое ячеек С3-С5 необходимо проверить. Они обязательно должны содержать информацию).
• В строке Меню указатель мыши помесить на Сервис. В развернутом меню выбрать команду Поиск решения. Появляется диалоговое окно Поиск решения.
• Запускаем команду Поиск решения.
• Назначаем ячейку для целевой функции ( устанавливаем целевую ячейку), указываем адреса изменяемых ячеек.
• Помещаем курсор в строку Установить целевую ячейку.
• Вводим  адрес ячейки $С$3.
• Вводим тип целевой функции в зависимости от условия нашей задачи. Для этого отмечаем, чему равна целевая функция – Максимальному значению или Минимальному значению.
• Помещаем курсор в строку Изменяя ячейки.

• Вводим адреса искомых переменных A$2:B$2

      7. Вводим ограничения.

• Помещаем указатель мыши на кнопку Добавить. Появляется диалоговое окно Добавление ограничения.
• В строке Ссылка на ячейку вводим адрес $C$4.
• Вводим знак ограничения.
• В строке Ограничение вводим адрес $D$4.
• Помещаем указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.
• Вводим остальные ограничения задачи по вышеописанному алгоритму.
• После введения последнего ограничения  нажимаем на кнопку ОК.

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

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

         8. Вводим параметры  для решения задачи линейного программирования.

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

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

Рис.4 Решение  найдено.Все ограничения и условия  оптимальности выполнены.

   В  результате решения задачи был  получен ответ: для получения максимальной прибыли необходимо произвести: 100 шт. шкафов и 150 комодов. 

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

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

     - Анализ использования ресурсов  в оптимальном плане выполняется с помощью второй теоремы двойственности:

     если  Y_i > 0,то ∑ a_ijX_j = b_i, i = 1, …, m; 

     если  ∑ a_ijX_j = b_i, то Y_i = 0,  i = 1, …, m. 

     

     0,1 +0,3 +1,5 8000

     0,2 +0,1 +1,2 6000

     

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

     

       

       так как 330 < 360, то  то  =27368,4211 , а =5263,15789

     

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

     

       

     Ресурс  «труд» используется не полностью (330 < 360), поэтому имеет нулевую двойственную оценку (Y₂ = 0)

     

     330 < 360

     Этот  ресурс влияет на план выпуска продукции.

     Общая стоимость используемых ресурсов при  выпуске 30 ковров второго вида и 10 ковров третьего вида составит 150 тыс. руб.:

     g (Y) = 40 * Y₁ + 45 * Y₂ + 360 * Y₃  = 40 * 27368,4211 + 45 * 5263,15789 + 360 * 0= 1700000 руб..