Транспортная задача

                                                                                                                 Таблица 2

       Найдём  опорный план данной задачи методом  Двойного Предпочтения.

 Рассматриваются отдельно столбцы и строки и отмечают клетку с минимальным тарифом по столбцу и по строке. В результате часть клеток имеет две отметки, часть одну отметку и часть не одной. При просмотре таблицы сначала заполняют клетки с двумя отметками, потом с одной отметкой и потом клетки без отметок.  

 В результате просмотра таблицы 3: клетки X₂₃, X₄₄ имеют по две отметки, клетки X_13, X_21, X_22, X_32, X₅₃ имеют по одной отметке, остальные клетки не имеют ни одной отметки.

       Сначала заполняем клетки с двумя отметками. Первая клетка с минимальным тарифом  и двумя отметками это клетка X₂₃  сравниваем запасы и потребности на пересечение этой клетки X₂₃={34,47}=34, остались запасы A₂ равные 13, так как потребности B₃ равны 0, то значения клеток X₁₃, X₃₃, X₄₃, X₅₃ равны нулю. Вторая клетка с минимальным тарифом и двумя отметками это клетка X₄₄  сравниваем запасы и потребности на пересечение этой клетки X₄₄={51,28}=28, остались потребности B₄ равные 23, так как запасы A₄ равны 0, то значения клеток X₄₁, X₄₂, X₄₃, X₄₅ равны нулю.  Клеток с двумя отметками больше не осталось. Первая клетка с минимальным тарифом и с одной отметкой это клетка X₂₂  сравниваем запасы и потребности на пересечение этой клетки X₂₂={29,13}=13, остались потребности B₂ равные 16, так как запасы A₂ равны 0, то значения клеток X₂₁, X₂₄, X₂₅ равны нулю. Вторая клетка с минимальным тарифом и с одной отметкой это клетка X₃₂, сравниваем запасы и потребности на пересечение этой клетки X₃₂={16,71}=16, остались запасы A₃ равные 55, так как потребности B₂ равны 0, то значения клеток X₁₂, X₄₂, X₅₂ равны нулю. Клеток с одной отметкой больше не осталось. Первая клетка с минимальным тарифом без отметок это клетка X₃₁  сравниваем запасы и потребности на пересечение этой клетки X₃₁={18,55}=18, остались запасы A₃ равные 37, так как потребности B₁ равны 0, то значения клеток X₁₁, X₅₁ равны нулю. Вторая клетка с минимальным тарифом и без отметок это клетка X₃₄  сравниваем запасы и потребности на пересечение этой клетки X₃₄={23,37}=23, остались запасы A₃ равные 14, так как потребности B₄ равны 0, то значения клеток X₁₄, X₁₅ равны нулю. Оставшиеся запасы и потребности разлаживаем по оставшимся клеткам так, чтобы сумма тарифов не превышала количество запасов и потребностей: значение клетки  X₁₅ равна 15,  значение клетки  X₃₅ равна 14, значение клетки  X₅₅  равна 33.

         Постоим матрицу перевозок x_ij  (6)  и посчитаем целевую функцию.

         (6) 

        ед. 

       Таблица 3 

       Опорный план данной задачи решённый методом Северо-Западного угла является наиболее эффективным чем методом Двойного Предпочтения и метод Минимального Элемента. 
 
 
 
 
 
 
 
 
 
 
 

         ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО  ПЛАНА

       Метод потенциалов позволяет найти  оптимальный план транспортной задачи. Поиск оптимального плана начинают с нахождения какого-либо опорного плана,  затем его улучшают количество планов max (m+n-1). 

       Теорема оптимальности.

       Если  для некоторого опорного плана х^* существуют такие числа , , что при х_ij > 0,  при x_ij = 0, то план х^* является оптимальным, а числа и называются потенциалами (разность потенциалов равна тарифу для занятых клеток) (разность потенциалов меньше тарифов для целых клеток).  

       Алгоритм  методов потенциалов.

1. Находим опорный план любым методом (число занятых клеток должно быть  m+n-1).
2. Находим потенциалы
3. Для каждой свободной клетки определяют величину
4. Если среди чисел _j нет положительных, то план оптимален, если положительные числа есть, то план нужно улучшить, для этого среди чисел _j выбирают max.Для клетки, в которой стоит максимальное, строят цикл пересчета.

       Цикл  пересчета называется ломаная линия  вершины, которых расположены в  занятых клетках, а звенья вдоль  строк и столбцов.

         Производят сдвиг по построенному  циклу пересчета. 

       Правило сдвига- в каждой клетки, которая  находится в вершине цикла, приписывают знак «+» или « - » причем свободной «+», а остальным поочередно. Определяют минимальную перевозку отмеченную « - »  для получения нового опорного плана найденную перевозку прибавляем к числам в клетках «+» и вычитают из чисел в клетках « - ». Полученный план проверяют на оптимальность. 

       Возьмем опорный план найденный методом  Севера – Западного угла и определим, является ли данный опорный план оптимальным, и улучшим опорный план, если он не является оптимальным. Опорный план, рассчитанный методом Севера – Западного угла представлен в таблице 4.