Составители:
Рубрика:
71 72
Переменные
БП
1
x
2
x
3
x
4
x
5
x
Свободный
член
3
x
1
1
1
0 0 5
4
x
2 1 0 1 0 9
5
x
1 2 0 0 1 7
1
Z
–2 –1 1 –1 1 0
В клетку на пересечении Z
1
-строки и столбца “Свободный
член” запишем свободный член целевой функции с противопо-
ложным знаком. В данном случае он равен 0.
Приравняв свободные переменные нулю х
1
=х
2
=0, получим
базисное решение системы ограничений:
,),,,,(
Т
79500
1
=
Χ
где х
3
=5, х
4
=9, х
5
=7.
Так как
,,,,j,x
j
5210 K
=
≥
то базисное решение Х
1
явля-
ется опорным решением (планом) задачи. Итак, первоначальное
опорное решение найдено.
Для проверки его на оптимальность выразим функцию цели
Z
1
через свободные переменные х
1
и х
2
. Для исключения пере-
менной х
3
из функции цели Z возьмем за разрешающий элемент
а
13
=1 в третьем столбце предыдущей таблицы. Сделав один шаг
преобразований Жордана
–Гаусса, придем к таблице вида:
Переменные
БП
1
x
2
x
3
x
4
x
5
x
Свободный
член
3
x
1
1
1 0 0 5
4
x
2 1 0 1 0 9
5
x
1 2 0 0 1 7
1
Z
–3 –2 0 –1 1 –5
Сделав аналогично еще два шага исключения неизвестных х
4
и х
5
из функции цели Z
1
, придем к таблице:
Переменные
БП
1
x
x
2
3
x
4
x
5
x
Свободный
член
1
x
1
1
1 0 0 5
4
x
2
1 0 1 0 9
x
5
1
2
0 0 0 7
1
Z
–2 –3
0 0 0
–3
Из таблицы видно, что
Z
1
(Х
(1)
)=3, r =(–2; –3).
Так как условие
0≥r не выполняется, то полученный опор-
ный план Х
(1)
не является оптимальным.
Необходимо перейти к новому опорному плану, для которо-
го значение функции уменьшится. Для перехода к следующему
опорному плану нужно одну из свободных переменных (х
1
либо
х
2
) перевести в базис, а одну из базисных (х
3
, либо х
4
, либо х
5
) пе-
ревести в свободные. Выбор свободной переменной, вводимой в
базис, определяется максимальной по модулю отрицательной
компонентой вектора r= (–2; –3).
Компоненте r
2
= –3 соответствует в таблице переменная х
2
,
которая вводится в базис, и второй столбец становится разре-
шающим.
Для выбора разрешающей строки вычислим
2
7
2
7
1
9
1
5
min =
⎭
⎬
⎫
⎩
⎨
⎧
,,
.
Итак, третья строка стала разрешающей, а разрешающим
элементом стал элемент а
32
=2. Сделав один шаг в симплекс-
таблице, получим новое опорное решение:
Т)(
),/,/,/,( 021123270
2
=
Χ
.
Это решение также не является оптимальным, так как в вектор
r =(–1/2; 3/2) имеет отрицательную компоненту:
Переменные Свободный Сделав аналогично еще два шага исключения неизвестных х4
БП и х5 из функции цели Z1, придем к таблице:
x1 x2 x3 x4 x5 член
Переменные Свободный
x3 1 1 1 0 0 5 БП
x1 x2 x3 x4 x5 член
x4 2 1 0 1 0 9 x1 1 1 1 0 0 5
x5 1 2 0 0 1 7 x4 2 1 0 1 0 9
Z1 –2 –1 1 –1 1 0 x5 1 2 0 0 0 7
В клетку на пересечении Z1-строки и столбца “Свободный Z1 –2 –3 0 0 0 –3
член” запишем свободный член целевой функции с противопо-
ложным знаком. В данном случае он равен 0.
Приравняв свободные переменные нулю х1=х2=0, получим Из таблицы видно, что
базисное решение системы ограничений: Z1(Х(1))=3, r =(–2; –3).
Так как условие r ≥ 0 не выполняется, то полученный опор-
Χ 1 = ( 0, 0 , 5, 9 ,7 )Т , ный план Х(1) не является оптимальным.
где х3=5, х4=9, х5=7. Необходимо перейти к новому опорному плану, для которо-
Так как x j ≥ 0 , j = 1 , 2 , K , 5 , то базисное решение Х1 явля- го значение функции уменьшится. Для перехода к следующему
ется опорным решением (планом) задачи. Итак, первоначальное опорному плану нужно одну из свободных переменных (х1 либо
опорное решение найдено. х2) перевести в базис, а одну из базисных (х3, либо х4, либо х5) пе-
Для проверки его на оптимальность выразим функцию цели ревести в свободные. Выбор свободной переменной, вводимой в
Z1 через свободные переменные х1 и х2. Для исключения пере- базис, определяется максимальной по модулю отрицательной
менной х3 из функции цели Z возьмем за разрешающий элемент компонентой вектора r= (–2; –3).
а13=1 в третьем столбце предыдущей таблицы. Сделав один шаг Компоненте r2= –3 соответствует в таблице переменная х2,
преобразований Жордана–Гаусса, придем к таблице вида: которая вводится в базис, и второй столбец становится разре-
Переменные Свободный шающим.
БП
x1 x2 x3 x4 x5 член Для выбора разрешающей строки вычислим
⎧5 9 7⎫ 7 .
x3 1 1 1 0 0 5 min ⎨ , , ⎬=
⎩1 1 2⎭ 2
x4 2 1 0 1 0 9 Итак, третья строка стала разрешающей, а разрешающим
элементом стал элемент а32=2. Сделав один шаг в симплекс-
x5 1 2 0 0 1 7 таблице, получим новое опорное решение:
Χ ( 2 ) = ( 0 , 7 / 2 , 3 / 2 , 11 / 2 , 0 )Т .
Z1 –3 –2 0 –1 1 –5 Это решение также не является оптимальным, так как в вектор
r =(–1/2; 3/2) имеет отрицательную компоненту:
71 72
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
