Курсовая работа: Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования

Таблица3- Симплекс-таблица 3

Базис	Х1	Х2	Х3	Х4	Х5	Решение
E	0	0	1,4	0	1,2	2220
Х2	0	1	0,3	0	-0,1	190
Х4	0	0	-0,1	1	-0,8	270
Х1	1	0	-0,2	0	0,4	140

Как видно из таблицы 3, в строке целевой функции нет отрицательных коэффициентов. Это значит, что оптимальное решение найдено. Оно состоит в следующем:

Х1=140;

Х2=190;

Х4=270;

Х3= Х5=0;

Е=2220.

5. АНАЛИЗ РЕЗУЛЬТАТОВ БАЗОВОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ И ПРЕДЛОЖЕНИЯ ПО МОДИФИКАЦИИ

Проанализируем полученный результат решения задачи:

Х1=140;

Х2=190;

Х4=270;

Х3= Х5=0;

Е=2220.

Значения переменных X1 = 140, X2 = 190 показывают, что предприятие по плану должно выпускать 140 тонн удобрения «Флора» и 190 тонн удобрения «Росток». В этом случае будет получена максимальная прибыль в размере 2220 ден. ед. (значение целевой функции). Так как X3 = 0, значит, весь запас азотной кислоты (900 тонн) расходуется на выпуск удобрений. Аналогично можно показать, что переменная X4 представляет собой неизрасходованный остаток аммиака, а X5 – калийной соли. Таким образом, остается неизрасходованным 270 тонн аммиака (расход аммиака на выпуск всех удобрений составит 1000 - 270 = 730 тонн). Неизрасходованный остаток калийной соли равен нулю, значит, все 800 тонн калийной соли расходуются на производство удобрений.

Проведем анализ полученного решения на чувствительность. Для начала определим статус имеющихся в задаче ресурсов. По статусу все ресурсы делятся на дефицитные и недефицитные. Если для реализации оптимального решения ресурс расходуется полностью, то он называется дефицитным, если не полностью – недефицитным. Статус ресурсов определяется по значениям остаточных переменных. В данной задаче дефицитными ресурсами являются азотная кислота и калийная соль, т.к. они полностью расходуются в процессе производства (Х3=0; Х5=0). Аммиак - недефицитный ресурс, так как 270 тонн аммиака остаются неизрасходованными (X4 = 270). Увеличение запасов дефицитных ресурсов позволяет увеличить целевую функцию (прибыль). Снижение запасов дефицитных ресурсов приводит к снижению прибыли. Увеличение запасов недефицитных ресурсов всегда нецелесообразно, так как оно приводит только к увеличению неизрасходованных остатков. Запас недефицитного ресурса можно снизить на величину его остатка; это никаким образом не влияет на оптимальное решение (в том числе на оптимальные объемы производства и на прибыль), уменьшается только неизрасходованный остаток ресурса. Если запас недефицитного ресурса снизится на величину, превышающую его остаток, то для определения нового оптимального плана производства необходимо решать задачу заново. В нашем случае увеличение запасов азотной кислоты и калийной соли позволит увеличить прибыль. Запас аммиака можно снизить на 270 т (т.е. до 730 т); эти 270 т аммиака предприятие может, например, продать или использовать в другом цехе. Например, если запас аммиака составит не 1000 т, а только 800 т, то оптимальное решение задачи будет следующим: X1 =140; X2 = 190; X3 = 0; X4 = 70; X5 = 0; E = 2220 ден. ед. Таким образом, оптимальное решение не изменится (кроме снижения неизрасходованного остатка аммиака). Если запас стали снизится более чем на 270 т (т.е. составит менее 730 т), то для определения нового оптимального плана производства необходимо решать задачу заново. Для нового оптимального решения изменятся не только значения переменных, но и состав переменных в оптимальном базисе (т.е. в оптимальный базис будут входить не переменные X1, X2 и X5, а другие переменные). Значение целевой функции при этом снизится, т.е. составит менее 2220 ден. ед.

