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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
48
Итерация 0. Определяем начальный базис методом минимального элемента .
j
b
i
a
12 8 7 7 6
7 4 3 2 5
6
6
3 4 3 5 1
8
0 2 6
0 4 2 3 6
12
12
7 1 8 4 5
14
8 5 1
)}4,4(),3,4(),2,4(),1,3(),5,2(),3,2(),1,2(),4,1{(
761*45*82*30*36*26*18*112*0)(
0
=
=+++++++=
Ω
xL
Итерация 1.
1.1 Помечаем звездочками места , занимаемые базисными элементами. Пола -
гаем
0
1
=
u
.
.6,4,6
,63,6
,1,2,2
131322552211
221132324433
442244441144
−=−==−==−=
=−=−=−==−=
−
=
−
=
=
−
=
=
−
=
vcuucvucv
ucvvcuucv
ucvvcuucv
1.2 Оценки
ij
∆
записываем на свободные места таблицы .
v
j
u
i
6 -1 6 2 4
0 -1 -5 3 * -1
-3 * -8 * -6 *
-6 * -11 -2 -7 -8
2 -3 * * * 1
1.3 (i
0
,j
0
)=(1,3).
1.4. .03
13
>
=
∆
1.5. Отмечаем звездочкой элемент (1,3) и по правилу вычеркивания опреде-
ляем цикл.
+ * * –
* * *
*
* – * * + 
Линейное программирование



Итерация 0. Определяем начальный базис методом минимального элемента.



               bj
                             12             8                7               7            6
 ai
                                  7             4                    3            2           5
           6
                                                                         6
                                  3             4                    3            5           1
           8
                        0                                2                            6
                                  0             4                    2            3           6
       12
                        12
                                  7             1                    8            4           5
       14
                                        8                5               1

L( x 0 ) =0 * 12 +1 * 8 +1 * 6 +2 * 6 +3 * 0 +3 * 2 +8 * 5 +4 * 1 =76
Ω ={(1,4), ( 2,1), (2,3), (2,5), (3,1), (4,2), (4,3), (4,4)}
Итерация 1.
1.1 Помечаем звездочками места, занимаемые базисными элементами. Пола-
гаем u1 =0 .
v 4 =c14 −u1 =2,          u 4 =c 44 −v 4 =2,          v 2 =c 42 −u 4 =−1,
v 3 =c 43 −u 4 =6,                u 2 =c 23 −v3 =−3      v1 =c 21 −u 2 =6,
v1 =c 21 −u 2 =6,   v5 =c 25 −u 2 =4,  u 3 =c 31 −v1 =−6.
1.2 Оценки ∆ij записываем на свободные места таблицы.
      vj            6             -1            6                2           4
ui
  0          -1       -5       3           *                                 -1
  -3          *       -8       *          -6                                  *
  -6          *      -11      -2          -7                                 -8
  2          -3        *       *           *                                 1
1.3 (i0,j0)=(1,3).
1.4. ∆13 =3 >0.
1.5. Отмечаем звездочкой элемент (1,3) и по правилу                          вычеркивания опреде-
ляем цикл.
                            + *      * –
                   *           *              *
                   *
                         *  – *      * +

                                                    48

Страницы