Транспортная задача: Методы построения допустимого решения
Метод минимальной стоимости.
Заметим, что в методе Северо-западного угла цены перевозок вообще не учитывались. Мы рассмотрим метод нахождения начального допустимого плана, в котором за основу взята цена соответствующих перевозок. Вначале в таблице транспортной задачи находится клетка с минимальной ценой:
![\[{c_{lk}} = \min {c_{ij}},i = 1..m,j = 1..n.\]](https://spisok-literaturi.ru/cache/62cca07b11dcf4b72a8d5dbbb8bf0861.png)
![\[{x_{lk}} = \min \{ {a_l},{b_k}\} \]](https://spisok-literaturi.ru/cache/4e4a98595704b0efc2c8c80e89d2f3ee.png)
После этого возможны три случая:
1. ![\[{a_l} > {b_k}.;{a_l} = {a_l} - {b_k};{x_{ik}} = 0,i \ne l\]](https://spisok-literaturi.ru/cache/21b882274cbc5b36b25d31aad31094e7.png)
2. ![\[{a_l} < {b_k}.;{b_k} = {b_k} - {a_l};{x_{lj}} = 0,j \ne k.\]](https://spisok-literaturi.ru/cache/72623dc1c2bd9bd05c0383c5e8a66144.png)
3. ![\[{a_l} = {b_k}.;{x_{ik}} = 0,i \ne l\quad \quad {x_{lj}} = 0,j \ne k.\]](https://spisok-literaturi.ru/cache/6a520dc4627f295cd9af71a40f30b91d.png)
Таким образом, в таблице будут заполнены: либо столбец (первый случай), либо строка (второй случай), либо как столбец, так и строка (третий случай). Для незаполненной части таблицы процедура повторяется.
Очевидно, что также как и в методе Северо-западного угла, методом Минимальной стоимости будет построено допустимое решение транспортной задачи.
Метод аппроксимации Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.
Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.
Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).
Метод двойного предпочтения
В случае больших размерностей, эффективен способ определения первоначального опорного плана с помощью метода двойного предпочтения.
В каждом столбце отмечают знаком клетку с наименьшей стоимостью. Затем тоже проделывают в каждой строке. В результате некоторые клетки имеют двойную отметку. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая и рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам с единичной отметкой. Остальные перевозки распределяют по наименьшей стоимости.
