Раздел 1 Разработка оптимального плана перевозки грузов на рассматриваемом полигоне
Е И З
500 400 500
А
400 Б 1200 В 1400 1100 К 1800
О
Ж
1600 900
1000 800 1000 800
Г 1700 Д 300 П 1100 Л 300 Н
700 500
Р М
Рисунок 1.1 – железнодорожный полигон
Экономико-математическая формулировка задачи
Для решения задачи, прикрепление поставщиков потребителей, используется транспортная задача линейного программирования. (В качестве поставщиков выступают Станции отправления; В качестве потребителей станции назначения)
Данная задача решается для каждого груза отдельно.
Известно:
m – Количество станций отправления.
n – Количество станций назначения.
- количество груза в i-ом
пункте отправления
-
количество груза, которое требуется
доставить в j-ый
пункт назначения.
Критерий оптимальности (Кратчайшее расстояние)
Требуется
найти неотрицательные значения 
,
удовлетворяющий условию, что сумма
транспортных затрат выраженная в т*км,
будет минимальна.
F(функционал) = => min
Данная задача имеет ограничения:
Суммарное количество груза подлежащие отправлению должно быть равно количеству груза, необходимому для станций назначения.
Сумма поставок груза с каждой станции отправления должна быть равна общему наличию груза.
Сумма поставок, в каждый пункт назначения должна быть равна общей потребности груза.
;
Условие неотрицательности поставок.
;
Условие неотрицательности критерия оптимальности.
;
Все эти 5 условий являются условиями допустимости плана. Существуют условия разрешимости:
m+n-1 (Количество поставок, после распределения, должно быть = m+n-1);
Построение исходной матрицы
На основе таблиц 1,2 задания, а так же полигона, строятся исходные матрицы . (6x6; 12x12)
Данная задача решается методом двойного предпочтения.
Порядок решения:
Просматриваем матрицу по строкам и помечаем клетки с min критерием оптимальности.
Просматриваем матрицу по столбцам и помечаем клетки с max критерием оптимальности.
В клетках помеченных дважды проставляются max возможная поставка.
Поставки распределяются по клеткам помеченным 1 раз.
Оставшиеся поставки распределяются с учётом спроса потребителей.
Уголь каменный:
Отправление: Е/690; М/375; Б/846; О/643; К/785; З/1272. Итого: 4611
Прибытие: А/1151; Ж/450; Г/670; Р/700; Н/1300; Д/340. Итого: 4611
-
Поставщики и их грузы
Потребители и их спрос
Итог
А
Ж
Г
Р
Н
Д
1151
450
670
700
1300
340
4611
Е
690
670
20
690
М
375
375
375
Б
846
846
846
О
643
643
643
К
785
700
85
785
З
1272
305
450
282
235
1272
Итог
4611
1151
450
670
700
1300
340
Балласт:
Отправление: М/833; Л/894; Е/829; Г/808; И/768; Б/705. Итого: 4837
Прибытие: Ж/658; В/901; О/976; Д/992; З/562; К/748. Итого: 4837
-
Поставщики и их грузы
Потребители и их спрос
Итог
Ж
В
О
Д
З
К
658
901
976
992
562
748
4837
М
833
833
833
Л
894
143
3
748
894
Е
829
829
829
Г
808
72
284
452
808
И
768
658
110
768
Б
705
705
705
Итог
4837
658
901
976
992
562
748
Тяжеловесные грузы:
Отправление: А/605; Н/413; Р/310; Г/626; О/377; И/599. Итого: 2930
Прибытие: З/572; Л/628; К/358; В/418; Д/457; Ж/497. Итого: 2930
-
Поставщики и их грузы
Потребители и их спрос
Итог
З
Л
К
В
Д
Ж
572
628
358
418
457
497
2930
А
605
409
196
605
Н
413
413
413
Р
310
310
310
Г
626
61
418
147
626
О
377
215
162
377
И
599
102
497
599
Итог
2930
572
628
358
418
457
497
Лес:
Отправление: Б/602; Ж/739; И/584; З/685; К/610; Л/704. Итого: 3928
Прибытие: О/758; Е/607; А/538; Г/611; Н/704; Д/710. Итого: 3928
-
Поставщики и их грузы
Потребители и их спрос
Итог
О
Е
А
Г
Н
Д
758
607
538
611
704
710
3928
Б
602
538
64
602
Ж
739
607
32
100
739
И
584
69
515
584
З
689
689
689
К
610
610
610
Л
704
704
704
Итог
3928
758
607
538
611
704
710
Хлеб:
Отправление: Г/289; К/446; Б/417; К/403; Н/439; З/409. Итого: 2403
Прибытие: В/413; Е/353; Л/340; М/467; А/393; Ж/427. Итого: 2403
-
Поставщики и их грузы
Потребители и их спрос
Итог
В
Е
Л
М
А
Ж
413
353
340
467
393
427
2403
Г
289
289
289
К
446
100
346
446
Б
417
24
393
417
К
413
7
368
18
413
Н
439
340
99
439
З
409
409
409
Итог
2403
413
353
340
467
393
427
Нефть:
Отправление: И/343; Н/397; В/276; Р/256; М/345; Г/285. Итого: 1902
Прибытие: Д/210; К/375; Л/248; А/459; З/281; П/329. Итого: 1902
-
Поставщики и их грузы
Потребители и их спрос
Итог
Д
К
Л
А
З
П
210
375
248
459
281
329
1902
И
343
62
281
343
Н
397
149
248
397
В
276
174
102
276
Р
256
210
46
256
М
345
164
181
345
Г
285
285
285
Итог
1902
210
375
248
459
281
329
Скоропортящиеся грузы:
Отправление: Л/167; И/261; Д/320; Е/287; В/305; Г/337. Итого: 1677
Прибытие: Б/282; К/287; З/398; М/266; А/306; Р/188. Итого: 1677
-
Поставщики и их грузы
Потребители и их спрос
Итог
Б
К
З
М
А
Р
282
287
398
266
306
188
1677
Л
167
167
167
И
261
261
261
Д
370
182
188
370
Е
287
105
83
99
287
В
305
282
23
305
Г
337
31
306
337
Итог
1677
282
287
398
266
306
188
Контейнерные грузы:
Отправление: К/129; З/223; И/275; Р/243; Н/283; М/163; А/255; Е/236; О/196; Л/237; Ж/242; Б/273. Итого: 2755
Прибытие: Г/275; Ж/254; Д/144; Б/266; А/164; Н/196; В/232; И/296; Е/249; Л/163; М/228; О/288. Итого: 2755
Постав-щики и их грузы |
Потребители и их спрос |
Итог |
|||||||||||||
Г |
Ж |
Д |
Б |
А |
Н |
В |
И |
Е |
Л |
М |
О |
||||
275 |
254 |
144 |
266 |
164 |
196 |
232 |
296 |
249 |
163 |
228 |
288 |
2755 |
|||
К |
129 |
|
|
|
|
|
|
|
54 |
|
|
|
75 |
129 |
|
З |
223 |
|
|
|
|
|
|
|
|
223 |
|
|
|
223 |
|
И |
275 |
|
254 |
|
11 |
|
|
|
|
10 |
|
|
|
275 |
|
Р |
243 |
99 |
|
144 |
|
|
|
|
|
|
|
|
|
243 |
|
Н |
283 |
|
|
|
|
|
|
|
|
|
163 |
120 |
|
283 |
|
М |
163 |
|
|
|
|
|
|
|
|
|
|
|
163 |
163 |
|
А |
255 |
|
|
|
255 |
|
|
|
|
|
|
|
|
255 |
|
Е |
236 |
4 |
|
|
|
|
|
232 |
|
|
|
|
|
236 |
|
О |
196 |
129 |
|
|
|
|
|
|
|
|
|
67 |
|
196 |
|
Л |
237 |
|
|
|
|
|
196 |
|
|
|
|
41 |
|
237 |
|
Ж |
242 |
|
|
|
|
|
|
|
242 |
|
|
|
|
242 |
|
Б |
273 |
43 |
|
|
|
164 |
|
|
|
16 |
|
|
50 |
273 |
|
Итог |
275 |
254 |
144 |
266 |
164 |
196 |
232 |
296 |
249 |
163 |
228 |
288 |
|
||
Тарно – штучные грузы:
Отправление: М/238; Ж/194; Р/284; К/237; О/310; Г/234; И/200; Л/252; Д/267; Б/145; А/147; П/284. Итого: 2792
Прибытие: Б/202; И/130; Л/298; Д/269; М/136; Е/153; А/314; Ж/304; В/280; Н/151; Г/305; З/250. Итого: 2792
Постав-щики и их грузы |
Потребители и их спрос |
Итог |
|||||||||||||
Б |
И |
Л |
Д |
М |
Е |
А |
Ж |
В |
Н |
Г |
З |
||||
202 |
130 |
298 |
269 |
136 |
153 |
314 |
304 |
280 |
151 |
305 |
250 |
2792 |
|||
М |
238 |
|
|
46 |
|
|
|
|
104 |
|
|
|
88 |
238 |
|
Ж |
194 |
|
130 |
|
|
|
|
|
|
|
|
|
64 |
194 |
|
Р |
284 |
55 |
|
|
|
|
|
101 |
|
|
|
128 |
|
284 |
|
К |
237 |
|
|
237 |
|
|
|
|
|
|
|
|
|
237 |
|
О |
310 |
|
|
|
|
35 |
|
|
|
|
|
177 |
98 |
310 |
|
Г |
234 |
|
|
|
|
|
153 |
68 |
|
13 |
|
|
|
234 |
|
И |
200 |
|
|
|
|
|
|
|
200 |
|
|
|
|
200 |
|
Л |
252 |
|
|
|
|
101 |
|
|
|
|
151 |
|
|
252 |
|
Д |
267 |
|
|
|
|
|
|
|
|
267 |
|
|
|
267 |
|
Б |
145 |
|
|
|
|
|
|
145 |
|
|
|
|
|
145 |
|
А |
147 |
147 |
|
|
|
|
|
|
|
|
|
|
|
147 |
|
П |
284 |
|
|
15 |
269 |
|
|
|
|
|
|
|
|
284 |
|
Итог |
202 |
130 |
298 |
269 |
136 |
153 |
314 |
304 |
280 |
151 |
305 |
250 |
|
||