0,25Х2+0,625Х7+0,375Х8 + 2,25Х9 ≥ 0,5
Или, после приведения к стандартному виду, получим:
-0,25Х2 – 0,625Х7 – 0,375Х8 – 2,25Х9 + Х10 = -0,5
Добавим это ограничение к нашей предыдущей симплекс-таблице:
| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | БР |
| E | 0 | 1,25 | 0 | 0 | 0 | 0 | 1,875 | 1,875 | 3,75 | 0 | 37,5 |
| Х3 | 0 | 0,75 | 1 | 0 | 0 | 0 | 0,625 | -0,375 | 2,25 | 0 | 6,5 |
| X6 | 0 | -0,5 | 0 | 0 | 0 | 1 | -0,25 | 0,75 | -1,5 | 0 | 1 |
| X4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 2 |
| X5 | 1 | 0,5 | 0 | 0 | 1 | 0 | 0,2 | 0,25 | 0,5 | 0 | 5 |
| Х1 | 1 | 0,25 | 0 | 0 | 0 | 0 | 0,375 | 0,375 | -2,25 | 0 | 1,5 |
| X10 | 0 | -0,25 | 0 | 0 | 0 | 0 | -0,375 | -0,375 | -2,25 | 1 | -0,5 |
Таблица 10. Симплекс-таблица №9.
Переменная, исключаемая из базиса – это X10, т.к. ее значение –0,5 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –2,25. Получим новую симплекс-таблицу:
| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | БР |
| E | 0 | 0,83 | 0 | 0 | 0 | 0 | 1,25 | 1,25 | 0 | 1,67 | 36,67 |
| Х3 | 0 | 0,5 | 1 | 0 | 0 | 0 | 0,25 | -0,75 | 0 | 1 | 6 |
| X6 | 0 | -0,33 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | -0,67 | 1,33 |
| X4 | 0 | 0,111 | 0 | 1 | 0 | 0 | -0,17 | -0,17 | 0 | 0,44 | 1,78 |
| X5 | 0 | 0,444 | 0 | 0 | 1 | 0 | 0,17 | 0,17 | 0 | 0,22 | 4,89 |
| Х1 | 1 | 0,5 | 0 | 0 | 0 | 0 | 0,75 | 0,75 | 0 | -1 | 2 |
| X9 | 0 | 0,11 | 0 | 0 | 0 | 0 | 0,17 | 0,17 | 1 | -0,44 | 0,22 |
Таблица 11. Симплекс-таблица №10.
Решение все еще не целочисленное, поэтому переходим к следующей итерации. Переменная, имеющая максимальную дробную часть – это Х5 ({4,89}=0,89), она должна быть целой, переменные Х7, Х8 и Х10 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х5 и небазисных переменных Х2, X7, X8,Х10≥0(0,44≥0, 0,17≥0, 0,22≥0), токоэффициент при переменной Х2 рассчитаем по формуле (3):L1={0,44}=0,44, коэффициенты при переменных Х7, Х9и Х10 рассчитаем по формуле (1):L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} = 0,89. Ограничение будет иметь вид:
0,44Х2 + 0,17Х7 + 0,17Х8 + 0,22Х10 ≥ 0,89
Или, после приведения к стандартному виду, получим:
-0,44Х2 – 0,17Х7 – 0,17Х8 – 0,22Х10 + Х11 = -0,89
Добавим это ограничение к нашей предыдущей симплекс-таблице:
| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | Х11 | БР |
| E | 0 | 0,83 | 0 | 0 | 0 | 0 | 1,25 | 1,25 | 0 | 1,67 | 0 | 36,67 |
| Х3 | 0 | 0,5 | 1 | 0 | 0 | 0 | 0,25 | -0,75 | 0 | 1 | 0 | 6 |
| X6 | 0 | -0,3 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | -0,67 | 0 | 1,33 |
| X4 | 0 | 0,11 | 0 | 1 | 0 | 0 | -0,17 | -0,17 | 0 | 0,44 | 0 | 1,78 |
| X5 | 0 | 0,44 | 0 | 0 | 1 | 0 | 0,17 | 0,17 | 0 | 0,22 | 0 | 4,89 |
| Х1 | 1 | 0,5 | 0 | 0 | 0 | 0 | 0,75 | 0,75 | 0 | -1 | 0 | 2 |
| Х9 | 0 | 0,11 | 0 | 0 | 0 | 0 | 0,17 | 0,17 | 1 | -0,44 | 0 | 2 |
| X11 | 0 | -0,44 | 0 | 0 | 0 | 0 | -0,17 | -0,17 | 0 | -0,22 | 1 | -0,89 |
Таблица 12. Симплекс-таблица №11.
Переменная, исключаемая из базиса – это X11, т.к. ее значение –0,89 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. После пересчетов получим получим новую симплекс-таблицу:
| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | Х11 | БР |
| E | 0 | 0 | 0 | 0 | 0 | 0 | 0,938 | 0,94 | 0 | 1,25 | 1,89 | 35 |
| Х3 | 0 | 0 | 1 | 0 | 0 | 0 | 0,063 | -0,938 | 0 | 0,75 | 1,125 | 5 |
| X6 | 0 | 0 | 0 | 0 | 0 | 1 | 0,125 | 1,125 | 0 | -0,5 | -0,75 | 2 |
| X4 | 0 | 0 | 0 | 1 | 0 | 0 | -0,125 | -0,125 | 0 | 0,5 | -0,25 | 2 |
| X5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 4 |
| Х1 | 1 | 0 | 0 | 0 | 0 | 0 | 0,563 | 0,563 | 0 | -1,25 | 1,125 | 1 |
| Х9 | 0 | 0 | 0 | 0 | 0 | 0 | 0,125 | 0,125 | 1 | -0,5 | 0,25 | 0 |
| X2 | 0 | 1 | 0 | 0 | 0 | 0 | 0,375 | 0,375 | 0 | 0,5 | -2,25 | 2 |
Таблица 13. Симплекс-таблица №12.
Столбец решений не содержит отрицательных элементов, все переменные X1, X2, X3 , X4 , X5 , X6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно: (X1,X2,X3,X4,X5,X6)=(1,2,5,2,4,2), целевая функция при этом принимает максимальное значение: Е=35.
После проведенных вычислений, решив задачу оптимизации, мы получили следующие результаты: оптимальный план работы станков состоит в том, чтобы токарный станок работал 1 час над деталями типа 1, 2 часа над деталями типа 2 и 5 часов над деталями типа 3 за смену; станок-автомат должен работать 2 часа над деталями типа 1 , 4 часа над деталями типа 2 и 2 часа над деталями типа 3 за смену. При этом количество комплектов деталей, выпускаемых цехом, будет максимально и равно 35.
В результате проведенного анализа на чувствительность к изменению запаса времени работы токарного станка получили, что если запас времени работы этого станка будет находиться в пределах от 0 до 8 часов, то базис оптимального решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5).
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995.
2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.2. – Мн.: БГУИР, 1996.
3. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. - Мн.: БГУИР, 1997.
4. Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1986.
УСЛОВНЫЕ СОКРАЩЕНИЯ
БР – базисное решение
БП – базисная переменная
Условие задачи. Приложение.
+-----------------------------------------------------------------------+
¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦Вид огр.¦Значение¦
+--------+--------+--------+--------+--------+--------+--------+--------¦
¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ E ¦ ¦
+--------+--------+--------+--------+--------+--------+--------+--------¦
¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ == ¦ 0.00¦
¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ == ¦ 0.00¦
¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ <= ¦ 8.00¦
¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ <= ¦ 8.00¦
+-----------------------------------------------------------------------+
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ 1¦ E ¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ ¦ -W ¦ -4.00¦ 1.00¦ 2.00¦ -12.00¦ 3.00¦ 2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ ¦ X9 ¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦
¦ ¦ X10¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦
¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦
¦ ¦ X8 ¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 8.00¦
+----------------------------------------------------------------------------------------------------------+
Ведущий элемент находится в 4 столбце и 1 строке.
Вывод промежуточных результатов оптимизации.