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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
43
Пример 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

Страницы