Мегаобучалка Главная | О нас | Обратная связь


Кружки – пункты потребления.



2018-06-29 351 Обсуждений (0)
Кружки – пункты потребления. 0.00 из 5.00 0 оценок




ТРАНСПОРТНАЯ ЗАДАЧА С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

( В СЕТЕВОЙ ПОСТАНОВКЕ)

В матричной транспортной задаче перевозки осуществляются из пунктов производства только к пунктам потребления. Перевозки между пунктами производства или между пунктами потребления в ней не рассматриваются. Однако на практике перевозки могут осуществляться и через несколько промежуточных пунктов.

Поэтому разработана транспортная модель, в которой допускаются перевозки через промежуточные пункты. В этой модели для каждого пункта составляется уравнение материального отношения с учётом завоза (вывоза) и потребления (производства). Алгоритм решения задачи в сетевой постановке существенно не отличается от задачи в матричной постановке.

 

Математическая постановка

Дано: пунктов (производства, потребления и промежуточных) или вершин. В каждом пункте объём производства равен Qi ( i = 1, …, N );

Для пунктов производства Qi > 0;

Для пунктов потребления Qi < 0;

Для промежуточных пунктов Qi = 0;

rучастков сети (дуг), каждый участок s ( s = 1,…, r ) связывает пункт производства is с пунктом потребления js;

(Cs )матрица себестоимости перевозки единицы груза по s –тому участку (s = 1,…,r).

Считается, что можно по каждому участку осуществлять перевозки из is в jsв одном направлении. Если перевозки допускаются в двух направлениях, то каждый участок фигурирует дважды.

Требуется:определить план P = ( X1, X2, …, Xr ), показывающий объём перевозок по каждому участку сети.

Уравнение материального баланса для каждого j-го пункта выражает то обстоятельство, что объём вывезенного груза минус объём завезённого груза равен «чистому» объёму груза, произведённого в этом пункте (если разность положительна), или «чистому» объёму потребления (если разность отрицательна).

I ≠ j Xij + Qj* = ∑ k ≠ j Xjk + Vj * = Xjj *

Где:

Xijобщий объём перевозок из i в jдля i ≠ j;

Xjj * - суммарный объём поставки в j;

Qj *- объём производства в пункте j;

Vj *- объём потребления в пункте j.

«Чистый» объём производства Qj и потребления Vj выражаются через Qj* и Vj* следующим образом:

Qj = Qj* - min (Qj* , Vj* );

Vj= Vj*- min (Vj* , Vj* ).

1) Xs ≥ 0 (s = 1, …, r);

2) ∑sj Xs - ∑si Xs = | Qi ‌ ‌| (s = 1, …, r);

По каждому i –му пункту, отправляющему данный груз, разность между суммой пустот на всех выходах из него и суммой пустот на всех подходах к нему равна ресурсам груза, подлежащим отправлению из пункта i.

Транспортная задача в сетевой форме впервые была поставлена советскими экономистами в 1929 – 30 гг., но точной математической формулировки она тогда ещё не получила.

 

Условия допустимости плана:

1) Xs ≥ 0 (перевозки не отрицательны);

2) I ≠ j Xij - Xjj = Vj

(общее количество направляемого в пункт j груза минус объём транзитного груза равно «чистому» потреблению);

3) k ≠ j Xjk - Xjj = Qj

(общее количество вывезенного из j груза минус объём транзитного груза равно «чистому» производству).

R

Допустимый план является оптимальным, если s = i Cs Xs - минимальна ( т.е. суммарные затраты минимальны).

§ 2. Критерий оптимальности плана

Для оптимальности допустимого плана необходимо и достаточно, чтобы существовали оценочные числа (потенциалы) а1, а2, …, а n ,удовлетворяющие условиям:

а) аjs – аis = Cs (s = 1, …, r) – для Хs > 0 , т.е. для участков, где существует перевозка;

б) аjs – аis ≤ Cs - для Хs = 0, т.е. для участков, где перевозка не осуществляется (разность потенциалов не превосходит затрат по перемещению единицы груза на данном участке).

