Реферат: Решение оптимизационной задачи линейного программирования

Таблица 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¦

+-----------------------------------------------------------------------+

Вывод промежуточных результатов оптимизации.

+----------------------------------------------------------------------------------------------------------+

Страницы: 1, 2, 3, 4, 5, 6