Определим ценность имеющихся ресурсов. Ценность ресурса – это увеличение значения целевой функции (прибыли) при увеличении запаса ресурса на единицу (или, соответственно, снижение целевой функции при уменьшении запаса ресурса на единицу).

Ценности ресурсов определяются по симплекс-таблице, соответствующей оптимальному решению. Ценности ресурсов представляют собой коэффициенты E-строки при остаточных переменных, соответствующих остаткам ресурсов.

В нашем случае ценность азотной кислоты равна 1,4 ден. ед./т, ценность калийной соли - 1,2 ден. ед./т. Это означает, например, что увеличение запаса азотной кислоты на единицу (т.е. на 1 т) приводит к увеличению прибыли предприятия в среднем на 1,4 ден. ед. Например, если запас азотной кислоты увеличится на 100 т (т.е. составит 1000 т), то прибыль составит примерно 2220 + 1,4*100 =2360 ден. ед. Снижение запаса азотной кислоты приведет к соответствующему снижению прибыли.

Ценность недефицитного ресурса всегда равна нулю. В данном примере ценность аммиака равна нулю, так как увеличение его запаса не приводит к увеличению прибыли, а снижение (не более чем на 270 кг) - не приводит к снижению прибыли.

Ценность ресурса показывает максимальную (предельную) цену, по которой выгодно закупать ресурсы. Например, в рассматриваемой задаче предприятию выгодно закупать азотную кислоту по цене не более 1,4 ден. ед./т, калийную соль - по цене не более 1,2 ден. ед./т. Закупка ресурса по цене, превышающей его ценность, означает, что затраты предприятия на закупку ресурса превышают прибыль от его использования.

6. ПРОВЕРКА ОПТИМАЛЬНОГО РЕШЕНИЯ В СРЕДЕ MS EXCEL С ИСПОЛЬЗОВАНИЕМ ПРОГРАМНОЙ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» (ПАКЕТ «SOLVER»)

Для решения оптимизационных задач в среде MS Excel используется инструмент «Поиск решения» (пункт меню «Данные Поиск решения»).

Для решения задачи необходимо выполнить следующие этапы:

ü  Внести исходные данные;

ü  Определить ячейки, в которые будет помещен конечный результат (изменяемые ячейки);

ü  Внести в определенную ячейку формулу для расчета целевой функции;

ü  Внести в ячейки формулы для расчета ограничений.

В результате получается следующее:

ü  Вызвать надстройку «Поиск решения» и, определив для нее основные параметры, определить решение:

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

1.Для повторного решения задачи оптимизации следует удалить содержимое ячеек с элементами решения и сбросить полученные результаты (клавиша «Delete»).

2.Фрагмент рабочего листа MS Excel с результатами решения задачи оптимизации сохраняется и переносится в документ MS Word (например, с помощью команд «Ctrl&PrintScreen» в среде MS Excel и «Вставить» в документе MS Word или с помощью команд «Копировать» и «Вставить», расположенных на панели инструментов во всех приложениях пакета MS Office).

Оптимальное решение, полученное с помощью двухэтапного метода, совпадает с решением, полученным в среде MS Excel с помощью программной надстройки «Поиск решения».

7. ПРИМЕРЫ ПОСТАНОВОК, ФОРМАЛИЗАЦИИ И РЕШЕНИЯ ПЕРСПЕКТИВНЫХ ОПТИМИЗАЦИОННЫХ УПРАВЛЕНЧЕСКИХ ЗАДАЧ

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

Примечание. Графический метод может применяться также для решения задач с любым количеством переменных, если возможно выразить все переменные задачи через какие-либо две переменные.

