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

 

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

Запасы однотипной продукции, которая находится у поставщиков A1, A2, A3.

Потребность в однотипной продукции потребителей B1, B2, B3, B4.

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



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

Решение:

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

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

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


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


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


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


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

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

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

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



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

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


2)



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

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



3)



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

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


4)



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

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



5)



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

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


6)



От поставщика A3 к потребителю B4 будем доставлять 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 , называемое потенциалом потребителя.

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

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

Примем v3 = 0.



A2B3: v3 + u2 = 9, u2 = 9 - 0 = 93B3: v3 + u3 = 3, u3 = 3 - 0 = 33B4: v4 + u3 = 6, v4 = 6 - 3 = 32B2: v2 + u2 = 5, v2 = 5 - 9 = -41B2: v2 + u1 = 8, u1 = 8 - (-4) = 121B1: v1 + u1 = 7, v1 = 7 - 12 = -5



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


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

A1B3: 13 = 1 - ( 12 + 0 ) = -111B4: 14 = 2 - ( 12 + 3 ) = -132B1: 21 = 4 - ( 9 + ( -5 ) ) = 02B4: 24 = 8 - ( 9 + 3 ) = -43B1: 31 = 9 - ( 3 + ( -5 ) ) = 113B2: 32 = 2 - ( 3 + ( -4 ) ) = 3




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

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

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

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



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

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


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 = 14 * 50.


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

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


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


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

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



Шаг 2

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

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

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

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

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

Примем v4 = 0.



A1B4: v4 + u1 = 2, u1 = 2 - 0 = 23B4: v4 + u3 = 6, u3 = 6 - 0 = 61B1: v1 + u1 = 7, v1 = 7 - 2 = 53B3: v3 + u3 = 3, v3 = 3 - 6 = -32B3: v3 + u2 = 9, u2 = 9 - (-3) = 12

A2B2: v2 + u2 = 5, v2 = 5 - 12 = -7



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


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

A1B2: 12 = 8 - ( 2 + ( -7 ) ) = 131B3: 13 = 1 - ( 2 + ( -3 ) ) = 22B1: 21 = 4 - ( 12 + 5 ) = -132B4: 24 = 8 - ( 12 + 0 ) = -43B1: 31 = 9 - ( 6 + 5 ) = -23B2: 32 = 2 - ( 6 + ( -7 ) ) = 3




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

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

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

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



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

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


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 = 21 * 50.


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

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



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


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

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



Шаг 3

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

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

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

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

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

Примем v4 = 0.



A1B4: v4 + u1 = 2, u1 = 2 - 0 = 23B4: v4 + u3 = 6, u3 = 6 - 0 = 61B1: v1 + u1 = 7, v1 = 7 - 2 = 52B1: v1 + u2 = 4, u2 = 4 - 5 = -12B2: v2 + u2 = 5, v2 = 5 - ( -1 ) = 6

A3B3: v3 + u3 = 3, v3 = 3 - 6 = -3



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


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

A1B2: 12 = 8 - (2 + 6) = 01B3: 13 = 1 - (2 + (-3)) = 22B3: 23 = 9 - (-1 + (-3)) = 132B4: 24 = 8 - (-1 + 0) = 93B1: 31 = 9 - (6 + 5) = -23B2: 32 = 2 - (6 + 6) = -10




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

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

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

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



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

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


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 = 32 * 40.


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

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



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


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

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



Шаг 4

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

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

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

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

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

Примем v2 = 0.



A2B2: v2 + u2 = 5, u2 = 5 - 0 = 53B2: v2 + u3 = 2, u3 = 2 - 0 = 23B3: v3 + u3 = 3, v3 = 3 - 2 = 12B1: v1 + u2 = 4, v1 = 4 - 5 = -11B1: v1 + u1 = 7, u1 = 7 - (-1) = 8

A1B4: v4 + u1 = 2,v4 = 2 - 8 = -6



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


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

A1B2: 12 = 8 - (8 + 0) = 01B3: 13 = 1 - (8 + 1) = -82B3: 23 = 9 - (5 + 1) = 32B4: 24 = 8 - (5 + (-6)) = 93B1: 31 = 9 - (2 + (-1)) = 83B4: 34 = 6 - (2 + (-6)) = 10




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

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

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

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



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

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


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 = 13 * 60.


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


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


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


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

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



Шаг 5

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

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

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

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

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

Примем v3 = 0.



A1B3: v3 + u1 = 1, u1 = 1 - 0 = 11B4: v4 + u1 = 2, v4 = 2 - 1 = 13B3: v3 + u3 = 3, u3 = 3 - 0 = 33B2: v2 + u3 = 2, v2 = 2 - 3 = -12B2: v2 + u2 = 5, u2 = 5 - (-1) = 6

A2B1: v1 + u2 = 4,v1 = 4 - 6 = -2



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


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

A1B1: 11 = 7 - (1 + (-2)) = 81B2: 12 = 8 - (1 + (-1)) = 82B3: 23 = 9 - (6 + 0) = 32B4: 24 = 8 - (6 + 1) = 13B1: 31 = 9 - (3 + (-2)) = 8

A3B4: 34 = 6 - (3 + 1) = 2




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

Ответ:


X опт =006014015030000100900

S = 1560 ден. ед.



Введенная Вами таблица дает нам следующую информацию: Запасы однотипной продукции, которая находится у поставщиков A1, A2, A3. Потребность в однотипной пр

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