Целевая функция – минимум суммарных затрат на перевозки

(1)

Область допустимых решений:

Объём перевозки не может быть отрицательным

x_i,j ³ 0, 1 £ i £ n, 1 £ j £ m. (2)

Баланс по отправлению

1 £ i £ n. (3)

Баланс по назначению

1 £ j £ m. (4)

Баланс запасов и потребностей в продуктах

(5)

Если условие (5) выполнено, то задачу называют с правильным балансом. Только такая задача имеет математическое решение. Если задача с неправильным балансом, т.е. имеет место избыток продукта () или его дефицит (), то для решения её нужно привести к правильному балансу (см. п. 1.2.).

Решение задачи

Транспортная задача решается в два этапа: составление опорного решения и улучшение решения – нахождение оптимального решения.

Опорное решение проще всего составляется методом северо-западного (левого верхнего) угла. В начале определяется x _1,1 = min(a ₁, b ₁ ). Затем переходят к следующей соседней перевозке, куда заносят остаток от a₁ или b₁. Процедура продолжается слева–направо и сверху–вниз пока ни будут распределены все перевозки. В задаче с правильным балансом на перевозке x_n,m условия (3) и (4) выполняются. В опорном решении выполняется условие – число ненулевых перевозок k = n + m – 1, если это условие не выполнено, вводится фиктивная ненулевая перевозка с бесконечно малым объёмом (x_ij = e).

Оптимальное решение находят методом потенциалов или фиктивных стоимостей. Потенциал a _i – это фиктивный платёж пункта отправления A_i за вывоз единицы продукта, потенциал b _j – это фиктивный платёж пункта назначения B_j за доставку единицы продукта. Суммарный потенциал

c^*_i,j = a _i + b _j. (6)

Для ненулевых перевозок c^*_i,j = c_i,j, откуда

b _j = c_ij - a _i, (7)

a _i = c_ij - b _j. (8)

Число неизвестных a _i и b _j равно n + m, а уравнений k = n + m – 1, т.е. уравнений на одно меньше, чем неизвестных, поэтому одному из потенциалов нужно задать любое значение. Начинают решение задачи с присвоения a ₁ = 0. Далее по формулам (7) и (8) рассчитывают a _i и b _j для всех ненулевых перевозок. Затем для всех нулевых перевозок по формуле (6) рассчитывают значения c^*_i,j. Маршруты A_i ® B_j, для которых c^*_i,j > c_i,j, более выгодны, чем использованные в рассматриваемом плане.

Перенос единицы перевозки на маршрут A_i ® B_j даёт экономию, равную c^*_i,j - c_i,j. Выбирается маршрут A_i ® B_j, для которого max (c^*_i,j - c_i,j) и для него строится цикл переноса перевозки. Цикл переноса перевозки представляет собой прямоугольную фигуру, одна из вершин которой находится в нулевой перевозке, соответствующей выбранному наиболее выгодному маршруту. Остальные вершины находятся в ненулевых перевозках. Каждой нулевой перевозке соответствует единственный цикл переноса перевозки. В пункте нулевой перевозки ставится знак «+», далее в вершинах цикла переноса перевозок знаки «-» и «+» чередуются. Они соответствуют увеличиваемым и уменьшаемым перевозкам. Выбирается меньшая из уменьшаемых перевозок, и она по циклу переносится на место нулевой перевозки. При этом появляется одна новая ненулевая перевозка и одна ненулевая становится нулевой, т.е. число ненулевых перевозок сохраняется (k = n + m – 1) и сохраняется все условия (3), (4). Процедура улучшения плана перевозок повторяется. Условие оптимального решения – для всех нулевых перевозок c^*_i,j £ c_i,j.

Пример 1. Транспортная задача задана в виде таблицы 1. Здесь приведены объёма поставок a_i (i= 1,3), объёмы заказов b_j (j= 1,4) и транспортные издержки c_ij (в правых верхних углах).

Решение начинается с составления опорного плана методом левого верхнего (северо-западного) угла. Результат приведен в этой же таблице.

Таблица 1

Пункты отправления	Пункты назначения	Объёмы поставок ai	Потенциалы ai
В 1	В 2	В 3	В 4
А 1		8 > 1	10 > 3	5 6
70 -	+
А 2				1 10		-4
40 +	- 80
А 3	6 > 1	5 > 4				-3
Объёмы заказов bj
Потенциалы bj

Транспортные издержки опорного плана равны W₀ = 9 × 70+5 × 40+4 × 80 + 6 × 60 + 7 × 10 + 2 × 120 = 1820.

На втором этапе определяется оптимальный план перевозок путём последовательного улучшения плана методом потенциалов. Потенциалы или фиктивные платежи определяются по формулам:

c^*_ij = a _i + b _j; b _j = c_ij - a _i; a _i = c_ij - b _j.

b₁ = c ₁₁ - a₁ = 9 - 0 = 9; a₂ = c ₂₁ - b₁ = 5 – 9 = - 4; b₂ = c ₂₂ - a₂ =

= 4 – (-4) = 8; b₃ = c ₂₃ - a₂ = 6 – (-4) = 10; a₃ = c ₃₃ - b₃ = 7 – 10 = -3;

b₄ = c ₃₄ - a₃ = 2 – (-3) = 5.

