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

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

Санкт-Петербургский  государственный политехнический  университет

—

Инженерно-экономический  институт

Кафедра «Информационные системы  в экономике и менеджменте»

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

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

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

 

 

 

 

 

 

 

Выполнил

студент гр. 3242/2в                                                 А.В.Лебедев

Руководитель

доцент, к.ф.-м.н.       А.Л. Кутузов

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2013

 

Оглавление

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

2. Решение задачи линейного программирования 4

2.1. С помощью Microsoft Excel 4

2.2. В программе WinQSB 8

3. Ответы на поставленные вопросы 10

4. Параметрический анализ 15

4.1. Параметрический анализ целевой функции 15

4.2. Параметрический анализ правой части ограничений 17

Учебные материалы 19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Разновидность	Многоквартирный дом	Барак	Коттедж	Дачный дом	Гараж	Запас ресурса, тонн
Ресурс. тонн
Бетон	80	40	12	8	5	2800
Цемент	95	34	35	15	5	3000
Кирпич	60	22	47	12	8	1850
Дерево	66	33	42	20	2	3200
Пластик	25	18	25	10	2	800
Прибыль, $/ед.	880	380	530	250	50

 

Наша задача максимизировать прибыль.

Пусть x₁,x2,x3,x4,x5 будут обозначат стройматериалы: бетон, цемент, кирпич, дерево и пластик соответственно.Получаемая прибыль - C(x). Математическая модель представлена ниже.

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

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

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

 

 

2. Решение задачи линейного программирования 

2.1. С помощью Microsoft Excel 

 

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

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

 

 

 

 

 

 

После ввода данных, воспользуемся средством «Поиск решения» (рис.2). Укажем ссылки на необходимые для решения исходные данные, и позволим программе выполнить поиск решения. Результаты приведены ниже (рис.3).

Рис.2. Окно средства Поиск решения в Excel

 

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

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

Рис.4. Отчеты

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. В программе WinQSB

 

Теперь решим задачу с помощью WinQSB. Программа производит все расчеты автоматически после введение исходных данных (рис.5).

Рис.5.Задание коэффициентов целевой функции и ограничений в WinQSB

Рис.6. Измененные названия переменных и ограничений

После решения  программа выводит отчет, содержащий оптимальный план и данные (рис.7).

Рис.7. Сводный отчет о решении задачи линейного программирования

В данном оптимальном  плане в производстве находятся 2 жилых домов, это все те же многоквартирные дома и дачи . Для достижения максимальной прибыли должно производиться 5 дач и 29 многоквартирных домов. Оставшиеся 3 вида являются убыточными. Если включить в производственный план единицу продукции одного из этих видов, то предприятие понесет убыток в размерах $73,4, $239,5  и $47,6. Для каждого типа продукции существуют интервалы оптимальности. Если штучная прибыль будет находиться в этих интервалах, то оптимальное решение меняться не будет, будет только меняться значение целевой функции. Эти интервалы указаны в правых крайних столбцах.

Так же видно, что кирпич и пластик дефицитные товары.

3. Ответы на поставленные вопросы

1. Каково решение задачи линейного программирования и в чем его экономический смысл?

Решение задачи линейного программирования - оптимальный  план (в данной задаче – (29,0,0,5,0)), при котором целевая функция достигает своего экстремума. Это означает, что при описанном выпуске предприятие получит максимальную прибыль – $27565.

2. Какие ограничения являются связанными (активными), что это означает?

Связанные ограничения – ограничения, разница  между правыми и левыми частями  которого равна 0 (т.е. ограничения дефицитных ресурсов). По отчету видно, что связанные  ограничения – ограничения на кирпичи и пластик.

3. Если имеются ограничения на ресурсы, то какие из них дефицитны, а какие — нет?

Дефицитные  – те ресурсы, у которых в сводном  отчете в графе slack or surplus стоит нуль; недефицитные – число, отличное от нуля. По сводному отчету можно увидеть, что кирпичи и пластик являются дефицитными, а остальные – недефицитными.

4. Каков экономический смысл левой части (функции) каждого ограничения и соответствующего остатка или избытка?

Левая часть  ограничения – суммарные затраты  какого-то определенного ресурса. Остаток  или избыток – количество ресурса, не участвующее в производстве.

5. Что происходит при изменении каждого из коэффициентов целевой функции?

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

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

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

6. Если какие-то переменные в оптимальном решении равны нулю, как сделать их положительными?

Для этого  необходимо увеличить их коэффициенты при целевой функции минимум  на величину их двойственных оценок. Например, для второй переменной (барак) минимальное необходимое увеличение составляет $73,4, чтобы выпускать это изделие стало выгоднее (рис.7-Reduced cost).

7. Что происходит при изменении правых частей каждого из ограничений?

При изменении  правых частей каждого из ограничений  может происходить два различных  события в зависимости от того, в каком интервале будут происходить  изменения. Если в пределах интервала  устойчивости, то будет сохраняться  структура оптимального решения. (рис.10) При выходе из интервала будет меняться структура, компоненты и значение целевой функции оптимального плана.(рис.11) Интервалы устойчивости можно увидеть в сводном отчете выше.

Рис.10. Сводный отчет о решении задачи линейного программирования с измененными правыми части ограничений в пределах интервала устойчивости

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

8. Если придется дополнительно покупать или продавать ресурсы, то по какой цене это следует делать?

Если придется дополнительно покупать или продавать  ресурсы, то это следует делать по цене, не превосходящей их двойственные оценки. По условиям данной задачи, следует покупать, например, кирпич по цене не выше $8,5, чтобы приобретение дополнительного ресурса было выгодно для нас (рис.7, столбец Shadow Price)

9. В каких пределах можно изменять правые части каждого из ограничений и что при этом происходит?

При изменении  внутри интервала устойчивости структура  останется прежней, а при изменении  вне интервала устойчивости изменится оптимальное решение. Проиллюстрировано на рисунках 10 и 11.

10. Есть ли у задачи альтернативные решения, и, если есть, то чему равны?

Альтернативные  решения у данной задачи отсутствуют, т.е. у нулевых компонент оптимального плана отсутствует нулевые двойственные оценки. Это можно увидеть в  сводном отчете. (так как в сводном отчете(рис.7) рядом со значением целевой функции отсутствует надпись Note: Alternate Solution Exists!)

11. Является ли решение вырожденным?

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

 

 

4. Параметрический анализ

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

4.1. Параметрический  анализ целевой функции

 

Пусть под  действием времени меняется стоимость . В таком случае целевая функция изменяется следующим образом:

С=(880+2t)x1+380x2+(530+t)x3+250x4+(50+t)x5,

Где t - изменяющийся параметр (изменение цены со временем). В таком случае вектор изменения (2,0,1,0,1)

Рис.12. Задание вектора изменения коэффициентов целевой функции

Рис.13. Параметрический анализ в WinQSB

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

 

2. Параметрический анализ правой части ограничений

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

где m- изменяющийся параметр (изменение количество товара в производстве), в таком случае вектор изменения (3,-2,1,4,-1)

Рис. 14. Задание вектора изменения правых частей ограничения

Рис.15 Параметрический анализ в WinQSB.

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

 

Учебные материалы

1. Кутузов А.Л. Исследование операций: учебное пособие. СПб.: Изд-во Политехн. Ун-та,2012