Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

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. Составляем исходную симплекс-таблицу:

|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР |
|E |-1 |-1 |-2 |-3 |-3 |-2 |0 |0 |0 |0 |0 |
|-W |-4 |1 |2 |-12 |3 |2 |0 |0 |0 |0 |0 |
|X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 |
|X8 |0 |0 |0 |1 |1 |1 |0 |1 |0 |0 |8 |
|X9 |2 |-1 |0 |6 |-3 |0 |0 |0 |1 |0 |0 |
|X10 |2 |0 |-2 |6 |0 |-2 |0 |0 |0 |1 |0 |

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

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

6. Реализуем первый этап двухэтапного метода: с помощью процедур симплекс- метода выполняем максимизацию функции -W. При этом переменные, включаемые в базис, выбираются по W-строке (т.е. на каждом цикле в базис включается переменная, которой соответствует максимальный по модулю отрицательный элемент в W-строке; столбец, соответствующий этой переменной, становится ведущим). В нашем случае это столбец X4, т. к. коэффициент при этой переменной в W-строке равен –12. Ведущую строку определяем следующим образом: рассчитываем так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным. Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения: по переменной Х8
(8/1=8), Х9 (0/6=0) и Х10 (0/6=0). Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х9. После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца (в нашем случае он равен 6). Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка. Далее все преобразования выполняем по обычным формулам симплекс-метода или по "правилу прямоугольника".
Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W- строку и столбец решений. Получаем новую симплекс-таблицу:
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР |
|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 |
|X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 |
|X8 |-0,33|0,17 |0 |0 |1,5 |1 |0 |1 |-0,17|0 |8 |
|X4 |0,33 |-0,17 |0 |1 |-0,5 |0 |0 |0 |0,17 |0 |0 |
|X10 |0 |1 |-2 |0 |3 |-2 |0 |0 |-1 |1 |0 |

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

Мы получили новое решение (Х7,Х8,Х4,Х10)=(8,8,0,0). Это решение недопустимо, так как в базисе содержится искусственная переменная Х10.
Выполим очередную итерацию. По строке –W для включения в базис выбираем переменную X5 (т.к. –3 – максимальное по модулю отрицательное число).
Столбец X5 становится ведущим. По минимальному симплексному отношению (
8/1,5=5,33; 0/3=0) для исключения из базиса выбираем переменную Х10.
Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу:

|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР |
|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 |
|X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 |
|X8 |-0,33|-0,33 |1 |0 |0 |2 |0 |1 |0,33 |-0,5 |8 |
|X4 |0,33 |0 |-0,33|1 |0 |-0.33|0 |0 |0 |0,17 |0 |
|X5 |0 |0,33 |-0,67|0 |1 |-0,67|0 |0 |-0,33|0,33 |0 |

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

4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА

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

|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |БР |
|E |0 |0 |-5 |0 |0 |-5 |0 |0 |0 |
|X7 |1 |1 |1 |0 |0 |0 |1 |0 |8 |
|X8 |-0,33|-0,33 |1 |0 |0 |2 |0 |1 |8 |
|X4 |0,33 |0 |-0,33 |1 |0 |-0,33 |0 |0 |0 |
|X5 |0 |0,33 |-0,67 |0 |1 |-0,67 |0 |0 |0 |

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

Наше начальное допустимое решение не является оптимальным, так как в Е- строке содержатся отрицательные коэффициенты. Определим по Е-строке новую переменную для включения в базис. Это переменная X3, т.к. –5 – максимальное по модулю отрицательное число (коэффициент Е-строки при переменной X6 также равен –5, поэтому выбрали любую из этих переменных, например X3). Столбец
X3 становится ведущим. По минимальному симплексному отношению ( 8/1=8;
8/1=8) для исключения из базиса выбираем переменную Х7 (симплексное отношение при переменной X8 также равно 8, поэтому выбрали любую из этих переменных). Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу:
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |БР |
|E |5 |5 |0 |0 |0 |-5 |5 |0 |40 |
|X3 |1 |1 |1 |0 |0 |0 |1 |0 |8 |
|X8 |-1,33|-1,33 |0 |0 |0 |2 |-1 |1 |0 |
|X4 |0,67 |0,33 |0 |1 |0 |-0,33 |0,33 |0 |2,67 |
|X5 |0,67 |1 |0 |0 |1 |-0,67 |0,67 |0 |5,33 |

Рекомендуем скачать другие рефераты по теме: банковские рефераты, контрольные 1 класс.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки