Наличие порожняка

В строке записываются значения индексов Vj, а в столбце – значения индексов Ui .
Для дальнейших расчётов необходимо определить количество автомобиле-ездок, их находим по формуле :
Ze= Q/ q*g,
где Q – объём перевозок;
q – грузоподъёмность автомобиля (т);
g-- коэффициент использования грузоподъёмности.
Значения q иgвозьмём из таблицы 3. Результаты вычисления занесём в таблицу 5.

ТАБЛИЦА 5.Расчёт ездок от объёма перевозки грузов (в тоннах).

Пункт отправления	А 1	А 1	А 1	А 2	А 3	А 4	А 4	А 5	А 5	А 6	А 6
Пункт назначения	Б 1	Б 7	Б8	Б 2	Б 5	Б 3	Б 4	Б 1	Б 3	Б 5	Б 6
Объём перевозок	189	81	81	81	81	36	54	108	54	54	54
Количество автомобиле- ездок	42	18	18	18	18	8	12	24	12	12	12

В правом верхнем углу клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами; условиеSbj=Sаi= 194 (ездки)выполняется.

ТАБЛИЦА 6.Допустимый исходный план.

Пункт назначения (образов. порожняка)

Пункт назначения	Вспом. Индек.	Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8	Потребность в перевозках

	Ui \ Vi

А1		425	1	7	8	4	2	1814	1815	78
А2		5	1813	8	6	3	1	7	3	18
А3		12	4	14	13	1811	4	12	10	18
А4		16	7	815	1215	13	5	15	12	20
А5		249	01	1213	6	01	1	4	1	36
А6		3	1	5	3	128	1210	3	2	24

Наличие порожняка		66	18	20	12	30	12	18	18	194/194

План разрабатывается способом минимального элемента по строке. Разработка производится в следующем порядке: сначала, планируются перевозки с первого склада, записывая их в соответствующие клетки первой строки, при этом удовлетворяются запросы потребителя, находящегося ближе всего к этому складу.
Планируем перевозки ближайшим из неудовлетворённых ещё потребителей, записывая соответствующие загрузки в клетки с наименьшими расстояниями. При соблюдении условий, описанных выше, удовлетворяя спрос и предложения пунктов отправления и потребления, происходит заполнение необходимых клеток; остаток по столбцу или строке сносится в клетку остатков, который впоследствии заносится в свободные не вычеркнутые клетки. При этом необходимо соблюдать условие, что количество заполненных клеток должно соответствовать числу m + n -1,где m— число пунктов отправления или погрузки; n – число пунктов погрузки.
В таблице 6 количество занятых клеток равно числу m + n -1=13; а в таблице 6 количество занятых клеток не равно этому числу 13 . Поэтому необходимо создать недостающие клетки, поставив нулевые загрузки в клетки А5-Б2 и А5-Б5.
Допустимый исходный план составлен, проверим его на оптимальность.

п.4.2. Расчёт индексов для занятых клеток.
п.4.2.1. Расчёт суммарного холостого пробега.Рассчитываем суммарный холостой пробег для допустимого исходного плана (таблица 6) с помощью формулы:
nm
SLx =S SXij * lij , { 6 }
j=1 i=1
гдеSLx -- суммарный холостой пробег (км); Xij – количество порожняка, подаваемого между i-ым пунктом назначения, ездки; lij– расстояние от i-ого пункта отправления до j-ого пункта назначения (км).

п.4.2.2. Расчёт индексов.Следующим пунктом вычислений находим индексы для загруженных клеток :
Ui + Vj =lij Xij , { 7 }
Проверка допустимого плана на оптимальность заключается в соблюдении условий:
Ui + Vj =lij , для Xij>0 { 8 } иUi + Vj =lij , дляXij=0 . { 9 }
Для определения индексов используются следующие правила:
а) индексы Ui записываются во вспомогательный столбец ;
б) индексыVj записываются во вспомогательную строку;
в) индексы правой клетки вспомогательного столбца принимаются за нуль:U1=0.
Тогда из уравнения {6}можно выразить Ui и Vj .
Далее, рассчитаем индексы для таблицы 7 допустимого исходного плана по этим правилам.

