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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
48
Цикл образуют элементы (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, x143 =5 −5 =0, x144 =1 +5 =6,
       0
     x 21 =0, x123 =2, x125 =6, x31
                                 1
                                    =12, x142 =8.
1.8 Имеется только один элемент (4,3) из Ω , для которого x 430
                                                                =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 ) =L( x ) −x13
                 1       0         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
                                     ∑ xij    ≤b j ,   j =1, n               (9)
                                     i =1




                                            48

Страницы