--PAGE_BREAK--т. Эта величина не должна превышать 900 т, так как запас азотной кислоты составляет 900т. Поэтому можно записать следующее ограничение:
X1+4X2 ≤900
Аналогично можно составить ограничение на аммиак:
2,5X1+2X2≤1000
и на расход калийной соли:
3Х1+2Х2≤800
Кроме того, переменные X1 иX2 по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество тонн удобрений. Поэтому необходимо указать ограничения неотрицательности:
X1>0, X2>0.
В данной задаче требуется определить количество тонн выпускаемых удобрений, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одной тонны удобрения «Флора» составляет 5 ден. ед.; значит, прибыль отвыпуска удобрения «Флора» составит 5X1 ден. ед. Прибыль от выпуска удобрения «Росток» составит 8X2 ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 5X1 + 8X2 ден. ед. Требуется найти такие значенияпеременных X1иX2, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:
Е =5X1 + 8X2 →max
Для решения задачи симплекс-методом требуется привести ее к стандартной форме. Все ограничения задачи имеют вид «меньше или равно». Их необходимо преобразовать в равенства. Для этого требуется добавить в каждое ограничение дополнительную (остаточную) переменную. Математическая модель задачи в стандартной форме будет иметь следующий вид:
Х1+4Х2+Х3=900
2,5Х1+2Х2+Х4=1000
3Х1+2Х2+Х5=800
Е =5X1 + 8X2 →max
X1>0, X2>0.
Где:
Х3-остаток азотной кислоты;
Х4-остаток аммиака;
Х5-остаток калийной соли.
3. ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ
Необходимо решить задачу по критерию максимизации прибыли и определить оптимальный объём выпуска удобрений «Флора» и «Росток». Построив математическую модель задачи, мы видим, что целевая функция и ограничения линейны, следовательно, данная задача является задачей линейного программирования. Из множества методов решения задач линейного программирования, для решения данной, был выбран метод определения оптимального решения на основе симплекс-таблиц.
Поиск оптимального решения на основе симплекс-метода состоит в целенаправленном переборе смежных угловых точек ОДР в направлении улучшения значения целевой функции. Можно доказать, что переход из одной угловой точки ОДР в другую (смежную) соответствует замене одной переменной в базисе. Такая замена означает, что одна из небазисных переменных (имевшая нулевое значение) включается в базис, т.е. увеличивается, а одна из базисных переменных уменьшается до нуля, т.е. исключается из базиса. Выбор таких переменных выполняется по определенным правилам, обеспечивающим максимально быстрое увеличение целевой функции.
Рассмотрим алгоритм поиска оптимального решения на основе симплекс-таблиц:
1. Строится исходная симплекс-таблица.
2. Симплекс-таблица строится по следующим правилам:
• в первой строке перечисляются все переменные задачи, как исходные (X1, X2, ...,Xn), так и дополнительные, введенные при приведении к стандартной форме (Xn+1, Xn+2, ...,Xk). Для задач, содержащих только ограничения «меньше или равно», дополнительные переменные Xn+1, Xn+2, ..., Хк~ это остаточные переменные;
• в первой колонке таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений. Для задач, содержащих только ограничения «меньше или равно», начальный базис состоит из остаточных переменных Xn+1, Xn+2, ..., Xk
. В этой же колонке указывается обозначение целевой функции E;
• в строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для остаточныхпеременных Xn+1, Xn+2, ..., Xk), указываются нули;
• в строках базисных переменных указываются коэффициенты ограничений, в которые входят эти переменные. Для переменных, не входящих в ограничения, указываются нулевые коэффициенты;
• в последнем столбце («Решение») указываются значения базисных переменных (они равны правым частям ограничений), а также начальное значение целевой функции (0).
Если таблица построена правильно, то в столбце каждой базиснойпеременной должна присутствовать только одна единица (в строке ограничения, в которое входит эта переменная); остальные коэффициенты — нулевые.
2. Если все коэффициенты в строке целевой функции неотрицательны, то оптимальное решение найдено, и алгоритм завершается. Иначе осуществляется переход к этапу 3.
3. Из числа текущих небазисных переменных выбирается переменная, включаемая в новый базис. В качестве такой переменной выбирается переменная, которой соответствует максимальный по модулю отрицательный коэффициент в строке целевой функции. Выбор максимального по модулю отрицательного элемента означает включение в базис переменной, увеличение которой приводит к максимальному росту целевой функции.
4. Из числа текущих небазисных переменных выбирается переменная, исключаемая из базиса. Для этого вычисляются так называемые симплекс-отношения элементов текущего решения к элементам ведущего столбца. Переменная, которой соответствует минимальное отношение, исключается из базиса. Строку, соответствующую исключаемой переменной, называют ведущей строкой, а элемент на пересечении ведущей строки и столбца — ведущим элементом.
5. Выполняется преобразование симплекс-таблицы по следующим правилам:
Новая ведущая строка =
Все элементы ведущего столбца кроме ведущего элемента обнуляются. Оставшиеся элементы пересчитываются по правилу прямоугольника, который образуется на базе пересчитываемого и ведущего элемента: из произведения пересчитываемого и ведущего элемента вычитается произведение элементов, расположенных на другой диагонали этого прямоугольника; результат делится на ведущий элемент.
6. Находится новое базисное решение, соответствующее новой структуре небазисных и базисных переменных. Осуществляется переход к шагу 2.
По окончании реализации алгоритма в столбце «Базисное решение» находятся значения переменных, вошедших в оптимальный базис, а также значение целевой функции, соответствующее оптимальному решению. Переменные, не вошедшие в оптимальный базис, в оптимальном решении равны нулю.
4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ ТЕХНОЛОГИИ СИМПЛЕКС-МЕТОДА
Математическая модель решаемой задачи имеет следующий вид:
Х1+4Х2+Х3=900
2,5Х1+2Х2+Х4=1000
3Х1+2Х2+Х5=800
Е =5X1 + 8X2 →max
X1>0, X2>0.
Составим исходную симплекс-таблицу (табл.1):
Таблица 1
Базис
Х1
Х2
Х3
Х4
Х5
Решение
E
-5
-8
Х3
1
4
1
900
Х4
2,5
2
1
1000
Х5
3
2
1
800
Определяется переменная для включения в базис.
Для рассматриваемого примера в базис необходимо включить переменную X2,так как ей соответствует максимальный по модулю отрицательный коэффициент E-строки (-8). Это означает увеличение выпуска удобрения «Росток». Из условия задачи и целевой функции видно, что увеличение выпуска удобрения «Росток» приводит к более быстрому росту целевой функции, чем увеличение выпуска удобрения «Флора»: выпуск каждой тонны удобрения «Росток» увеличивает целевую функцию (прибыль) на 8 ден. ед., а выпуск каждой тонны удобрения «Флора» — только на 5 ден. ед.
Определим переменную для исключения из базиса. Для этого необходимо поделить коэффициенты столбца решения на коэффициенты ведущего столбца Х2 (при этом следует помнить, чтобы коэффициенты ведущего столбца были положительны). В результате получатся симплексные отношения:
900/4=225; 1000/2=500; 800/2=400.
Смысл поиска переменной, исключаемой из базиса в следующем: при включении новой переменной в базис, её значение увеличивается. При этом чтобы соблюдать исходные ограничения задачи необходимо уменьшать базисные переменные. Уменьшение переменных возможно только до 0. Симплексное отношение показывает через сколько увеличений переменой, включаемой в базис, данная базисная переменная приблизится к нулю. Поэтому переменная, имеющая минимальное симплексное отношение, исключается из базиса. Строка с переменной, исключаемой из базиса, называется ведущей строкой. Итак, исключаем из базиса переменную Х3 (симплексное отношение минимальное и равно 225), строка Х3 является ведущей. Элемент, находящийся на пересечении ведущей строки Х3 и ведущего столбца Х2, называется ведущим (разрешающим) элементом. Для данной таблицы ведущий элемент равен 4.
Выполним преобразования таблицы по правилам симплекс-метода, описанным в разделе 3: ведущая строка Х3 делится на ведущий элемент, равный 4; ведущий столбец Х2 заполняется нулями; все остальные элементы таблицы пересчитываются по “правилу прямоугольника”. Например, коэффициент на пересечении Е-строки и столбца Х1 пересчитывается следующим образом: [4*(-5)–1*(-8)] /4= -3. Полученная симплекс-таблица приведена в табл.2.:
Таблица 2- Симплекс-таблица 2
Базис
Х1
Х2
Х3
Х4
Х5
Решение
E
-3
2
1800
Х2
0,25
1
0,25
225
Х4
2
-0,5
1
550
Х5
2,5
-0,5
1
350
Т.к. в строке целевой функции есть отрицательные коэффициенты, то данное решение не является оптимальным. Пересчитаем таблицу по описанному выше примеру.
Таблица3- Симплекс-таблица 3
Базис
Х1
Х2
Х3
Х4
Х5
Решение
E
1,4
1,2
2220
Х2
1
0,3
-0,1
190
Х4
-0,1
1
-0,8
270
Х1
1
-0,2
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 кг) — не приводит к снижению прибыли.
Ценность ресурса показывает продолжение
--PAGE_BREAK--