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

Размещено на http://www.allbest.ru/

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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

2)

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

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



3)

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

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

4)

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

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



5)

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

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

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

6)

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



7)

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

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

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

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

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

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

3 + 4 - 1 = 6,

где

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 1

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

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

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

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

Примем v₃ = 0.



A₂B₃: v₃ + u₂ = 9, u₂ = 9 - 0 = 9

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

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

A₂B₂: v₂ + u₂ = 5, v₂ = 5 - 9 = -4

A₁B₂: v₂ + u₁ = 8, u₁ = 8 - (-4) = 12

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

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

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

A₁B₃: ₁₃ = 1 - ( 12 + 0 ) = -11

A₁B₄: ₁₄ = 2 - ( 12 + 3 ) = -13

A₂B₁: ₂₁ = 4 - ( 9 + ( -5 ) ) = 0

A₂B₄: ₂₄ = 8 - ( 9 + 3 ) = -4

A₃B₁: ₃₁ = 9 - ( 3 + ( -5 ) ) = 11

A₃B₂: ₃₂ = 2 - ( 3 + ( -4 ) ) = 3



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

A₃B₄: v₄ + u₃ = 6, u₃ = 6 - 0 = 6

A₁B₁: v₁ + u₁ = 7, v₁ = 7 - 2 = 5

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

A₂B₃: v₃ + u₂ = 9, u₂ = 9 - (-3) = 12

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

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

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

A₁B₂: ₁₂ = 8 - ( 2 + ( -7 ) ) = 13

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

A₂B₁: ₂₁ = 4 - ( 12 + 5 ) = -13

A₂B₄: ₂₄ = 8 - ( 12 + 0 ) = -4

A₃B₁: ₃₁ = 9 - ( 6 + 5 ) = -2

A₃B₂: ₃₂ = 2 - ( 6 + ( -7 ) ) = 3



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

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

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

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

Пусть ячейка 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

A₃B₄: v₄ + u₃ = 6, u₃ = 6 - 0 = 6

A₁B₁: v₁ + u₁ = 7, v₁ = 7 - 2 = 5

A₂B₁: v₁ + u₂ = 4, u₂ = 4 - 5 = -1

A₂B₂: v₂ + u₂ = 5, v₂ = 5 - ( -1 ) = 6

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

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

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

A₁B₂: ₁₂ = 8 - (2 + 6) = 0

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

A₂B₃: ₂₃ = 9 - (-1 + (-3)) = 13

A₂B₄: ₂₄ = 8 - (-1 + 0) = 9

A₃B₁: ₃₁ = 9 - (6 + 5) = -2

A₃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

A₃B₂: v₂ + u₃ = 2, u₃ = 2 - 0 = 2

A₃B₃: v₃ + u₃ = 3, v₃ = 3 - 2 = 1

A₂B₁: v₁ + u₂ = 4, v₁ = 4 - 5 = -1

A₁B₁: v₁ + u₁ = 7, u₁ = 7 - (-1) = 8

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

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

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

A₁B₂: ₁₂ = 8 - (8 + 0) = 0

A₁B₃: ₁₃ = 1 - (8 + 1) = -8

A₂B₃: ₂₃ = 9 - (5 + 1) = 3

A₂B₄: ₂₄ = 8 - (5 + (-6)) = 9

A₃B₁: ₃₁ = 9 - (2 + (-1)) = 8

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



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

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

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

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

Пусть ячейка 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

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

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

A₃B₂: v₂ + u₃ = 2, v₂ = 2 - 3 = -1

A₂B₂: v₂ + u₂ = 5, u₂ = 5 - (-1) = 6

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

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

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

A₁B₁: ₁₁ = 7 - (1 + (-2)) = 8

A₁B₂: ₁₂ = 8 - (1 + (-1)) = 8

A₂B₃: ₂₃ = 9 - (6 + 0) = 3

A₂B₄: ₂₄ = 8 - (6 + 1) = 1

A₃B₁: ₃₁ = 9 - (3 + (-2)) = 8

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



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

Ответ:

X опт =		0	0	60	140
		150	30	0	0
		0	100	90	0

S = 1560 ден. ед.

Размещено на Allbest.ru