ТАБЛИЦА 7.Допустимый исходный план( предварительный вариант).

Пункт назначения (образов. порожняка)

Пункт назначения	Вспом. Индек.	Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8	Потребность в перевозках

	Ui \ Vi	5	-3	9	9	-3	-1	14	15

А1	0	425	1	72	81	4	2	1814	1815	78
А2	16	516	1813	817	619	310	114	723	+328	18
А3	14	127	47	149	1310	1811	49	1216	1019	18
А4	6	16	7	815	1215	13	5	155	129	20
А5	4	249	01	1213	67	01	12	419	18	36
А6	11	313	17	515	313	128	1210	322	224	24

Наличие порожняка		66	18	20	12	30	12	18	18	194/194

V1= A1Б1 – U1 = 5-0= 5; V7 = A1Б7 – U1 = 14-0=14; V8 = A1 Б8 – U1= 15-0 =15
……………………….. ………………………….. …………………………
U5= A5Б1 – V1 = 9-5= 4; V3 = A5Б3 – U5 = 13-4= 9; U4= A4 Б3 – V3 = 15-9 =6;
После расчёта индексов проверяем незанятые клетки на потенциальность.
п.4.2.3. Определение потенциальных клеток.Незанятые клетки, для которых получилось, что Ui + Vj >lij – называются потенциальными. Проверяем незанятые клетки на потенциальность. Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов.
А1Б2 = u1 + v2 = 0-3 = -3 <( l1-2=1);
А1Б3 = u1 + v3 = 0+9 = 9 >( l1-3=7)--2;
....................................................................;
А2Б8 =u2 + v8 = 16+15= 31>( l2-8=3)--28;
.....................................................................;
А6Б8 = u6 + v8 = 11+15= 26>( l6-8=2)--24.
По данным вычислений построим таблицу 7.

4.1.5. Оптимизация плана.Проверка допустимого плана на оптимальность заключается в соблюдении условий: {8} e {9}. Если данные условия не соблюдаются для клеток Xij=0, то значение потенциала отрицательно, что и определяет потенциальную клетку. Следует скорректировать допустимый план. Корректировка плана состоит в перемещении в потенциальную клетку с наименьшим по модулю потенциалом какую-нибудь загрузку. Перемещение производится при условии сохранения количества “+” и “-“ по строке и столбцу. Производя перемещение, следует повторить процесс определения потенциала до тех пор, пока условия {8} и {9}не будут соблюдены. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.
Из наличия потенциальных клеток можно сделать вывод, что составленный план не является оптимальным. Выявленные клетки являются резервом улучшения плана, а превышение суммы индексов над расстоянием – потенциалом (в таблице 7 они размещены в нижнем правом углу клетки и выделены другим цветом). Улучшение неоптимального плана сводится к перемещению загрузки в потенциальную клетку матрицы.
Цепочку возможных перемещений определяют: для потенциальной клетки с наибольшим значением потенциала строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна из её вершин находилась в данной клетке, а все остальные вершины в занятых клетках. Знаком “+” отмечают в цепочке её нечётные вершины, считая вершину в клетке с наибольшим потенциалом, а знаком “-“ – чётные вершины. Наименьшая загрузка в вершинах 18 ездок, уменьшая загрузку в вершинах со знаком “-“ и увеличивая её в вершинах со знаком “+” получают улучшенный план. Дальнейшие расчёты по его оптимизации производятся аналогично. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.
В результате всех вычислений имеем конечный оптимальный план возврата порожняка в таблице 8.

ТАБЛИЦА 8.Оптимальный план возврата порожняка.

Пункт назначения (образов. порожняка)

Пункт назначения	Вспом. Индек.	Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8	Потребность в перевозках

Страница: 2 из 4      <-- предыдущая следующая -->

Перейти на страницу: скачать реферат | 1 2 3 4

© 2007 ReferatBar.RU - Главная | Карта сайта | Справка