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

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


       Метод "северо-западного угла"

Алгоритм построения исходной базисной точки складывается из нескольких
шагов, на каждом из которых определяется верхний левый элемент матрицы
X . Сформулируем алгоритм метода "северо-западного угла".

Шаг 0. Полагаем i 0 =1, j 0 =1, a i′ =a i , b ′j =b j           i =1, m, j =1, n .
                                (            )
Шаг 1. Полагаем x i0 j0 =min a i′0 , b ′j0 . Если x i0 j0 =a i′0 , то переходим к шагу 2,
в противном случае - к шагу 4.
Шаг 2. Полагаем b ′j0 =b ′j0 −x i0 j0 . Индексу i 0 присваиваем значение i 0 +1 .
Если i 0 =m , то переходим к шагу 3, в противном случае к шагу 1.
Шаг 3. Полагаем x i0 j =b ′j для всех j ≥ j 0 . Решение закончено.
Шаг 4. Полагаем a i′0 =a i′0 −x i0 j0 . Индексу j 0 присваиваем значение j 0 +1 .
Если j 0 =n , то переходим к шагу 5, в противном случае переходим к шагу 1.
Шаг 5. Полагаем x ij0 =a i′ для всех i ≥i 0 . Решение закончено.
     Рассмотрим пример использования данного алгоритма.

       Пример 1. Исходные данные:

            bj
                      30            36                 36                 22              56
  ai
                           3             4                  2                  4               5
       45
                 30            15
                           3             1                  4                  2               4
       70
                               21                 36                 13
                           4             3                  5                  3               6
       15
                                                                      9              6
                           2             4                  3                  6               8
       50
                                                                                     50

          В верхнем правом углу в каждой ячейке стоят коэффициенты
c ij , i =1,4, j =1,5 . Данная задача является закрытой транспортной задачей, так
как сумма потребностей в продукте равна сумме имеющегося продукта
                            45+70+15+50=30+36+36+22+56.
Результаты работы алгоритма записаны в в нижнем левом углу ячейки. По-
лучена исходная базисная точка


                                             41