Второй этап двухэтапного симлекс-метода

 

Итак, как видно из Таблицы 4, все искусственные переменные вышли из базиса, искусственная целевая функция обнулилась – значит, первый этап двухэтапного симплекс-метода закончен, найдено начальное допустимое решение: (Х 1,X 2,X 3,X 4,X 5,X 6) = (0,0,0,0,0,0), целевая функция Е=0. Теперь переходим к реализации второго этапа: вычеркиваем из таблицы строку искусственной целевой функции и столбцы искусственных переменных; над новой таблицей выполняем обычные процедуры симплекс-метода, а именно: ведущий столбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулю отрицательный коэффициент находим по Е- строке целевой функции. Расчет ведем до тех пор, пока в Е- строке не останется отрицательных коэффициентов:

 

БП	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	БР
E	0	0	-5	0	0	-5	0	0	0
X 7	1	1	1	0	0	0	1	0	8
X 8	-0,33	-0,33	1	0	0	2	0	1	8
X 4	0,33	0	-0,33	1	0	-0,33	0	0	0
X 5	0	0,33	-0,67	0	1	-0,67	0	0	0

Таблица 5. Симплекс-таблица №4.

Наше начальное допустимое решение не является оптимальным, так как в Е- строке содержатся отрицательные коэффициенты. Определим по Е- строке новую переменную для включения в базис. Это переменная X 3, т.к. –5 – максимальное по модулю отрицательное число (коэффициент Е- строки при переменной X 6 также равен –5, поэтому выбрали любую из этих переменных, например X 3). Столбец X 3 становится ведущим. По минимальному симплексному отношению (8/1=8; 8/1=8) для исключения из базиса выбираем переменную Х 7 (симплексное отношение при переменной X 8 также равно 8, поэтому выбрали любую из этих переменных). Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу:

БП	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	БР
E	5	5	0	0	0	-5	5	0	40
X 3	1	1	1	0	0	0	1	0	8
X 8	-1,33	-1,33	0	0	0	2	-1	1	0
X 4	0,67	0,33	0	1	0	-0,33	0,33	0	2,67
X 5	0,67	1	0	0	1	-0,67	0,67	0	5,33

Таблица 6. Симплекс-таблица №5.

Итак, как видно из таблицы, некоторые из искомых переменных, а именно Х 3, Х 4 и Х 5, начали расти, что привело и к росту значения целевой функции – из нулевого значения она приняла значение 40. Это можно объяснить тем, что из точки начального допустимого решения мы перешли к соседней угловой точке области допустимых решений, причем в этой соседней точке рост целевой функции максимален. Однако в Е- строке есть еще отрицательный коэффициент, поэтому продолжим расчеты.

Определим по Е- строке новую переменную для включения в базис. Это переменная X 6, т.к. –5 – максимальное по модулю отрицательное число. Столбец X 6 становится ведущим. По минимальному симплексному отношению (0/2=0) для исключения из базиса выбираем переменную Х 8. Получаем новую симплекс-таблицу:

БП	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	40
X 3	1	1	1	0	0	0	1	0	8
X 6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0
X 4	0,44	0,11	0	1	0	0	0,17	0,17	2,67
X 5	0,22	0,55	0	0	1	0	0,33	0,33	5,33

Таблица 7. Симплекс-таблица №6.

    Так как все коэффициенты E- строки таблицы 7 положительные, то оптимальное решение найдено. Оптимальный план состоит в том, чтобы токарный станок работал над деталями типа 3 8 часов за смену, то есть всю рабочую смену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат должен работать за смену 2,67 часа над деталями типа 1 и 5,33 часа над деталями типа 2 и не должен работать над деталями типа 3. При этом за смену будет выпускаться максимально возможное количество комплектов деталей, а именно 40 комплектов. Ни один из станков не будет простаивать.

 

 

А НАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

В окончательной симплекс-таблице, содержащей оптимальное решение, содержится не только само оптимальное решение, но и другая информация. На основе последней симплекс-таблицы решаются задачи анализа на чувствительность - определение влияния изменений в исходных данных задачи на оптимальное решение. Интерпретация симплекс-таблицы и анализ на чувствительность полностью зависят от содержательного смысла конкретной задачи. В нашем случае мы имеем дело с задачей о распределения ресурсов, а именно ресурсов времени.

 

СТАТУС РЕСУРСОВ

 

По статусу ресурсы делятся на дефицитные и недефицитные. Если некоторый ресурс при реализации оптимального плана расходуется полностью, он называется дефицитным, если не полностью - недефицитным.

Статус ресурсов определяется по значениям остаточных переменных Х 7 и Х 8, введенных в исходную систему ограничений для приведения ее к стандартной форме. Эти переменные означают остатки ресурсов при реализации оптимального плана. Ни одна из остаточных переменных не входит в оптимальное решение, т.е. их значения равны нулю. Это означает, что токарный станок и станок-автомат использовались все выделенное для их работы время, т.е. запасы времени работы станков являются дефицитными ресурсами. Увеличение запасов дефицитных ресурсов позволяет увеличить значение целевой функции, а снижение этих запасов приводит к уменьшению целевой функции.

 

Ц ЕННОСТЬ РЕСУРСОВ

Ценность ресурса - это величина увеличения значения целевой функции при увеличении запасов данного ресурса на единицу (или соответственно величина уменьшения целевой функции при снижении запаса ресурса). Другое название этой величины - теневая (скрытая) цена. В симплекс-таблице, соответствующей оптимальному решению, теневые цены содержатся в E-строке и представляют собой коэффициенты при остаточных переменных, соответствующим остаткам ресурсов. Таким образом, ценность времени работы токарного станка и станка-автомата соответственно равна по 2,5 комплекта деталей. Другими словами, если запас времени работы токарного станка увеличить (уменьшить) на 1 час, то количество производимых комплектов деталей увеличится (уменьшится) на 2,5 единицы, и, аналогично, если увеличить (уменьшить) время работы станка-автомата станка на 1 час, то количество комплектов увеличится (уменьшится) на 2,5 комплекта.

 

123	Поделиться:

Воспользуйтесь поиском по сайту: