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

UptoLike

Рубрика: 

Линейное программирование
42
Пример 2.
j
b
i
a
30 36 36 22 56
3 4 2 4 5
45
36
(2)
9
(5)
3 1 4 2 4
70
36
(1)
22
(3)
12
(5)
4 3 5 3 6
15
15
(5)
2 4 3 6 8
50
30
(4)
20
(5)
Для наглядности каждый элемент снабжен индексом , равным номеру итера-
ции, на которой был получен данный элемент. В результате получили сле-
дующую базисную точку
=
2000030
150000
12220360
903600
X
со значением целевой функции, равным 545. Данное значение явно меньше,
чем значение целевой функции на базисной точке , полученной методом "се-
веро-западного угла ".
Замечание 1. Признаком вырожденности транспортной задачи являет -
ся существование
n
s
m
r
<
<
,
, для которых выполняется равенство
∑∑
==
=
s
l
j
r
k
i
lk
ba
11
.
В этом случае при использовании приведенных алгоритмов может оказаться,
что среди
1
+
m
n
базисных координат есть нулевые.
Пример 3. Построим методом "северо-западного угла " исходную ба -
зисную точку для следующей задачи
Линейное программирование


      Пример 2.

           bj
                     30              36                       36              22              56
 ai
                          3                   4                    2               4               5
      45
                                                   36(2)                               9(5)
                          3                   1                    4               2               4
      70                           (1)                                      (3)             (5)
                              36                                       22              12
                          4                   3                    5               3               6
      15                                                                                    (5)
                                                                                       15
                          2                   4                    3               6               8
      50
                30 (4)                                                                 20(5)

Для наглядности каждый элемент снабжен индексом, равным номеру итера-
ции, на которой был получен данный элемент. В результате получили сле-
дующую базисную точку

                                  � 0 0 36 0 9 �
                                   �                     �
                                     � 0 36 0 22 12 �
                              X =�
                                            0 0 0 0 15 �
                                      ��                   ��
                                         � 30 0 0 0 20        �

со значением целевой функции, равным 545. Данное значение явно меньше,
чем значение целевой функции на базисной точке, полученной методом "се-
веро-западного угла".

     Замечание 1. Признаком вырожденности транспортной задачи являет-
ся существование r