Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования (стр. 4 из 5)

Выполним преобразования таблицы по правилам симплекс-метода, описанным в разделе 3: ведущая строка Х3 делится на ведущий элемент, равный 4; ведущий столбец Х2 заполняется нулями; все остальные элементы таблицы пересчитываются по “правилу прямоугольника”. Например, коэффициент на пересечении Е-строки и столбца Х1 пересчитывается следующим образом: [4*(-5)–1*(-8)] /4= -3. Полученная симплекс-таблица приведена в табл.2.:

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

Базис	Х1	Х2	Х3	Х4	Х5	Решение
E	-3	0	2	0	0	1800
Х2	0,25	1	0,25	0	0	225
Х4	2	0	-0,5	1	0	550
Х5	2,5	0	-0,5	0	1	350

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

Таблица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; X₃= 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. ПРОВЕРКА ОПТИМАЛЬНОГО РЕШЕНИЯ В СРЕДЕ MSEXCEL С ИСПОЛЬЗОВАНИЕМ ПРОГРАМНОЙ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» (ПАКЕТ «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), т.е. некоторую область на плоскости (обычно – многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается в одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом: