Решение двойственной задачи с помощью надстройки Excel Поиск решения

Лабораторная работа №2

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

Целью работы является приобретение навыков по­строения математических моделей двойственных задач линейного программи­рования и их решения в среде Microsoft Excel.

Порядок выполнения лабораторной работы

Для выполнения лабораторной работы необходимо:

1) повторить теоретический материал, относящийся к данному занятию;

2) по номеру своего варианта выбрать условие задачи (см. лаб. раб. №1) и постро­ить математическую модель двойственной задачи;

3) решить двойственную задачу линейного программи­рования с помощью надстройки Поиск решений в среде Excel (см. п.2);

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

Отчет по лабораторной работе должен занимать 5-7 страниц и содержать:

• титульный лист;

• постановку экономической задачи (исходные данные вари­анта);

• экономико-математическую модель с необходимыми коммен­тариями по ее элементам с указанием всех единиц измерения;

• протокол решения задачи, куда должны входить:

а) фрагмент исходного рабочего листа Excel;

б) диалоговое окно Поиск решения;

в) отчет по устойчивости и результаты его анализа c ответами на вопросы:

· Какие ресурсы в решенной задаче являются дефицитными?

· На сколько максимально можно увеличить запасы дефицитных ресурсов, сохранив при этом оптимальное решение?

· Как изменится целевая функция задачи, если один из дефицитных ресурсов максимально увеличить?

· Какие изделия являются эффективными в решаемой задаче? Показать с помощью теневых цен.

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

Отчет оформляется в установленные преподавателем сроки.

2. Инструкция по использованию
MICROSOFT EXCEL при решении двойственных задач линейного программирования

Рассмотрим в качестве примера решение средствами Microsoft Excel двойственной задачи к задаче о коврах:

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

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

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

Z= 80∙y₁ + 480∙ y₂ + 130∙ y₃ → min (1)

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

7∙ y₁ + 5 ∙y₂ + 2 ∙y₃ ≥ 3, (2)

2∙ y₁ + 8∙ y₂+ 4∙y₃ ≥ 4, (3)

2∙ y₁ + 4∙ y₂+ 1∙y₃ ≥3, (4)

6∙ y₁ + 3∙ y₂+ 8∙y₃ ≥1, (4)

y₁ ³ 0, y₂ ³ 0, y₃ ³ 0, (5)

где y₁ – теневая цена ресурса «труд»;

y₂ - теневая цена ресурса «сырье»;

y₃ - теневая цена ресурса «оборудование».

Решение двойственной задачи с помощью надстройки Excel Поиск решения

Решение двойственной задачи можно найти в Отчете по устойчивости решения исходной задачи (рис. 2.1).

Рис. 2.1. Содержание отчета по устойчивости

Отчет по устойчивости содержит информацию, относя­щуюся к переменным:

• Результат решения задачи.

• «Нормированная стоимость» показывает, на сколько изменится значение целевой функции в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи (см. рис. 2.1) нормированная стоимость для ковров первого типа равна -7 тыс. руб./шт. Это означает, что если мы, несмотря на оптимальное решение (0; 30; 10; 0), попробуем включить в план выпуска один ковер первого типа, то новый план выпуска принесет нам доход 143 тыс. руб., что на 7 тыс. руб. меньше, чем прежнее оптимальное решение.

• Коэффициенты целевой функции.

• Предельные значения приращения целевых коэффициентов Δс_j, при которых сохраняется первоначальное оптимальное реше­ние. Например, допустимое увеличение цены на ковер первого типа равно 7 тыс. руб./шт., а допустимое уменьшение — практически не ограничено. Это означает, что если цена ковра первого типа возрастет более чем на 7 тыс. руб./шт ., то оптимальное решение изменится: станет целесообразным вы­пускать ковры первого типа.А если их цена будет снижаться вплоть до нуля, то оптимальное решение (0; 30; 10; 0) останется прежним.

Во второй части Отчета по устойчивости содержится информация, относя­щаяся к ограничениям:

• Величина использованных ресурсов в колонке Результирующее значение.

• Предельные значения приращения ресурсов Δb_i. В графе Допустимое уменьшение (увеличение) показано, на сколько можно уменьшить (увеличить) ресурс, сохранив при этом оптималь­ное решение.

Рассмотрим анализ дефицитных ресурсов. Ана­лизируя отчет по результатам, мы установили, что существуют причины (ограничения), не позволяющие фабрике выпускать больше ковров, чем в оптимальном решении, и получать более высокий доход. В рассматриваемой задаче такими ограниче­ниями являются дефицитные ресурсы «труд» и «оборудование». Поскольку знак ограничений этих запасов имеет вид ≤, то возникает вопрос, на сколько максимально должен возрасти запас этих ресурсов, чтобы обеспечить увеличение выпуска продукции. Ответ дает графа «Допустимое увеличение». Ресурс «труд» имеет смысл увеличить максимум на 150 чел.- дней, а ресурс «оборудование» - на 30 станко –часов.

• Ценность дополнительной единицы ресурса (теневые цены) рассчитываются только для дефицитных ресурсов.