Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 47 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
49
Цикл образуют элементы (1,3)→ (1,4) → (4,4) → (4,3).
)}.3,4(),4,1{()},4,4{( ==
−+
ΩΩ
1.6
.
5
)
5
,
6
min(
=
=
Θ
1.7 ,651,055,156,5
1
44
1
43
1
14
0
13
=+==−==−=== xxxx Θ
.8,12,6,2,0
1
42
1
31
1
25
1
23
0
21
===== xxxxx
1.8 Имеется только один элемент (4,3) из
Ω
, для которого 0
0
43
=x . Поэтому
он становится небазисным . Новая базисная точка имеет вид
=
0 6 0 8 0
0 0 0 0 12
6 0 2 0 0
0 1 5 0 0
1
x
1.9
613*576)()(
13
1
13
01
=−=−= ∆ xxLxL
Итерация 2.
2.1, 2.2
v
j
u
i
3 -1 3 2 1
0 -4 -5 * * -4
0 * -5 * -3 *
-3 * -8 -2 -4 -8
2 -2 * -3 * -2
2.3 , 2.4. .02max
00
<
−
=
=
ijji
∆
∆
Решение закончено. .61)(,
*1*
== xLxx
Открытая транспортная задача
Открытой транспортной задачей называется транспортная задача , в которой
не выполнено условие баланса . При этом возможны два случая.
Случай 1.
∑∑
==
<
n
j
j
m
i
i
ba
11
. В этом случае математическая постановка задачи
имеет вид.
cx
ijij
ji
m
==
∑∑
→
11
min (7)
miax
i
n
j
ij
,1,
1
==
∑
=
(8)
njbx
j
m
i
ij
,1,
1
=≤
∑
=
(9) 
                                                                             Линейное программирование



Цикл образуют элементы (1,3)→(1,4) →(4,4) →(4,3).
Ω + ={( 4,4)}, Ω − ={(1,4), (4,3)}.
1.6 Θ =min(6,5) =5.
     0
1.7 x13 =Θ =5, x14
                1
                   =6 −5 =1, x 143 =5 −5 =0, x 144 =1 +5 =6,
       0
     x 21 =0, x 123 =2, x 125 =6, x 31
                                    1
                                       =12, x 142 =8.
1.8 Имеется только один элемент (4,3) из Ω , для которого x 43
                                                            0
                                                               =0 . Поэтому
он становится небазисным. Новая базисная точка имеет вид
    � 0 0 510 �
       �                  �
         � 0 0 2 0 6�
x =�
  1
             12 0 0 0 0 �
          ��                ��
     �       0  8 0 6 0        �
1.9 L( x 1 ) =L( x 0 ) −x13
                         1
                            ∆13 =76 −5 * 3 =61
Итерация 2.
2.1, 2.2
     vj       3            -1         3                       2                 1
ui
   0         -4            -5         *                        *                -4
   0          *            -5         *                       -3                *
  -3          *           -8         -2                       -4                -8
   2         -2             *        -3                        *                -2
2.3 , 2.4. ∆i0 j0 =max ∆ij =−2 <0.
Решение закончено. x * =x 1 , L( x * ) =61.

                    Открытая транспортная задача
Открытой транспортной задачей называется транспортная задача, в которой
не выполнено условие баланса. При этом возможны два случая.
             m       n
Случай 1.    ∑ a i <∑ b j . В этом случае математическая постановка задачи
             i =1   j =1
имеет вид.
                                           m
                                          ∑ ∑ cij x ij →            min                            (7)
                                          i =1 j =1
                                          n
                                         ∑ xij       =a i , i =1, m                                (8)
                                         j =1
                                         m
                                         ∑ x ij      ≤b j ,        j =1, n                         (9)
                                         i =1




                                                49

Страницы