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

                                                                    Линейное программирование


          bj
                   10                  4                  9                 6
ai
                        3                  4                  2                 4
     6
               6
                        3                  1                  4                 2
     8
               4                4
                        4                  3                  5                 3
     10                            *
                               0                      9                 1
                        2                  4                  3                 6
     5
                                                                        5

Здесь при вычислении элемента x 22 оказалось a ′2 =b2′ =4 . Поэтому, напри-
мер, заполняется только вторая строка и полагается b2′ =0 . После чего
x32 =0 . Звездочкой помечен базисный элемент, равный нулю.
Зная исходную базисную точку, мы можем продолжить решение транспорт-
ной задачи методом потенциалов, который является несколько иной формой
изложения симплексного метода, связанной со спецификой транспортной
задачи. В первую очередь заметим, что целевая функция в транспортной за-
даче минимизируется, поэтому при выборе вектора, который будет вводится
в базис на очередной итерации, будет выбираться вектор с отрицательной
оценкой. Для определения вида оценок в транспортной задаче воспользуем-
ся замечанием 1 к §6, в соответствии с которым оценка j -й переменной
представляет собой разность между левой и правой частями j -го ограниче-
ния двойственной задачи ∆ j = y T A j −c j , при подстановке в него вектора y ,
который можно найти из условия ∆k = y T Ak −c k =0, k ∈J B .
Задача, двойственная к транспортной задаче имеет вид
                               m               n
                               ∑ a i u i +∑ b j v j → min
                               i =1            j =1

                            u i +v j ≤cij          i =1, m, j =1, n ,
где u i , i =1, m - переменные двойственной задачи, соответствующие ограни-
чениям (2), а v j , j =1, n - переменные двойственной задачи, отвечающие ог-
раничениям (3). В соответствии с данным видом двойственной задачи оценки
                      в транспортной задаче будут иметь вид
                         ∆ij =u i −v j −cij i =1, m, j =1, n ,
причем переменные u i , i =1, m и v j , j =1, n представляют собой произволь-
ное решение системы уравнений


                                               43