Для нулевых перевозок c ^*₁₂ = a₁ + b₂ = 8 + 0 = 8, аналогично: c ^*₁₃ = 10; c ^*₁₄ = 5; c ^*₂₄ = 1; c ^*₃₁ = 6; c ^*₃₂ = 5. Находим нулевые перевозки, для которыхпотенциалы больше транспортных издержек; это c ^*₁₂ > c ₁₂; c ^*₁₃ > c ₁₃; c ^*₃₁> c ^*₃₁; c ^*₃₂ > c ^*₃₂ . Наибольшие разности c ^*₁₂ - c ₁₂ = 7 и c ^*₁₃ - c ₁₃ = 7.

Результаты расчётов приведены в таблице 1. Для нулевой перевозки А ₂ ® В ₂ составляем цикл переноса перевозки, который представляет собой прямоугольную фигуру, в одной из вершин которой нулевая перевозка, а в остальных – ненулевые перевозки. Максимально возможный объём переноса перевозки равен меньшей из уменьшаемых величин, а именно 70 единиц (А ₂ ® В ₂). Улучшенный план приведен в таблице 2, W ₁ = 1820 – 7× 70=1330.

Таблица 2

Пункты отправления	Пункты назначения	Объёмы поставок ai	Потенциалы ai
В 1	В 2	В 3	В 4
А 1	2 9		3 3	2 6
А 2				1 10
110 -		+60
А 3	6 > 1	5 > 4
+		-10
Объёмы заказов bj
Потенциалы bj				-2

Второй шаг оптимизации приведен в таблице 2, а его результат – в таблице 3. W ₂ = 1330 – 5 × 10 = 1280.

Таблица 3

Признак оптимальности плана: для всех нулевых перевозок c^*_ij £ c_ij. План, приведенный в таблице 3, удовлетворяет условию оптимальности.

Таким образом, оптимальный план перевозок приведен в таблице 3. Минимальные затраты на перевозки составляют W _min = 1280, по сравнению с исходным планом экономия составляет 540 или примерно 42%.

1.2. Приведение транспортной задачи к правильному балансу

Возможны две ситуации – избыток или дефицит продукта

1. Избыток продукта .

В этом случае вводится дополнительный фиктивный пункт назначения B_{m+ 1}, в котором якобы имеются потребности b_{m+ 1} на избыточный продукт в количестве . Так как перевозки являются фиктивными и производиться не будут, затраты на них равны нулю (c_{i,m+ 1} = 0, 1 £ i £ n). Задача становится сбалансированной и может решаться обычными методами.

Результаты решения такой задачи должны интерпретироваться следующим образом. Перевозки х_{i,m+ 1}, 1 £ i £ n являются фиктивными, эти объёмы грузов вывезены не будут. В оптимальном плане перевозок не будет вывезена часть грузов из пунктов отправления, откуда перевозки окажутся наиболее дорогими. В условиях рыночной экономики это означает, что поставщики должны либо искать новых заказчиков в более близком регионе, либо переводить производство на более востребованную продукцию.

2. Дефицит продукта .

Здесь возможно несколько стратегий приведения задачи к правильному балансу.

2.1. При отсутствии каких-либо ограничений вводится дополнительный фиктивный пункт отправления А_{n+ 1}, в котором якобы имеются запасы а_{n+ 1} недостающего продукта в количестве . Так как перевозки являются фиктивными и производиться не будут, затраты на них равны нулю (c_{n+ 1, j}= 0, 1 £ j £ m). Задача становится сбалансированной и может решаться обычными методами.

Результаты такого решения должны интерпретироваться следующим образом. Перевозки х_{n+ 1, j}, 1 £ j £ m являются фиктивными, эти объёмы грузов доставлены не будут. В оптимальном плане перевозок не будет доставлена часть грузов в пункты назначения, куда перевозки окажутся наиболее дорогими. В условиях рыночной экономики это означает, что заказчики должны либо искать новых поставщиков в более близком регионе, либо ограничивать свои потребности на данный продукт.

2.2. Продукт имеет важное социальное или стратегическое значение и других поставщиков этого продукта в близлежащем регионе нет. В этом случае нельзя оставить часть потребителей вообще без продукта и обычно просто все заявки пропорционально уменьшают. Вводится коэффициент d пропорционального уменьшения заявок , и все заявки корректируются в сторону уменьшения b_j^* = d ×b_j, где b_j^* - скорректированные объёмы заявок.

Примечание: скорректированные объёмы заявок должны быть округлены таким образом, чтобы выполнялось балансное условие (5).

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

2.3. Все пункты отправления и пункты назначения принадлежат одной фирме. Тогда можно найти более эффективное решение. Как и в п. 2.1. вводится дополнительный фиктивный пункт отправления А_{n+ 1}, в котором якобы имеются запасы а_{n+ 1} недостающего продукта в количестве

.

Только вместо затрат на перевозки в качестве c_{n+ 1, j}, 1 £ j £ m используют потери от недопоставки единицы продукта в пункт назначения B_{m+ 1}. В этом случае целевая функция представляет собой сумму транспортных издержек и потерь от недопоставки грузов.

Результаты такого решения должны интерпретироваться следующим образом. Перевозки х_{n+ 1, j}, 1 £ j £ m являются фиктивными, эти объёмы грузов доставлены не будут. В оптимальном плане перевозок не будет доставлена часть грузов в те пункты назначения, куда, во-первых, перевозки окажутся наиболее дорогими и, во-вторых, где потери от недопоставки продуктов будут минимальны.

2. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ

Принцип оптимальности

Задача распределения ресурсов решается с помощью предложенного Р. Белланом метода динамического программирования. Условия применимости динамического программирования:

1. Работа системы рассматривается на m последовательных этапах.