 |
Метод Гомори для частично целочисленных задач
|
|
|
|
Метод Гомори для нахождения целочисленного решения относится к большой группе методов, называемых методами отсечений. Эти методы основаны на введении в задачу дополнительных ограничений, позволяющих учесть требование целочисленности. Основная идея методов отсечений состоит в том, что на полученное оптимальное нецелочисленное решение накладывается дополнительное ограничение, которое делает это решение недопустимым, но и не отсекает ни одного целочисленного решения от области допустимых решений.
Ограничения составляются по финальной симплекс-таблице, в которой получено оптимальное нецелочисленное решение. При этом на первоначальную систему ограничений накладывается новое ограничение по следующей формуле:
L1*W1 + L2*W2 + … +Ln*Wn ≥ {Bi}, где
Aij, если Aij≥0 и Wj может быть дробной, (1)
({Bi}*Aij)/({Bi}-1), если Aij<0 и Wj может быть дробной, (2)
Lj = {Aij}, если {Aij}£{Bi} и Wi должна быть целой, (3)
{Bi}*(1-{Aij})/(1-{Bi}), если {Aij}>{Bi} и Wi должна быть целой, (4)
j=1,…,n
где Wn – небазисная переменная;
Bi - базисная переменная, имеющая максимальную дробную часть (дробная часть числа – это разность между этим числом и максимальным целым числом, не превосходящим его);
Aij – коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной;
Далее полученное ограничение приводится к стандартному виду:
-L1*W1 - L2*W2 - … -Ln*Wn + Sr = -{Bi}
где r – номер итерации алгоритма.
Здесь Sr – неотрицательная остаточная переменная, не имеющая никакого содержательного смысла; в оптимальном целочисленном решении эта переменная оказывается равной нулю.
|
|
|
В нашем случае переменная, имеющая максимальную дробную часть – это Х 4 ({2,67}=0,67), она должна быть целой, переменные Х 7 и Х 8 могут быть дробными, переменные Х 1 и Х 2 должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение. Так как все коэффициенты на пересечениях базисной переменной Х 4 и небазисных переменных Х 1, Х 2, Х 7, Х 8 ≥ 0 (0,44≥0, 0,11≥0, 0,17≥0), то коэффициенты при переменных Х 1 и Х 2 рассчитали по формуле (3): L 1 ={0,44}=0,44, L 2 ={0,11}=0,11, а коэффициенты при переменных Х 7 и Х 8 рассчитали по формуле (1): L 3 =0,17, L 4 =0,17. { В 4 }={ Х 4 } = {2,67} = 0,67. Ограничение будет иметь вид:
0,44 Х1 + 0,11 Х2 + 0,17 Х7 + 0,17 Х8 ≥ 0,67
Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым (если подставить Х1=0, Х2=0, Х7=0, Х8=0, - значения переменных, полученных в оптимальном нецелочисленном решении, то получим 0≥0,67 – неверно).
Приведя ограничение к стандартному виду, имеем:
-0,44 Х1 - 0,11 Х2 - 0,17 Х7 - 0,17 Х8 + Х9 = - 0,67
Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х 9:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | БР |
| E | 1,67 | 1,67 | 0 | 0 | 0 | 0 | 2,5 | 2,5 | 0 | 40 |
| X 3 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 8 |
| X 6 | -0,67 | -0,67 | 0 | 0 | 0 | 1 | -0,5 | 0,5 | 0 | 0 |
| X 4 | 0,44 | 0,11 | 0 | 1 | 0 | 0 | 0,17 | 0,17 | 0 | 2,67 |
| Х 5 | 0,22 | 0,55 | 0 | 0 | 1 | 0 | 0,33 | 0,33 | 0 | 5,33 |
| X 9 | -0,44 | -0,11 | 0 | 0 | 0 | 0 | -0,17 | -0,17 | 1 | -0,67 |
Таблица 8. Симплекс-таблица №7.
Как видно, полученная симплекс-таблица содержит недопустимое решение (переменная Х 9 имеет отрицательное значение). Произведем дальнейший пересчет таблицы, причем ведущую строку определяем максимальным по модулю отрицательным элементом столбца решений, а ведущий столбец – минимальным по модулю отношением элемента Е- строки к отрицательным элементам ведущей строки. Пересчет симплекс-таблицы осуществляется на основе стандартных процедур симплекс-метода.
|
|
|
Итак, переменная, исключаемая из базиса – это X 9, т.к. ее значение –0,67 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X 1, т.к. |1,67/(-0,44)|=3,8, |1,67/(-0,11)|=15,2, |2,5/(-0,17)|=14,7, 3,8 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. Получим новую симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | БР |
| E | 0 | 1,25 | 0 | 0 | 0 | 0 | 1,875 | 1,875 | 3,75 | 37,5 |
| X 3 | 0 | 0,75 | 1 | 0 | 0 | 0 | 0,625 | -0,375 | 2,25 | 6,5 |
| X 6 | 0 | -0,5 | 0 | 0 | 0 | 1 | -0,25 | 0,75 | -1,5 | 1 |
| X 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 2 |
| Х 5 | 0 | 0,5 | 0 | 0 | 1 | 0 | 0,25 | 0,25 | 0,5 | 5 |
| X 1 | 1 | 0,25 | 0 | 0 | 0 | 0 | 0,375 | 0,375 | -2,25 | 1,5 |
Таблица 9. Симплекс-таблица №8.
Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменная Х 1, переменные Х 3, Х 4 и Х 5 уменьшили свое значение, а переменная Х 6 увеличилась. Значение целевой функции уменьшилось и стало равно 37,5, что объясняется тем, что оптимальное нецелочисленное решение было отсечено нашим дополнительным ограничением, и для поиска оптимального целочисленного решения мы ушли вглубь области допустимых решений, где значение целевой функции меньше оптимального. Наше решение все еще нецелочисленное, поэтому составим новое ограничение.
Переменная, имеющая максимальную дробную часть – это Х 3 ({6,5}=0,5) (Х 1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х 3), она должна быть целой, переменные Х 7, Х 8 и Х 9 могут быть дробными, переменная Х 2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х 3 и небазисных переменных Х 2, Х 7, Х 9 ≥ 0 (0,75≥0, 0,625≥0, 2,25≥0), то коэффициент при переменной Х 2 рассчитаем по формуле (3): L 1 ={0,75}=0,75, коэффициенты при переменных Х 7 и Х 9 рассчитаем по формуле (1): L 3 =0,625, L 4 =2,25. Так как коэффициент на пересечении базисной переменной Х 3 и небазисной переменной Х 8 <0, то коэффициент при переменной Х 8 рассчитаем по формуле (2): L 2 =({6,5}*(-0,375))/({6,5}-1)=0,375. { В 3 }={ Х 3 } = {6,5} = 0,5. Ограничение будет иметь вид:
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
Добавим это ограничение к нашей предыдущей симплекс-таблице:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | БР |
| 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 |
| X 6 | 0 | -0,5 | 0 | 0 | 0 | 1 | -0,25 | 0,75 | -1,5 | 0 | 1 |
| X 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 2 |
| X 5 | 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 |
| X 10 | 0 | -0,25 | 0 | 0 | 0 | 0 | -0,375 | -0,375 | -2,25 | 1 | -0,5 |
Таблица 10. Симплекс-таблица №9.
Переменная, исключаемая из базиса – это X 10, т.к. ее значение –0,5 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X 9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –2,25. Получим новую симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | БР |
| 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 |
| X 6 | 0 | -0,33 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | -0,67 | 1,33 |
| X 4 | 0 | 0,111 | 0 | 1 | 0 | 0 | -0,17 | -0,17 | 0 | 0,44 | 1,78 |
| X 5 | 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 |
| X 9 | 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, X 7, X 8, Х 10 ≥0 (0,44≥0, 0,17≥0, 0,22≥0), то коэффициент при переменной Х 2 рассчитаем по формуле (3): L 1 ={0,44}=0,44, коэффициенты при переменных Х 7, Х 9 и Х 10 рассчитаем по формуле (1): L 2 =0,17, L 3 =0,17, L 4 =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
Добавим это ограничение к нашей предыдущей симплекс-таблице:
|
|
|
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | Х 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 |
| X 6 | 0 | -0,3 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | -0,67 | 0 | 1,33 |
| X 4 | 0 | 0,11 | 0 | 1 | 0 | 0 | -0,17 | -0,17 | 0 | 0,44 | 0 | 1,78 |
| X 5 | 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 |
| X 11 | 0 | -0,44 | 0 | 0 | 0 | 0 | -0,17 | -0,17 | 0 | -0,22 | 1 | -0,89 |
Таблица 12. Симплекс-таблица №11.
Переменная, исключаемая из базиса – это X 11, т.к. ее значение –0,89 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X 2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. После пересчетов получим получим новую симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | Х 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 |
| X 6 | 0 | 0 | 0 | 0 | 0 | 1 | 0,125 | 1,125 | 0 | -0,5 | -0,75 | 2 |
| X 4 | 0 | 0 | 0 | 1 | 0 | 0 | -0,125 | -0,125 | 0 | 0,5 | -0,25 | 2 |
| X 5 | 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 |
| X 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0,375 | 0,375 | 0 | 0,5 | -2,25 | 2 |
Таблица 13. Симплекс-таблица №12.
Столбец решений не содержит отрицательных элементов, все переменные X 1, X 2, X 3, X 4, X 5, X 6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно: (X 1,X 2, X 3,X 4,X 5,X 6)=(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 строке.
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 2¦ E ¦ 0.00¦ -1.50¦ -2.00¦ 0.00¦ -4.50¦ -2.00¦ 0.00¦ 0.00¦ 0.50¦ 0.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ -W ¦ 0.00¦ -1.00¦ 2.00¦ 0.00¦ -3.00¦ 2.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
¦ ¦ X4 ¦ 0.33¦ -0.17¦ 0.00¦ 1.00¦ -0.50¦ 0.00¦ 0.00¦ 0.00¦ 0.17¦ 0.00¦ 0.00¦
¦ ¦ X10¦ 0.00¦ 1.00¦ -2.00¦ 0.00¦ 3.00¦ -2.00¦ 0.00¦ 0.00¦ -1.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.33¦ 0.17¦ 0.00¦ 0.00¦ 1.50¦ 1.00¦ 0.00¦ 1.00¦ -0.17¦ 0.00¦ 8.00¦
+----------------------------------------------------------------------------------------------------------+
Ведущий элемент находится в 5 столбце и 2 строке.
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -1.00¦ 1.50¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
¦ ¦ -W ¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦ 0.00¦ 0.00¦ 0.17¦ 0.00¦
¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦ 0.00¦ -0.33¦ 0.33¦ 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.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 1.00¦ 0.33¦ -0.50¦ 8.00¦
+----------------------------------------------------------------------------------------------------------+
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦ 0.00¦ 0.00¦
¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦
¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦
¦ ¦ X8 ¦ -0.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 1.00¦ 8.00¦
+----------------------------------------------------------------------------------------+
Ведущий элемент находится в 3 столбце и 3 строке.
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ 4¦ E ¦ 5.00¦ 5.00¦ 0.00¦ 0.00¦ 0.00¦ -5.00¦ 5.00¦ 0.00¦ 40.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ ¦ X4 ¦ 0.67¦ 0.33¦ 0.00¦ 1.00¦ 0.00¦ -0.33¦ 0.33¦ 0.00¦ 2.67¦
¦ ¦ X5 ¦ 0.67¦ 1.00¦ 0.00¦ 0.00¦ 1.00¦ -0.67¦ 0.67¦ 0.00¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦
¦ ¦ X8 ¦ -1.33¦ -1.33¦ 0.00¦ 0.00¦ 0.00¦ 2.00¦ -1.00¦ 1.00¦ 0.00¦
+----------------------------------------------------------------------------------------+
Ведущий элемент находится в 6 столбце и 4 строке.
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ 5¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦ 2.50¦ 40.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦ 0.17¦ 2.67¦
¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦ 0.33¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 8.00¦
¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦ 0.50¦ 0.00¦
+----------------------------------------------------------------------------------------+
Результаты оптимизации.
Базис Значение
X4 2.67
X5 5.33
X3 8.00
X6 0.00
Максимум функции равен 40.00
Вывод промежуточных результатов оптимизации.
+-------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+---
¦ 1¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦ 2.50¦ 0.00¦ 40.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦ 0.17¦ 0.00¦ 2.67¦
¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦ 0.33¦ 0.00¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 8.00¦
¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦ 0.50¦ 0.00¦ 0.00¦
¦ ¦ X9 ¦ -0.44¦ -0.11¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ 1.00¦ -0.67¦
+-------------------------------------------------------------------------------------------------+
Ведущий элемент находится в 1 столбце и 5 строке.
Вывод промежуточных результатов оптимизации.
+-------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦ 1.88¦ 3.75¦ 37.50¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦ -0.00¦ 1.00¦ 2.00¦
¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦ 0.25¦ 0.50¦ 5.00¦
¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦ -0.38¦ 2.25¦ 6.50¦
¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦ 0.75¦ -1.50¦ 1.00¦
¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -2.25¦ 1.50¦
+-------------------------------------------------------------------------------------------------+
Результаты оптимизации.
Базис Значение
X4 2.00
X5 5.00
X3 6.50
X6 1.00
X1 1.50
Максимум функции равен 37.50
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦ 1.88¦ 3.75¦ 0.00¦ 37.50¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦ -0.00¦ 1.00¦ 0.00¦ 2.00¦
¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦ 0.25¦ 0.50¦ 0.00¦ 5.00¦
¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦ -0.38¦ 2.25¦ 0.00¦ 6.50¦
¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦ 0.75¦ -1.50¦ 0.00¦ 1.00¦
¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -2.25¦ 0.00¦ 1.50¦
¦ ¦ X10¦ 0.00¦ -0.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.38¦ -0.38¦ -2.25¦ 1.00¦ -0.50¦
+----------------------------------------------------------------------------------------------------------+
Ведущий элемент находится в 9 столбце и 6 строке.
Вывод промежуточных результатов оптимизации.
+----------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 3¦ E ¦ -0.00¦ 0.83¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.25¦ 1.25¦ -0.00¦ 1.67¦ 36.67¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ X4 ¦ -0.00¦ -0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ -0.00¦ 0.44¦ 1.78¦
¦ ¦ X5 ¦ -0.00¦ 0.44¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.17¦ 0.17¦ -0.00¦ 0.22¦ 4.89¦
¦ ¦ X3 ¦ -0.00¦ 0.50¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.25¦ -0.75¦ -0.00¦ 1.00¦ 6.00¦
¦ ¦ X6 ¦ -0.00¦ -0.33¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ 1.00¦ -0.00¦ -0.67¦ 1.33¦
¦ ¦ X1 ¦ 1.00¦ 0.50¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.75¦ 0.75¦ -0.00¦ -1.00¦ 2.00¦
¦ ¦ X9 ¦ -0.00¦ 0.11¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.17¦ 0.17¦ 1.00¦ -0.44¦ 0.22¦
+----------------------------------------------------------------------------------------------------------+
Результаты оптимизации.
Базис Значение
X4 1.78
X5 4.89
X3 6.00
X6 1.33
X1 2.00
X9 0.22
Максимум функции равен 36.67
Вывод промежуточных результатов оптимизации.
+-------------------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦ X11 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 3¦ E ¦ -0.00¦ 0.83¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.25¦ 1.25¦ -0.00¦ 1.67¦ 0.00¦ 36.67¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-
¦ ¦ X4 ¦ -0.00¦ -0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ -0.00¦ 0.44¦ 0.00¦ 1.78¦
¦ ¦ X5 ¦ -0.00¦ 0.44¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.17¦ 0.17¦ -0.00¦ 0.22¦ 0.00¦ 4.89¦
¦ ¦ X3 ¦ -0.00¦ 0.50¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.25¦ -0.75¦ -0.00¦ 1.00¦ 0.00¦ 6.00¦
¦ ¦ X6 ¦ -0.00¦ -0.33¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ 1.00¦ -0.00¦ -0.67¦ 0.00¦ 1.33¦
¦ ¦ X1 ¦ 1.00¦ 0.50¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.75¦ 0.75¦ -0.00¦ -1.00¦ 0.00¦ 2.00¦
¦ ¦ X9 ¦ -0.00¦ 0.11¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.17¦ 0.17¦ 1.00¦ -0.44¦ 0.00¦ 0.22¦
¦ ¦ X11¦ 0.00¦ -0.44¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.17¦ -0.17¦ 0.00¦ -0.22¦ 1.00¦ -0.89¦
+-------------------------------------------------------------------------------------------------------------------+
Ведущий элемент находится в 2 столбце и 7 строке.
Вывод промежуточных результатов оптимизации.
+-------------------------------------------------------------------------------------------------------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦ X11 ¦Баз.Реш.¦
+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--
¦ 4¦ E ¦ -0.00¦ -0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.94¦ 0.94¦ -0.00¦ 1.25¦ 1.88¦ 35.00¦
¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
¦ ¦ X4 ¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦ -0.00¦ -0.12¦ -0.12¦ -0.00¦ 0.50¦ -0.25¦ 2.00¦
¦ ¦ X5 ¦ -0.00¦ -0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ 4.00¦
¦ ¦ X3 ¦ -0.00¦ -0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.06¦ -0.94¦ -0.00¦ 0.75¦ 1.13¦ 5.00¦
¦ ¦ X6 ¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ 0.12¦ 1.12¦ -0.00¦ -0.50¦ -0.75¦ 2.00¦
¦ ¦ X1 ¦ 1.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.56¦ 0.56¦ -0.00¦ -1.25¦ 1.12¦ 1.00¦
¦ ¦ X9 ¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.12¦ 0.12¦ 1.00¦ -0.50¦ 0.25¦ 0.00¦
¦ ¦ X2 ¦ -0.00¦ 1.00¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦ 0.38¦ -0.00¦ 0.50¦ -2.25¦ 2.00¦
+-------------------------------------------------------------------------------------------------------------------+
Результаты оптимизации.
Базис Значение
X4 2.00
X5 4.00
X3 5.00
X6 2.00
X1 1.00
X9 0.00
X2 2.00
Максимум функции равен 35.00
|
|
|
