Транспортная задача: Методы построения допустимого решения

Метод минимальной стоимости.

 Заметим, что в методе Северо-западного угла цены перевозок вообще не учитывались. Мы рассмотрим метод нахождения начального допустимого плана, в котором за основу взята цена соответствующих перевозок. Вначале в таблице транспортной задачи находится клетка с минимальной ценой:

 \[{c_{lk}} = \min {c_{ij}},i = 1..m,j = 1..n.\]

\[{x_{lk}} = \min \{ {a_l},{b_k}\} \]

После этого возможны три случая:

1. \[{a_l} > {b_k}.;{a_l} = {a_l} - {b_k};{x_{ik}} = 0,i \ne l\]

2. \[{a_l} < {b_k}.;{b_k} = {b_k} - {a_l};{x_{lj}} = 0,j \ne k.\]

3. \[{a_l} = {b_k}.;{x_{ik}} = 0,i \ne l\quad \quad {x_{lj}} = 0,j \ne k.\]

Таким образом, в таблице будут заполнены: либо столбец (первый случай), либо строка (второй случай), либо как столбец, так и строка (третий случай). Для незаполненной части таблицы процедура повторяется.

Очевидно, что также как и в методе Северо-западного угла, методом Минимальной стоимости будет построено допустимое решение транспортной задачи.

 

Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.

Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.

Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

 

Метод двойного предпочтения

В случае больших размерностей, эффективен способ определения первоначального опорного плана с помощью метода двойного предпочтения.

В каждом столбце отмечают знаком клетку с наименьшей стоимостью. Затем тоже проделывают в каждой строке. В результате некоторые клетки имеют двойную отметку. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая и рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам с единичной отметкой. Остальные перевозки распределяют по наименьшей стоимости.

 


Наши друзья

Качественное решение задач курсовых работ, РГЗ по техническим предметам.
botaniks.ru

Околостуденческое

Рейтинг@Mail.ru

© 2009-2021, Список Литературы