Расчет затрат на перевозки

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

Пусть в р пунктах отправления находятся соответственно a1, a2, ..., ар единиц однородного груза, который должен быть доставлен q потребителям в количествах b1, b2, ..., bq единиц. Заданы стоимости cik перевозок единицы груза из i-го пункта отправления k-му пункту потребления. Обозначим xik - количество единиц груза, перевозимого из i-го пункта отправления k-му потребителю; тогда переменные xik, должны удовлетворять следующим ограничительным условиям:

1)

2)

3) xik ?0.

Суммарные затраты на перевозки равны L=c11.·x11 + c12.·x12 + * * * + cpqxpq. Следовательно, требуется найти pq переменных хik, удовлетворяющих указанным условиям и минимизирующих целевую функцию L.

Решение такой задачи разбивается на два этапа:

1) определение исходного опорного решения;

2) построение последовательных итераций, т. е. приближение к оптимальному решению.

1) Определение исходного опорного решения.

Метод минимального элемента заключается в том, что из всей таблицы стоимостей выбирают наименьшую стоимость, и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Пусть мы имеем таблицу исходных данных задачи

Проверим необходимое и достаточное условие разрешимости задачи:

?ai = 280 + 220 + 190 = 690

?bj = 190 + 140 + 180 + 120 + 170 = 800

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равную 110 (800--690). Тарифы перевозки единицы груза из базы во все магазины полагаем равными нулю.

Занесем исходные данные в распределительную таблицу:

Этап I. Поиск первого опорного плана. Искомый элемент равен 5

Для этого элемента запасы равны 280, потребности 140. Поскольку минимальным является 140, то вычитаем его.

x12 = min(280,140) = 140.

Искомый элемент равен 5

Для этого элемента запасы равны 190, потребности 190. Поскольку минимальным является 190, то вычитаем его.

x31 = min(190,190) = 190.

Искомый элемент равен 7

Для этого элемента запасы равны 140, потребности 180. Поскольку минимальным является 140, то вычитаем его.

x13 = min(140,180) = 140.

Искомый элемент равен 10

Для этого элемента запасы равны 220, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x23 = min(220,40) = 40.

Искомый элемент равен 13

Для этого элемента запасы равны 180, потребности 120. Поскольку минимальным является 120, то вычитаем его.

x24 = min(180,120) = 120.

Искомый элемент равен 15

Для этого элемента запасы равны 60, потребности 170. Поскольку минимальным является 60, то вычитаем его.

x25 = min(60,170) = 60.

Искомый элемент равен 0

Для этого элемента запасы равны 110, потребности 110. Поскольку минимальным является 110, то вычитаем его.

x45 = min(110,110) = 110.

Значение целевой функции для этого опорного плана равно:

L = 5*140 + 7*140 + 10*40 + 13*120 + 15*60 + 5*190 + 0*110 = 5490

Этап II. Приближение к оптимальному решению

Получив исходное опорное решение, перейдем к построению новых опорных решений, улучшающих друг друга, применив метод потенциалов.

Итак, после построения исходного опорного решения все переменные разбиты на две группы: хkl --базисные и xpq -- свободные, и линейные функции стоимости перевозок выразятся через свободные переменные так:

Для нахождения коэффициентов гpq при свободных переменных сопоставим каждому пункту отправления Аi некоторую величину ui (i=l, 2, ..., m), которую назовем потенциалом пункта Аi, и каждому пункту назначения Bj величину vj -- потенциал пункта Bj.

Свяжем эти величины равенством

uk + vl = ckl,

где ckl -- стоимость перевозки одной единицы груза из пункта Аi в пункт Вj. Доказывается, что совокупность уравнений uk + vl = ckl, составленных для всех базисных переменных, составляет совместную систему линейных уравнений, причем значение одной из переменных можно задавать произвольно, и тогда значения остальных переменных находятся из системы однозначно.

Обозначим для свободных переменных сумму соответствующих потенциалов через c'pq, т. е.

up + vq = c'pq,

и назовем ее косвенной стоимостью (в отличие от данной стоимости срq).

Коэффициенты при свободных переменных:

гpq = cpq - c'pq

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

Мы получили исходное опорное решение (следуя правилу «минимального элемента»):

Для нахождения потенциалов необходимо решить систему:

затраты перевозки итерация

u1 + v2 = c12 =5

u1 + v3 = c13 =7

u2 + v3 = c23 =10

u2 + v4 = c24 =13

u2 + v5 = c25 =15

u3 + v1 = c31 =5

u4 + v5 = c45 =0

Значение одного из неизвестных зададим произвольно, например u1 = 1. Тогда v2 = 4, v3 = 6, u2 = 4, v4 = 9, v5 = 11, u3 = 1, v1 = 4, u4 = - 11.

Далее вычисляем косвенные стоимости c'pq:

Подсчитаем теперь разности

гpq = cpq -- с'рq:

Следовательно, выражение L через свободные переменные имеет вид:

L = 5490 + 3x11 - 2x14 - 1x15 + 2x21 + 2x32 + 2x33 + 6x34 + 10x35 + 7x41 + 7x42 + 5x43 + 2x44

Среди коэффициентов при переменных в правой части есть отрицательные при x14 и x15.

Следовательно, можно уменьшить L за счет увеличения x14

Получим новый план перевозок

L = 5*20+7*140+8*120+8*120+10*40+15*60+5*190+0*110=5250

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

Для нахождения потенциалов необходимо решить систему:

u1 + v2 = c12 =5

u1 + v3 = c13 =7

u1 + v4 = c14 =8

u2 + v2 = c22 =8

u2 + v3 = c23 =10

u2 + v5 = c25 =15

u3 + v1 = c31 =5

u4 + v5 = c45 =0

Значение одного из неизвестных зададим произвольно, например u1 = 1. Тогда v2 = 4, v3 = 6, v4 = 7, u2 = 4, v5 = 11, u3 = 1, v1 = 4, u4 = - 11.

Далее вычисляем косвенные стоимости c'pq:

Подсчитаем теперь разности

гpq = cpq -- с'рq

Следовательно, выражение L через свободные переменные имеет вид:

L = 5250 + 3x11- 1x15 + 2x21 + 2x24 + 2x32 + 2x33 + 8x34 + 10x35 + 7x41 + 7x42 + 5x43 + 4x44

Среди коэффициентов при переменных в правой части есть отрицательный при x15.

Следовательно, L можно уменьшить за счет увеличения x15

Получим новый план перевозок

L = 5*20+7*80+8*120+11*60+8*120+10*100+5*190+0*110=5190

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

Для нахождения потенциалов необходимо решить систему:

u1 + v2 = c12 =5

u1 + v3 = c13 =7

u1 + v4 = c14 =8

u1 + v5 = c25 =11

u2 + v2 = c22 =8

u2 + v3 = c23 =10

u3 + v1 = c31 =5

u4 + v5 = c45 =0

Значение одного из неизвестных зададим произвольно, например u1 = 1. Тогда v2 = 4, v3 = 6, v4 = 7, v5 = 10, u2 = 4, u3 = 1, v1 = 4, u4 = - 10.

Далее вычисляем косвенные стоимости c'pq:

Подсчитаем теперь разности

гpq = cpq -- с'рq:

Следовательно, выражение L через свободные переменные имеет вид:

L = 5190 + 3x11+ 2x21 + 2x24 + 1x25 + 2x32 + 2x33 + 8x34 + 11x35 + 6x41 + 6x42 + 4x43 + 3x44

Среди коэффициентов при переменных в правой части нет отрицательных. Следовательно, исходное опорное решение является оптимальным.

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