Реферат: Решение оптимизационной задачи линейного программирования
Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимое решение. Для этого воспользуемся двухэтапным симплекс-методом.
4.4. ПЕРВЫЙ ЭТАП ДВУХЭТАПНОГО СИМПЛЕКС-МЕТОДА
Итак, на первом этапе двухэтапного метода отыскивается начальное допустимое решение. Для этого выполним следующие действия:
1. Строим искусственную целевую функцию – сумму всех искусственных
переменных:
W = X9 + X10Þ min
2. Так как целевая функция должна быть выражена только через небазисные
переменные, то выражаем искусственные переменные X9 и X10 через небазисные переменные, а затем, упростив полученное выражение, переписываем искусственную целевую функцию:
X9 = - 2 X1 + X2 - 6 X4 + 3 X5;
X10 = - 2 X1 + 2 X3 - 6 X4 + 2 X6.
W = - 4 X1 + X2 + 2 X3 – 12 X4 + 3 X5 + 2 X6Þ min
3. Для приведения к стандартной форме направим искусственную целевую
функцию на максимум, для этого умножим обе ее части на –1 :
-W = 4 X1 - X2 - 2 X3 + 12 X4 - 3 X5 - 2 X6Þ max
4. Определяем начальное, недопустимое решение. Базис состоит из четырех
переменных, из них две искусственные, остальные две - остаточные. Базисные переменные принимают значения, равные ограничениям задачи. Остальные переменные считаем равными нулю. В этом случае целевая функция Е принимает значение 0 , искусственная целевая функция – W также принимает значение 0.
5. Составляем исходную симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | БР |
| E | -1 | -1 | -2 | -3 | -3 | -2 | 0 | 0 | 0 | 0 | 0 |
| -W | -4 | 1 | 2 | -12 | 3 | 2 | 0 | 0 | 0 | 0 | 0 |
| X 7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 |
| X 8 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 8 |
| X 9 | 2 | -1 | 0 | 6 | -3 | 0 | 0 | 0 | 1 | 0 | 0 |
| X 10 | 2 | 0 | -2 | 6 | 0 | -2 | 0 | 0 | 0 | 1 | 0 |
Таблица 2 . Симплекс-таблица №1.
Итак, в первом столбце таблицы указаны базисные переменные, в последнем столбце - их значения, а так же значения целевой и искусственной целевой функций. В заголовке таблицы перечисляются все используемые переменные. В строках таблицы указываются коэффициенты ограничений задачи.
6. Реализуем первый этап двухэтапного метода: с помощью процедур симплекс-
метода выполняем максимизацию функции - W . При этом переменные, включаемые в базис, выбираются по W-строке (т.е. на каждом цикле в базис включается переменная, которой соответствует максимальный по модулю отрицательный элемент в W-строке; столбец, соответствующий этой переменной, становится ведущим). В нашем случае это столбец X 4 , т. к. коэффициент при этой переменной в W-строке равен –12 . Ведущую строку определяем следующим образом: рассчитываем так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным. Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения: по переменной Х 8 (8/1=8 ), Х 9 (0/6=0 ) и Х 10 (0/6=0 ). Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х 9 . После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца (в нашем случае он равен 6 ). Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка. Далее все преобразования выполняем по обычным формулам симплекс-метода или по "правилу прямоугольника". Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | БР |
| E | 0 | -1,5 | -2 | 0 | -4,5 | -2 | 0 | 0 | 0,5 | 0 | 0 |
| -W | 0 | -1 | 2 | 0 | -3 | 2 | 0 | 0 | 2 | 0 | 0 |
| X 7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 |
| X 8 | -0,33 | 0,17 | 0 | 0 | 1,5 | 1 | 0 | 1 | -0,17 | 0 | 8 |
| X 4 | 0,33 | -0,17 | 0 | 1 | -0,5 | 0 | 0 | 0 | 0,17 | 0 | 0 |
| X 10 | 0 | 1 | -2 | 0 | 3 | -2 | 0 | 0 | -1 | 1 | 0 |
Таблица 3 . Симплекс-таблица №2.
Мы получили новое решение (Х 7 ,Х 8 ,Х 4 ,Х 10 )=(8,8,0,0) . Это решение недопустимо, так как в базисе содержится искусственная переменная Х 10 . Выполим очередную итерацию. По строке –W для включения в базис выбираем переменную X 5 (т.к. –3 – максимальное по модулю отрицательное число). Столбец X 5 становится ведущим. По минимальному симплексному отношению ( 8/1,5=5,33; 0/3=0) для исключения из базиса выбираем переменную Х 10 . Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу:
| БП | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | БР |
| E | 0 | 0 | -5 | 0 | 0 | -5 | 0 | 0 | -1 | 1,5 | 0 |
| -W | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| X 7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 |
| X 8 | -0,33 | -0,33 | 1 | 0 | 0 | 2 | 0 | 1 | 0,33 | -0,5 | 8 |
| X 4 | 0,33 | 0 | -0,33 | 1 | 0 | -0.33 | 0 | 0 | 0 | 0,17 | 0 |
| X 5 | 0 | 0,33 | -0,67 | 0 | 1 | -0,67 | 0 | 0 | -0,33 | 0,33 | 0 |
Таблица 4 . Симплекс-таблица №3.
4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА
Итак, как видно из Таблицы 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 комплектов. Ни один из станков не будет простаивать.
5. А НАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ
В окончательной симплек