Второй этап двухэтапного метода

Второй этап двухэтапного метода. найденное на шаге 4 допустимое решение используется в качестве начального решения исходной задачи для поиска ее оптимального решения. 4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ СИМПЛЕКС- ТАБЛИЦ 4.1. Приведение задачи к стандартной форме Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений неравенств к равенствам.

Для этого введем дополнительные балансовые неотрицательные переменные. Также для упрощения дальнейших вычислений разделим обе части ограничений на комплектацию деталей на 5 X1 X2 X3 X7 8 X4 X5 X6 X8 8 2X1 X2 6X4 3X5 0 2X1 2X3 6X4 2X6 0 X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8 0. E X1 X2 2X3 3X4 3X5 2X6 max где Х7 , Х8 остаточные переменные.

Итак, нашу исходную задачу мы привели к стандартной форме основной задачи линейного программирования. 4.2. Определение начального допустимого решения Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений.

Поэтому для нахождения начального решения задачи требуется выразить m переменных т.е. количество переменных, равное количеству уравнений через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных в заданной задаче m4 и n8. Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны некоторые из них могут оказаться равными нулю. Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением.

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

Итак, для нахождения начального допустимого решения необходимо, чтобы в каждое из уравнений входила переменная с коэффициентом 1 и не входила в другие уравнения базисная переменная. В нашем случае мы имеем только 2 базисные переменные X7 и X8 , не хватает еще двух базисных переменных. Их можно создать с помощью специального способа, который называется построением искусственного базиса. 4.3. Построение искусственного базиса Методы искусственного базиса предназначены для построения начального базиса т.е. для получения начального решения в случаях, когда его построение непосредственно на основе стандартной формы невозможно.

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

В нашем случае это 2X1 X2 6X4 3X5 Х9 0 2X1 2X3 6X4 2X6 Х10 0. где Х9 и Х10 искусственные переменные, не имеющие никакого физического смысла, причем Х9 , Х10 0. После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис Х7 , Х8 , Х9 , Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е. Х7 8 Х8 8 Х9 0 Х10 0. Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимое решение.

Для этого воспользуемся двухэтапным симплекс-методом. 4.4. ПЕРВЫЙ ЭТАП ДВУХЭТАПНОГО СИМПЛЕКС-МЕТОДА Итак, на первом этапе двухэтапного метода отыскивается начальное допустимое решение. Для этого выполним следующие действия 1. Строим искусственную целевую функцию сумму всех искусственных переменных W X9 X10 min 2. Так как целевая функция должна быть выражена только через небазисные переменные, то выражаем искусственные переменные X9 и X10 через небазисные переменные, а затем, упростив полученное выражение, переписываем искусственную целевую функцию X9 - 2X1 X2 - 6X4 3X5 X10 - 2X1 2X3 - 6X4 2X6. W - 4X1 X2 2X3 12X4 3X5 2X6 min 3. Для приведения к стандартной форме направим искусственную целевую функцию на максимум, для этого умножим обе ее части на 1 -W 4X1 - X2 - 2X3 12X4 - 3X5 - 2X6 max 4. Определяем начальное, недопустимое решение.

Базис состоит из четырех переменных, из них две искусственные, остальные две - остаточные. Базисные переменные принимают значения, равные ограничениям задачи.

Остальные переменные считаем равными нулю. В этом случае целевая функция Е принимает значение 0, искусственная целевая функция W также принимает значение 0. 5. Составляем исходную симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE-1-1-2-3-3-20- W-412-12320X711100010008X800011101008X92 -106-3000100X1020-260-200010Таблица 2. Симплекс-таблица 1. Итак, в первом столбце таблицы указаны базисные переменные, в последнем столбце - их значения, а так же значения целевой и искусственной целевой функций.

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

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

Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения по переменной Х8 818, Х9 060 и Х10 060. Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х9. После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца в нашем случае он равен 6. Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка.

Далее все преобразования выполняем по обычным формулам симплекс-метода или по правилу прямоугольника. Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE0-1,5-20-4,5-2 000,500-W0-120-3200200X711100010008X8-0, 330,17001,5101-0,1708X40,33-0,1701-0,500 00,1700X1001-203-200-110Таблица 3. Симплекс-таблица 2. Мы получили новое решение Х7,Х8,Х4,Х108,8,0,0. Это решение недопустимо, так как в базисе содержится искусственная переменная Х10. Выполим очередную итерацию.

По строке W для включения в базис выбираем переменную X5 т.к. 3 максимальное по модулю отрицательное число. Столбец X5 становится ведущим. По минимальному симплексному отношению 81,55,33 030 для исключения из базиса выбираем переменную Х10. Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE00-500-500-11, 50-W0110X711100010008X8-0,33-0,331002010 ,33-0,58X40,330-0,3310-0.330000,170X500, 33-0,6701-0,6700-0,330,330Таблица 4. Симплекс-таблица 3. 4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА Итак, как видно из Таблицы 4, все искусственные переменные вышли из базиса, искусственная целевая функция обнулилась значит, первый этап двухэтапного симплекс-метода закончен, найдено начальное допустимое решение Х1,X2,X3,X4,X5,X6 0,0,0,0,0,0, целевая функция Е0. Теперь переходим к реализации второго этапа вычеркиваем из таблицы строку искусственной целевой функции и столбцы искусственных переменных над новой таблицей выполняем обычные процедуры симплекс-метода, а именно ведущий столбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулю отрицательный коэффициент находим по Е-строке целевой функции.

Расчет ведем до тех пор, пока в Е-строке не останется отрицательных коэффициентов БПX1X2X3X4X5X6X7X8БРE00-500-5000X7111000 108X8-0,33-0,331002018X40,330-0,3310-0,3 3000X500,33-0,6701-0,67000Таблица 5. Симплекс-таблица 4. Наше начальное допустимое решение не является оптимальным, так как в Е-строке содержатся отрицательные коэффициенты.

Определим по Е-строке новую переменную для включения в базис.

Это переменная X3, т.к. 5 максимальное по модулю отрицательное число коэффициент Е-строки при переменной X6 также равен 5, поэтому выбрали любую из этих переменных, например X3. Столбец X3 становится ведущим.

По минимальному симплексному отношению 818 818 для исключения из базиса выбираем переменную Х7 симплексное отношение при переменной X8 также равно 8, поэтому выбрали любую из этих переменных. Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8БРE55000-55040X3111000 108X8-1,33-1,330002-110X40,670,33010-0,3 30,3302,67X50,671001-0,670,6705,33Таблиц а 6. Симплекс-таблица 5. Итак, как видно из таблицы, некоторые из искомых переменных, а именно Х3, Х4 и Х5, начали расти, что привело и к росту значения целевой функции из нулевого значения она приняла значение 40. Это можно объяснить тем, что из точки начального допустимого решения мы перешли к соседней угловой точке области допустимых решений, причем в этой соседней точке рост целевой функции максимален.

Однако в Е-строке есть еще отрицательный коэффициент, поэтому продолжим расчеты. Определим по Е-строке новую переменную для включения в базис.

Это переменная X6, т.к. 5 максимальное по модулю отрицательное число. Столбец X6 становится ведущим. По минимальному симплексному отношению 020 для исключения из базиса выбираем переменную Х8. Получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8БРE1,671,6700002,52,54 0X3111000108X6-0,67-0,670001-0,50,50X40, 440,1101000,170,172,67X50,220,5500100,33 0,335,33Таблица 7. Симплекс-таблица 6. Так как все коэффициенты E-строки таблицы 7 положительные, то оптимальное решение найдено.

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

Ни один из станков не будет простаивать. 5.