Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2018-01-29 | 183 |
5.00
из
|
Заказать работу |
|
|
При решении общей задачи линейного программирования методом Штифеля мы должны проделать следующие шаги:
1) переместить нули из правого заглавного столбца, в верхнюю заглавную строку (при этом столбец, в верхнюю часть которого попадает ноль, вычеркивается);
2) переместить все неограниченные на знак переменные из верхней заглавной строки, в правый заглавный столбец (при этом строка, в которую попадает такая переменная, запоминается, а затем вычеркивается);
3) добиться того, чтобы свободные члены, расположенные в последнем столбце таблицы, были неотрицательны (выйти в область планов) или доказать, что задача не имеет решения из-за отсутствия планов;
4) добиться того, чтобы оценки свободных переменных, расположенные в нижней строке таблицы, стали неотрицательными (найти оптимальный опорный план) или доказать, что задача не имеет решения из-за неограниченности функции цели.
Причем первый и второй этапы желательно проделать одновременно.
Пример 4.2. Найти максимум функции цели
z (X) = - 8 x 1 + x 2 + 6 x 3 + x 4 + 7 x 5 ® max, (4.4)
при условии, что
– 2 x 1 + x 2 + 2 x 3 - x 4 + x 5 £ – 4,
x 1 + 4 x 2 + x 3 – 2 x 4 – 2 x 5 = – 8, (4.5)
– 3 x 1 – x 2 + 2 x 3 + x 4 + 3 x 5 £ – 2,
x 1, x 3, x 4, x 5 ³ 0.
Решение. Перепишем систему ограничений (4.5) в виде:
2 x 1 – x 2 – 2 x 3 + x 4 – x 5 – 4 = y 1,
– x 1 – 4 x 2 – x 3 + 2 x 4 + 2 x 5 – 8 = 0, (4.6)
3 x 1 + x 2 – 2 x 3 – x 4 – 3 x 5 – 2 = y 2,
x 1, x 3, x 4, x 5, y 1, y 2 ³ 0.
Решим данную задачу методом Штифеля:
– x 1 | – x 2 | – x 3 | – x 4 | – x 5 | – x 1 | – x 2 | – x 3 | – x 4 | |||||
y 1 | –2 | –1 | –4 | y 1 | –3/2 | 5/2 | –2 | –8 | |||||
–2 | –2 | –8 | x 5 | –1/2 | –2 | –1/2 | |||||||
y 2 | –3 | –1 | –2 | y 2 | –3/2 | 7/2 | –2 | –14 | |||||
z | –1 | –6 | –1 | –7 | z | 9/2 | –15 | –19/2 |
Табл. 4.7. Табл. 4.8.
|
На первом шаге (при переходе от табл. 4.7 к табл. 4.8) свободная переменная x 5 меняется на базисную переменную 0. При попадании нуля на верх соответствующий столбец можно исключить из таблицы.
На втором шаге (при переходе от табл. 4.8 к табл. 4.9) свободная переменная x 2 меняется на базисную переменную y 2. После этого строку, соответствующую переменной x 2, можно, предварительно запомнив, исключить из таблицы 4.9. Таким образом, мы приходим к таблице 4.10:
– x 1 | – y 2 | – x 3 | – x 4 | |||||||||
y 1 | –0,6 | –0,6 | 0,4 | –0,8 | 0,4 | – x 1 | – y 2 | – x 3 | – x 4 | |||
x 5 | –1,1 | 0,4 | 0,9 | 0,2 | –1,6 | y 1 | –0,6 | –0,6 | 0,4 | –0,8 | 0,4 | |
x 2 | –0,3 | 0,2 | 0,7 | –0,4 | –2,8 | x 5 | –1,1 | 0,4 | 0,9 | 0,2 | –1,6 | |
z | –14 | z | –14 |
Табл. 4.9. Табл. 4.10.
На данном этапе завершается упрощение задачи. Заметим, что упрощение задачи можно было сделать иначе. На первом же шаге можно было базисную переменную 0 заменить на свободную переменную x 2. Тем самым, мы могли сэкономить один шаг.
До сих пор мы не следили за значениями функции цели и за оценками свободных и базисных переменных. На втором этапе обратим внимание на оценки базисных переменных y 1 и x 5, то есть на числа 0,4 и – 1,6 из последнего столбца таблицы 4. Среди этих чисел есть отрицательное
(–1,6). Просматривая другие элементы строки, соответствующей базисной переменной x 5, находим среди них еще одно отрицательное –1.1 (если бы такого отрицательного числа не нашлось, то задача не имела бы решения из-за отсутствия планов). Вычислим минимальное симплексное отношение для первого столбца, в котором находится отрицательное число –1,1. В данном случае оно, очевидно, равно (–1,6):(–1,1) = 16/11, и разрешающим элементом является число –1,1. После очередного пересчета приходим к таблице:
– x 5 | – y 2 | – x 3 | – x 4 | ||
y 1 | –6/11 | –9/11 | –1/11 | –1/11 | 14/11 |
x 1 | –10/11 | –4/11 | –9/11 | –2/11 | 16/11 |
z | –14 |
Табл. 4.11.
|
Теперь обе оценки базисных переменных положительны и, следовательно, мы вышли в область планов. Так как все оценки свободных переменных неотрицательны, то данный план является оптимальным. Причем он является единственным оптимальным планом данной задачи, несмотря на наличие нулевых оценок. Действительно, при попытке заменить любую из свободных переменных x 5 или x 4, имеющую нулевую оценку на любую из базисных переменных, нам пришлось бы в качестве разрешающего элемента выбрать отрицательное число, и тем самым выйти из области планов задачи. Таким образом, оптимальным планом задачи (4.6) является план с компонентами:
То есть, . При этом .
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!