Линейное программирование в EXCEL

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

(ННГАСУ)

Международный факультет экономики, права и менеджмента

КАФЕДРА МЕЖДУНАРОДНОГО МЕНЕДЖМЕНТА

 

 

 

 

Расчетно-графическая работа

по дисциплине

«Математические методы и модели в экономике»

 

Вариант 2

 

 

Выполнила:

студентка гр. ММ5.13

Никитенко А.И.,

 

Проверил:

 

доцент кафедры ПрИС

Юрченко Т.В.

 

 

 

 

Нижний Новгород

2015 г.

Содержание

 

1. Задача 1

1. Экономико-математическая модель задачи
2. Решение задачи в Excel
3. Двойственность в задачах линейного программирования
4. Математическая модель двойственной задачи
5. Решение двойственной задачи в Excel
6. Анализ

2. Транспортная задача

1. Проверка сбалансированности
2. Математическая модель
3. Решение задачи в Excel

 

 

Задача 1

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

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

Обозначим через Х1, Х2, Х3, Х4 производство изделий каждого вида.

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

f(x) = 5х1 + 7х2 + 3х3 + 8х4  → max

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

2х1 + х2 + 3х3 + 2х4 200

х1 + 2х2 + 4х3 + 8х4 160

2х1 + 4х2 + х3 + х4 170

2. Решение задачи в среде EXCEL

Создаем таблицу и вводим исходные данные. К исходной таблице добавляем строку «Производство» с изменяемыми ячейками [В7:Е7]. И столбец «Фактические затраты» с адресами в ячейках [G3:G5] – это будет правая часть наших ограничений.

Рис.1 Исходная таблица

 

Оптимальное значение целевой функции содержится в ячейке с адресом [В10]. Введем зависимость для ЦФ, поставив курсор в ячейку [В10]. С помощью кнопки «Вставить функцию» выбираем функцию «СУММПРОИЗВ» и перемножаем 2 массива: [В6:Е6] и [В7:Е7].

Рис. 2 Целевая функция

В столбец «Фактические затраты» необходимо ввести формулы: СУММПРОИЗВ(В3:Е3;В7:Е7), СУММПРОИЗВ(В4:Е4;В7:Е7), СУММПРОИЗВ(В5:Е5;В7:Е7).

Рис. 3 Фактические затраты

3. Технология решения задач линейного программирования с помощью поиска решений

Поиск решения – это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Если, в меню Данные отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду ФайлÞПараметрыÞНадстройки и активизируйте надстройку Поиск решения.

После выбора команд Данные Þ Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне «Поиск решения» есть три основных параметра:

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

• Изменяя ячейки

• Ограничения

Сначала нужно заполнить поле «Установить целевую ячейку». В данном случае адрес целевой ячейки [В10] и так как нам требуется составить план, при котором будет достигаться максимальная выручка от продажи, устанавливаем флажок «Максимум»

Второй важный параметр средства Поиск решения – это параметр «Изменяя ячейки». Изменяемые ячейки – это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Они не должны содержать формул, и изменение их значений будет отражаться на изменении результата в целевой ячейке. В таблице я выделила эти ячейки желтым цветом. Эти ячейки имеют адреса  [В7:Е7].

Третий параметр, который нужно ввести, для Поиска решения – это ограничения. В математической модели ограничения имели вид:

2х1 + х2 + 3х3 + 2х4 200

х1 + 2х2 + 4х3 + 8х4 160

2х1 + 4х2 + х3 + х4 170

В данной таблице: «Фактические затраты» «Запасы сырья»

Рис. 4 Ограничения

Далее выбираем метод решения – поиск решения линейных задач симплекс-методом. Таким образом, заполнены все параметры для того чтобы применить «Поиск решений», нажимаем «Найти решение».

Рис. 5 Поиск решений

После нажатия кнопки появляется диалоговое окно «Результаты поиска решений». Выделяем все 3 отчета и нажимаем «ОК».

Рис.6 Отчеты

Рис. 7 Готовый результат

 

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

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

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

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

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

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

g = 200у1 + 160у2 + 170у3 ® min

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

2у1 + у2 + 2у3 ³ 5

у1 + 2у2 + 4у3 ³ 7

3у1 + 4у2 + у3 ³ 3

2у1 + 8у2 + у3 ³ 8

2. Готовое решение двойственной задачи в среде EXCEL

Рис. 9 Поиск решений двойственной задачи

Рис. 10 Готовый результат

Рис. 11 Отчет об устойчивости двойственной задачи

 

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

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

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

Правые части этих ограничений равны левым частям.

х1 + 2х2 + 4х3 + 8х4 160

2х1 + 4х2 + х3 + х4 170

Если подставить полученное решение (80,0,0,10) в правые части ограничений исходной задачи, то получим равенство:

1´80 + 2´0 + 4´0 + 8´10 = 160

2´80 + 4´0 + 1´0 + 1´10 = 170

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

2х1 + х2 + 3х3 + 2х4 200     →    2´80 + 1´0 + 3´0 + 2´10 = 180

Этот ресурс не влияет на план выпуска продукции. Общую стоимость используемой продукции можно узнать подставив решение (0; 0,733; 2,13) двойственной задачи в формулу ЦФ двойственной задачи:

g = 200у1 + 160у2 + 170у3 ® min

200´0 + 160´0,733 + 170´2,13 ® min

480 – общая стоимость  ресурсов в оптимальном решении

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

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

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

Если изделие вошло в оптимальный план (Xj >0), то в двойственных оценках оно не убыточно, то есть, стоимость ресурсов, затраченных на производство единицы изделия равна его цене. Такие изделия эффективны, выгодны с точки зрения принятого критерия оптимальности. В данной задаче j=2,3. Если стоимость ресурсов, затраченных на производство одного изделия больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче j=1,4.

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

 Получаем:

2´0 + 1´0,733 + 2´2,133 = 5 = 5

1´0 + 2´0,733 + 4´2,133 = 10 > 7

3´0 + 4´0,733 + 1´2,133 = 5,066 > 3

2´0 + 8´0,733 + 1´2,133 = 8 = 8

Разницу между правыми и левыми частями ограничений двойственной задачи можно найти в «Отчете по устойчивости» в столбце «Нормируемая стоимость».

Проведем анализ чувствительности решения к измененияю запаса сырья с помощью теоремы об оценках. Предположим, что запас сырья «2» вырос на 10 единиц и теперь составляет 170 единиц. В данном случае, увеличив запасы сырья «2» ЦФ изменится на 7 пунктов. Посчитать это можно:

Df(x) = D bi´ yi

i = 1      b1 = 160     D b1 = 10    →    b1н = 170

у1 = 0    →   f(x) = 10´0,733 ≈ 7

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

Рис. 12 Отчет об устойчивости исходной задачи

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

    Предположим, что  запас сырья «1» вырос на 8 ед., запас сырья «2» вырос на 10 ед., а запас сырья «3» снизился  на 5 ед.

Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции приблизительно на 3 ед., но и к изменению плана выпуска. При этом структура плана не изменилась – изделия, которые были убыточны, не вошли и в новый план выпуска, т.к. цены на ресурсы не изменились. Новый план выпуска составляет примерно 77 ед. продукции «А» и 12 ед. продукции «Г».

Рис. 13 Отчет об устойчивости после внесения изменений

 

Задача 2

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

1. Выполним проверку сбалансированности математической модели задачи.

Транспортная задача может быть двух видов:

1. Закрытая или сбалансированная – в этом случае суммарные потребности равны суммарному наличию запасов на складе.

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

Поскольку, в нашей задаче суммарный запас груза а = 40 + 20 + 40 = 100 равен суммарной потребности b = 25 + 10 + 20 + 30 + 15 = 100, то рассматриваемая транспортная задача является сбалансированной или закрытой.

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

Пусть хij – объем перевозок с i-го пункта поставки в j-й пункт потребления. Суммарные транспортные расходы – это функция  , где сij – стоимость перевозки единицы продукции с i-го предприятия в j-й пункт потребления (i = 1̅,3; j = 1̅,5). Поэтому целевая функция  данной задачи будет иметь вид:

f(x) = 5х11 + 3х12 + 4х13 + 6х14 + 4х15 + 3х21 + 4х22 + 10х23 + 5х24 + 7х25 + 4х31 + 6х32 + 9х33 + 3х34 + 4х35 → min

 

Ограничения по поставщикам: = х11 + х12 + х13 + х14 + х15 = 40  = х21 + х22 + х23 + х24 + х25 = 20 = х31 + х32 + х33 + х34 + х35 = 40

Ограничения по потребителям:  = х11 + х21 + х31 = 25 = х12 + х22 + х32 = 10 = х13 + х23 + х33 = 20 = х14 + х24 + х34 = 30 = х15 + х25 + х35 = 15