Линейное программирование. Азарнова Т.В - 10 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Линейное программирование
12
Утверждение Если
*
x
является решением задачи (1), то найдется та-
кое
0
*
≥
u
, что
(
)
**
, ux является решением задачи (2). С другой стороны, если
)
€
,
€
( ux
является решением задачи (2), то
x
€ является решением задачи (1).
В связи с тем , что основной метод решения ЗЛП - симплексный метод
предназначен для решения задач в канонической форме, мы проиллюстриру-
ем работу описанных выше правил на примере приведения задачи к канони-
ческой форме.
Пример 1. Пусть исходная задача задана в виде
min23
321
→
−
+
xxx
при ограничениях
432
321
≥
+
−
xxx
2
321
≤
−
+
−
xxx
20
32
−
=
−
−
xx
0,0
32
≤
≥
xx
.
Привести данную задачу к канонической форме.
Решение.
1. Умножим целевую функцию на -1. В результате получим
max23
321
→
+
−
−
xxx .
2. Из левой части первого неравенства вычтем неотрицательную переменную
1
u и перейдем к ограничениям
0,432
11321
≥
=
−
+
−
uuxxx .
3. К левой части второго неравенства добавим неотрицательную переменную
2
u и перейдем к ограничениям
0,2
22321
≥
=
+
−
+
−
uuxxx .
4. Умножим обе части третьего равенства на -1
20
32
=
+
xx .
5. Осуществим замену переменных .0,0,
''
1
'
1
''
1
'
11
≥≥−= xxxxx
0,
'
333
≥
′
−= xxx
В результате задача принимает канонический вид
max233
'
32
''
1
'
1
→−−+− xxxx
4322
1
'
32
''
1
'
1
=−−−− uxxxx
2
2
'
32
''
1
'
1
=++++− uxxxx
20
'
32
=− xx
0,0,0,0,0,0
21
'
32
''
1
'
1
≥≥≥≥≥≥ uuxxxx .
Заметим , что последовательность применения правил приведения к канони-
ческой форме не существенна и может быть любой . 
Линейное программирование


          Утверждение Если x * является решением задачи (1), то найдется та-
                (     )
кое u * ≥0 , что x * , u * является решением задачи (2). С другой стороны, если
( x€, u€) является решением задачи (2), то x€ является решением задачи (1).

       В связи с тем, что основной метод решения ЗЛП - симплексный метод
предназначен для решения задач в канонической форме, мы проиллюстриру-
ем работу описанных выше правил на примере приведения задачи к канони-
ческой форме.
       Пример 1. Пусть исходная задача задана в виде
                              3 x1 +2 x 2 −x 3 → min
при ограничениях
                                  2 x1 −x 2 +3 x 3 ≥4
                                    −x1 + x 2 −x 3 ≤2
                                       −x 2 −x3 =−20
                                         x 2 ≥0, x 3 ≤0 .
Привести данную задачу к канонической форме.
Решение.
1. Умножим целевую функцию на -1. В результате получим
                             −3 x1 −2 x 2 + x 3 → max .
2. Из левой части первого неравенства вычтем неотрицательную переменную
u1 и перейдем к ограничениям
                        2 x1 −x 2 +3 x 3 −u1 =4, u1 ≥0 .
3. К левой части второго неравенства добавим неотрицательную переменную
u 2 и перейдем к ограничениям
                        −x1 + x 2 −x 3 +u 2 =2, u 2 ≥0 .

4. Умножим обе части третьего равенства на -1
                               x 2 +x 3 =20 .
5. Осуществим замену переменных x1 =x1' −x1'' , x1' ≥0, x1'' ≥0.
                                     x 3 =−x 3′ , x 3' ≥0
В результате задача принимает канонический вид
                       −3x1' +3x1'' −2 x 2 −x 3' → max
                            2 x1' −2 x1'' −x 2 −3x 3' −u1 =4
                            −x1' +x1'' +x 2 +x 3' +u 2 =2
                                    x 2 −x3' =20
                 x1' ≥0, x1'' ≥0, x 2 ≥0, x 3' ≥0, u1 ≥0, u 2 ≥0 .
Заметим, что последовательность применения правил приведения к канони-
           ческой форме не существенна и может быть любой.


                                        12

Страницы