Любая транспортная задача в сетевой постановке может быть преобразована в матричную. Однако при большом количестве mиn получается очень громоздкая матрица. Практически транспортные задачи чаще решаются в сетевой постановке.

 

Пример решения задачи

Алгоритм решения задачи проиллюстрируем на следующем примере.

Дано: 3 пункта производства:

Ас объёмом производства QА =50 ед. ( например, 50 вагонов и т.д.);

Сc объёмом производства QC= 150 ед.

Fc объёмом производства QF= 100 ед.

5 пунктов потребления:

Вс объёмом потребления QB= 105 ед.

Eс объёмом потребления QE= 30 ед.

Lс объёмом потребления QL = 30 ед.

Kс объёмом потребления QK = 70 ед.

Dс объёмом потребления QD= 65 ед.

Каждый пункт производства связан с каждым пунктом потребления участком сети.

Известны затраты на перевозку по каждому участку сети. (Смотри схему 1). Например, затраты на перевозку из пункта А в пункт В единицы груза равны 60 ед. и т.д.

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

Решение задачи

Составляем первоначальный план перевозок.

Стрелки красным карандашом.

Прямоугольники – пункты производства.

Кружки – пункты потребления.

 

Схема 1. Первоначальный план перевозки

Исходя из первого условия критерия оптимальности, а именно: ajs – ais = Cs для Xs > 0 определяем систему оценочных чисел (потенциалов).

Пусть аА = 100 (первый потенциал задаём произвольно), тогда следуя по сети участков где осуществляются перевозки, определяем оценочные числа для других пунктов (если перевозки (стрелки) совпадают с направлением движения – суммируем затраты по перевозке на участке, если направлены против движения – вычитаем), таким образом получим:

аЕ = 100 + 25 = 125

аL = 100 + 28 = 128

aF = 128 – 30 = 98

aK = 98 + 30 = 128

aD = 98 + 60 = 158

aC = 158 – 100 = 58

aB = 58 + 80 = 138

Проверяем выполнение второго условия критерия оптимальности, а именно: ajs – ais ≤ Cs для участков, на которых не осуществляется перевозка.

aB – aA = 138 – 100 = 38 < 60

aD – aA = 158 – 100 = 58 < 60

aK – aC =128 – 58 = 70 > 50

Из проверки видно, что на участке КС не выполнено второе условие критерия оптимальности (70 > 50). Следовательно, по участку СК нужно осуществлять перевозку.

Для того, чтобы определить, какое количество груза следует везти из пункта С в пункт К, нужно:

во-первых, построить кольцо, связывающее пункты, между которыми есть связь перевозок (кольцо включает один свободный участок с нарушением, а остальные участки обязательно должны быть заняты) - это кольцо пройдёт по участкам СК, KF, FD, DC;

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

Наименьшим количеством грузов, перевозимым на указанных участках будет 45 ед. (участок DC). Снимаем это количество груза с участка СD и направляем его по участку СК.

Чтобы сохранился баланс перевозок – эти 45 ед. снимаем с участков кольца, по которым грузопоток идёт в противоположном кольцу направлению, и добавляем к участкам кольца, по которым грузопоток идёт в направлении кольца.

Таким образом, мы приходим к плану (схема 2).

 

 

Схема 2

 

В результате улучшения (перераспределения) плана затраты на перевозку уменьшились на (+ 50 – 30 + 60 – 100) х 45 = - 900

Исходя из первого условия критерия оптимальности, а именно: аjs – аis = Сs для хs > 0 определяем систему оценочных чисел.

Пусть аA = 100 (задаём произвольно), тогда

aE = 100 + 25 = 125

aL = 100 + 28 = 128

aF = 128 – 30 = 98

aD = 98 + 60 = 158

aK = 98 + 30 = 128

aC = 128 – 50 = 78

aB = 78 + 80 = 158.

Проверим выполнение второго условия критерия оптимальности, а именно аjs - аis ≤ Сs для участков, на которых не осуществляется перевозка.

aB – аA = 158 – 100 = 58 < 60

aD – аA = 158 – 100 = 58 < 60

aD – аC = 158 – 78 = 80 < 100

aE – аC = 125 – 78 = 47 > 40 - нарушение!

