Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2018-01-29 | 184 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!