ОДР – это множество значений переменных X1,X2,...,Xn, удовлетворяющих ограничениям задачи. Для задач с двумя переменными ОДР представляет собой множество точек (X1; X2), т.е. некоторую область на плоскости (обычно – многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается в одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом:

ü  построить ОДР на плоскости в системе координат (X1; X2),

ü  определить все угловые точки ОДР,

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

Решим графическим методом следующую задачу: предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 25 ден.ед., выпуск одной тонны серной кислоты – 40 ден.ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

Составим математическую модель задачи. Для этого введем переменные. Обозначим через X1 количество выпускаемой соляной кислоты (в тоннах), через X2 – количество серной кислоты (в тоннах).

Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200т. соляной кислоты. Это ограничение можно записать следующим образом: X1 ≥ 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100т. серной кислоты: X2 ≥ 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5т. опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5·X1 т. При выпуске серной кислоты образуется 1,2·X2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5·X1 + 1,2·X2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5·X1 + 1,2·X2 ≤ 600.

Кроме того, переменные X1 и X2 по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо указать ограничения неотрицательности): X1 ≥ 0, X2 ≥ 0.

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден.ед.; значит, прибыль от выпуска соляной кислоты составит 25·X1 ден.ед. Прибыль от выпуска серной кислоты составит 40·X2 ден.ед. Таким образом, общая прибыль от выпуска кислот составит 25·X1+40·X2 ден.ед. Требуется найти такие значения переменных X1 и X2, при которых эта величина будет максимальной.

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

E = 25·X1+40·X2 → max.

Приведем полную математическую модель рассматриваемой задачи:

X1 ≥ 200

X2 ≥ 100 (1.3)

0,5·X1 + 1,2·X2 ≤ 600

X1 ≥ 0, X2 ≥ 0.

E = 25·X1+40·X2 → max.

В этой задаче имеется два ограничения больше или равно” и одно ограничение “меньше или равно”. Целевая функция подлежит максимизации.

Ограничение X1 ≥ 200 задается вертикальной линией X1=200. Все точки (X1; X2), расположенные справа от этой линии, удовлетворяют ограничению X1 ≥ 200, расположенные слева – не удовлетворяют. Ограничение X2 ≥ 100 задается горизонтальной линией X2=100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению X2 ≥ 100, расположенные снизу не удовлетворяют.

Для построения линии, задающей ограничение 0,5·X1 + 1,2·X2 ≤ 600, удобно записать его в виде равенства: 0,5·X1 + 1,2·X2 = 600. Выразим одну из переменных через другую: X2 = -0,417·X1 + 500. Это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5·X1 + 1,2·X2 ≤ 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

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

Рисунок 2. Решение задачи графическим методом

Оптимальное решение находится в одной из угловых точек ОДР (на рис.2 они обозначены как A,B,C). Эти точки можно найти путем решения соответствующих систем из двух уравнений. Найдем значения целевой функции в этих точках:

E(A) = 25·200 + 40·100 = 9000;

E(B) = 25·200 + 40·416,67 = 21666,8;

E(C) = 25·960 + 40·100 = 28000.

Таким образом, оптимальное решение находится в точке C=(960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5·960 + 1,2·100 = 600 т.

ЗАКЛЮЧЕНИЕ

В рамках данной работы была решена одна из задач линейного программирования. В результате применения процедуры симплекс-метода было получено оптимальное решение поставленной задачи, в соответствии с которым предприятию требуется выпустить 140 тонн удобрения «Флора» и 190 тонн удобрения «Росток». При этом количество неиспользованного аммиака составит 270 тонн, а азотная кислота и калийная соль будут использованы полностью. При этом предприятие получит максимальную прибыль равную 2220 денежных единиц.

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

Проверка результатов решения задачи в среде MS Excel показала аналогичное решение данной задачи оптимизации.

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.  Замков О.О., Толстопятенко А.В., Черешных Ю.Н. Математические методы в экономике: Учебник. – М.: МГУ им. М.В.Ломоносова, Издательство «ДИС», 1997.

2.  Конспект лекций по предмету «Экономико-математические методы и модели».

3.  Минюк С.А. Математические методы и модели в экономике: Учеб. пособие / Минюк С.А., Ровба Е.А., Кузьмич К.К. – Мн.: ТетраСистемс, 2002.

4.  Смородинский С.С., Батин Н. В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003.

5.  Экономико-математические методы и модели/ Под. ред. А. В. Кузнецова. Мн.: БГЭУ.1999.