Материал: Расчет стоимости доставки продукции

Примем v₂ = 0.

A₂B₂: v₂ + u₂ = 5, u₂ = 5 - 0 = 5₃B₂: v₂ + u₃ = 2, u₃ = 2 - 0 = 2₃B₃: v₃ + u₃ = 3, v₃ = 3 - 2 = 1₂B₁: v₁ + u₂ = 4, v₁ = 4 - 5 = -1₁B₁: v₁ + u₁ = 7, u₁ = 7 - (-1) = 8

A₁B₄: v₄ + u₁ = 2,v₄ = 2 - 8 = -6

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

Оценка незадействованного маршрута = тариф маршрута - (потенциал поставщика + потенциал потребителя).

A₁B₂: ₁₂ = 8 - (8 + 0) = 0₁B₃: ₁₃ = 1 - (8 + 1) = -8₂B₃: ₂₃ = 9 - (5 + 1) = 3₂B₄: ₂₄ = 8 - (5 + (-6)) = 9₃B₁: ₃₁ = 9 - (2 + (-1)) = 8₃B₄: ₃₄ = 6 - (2 + (-6)) = 10

1 незадействованный маршрут имеют отрицательную оценку.

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

Будем использовать новый маршрут доставки продукции от поставщика A₁ к потребителю B₃. (ячейка A₁B₃)

Построим цикл для нового маршрута. (<javascript:Comments(125)>)

Пусть ячейка A₁B₃, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = {60, 90, 150} = 60.

От ячеек цикла с четными номерами отнимает 60. К ячейкам с нечетными номерами прибавляем 60.

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

1 * 60 - 7 * 60 + 4 * 60 - 5 * 60 + 2 * 60 - 3 * 60 = ( 1 - 7 + 4 - 5 + 2 - 3 ) * 60 = -8 * 60 = ₁₃ * 60.

Выражение стоящее в скобках равно оценке нового маршрута!!

Поэтому новая стоимость доставки вычисляется именно так:

S = 2040 + ₁₃ * 60 = 2040 - 8 * 60 = 1560 ден. ед.

Один маршрут из построенного цикла, по которому ничего не доставляется, мы должны исключить.

Это маршрут от поставщика A₁ к потребителю B₁ (см. таблицу выше). Теперь данный маршрут незадействованный.

Шаг 5

Полученное решение является оптимальным?

Каждому поставщику A_i ставим в соответствие некоторое число - u _i, называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число - v _j, называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто)

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Примем v₃ = 0.

A₁B₃: v₃ + u₁ = 1, u₁ = 1 - 0 = 1₁B₄: v₄ + u₁ = 2, v₄ = 2 - 1 = 1₃B₃: v₃ + u₃ = 3, u₃ = 3 - 0 = 3₃B₂: v₂ + u₃ = 2, v₂ = 2 - 3 = -1₂B₂: v₂ + u₂ = 5, u₂ = 5 - (-1) = 6

A₂B₁: v₁ + u₂ = 4,v₁ = 4 - 6 = -2

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

Оценка незадействованного маршрута = тариф маршрута - (потенциал поставщика + потенциал потребителя).

A₁B₁: ₁₁ = 7 - (1 + (-2)) = 8₁B₂: ₁₂ = 8 - (1 + (-1)) = 8₂B₃: ₂₃ = 9 - (6 + 0) = 3₂B₄: ₂₄ = 8 - (6 + 1) = 1₃B₁: ₃₁ = 9 - (3 + (-2)) = 8

A₃B₄: ₃₄ = 6 - (3 + 1) = 2

Оценки всех незадействованных маршрутов неотрицательные. Следовательно, уменьшить общую стоимость доставки мы не сможем.

Ответ:

S = 1560 ден. ед.