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

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

Введенная Вами таблица дает нам следующую информацию:

Запасы однотипной продукции, которая находится у поставщиков A₁, A₂, A₃.

Потребность в однотипной продукции потребителей B₁, B₂, B₃, B₄.

Стоимость доставки единицы продукции от каждого поставщика к каждому потребителю (тарифы маршрутов).

Требуется составить план перевозок, при котором общая стоимость перевозок минимальная.

Решение:

Найдем начальное решение методом северо-западного угла.

Суммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

Запасы поставщиков:

+ 180 + 190 =570 единиц продукции.

Потребность потребителей:

+ 130 + 150 + 140 =570 единиц продукции.

Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

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

Начинаем заполнять таблицу от левого верхнего угла и постепенно "двигаемся" к правому нижнему.

От северо-запада к юго-востоку.

От поставщика A₁ к потребителю B₁ будем доставлять

= {200, 150} = 150 единиц продукции.

2)

От поставщика A₁ к потребителю B₂ будем доставлять

= {50, 130} = 50 единиц продукции.

3)

От поставщика A₂ к потребителю B₂ будем доставлять

= {180, 80} = 80 единиц продукции.

4)

От поставщика A₂ к потребителю B₃ будем доставлять

= {100, 150} = 100 единиц продукции.

5)

От поставщика A₃ к потребителю B₃ будем доставлять

= {190, 50} = 50 единиц продукции.

продукция доставка маршрут поставщик

6)

От поставщика A₃ к потребителю B₄ будем доставлять 140 единиц продукции.

7)

Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Мы нашли начальное решение.

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

S = 150 * 7 + 50 * 8 + 80 * 5 + 100 * 9 + 50 * 3 + 140 * 6 = 3740 ден. ед.

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

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

+ 4 - 1 = 6,

где

- количество строк в таблице.

- количество столбцов в таблице.

Количество задействованных маршрутов не может получиться больше 6, меньше - возможно.

Посчитайте. Количество задействованных маршрутов равно 6, что и требовалось.

В противном случае, мы не сможем найти потенциалы поставщиков и потребителей.

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

Находим потенциалы поставщиков и потребителей.

Зная потенциалы, находим оценки незадействованных маршрутов.

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

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

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

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

Шаг 1

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

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

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

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

Примем v₃ = 0.

A₂B₃: v₃ + u₂ = 9, u₂ = 9 - 0 = 9₃B₃: v₃ + u₃ = 3, u₃ = 3 - 0 = 3₃B₄: v₄ + u₃ = 6, v₄ = 6 - 3 = 3₂B₂: v₂ + u₂ = 5, v₂ = 5 - 9 = -4₁B₂: v₂ + u₁ = 8, u₁ = 8 - (-4) = 12₁B₁: v₁ + u₁ = 7, v₁ = 7 - 12 = -5

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

A₁B₃: ₁₃ = 1 - ( 12 + 0 ) = -11₁B₄: ₁₄ = 2 - ( 12 + 3 ) = -13₂B₁: ₂₁ = 4 - ( 9 + ( -5 ) ) = 0₂B₄: ₂₄ = 8 - ( 9 + 3 ) = -4₃B₁: ₃₁ = 9 - ( 3 + ( -5 ) ) = 11₃B₂: ₃₂ = 2 - ( 3 + ( -4 ) ) = 3

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

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

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

Построим цикл для нового маршрута.

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

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

min = {50, 100, 140} = 50.

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

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

2 * 50 - 8 * 50 + 5 * 50 - 9 * 50 + 3 * 50 - 6 * 50 = ( 2 - 8 + 5 - 9 + 3 - 6 ) * 50 = -13 * 50 = ₁₄ * 50.

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

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

S = 3740 + ₁₄ * 50 = 3740 - 13 * 50 = 3090 ден. ед.

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

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

Шаг 2

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

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

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

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

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

Примем v₄ = 0.

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

A₂B₂: v₂ + u₂ = 5, v₂ = 5 - 12 = -7

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

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

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

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

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

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

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

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

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

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

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

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

4 * 50 - 9 * 50 + 3 * 50 - 6 * 50 + 2 * 50 - 7 * 50 = ( 4 - 9 + 3 - 6 + 2 - 7 ) * 50 = -13 * 50 = ₂₁ * 50.

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

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

S = 3090 + ₂₁ * 50 = 3090 - 13 * 50 = 2440 ден. ед.

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

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

Шаг 3

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

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

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

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

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

Примем v₄ = 0.

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

A₃B₃: v₃ + u₃ = 3, v₃ = 3 - 6 = -3

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

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

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

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

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

Построим цикл для нового маршрута.

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

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

min = {40, 100, 130} = 40.

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

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

2 * 40 - 6 * 40 + 2 * 40 - 7 * 40 + 4 * 40 - 5 * 40 = ( 2 - 6 + 2 - 7 + 4 - 5 ) * 40 = -10 * 40 = ₃₂ * 40.

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

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

S = 2440 + ₃₂ * 40 = 2440 - 10 * 40 = 2040 ден. ед.

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

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

Шаг 4

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

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

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

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

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

Примем 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 ден. ед.