Виды ТЭО распределения товаров: транспортное, экспедиционное, коммерческо-правовое, информационно-консультационное

Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными. Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю.Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ). Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид:

 – условие сбалансированности. Это - условие для решения закрытых транспортных задач (ЗТЗ).

2.2. Условие транспортной задачи.

Организация работы по доставке груза между грузовладельцем и грузополучателями для выполнения курсового проекта представлена на схеме (рис. 1). Подвижной состав автотранспортного предприятия осуществляет перевозку песка из двух пунктов (из карьера, который находится в Ленинградской области, и из пункта погрузки, находящегося в черте города) до пунктов выгрузки на ул. Магнитогорской, ул. Руставели и на Киевском шоссе. В карьер и пункт погрузки машины возвращаются порожнем.

Организовать доставку песка в соответствии со схемой курсового проекта (рис. 1) при условии минимизации целевой функции по стоимости.

 

 

 

 

 

 

 

 

Рис. 1. Схема организации перевозок грузов

 

 

3. Решение Транспортной задачи

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

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.

 

4. Построение начального плана перевозок

Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

 

Потребители\Поставщики	ул. Магнитогорская	ул. Руставели	Киевское шоссе	Запасы
Карьер	90	105	80	50 000
Погрузочный пункт	60	75	85	70 000
Потребности	45 000	35 000	40 000

 

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

=

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков.

=50 000+70 000=120 000

=45 000+35 000+40 000=120 000

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

Клетка (i, j) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.

Построим начальный план перевозок т.е назначим объемы перевозок в клетки таблицы таким образом, чтобы:

а)число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);

б)сумма перевозок в любой строке должна быть равна запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ)  для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

1.Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j- номер потребителя).

2.В качестве перевозок в эту клетку назначаем наименьшую из ai и потребности bj.

xij = min{ai,bj }

З.Уменьшим запас ai и потребность bjна величину перевозки xij , т.е.

ai = ai - xij ,

bj =bj -xij

 

4.При исчерпании запаса (ai=0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности(bj=0) запрещаем такие же клетки вj-ом столбце.

В случае одновременного исчерпания запасов потребностей (ai=bj=0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.

Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).

 

Потребители \Поставщики	В1	В2	В n	Запасы
А1	90(-)	105 (10 000)	80 (40 000)	50 000
А2	60(45 000)	75 (25 000)	85 (-)	70 000
Потребности	45 000	35 000	40 000

 

 Подсчитаем число занятых клеток таблицы m+n-1=3+2-1=4 в результате полученный опорный план является допустимым, так как число занятых клеток таблицы равно 4 и соответствует формуле (m+n–1), т.е. опорный план является невырожденным.

Клетки таблицы, в которых записаны поставки, называются базисными, а остальные клетки – свободными.

Неотрицательная матрица X , удовлетворяющая условиям задачи, называется планом (или допустимым планом) задачи. Допустимый план называется оптимальным, если он доставляет минимум целевой функции.

Допустимый план, имеющий не более m+n−1 отличных от нуля компонентов xij, называется базисным, или опорным. Опорный план, имеющий ровно m+n−1 отличных от нуля компонент, называется невырожденным, а если число отличных от нуля компонент меньше, чем m+n−1, то план называется вырожденным.

 

5. Проверка текущего плана на оптимальность

Признаком того, что текущий план перевозок является оптимальным, служит условие

ui +vj -cij ≤0 (1)

 

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

 

ui+ vj = cij (2)

 

Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно.

Поскольку число занятых клеток равно m+n-1, то для однозначного определения потенциалов ui, vjодин из них можно брать произвольно, например, u1=0 (или число, отличное от нуля - неважно).

Потенциалы записываются в дополнительных строке и столбце. Пусть v2=0(выгоднее брать в качестве нулевой переменной ту, которая соответствует строке или столбцу с наибольшим количеством заполненных клеток), тогда остальные потенциалынаходятся последовательно следующим образом:

v3=0

v3+u1=c31=80 => u1=80 

v2+u1=c21=105 => v2=25

v2+u2=c22=75 => u2=50

v1+u2=c12=60 => v1=10

 

Потребители \Поставщики	В1	В2	В n	Ui
А1	90	105	80	80
А2	60	75	85	50
Vi	10	25	0

 

Считаем оценки для свободных клеток:

∆ij=cij-(ui+ vj)

∆11=90 – (10+80) = 0

∆32=85 – (0+50) = 35

 

Полученный опорный план является оптимальным, так как все оценки для свободных клеток ∆ij≥0. Выписываем оптимальный план:

 

Z =45 000*60+25 000*75+10 000*105+40 000*80=8 825 000  (руб.)

 

6. Определение места расположения распределительного склада на обслуживаемой территории.

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

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

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

 

7. Задание

На территории района (рис. 2) имеется 8 магазинов. Методом определения центра тяжести грузопотоков найти ориентировочное место для расположения склада, снабжающего магазины.

В табл. 1 приведены координаты обслуживаемых магазинов (в прямоугольной системе координат), а также их месячный объем перевозок.

Таблица 1

Объем перевозок и координаты обслуживаемых магазинов.

№ магазина	Координата Х, км	Координата Y, км	Объем перевозок, т/мес
			вариант
1	10	10	10
2	23	41	10
3	48	59	15
4	36	27	20
5	60	34	30
6	67	20	25
7	81	29	5
8	106	45	30