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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
47
Итерация 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,
v3 =c 43 −u 4 =6,         u 2 =c 23 −v3 =−3      v1 =c 21 −u 2 =6,
v1 =c 21 −u 2 =6,    v 5 =c 25 −u 2 =4,   u 3 =c31 −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) и по правилу вычеркивания опреде-
ляем цикл.
                                + *     * –
                   *                 *            *
                   *
                          *     – *     * +

                                            47

Страницы