Составители:
Рубрика:
77 78
Переменные
БП
1
x
2
x
3
x
4
x
Свободный
член
4
x
0
2
2 1 2
1
x
1 –1 –1 0 0
0
2
3 0 1
1
Z
0 –3 –2 –1 0
Система, записанная в данной таблице, разрешена относи-
тельно х
1
и х
4
, но так как она содержит три уравнения, то необхо-
димо ввести в базис еще одну переменную (х
2
или
х
3
) и при этом
иметь в качестве разрешающей третью строку. Посмотрим, какой
столбец с этой точки зрения следует брать за разрешающий. Если
возьмем второй столбец, то за разрешающую строку следует вы-
брать третью (благоприятный случай):
.,
2
1
2
1
2
2
min =
⎭
⎬
⎫
⎩
⎨
⎧
Если же возьмем третий столбец, то за разрешающую строку
также следует выбрать третью:
,
3
1
3
1
,
2
2
min =
⎭
⎬
⎫
⎩
⎨
⎧
следовательно, можно выбрать любой из них. Выберем, напри-
мер, второй столбец и, выполнив шаг преобразований Жордана–
Гаусса с разрешающим элементом а
32
= 2, придем к таблице:
Переменные
БП
х
1
х
2
х
3
х
4
Cвобод-
ный
член
х
4
0 0 –1
1
1
х
1
1 0 1/2 0 1/2
х
2
0 1 3/2 0 1/2
Z
1
0 0 5/2 –1 3/2
Теперь система приведена к базисному виду, базисными пе-
ременными являются х
1
,х
2
, х
4
, свободной – х
3
. Все свободные чле-
ны положительны, поэтому можем записать первоначальный
опорный план:
.,,/,/
Т
оп
)102121(
1
=
Χ
Чтобы ответить, является ли он оптимальным, необходимо
выполнить еще один шаг преобразований с разрешающим эле-
ментом а
14
= 1, чтобы выразить целевую функцию Z
1
только через
свободную переменную х
3
. Получим новую таблицу:
Переменные
БП
х
1
х
2
х
3
х
4
Cвобод-
ный
член
х
4
0 0 –1 1 1
х
1
1 0 1/2 0 1/2
х
2
0 1 3/2 0 1/2
Z
1
0 0 3/2 0 5/2
Опорное решение
,,,/,/
Т
оп
)102121(
1
=
Χ
содержащееся в таблице, является оптимальным, так как вектор
r = (3/2) содержит одну положительную компоненту. Минималь-
ное значение целевой функции:
2/5
min1
−
=
Z и, очевидно, 2/5
max
=
Z .
Итак,
25)102121( /Z,,,/,/
max
Т*
==
Χ
.
6.4. Вопросы для самопроверки
1. В чем заключается идея симплекс-метода?
2.
В каком виде должна быть записана модель ЗЛП для
решения симплекс-методом?
3.
Как построить первое базисное решение? В каком случае
оно будет опорным решением ЗЛП?
4.
Из каких этапов состоит переход от одного опорного ре-
шения к другому?
5.
Как определить, какой из столбцов выбирается за разре-
шающий в симплекс-преобразованиях?
Переменные Свободный Теперь система приведена к базисному виду, базисными пе-
БП ременными являются х1,х2, х4, свободной – х3. Все свободные чле-
x1 x2 x3 x4 член
ны положительны, поэтому можем записать первоначальный
x4 0 2 2 1 2 опорный план:
Χ оп
1
= (1 / 2 , 1 / 2 , 0 , 1)Т .
x1 1 –1 –1 0 0
Чтобы ответить, является ли он оптимальным, необходимо
0 2 3 0 1 выполнить еще один шаг преобразований с разрешающим эле-
ментом а14 = 1, чтобы выразить целевую функцию Z1 только через
Z1 0 –3 –2 –1 0 свободную переменную х3. Получим новую таблицу:
Система, записанная в данной таблице, разрешена относи- Cвобод-
Переменные ный
БП
тельно х1 и х4, но так как она содержит три уравнения, то необхо- х1 х2 х3 х4 член
димо ввести в базис еще одну переменную (х2 или х3) и при этом х4 0 0 –1 1 1
иметь в качестве разрешающей третью строку. Посмотрим, какой
х1 1 0 1/2 0 1/2
столбец с этой точки зрения следует брать за разрешающий. Если
возьмем второй столбец, то за разрешающую строку следует вы- х2 0 1 3/2 0 1/2
брать третью (благоприятный случай): Z1 0 0 3/2 0 5/2
⎧2 1⎫ 1
min ⎨ , ⎬= . Опорное решение
⎩2 2⎭ 2
Если же возьмем третий столбец, то за разрешающую строку Χ оп
1
= (1 / 2 , 1 / 2, 0, 1)Т ,
также следует выбрать третью: содержащееся в таблице, является оптимальным, так как вектор
⎧2 1⎫ 1 r = (3/2) содержит одну положительную компоненту. Минималь-
min ⎨ , ⎬= , ное значение целевой функции:
⎩2 3⎭ 3
следовательно, можно выбрать любой из них. Выберем, напри-
Z1 min = −5 / 2 и, очевидно, Z max = 5 / 2 .
мер, второй столбец и, выполнив шаг преобразований Жордана– Итак, Χ * = ( 1 / 2, 1 / 2, 0 , 1)Т , Z max = 5 / 2 .
Гаусса с разрешающим элементом а32 = 2, придем к таблице:
6.4. Вопросы для самопроверки
Переменные Cвобод- 1. В чем заключается идея симплекс-метода?
БП ный
х1 х2 х3 х4 2. В каком виде должна быть записана модель ЗЛП для
член
решения симплекс-методом?
х4 0 0 –1 1 1
3. Как построить первое базисное решение? В каком случае
х1 1 0 1/2 0 1/2 оно будет опорным решением ЗЛП?
4. Из каких этапов состоит переход от одного опорного ре-
х2 0 1 3/2 0 1/2 шения к другому?
Z1 0 0 5/2 –1 3/2
5. Как определить, какой из столбцов выбирается за разре-
шающий в симплекс-преобразованиях?
77 78
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