Из проверки видно, что на участке СE не выполнено первое условие критерия оптимальности (47 > 40).

Следовательно, по участку СЕ нужно осуществить перевозку. Строим кольцо (см. схему 2) и путём перераспределения вводим перевозку по участку СЕ. Получаем новый план (схема 3).

∆Э 3-2 = [(90 + 28 + 30) – (25 + 30 + 50)] … х 10... = - 70 ед. ?

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

Схема 3

aA = 100

aL = 100 + 28 = 128

aE = 100 + 25 = 125

aC = 125 – 40 = 85

aB = 85 + 80 = 165

aK = 85 + 50 = 135

aF = 135 – 30 = 105

aD = 105 + 60 = 165

 

aL – аF = 128 – 105 = 23 < 30

aD – аC = 165 – 85 = 80 < 100

aB –аA = 165 – 100 = 65 > 60 - нарушение!

В результате получим новый план (схема 4).

Выигрыш: ∆ Э 4-3 = [ (60 + 40) – (80 + 25) ] х 20 = -100

∆ Э 4-1 = - (900 + 70 + 100) = -1070.

 

 

Схема 4

 

aA = 100

aL = 100 + 28 = 128

aB = 100 + 60 = 160

aC = 160 – 80 = 80

aE = 80 + 40 = 120

aK = 80 + 50 = 130

aF = 130 – 30 = 100

aD = 100 + 60 = 160

 

aE – aA = 120 – 100 = 20 < 25

aL – aF = 128 – 100 = 28 < 30

aD –aC = 160 – 80 < 100

aD –aA = 160 – 100 = 60 = 60

 

Этот план является оптимальным, так как удовлетворяет обоим условиям оптимальности.

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

60 х 20 + 80 х 85 + 40 х 30 + 50 х 35 + 30 х 35 + 28 х 30 + 60 х 65 = 16740 ед. против 17810 в первоначальном плане, экономия – 1070 ед.

По приведённому алгоритму можно также решить задачу с ограниченными пропускными способностями участков и установить, насколько необходимо увеличить пропускную способность лимитирующих участков (приёмных пунктов), чтобы обеспечить перевозку грузов с минимальными затратами. В случае, если XS > qS (где qS - пропускная способность S -го участка), для оптимальности плана необходимо и достаточно выполнение условий:

1) аJS - аIS = СS + dS для XS > 0

2) аJS - аIS ≤ СS + dS для XS = 0

где dS - рента (прокатная оценка) отчётных участков пути, рассчитанная на единицу груза;

3) dS ≥ 0

dS = 0, если XS < qS , т.е. когда объём перевозки на S -том участке меньше его пропускной способности.

Прокатные оценки – это постоянные элементы специального экономического расчёта, учитывающие лимитированность и дефицитность отдельных видов оборудования (в частности, ограничения по пропускной способности). Прокатная оценка показывает, какую экономию труда можно достигнуть введя дополнительное количество наиболее экономичных машин (или повышая пропускную способность на участке пути с минимальной себестоимостью). Для случая транспортной задачи прокатная оценка определяется, например, если вследствие ограниченной пропускной способности пути перевозки с железнодорожного или водного транспорта передаются на более дорогостоящий автомобильный и т.п.

В настоящее время эти оценки по существу пока не учитываются.

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

При решении транспортной задачи в сетевой постановке, как и при матричной, могут встретиться некоторые осложнения (например, «вырождённость»). Этого можно избежать, как и в матричной задаче, путём изменения начальных данных и введения «фиктивного» очень малого потока.

Существует несложное доказательство того, что если в модели с промежуточными пунктами суммарный объём производства отличен от суммарного объёма потребления, то допустимых решений не существует. Иными словами, в сетевой постановке может решаться только «закрытая» модель транспортной задачи.

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

Для установления прямых связей между поставщиками и потребителями на длительный период (2 – 5 лет) целесообразно решать параметрическую транспортную задачу, учитывая изменяющиеся объёмы производства и потребления.



2018-06-29 351 Обсуждений (0)
Кружки – пункты потребления. 0.00 из 5.00 0 оценок









Обсуждение в статье: Кружки – пункты потребления.

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...
Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (351)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.01 сек.)