Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Если на первом этапе решение ВЗ закончилось случаем 1 или 2, то можно перейти ко второму этапу - решению исходной задачи.
(3.81)
(3.82)
(3.83)
так как расширенная матрица системы линейных уравнений (3.82) является К-матрицей.
РЕШЕНИЕ ЗАДАЧ
Вернемся к решению задачи из примера в начале темы. Для задачи (3.51)-(3.53) запишем ВЗ:
-(U1+U2+U3) max (3.84)
2X1+2X3+4X4+X5+U1=150
X1+X2+2X5+U2=200 (3.85)
X1+X3+2X6+U3=300
(3.86)
Результаты первого этапа представлены в табл. 3.6.
Таблица 3.6
-1 | -1 | -1 | ||||||||||||||
S | i | |||||||||||||||
-1 | 37.5 | |||||||||||||||
-1 | - | |||||||||||||||
-1 | - | |||||||||||||||
-650 | -2 | -3 | -3 | -4 | -3 | -2 | ||||||||||
37.5 | 0.5 | 0.5 | 0.25 | 0.25 | - | - | ||||||||||
-1 | - | |||||||||||||||
-1 | - | |||||||||||||||
-500 | -2 | -1 | -1 | -2 | -2 | |||||||||||
37.5 | 0.5 | 0.5 | 0.25 | 0.25 | - | |||||||||||
- | ||||||||||||||||
-1 | -1 | -2 | -1 | |||||||||||||
-100 | -1 | -2 | ||||||||||||||
37.5 | 0.5 | 0.5 | 0.25 | 0.25 | ||||||||||||
-0.5 | 0.5 | -1 | -0.5 | 0.5 | ||||||||||||
На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: =(200; 0; 0; 37.5; 0; 50; 0; 0; 0),
в котором ни одна из искусственных переменных не является базисной, следовательно, вектор =(200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К-матрицей.
На втором этапе решаем задачу
max(-0.4X1-0.3X2-0.1X3-0.1X5-0.2X6)
.
Решение приведено в табл. 3.7.
Таблица 3.7
-0.4 | -0.3 | -0.1 | -0.1 | -0.2 | |||||||
S | i | ||||||||||
37.5 | 0.5 | 0.5 | 0.25 | ||||||||
-0.4 | |||||||||||
-0.2 | -0.5 | 0.5 | -1 | - | |||||||
-90 | -0.5 | ||||||||||
12.5 | -0.125 | 0.375 | 0.5 | ||||||||
-0.1 | 0.5 | 0.5 | - | ||||||||
-0.2 | |||||||||||
-40 | 0.25 | 0.25 | |||||||||
-0.1 | -0.25 | 0.75 | |||||||||
-0.1 | 0.5 | ||||||||||
-0.2 | 137.5 | 0.625 | -0.375 | -1 | |||||||
-100 | 0.25 | 0.25 |
На первой итерации (табл. 3.7.) второго этапа получен оптимальный план исходной задачи 1=(0; 0; 12.5; 100; 150) и =40.
Так как =0, а вектор не является базисным, то его можно ввести в базис, и при этом в соответствии с формулой (3.28) значение целевой функции не изменится, т.е. на второй итерации можно получить еще один оптимальный план исходной задачи
2=(0; 0.25; 0; 100; 137.5) и =40.
Исходная задача имеет бесчисленное множество решений, задаваемое формулой (3.87)
Пример 3.15. Решить ЗЛП:
max(2X1-X2-X4)
X1-2X2+X3=10
-2X1-X2-2X4 18 (3.88)
3X1+2X2+X4 36
Приведем ЗЛП (3.88) к каноническому виду
max(2X1-X2-X4)
X1-2X2+X3=10
-2X1-X2-2X4- S1 =18 (3.89)
3X1+2X2+X4-S2 =36
Расширенная матрица системы линейных уравнений (3.89)
не является К-матрицей ЗЛП (3.89), т.к. не содержит единичной подматрицы.
Запишем вспомогательную задачу для ЗЛП (3.89). Т.к. матрица содержит один единичный вектор =(1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U1;U2 во второе и третье уравнения системы (3.89).
Итак, ВЗ имеет вид
-(U1+U2) max
X1-2X2+X3=10
-2X1-X2-2X4-X5+U1=18 (3.90)
3X1+2X2+X4-X6+U2=36
; U1,U2 0
Решение ВЗ приведено в табл 3.8.
Таблица 3.8
-1 | -1 | ||||||||||||
S | i | ||||||||||||
-1 | -2 | - | |||||||||||
-1 | -2 | -1 | -2 | -1 | - | ||||||||
-1 | -1 | ||||||||||||
-54 | -1 | -1 | |||||||||||
-1 | |||||||||||||
-1 | -0.5 | -1.5 | -1 | -0.5 | 0.5 | ||||||||
1.5 | 0.5 | -0.5 | 0.5 | ||||||||||
-36 | 0.5 | 1.5 | 0.5 | 0.5 |
На первой итерации получен оптимальный план.
=(0; 18; 46; 0; 0; 36; 0).
Т.к. вектор имеет отличную от нуля искусственную переменную U1=36, то множество планов ЗЛП (3.88) пусто в силу несовместности системы уравнений (3.89).
Дата публикования: 2015-10-09; Прочитано: 270 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!