Размещено на http: //www. allbest. ru/
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛА С.О. МАКАРОВА»
Кафедра математического моделирования и прикладной информатики
Лабораторная работа № 6
на тему “ Транспортная задача”
Моделирование транспортных процессов
Выполнила студентка гр.УВТ-3
Проверила профессор, к.э.н., доцент Шилкина И.Д.
Санкт-Петербург 2020
1. Вариант №12
Цель работы: решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
Необходимо решить транспортную задачу методом потенциалов.
Исходные данные
Таблица 1
|
Пункты отправления |
Объем вывоза, тыс. тонн |
|
|
В |
400 |
|
|
Г |
560 |
|
|
Е |
580 |
Таблица 2
|
Пункты назначения |
Объем ввоза, тыс. тонн |
|
|
К |
390 |
|
|
Л |
520 |
|
|
М |
220 |
|
|
Н |
260 |
|
|
П |
210 |
Расстояния между пунктами:
Таблица 3
|
В - К |
160 |
Г- К |
185 |
Е- К |
350 |
|
|
В- Л |
200 |
Г- Л |
270 |
Е- Л |
400 |
|
|
В- М |
170 |
Г- М |
130 |
Е- М |
340 |
|
|
В - Н |
330 |
Г - Н |
90 |
Е - Н |
230 |
|
|
В - П |
170 |
Г - П |
105 |
Е - П |
180 |
Алгоритм решения транспортной задачи методом потенциалов
1. Разработка начального плана.
2. Расчет потенциалов.
3. Проверка плана на оптимальность.
4. Поиск максимального звена не оптимальности, если условие оптимальности было нарушено.
5. Составление контура перераспределения ресурсов.
6. Определение минимального элемента в контуре перераспределения ресурсов.
7. Получение нового плана.
Описанная процедура повторяется несколько раз, пока не будет найдено оптимальное решение.
Математическая постановка задачи:
1) Искомые переменные:
- количество груза, которое будет перевозиться из i-го пункта отправления в j-й пункт назначения в оптимальном плане;
2) Целевая функция:
;
Z = Xвк*160+Xвл*200+ Xвм*170+ Xвн*330 +Xвп*170+ Xгк*185 +Xгл*270+ +Xгм*130+Xгн*90+Xгп*105+Xек*350+Xел*400+Xем*340+Xен*230+ +Xеп*180
3) Ограничения:
3.1. для всех i=1,2,3, j=1,2,3,4,5;
3.2. для всех i=1,2,3;
Xвк + Xвл + Xвм + Xвн + Xвп =400
Xгк + Xгл + Xгм + Xгн + Xгп=560
Xел + Xел + Xем + Xен + Xеп =580
3.3. для всех j=1,2,3,4,5.
Xвк + Xгк + Xек = 390
Xвл + Xгл + Xел = 520
Xвм + Xгм + Xем = 220
Xвн + Xгн + Xен = 260
Xвп + Xгп + Xеп = 210
Решение транспортной задачи
Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
Таблица 4
|
Qi Vj |
К 390 |
Л 520 |
М 220 |
Н 260 |
П 210 |
ai |
||||||
|
400 В |
50(2) |
160 |
50(3) |
200 |
- |
170 |
- |
330 |
- |
170 |
||
|
560 Г |
-(1) |
185 |
20(4) |
270 |
130 |
130 |
50 |
90 |
0 |
105 |
||
|
580 Е |
- |
350 |
- |
400 |
- |
340 |
- |
230 |
300 |
180 |
||
|
bj |
Наличие груза у поставщиков равно:
Qi=400+560+580=1540
Общая потребность в грузе в пунктах назначения равна:
Vj=390+520+220+260+210=1600
Модель транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт отправления Q4 c запасами 1600? 1540=60.
Тарифы перевозки из пункта отправления Q4 во все пункты назначения полагаем равными нулю. В результате получим закрытую модель транспортной задачи:
Таблица 5
|
Qi Vj |
К 390 |
Л 520 |
М 220 |
Н 260 |
П 210 |
ai |
||||||
|
400 В |
160 |
400 |
200 |
170 |
330 |
170 |
0 |
|||||
|
560 Г |
340 |
185 |
270 |
220 |
130 |
90 |
105 |
35 |
||||
|
580 Е |
50 |
350 |
60 |
400 |
340 |
260 |
230 |
210 |
180 |
200 |
||
|
60 А |
0 |
60 |
0 |
0 |
0 |
0 |
-200 |
|||||
|
bj |
150 |
200 |
95 |
30 |
-20 |
Z1 = 340*185 + 50*350 + 400*200 + 60*400 + 60*0 + 220*130 + 260*230+210*180 = 310600
Для расчета потенциалов и нахождения оптимального плана число заполненных клеток должно быть равно 5+4-1=8.
Проверка плана на оптимальность:
Признак оптимальности - выполнение следующего неравенства для пустых клеток:
транспортный потенциал груз доставка
(В;К) = 0+150=150<160
(В;М) = 0+95=95<170
(В;Н) = 0+30=30<330
(В;П) =0-20=-20<170
(Г;Л) = 35+200=235<270
(Г;Н) = 35+30=65<90
(Г;П) = 35-20=15<105
(Е;М) = 200+95=295<340
(А;К) = -200+150=-50<0
(А;М) = -200+95=-105<0
(А;Н) = -200+30=-170<0
(А;П) = -200-20=-220<0
Проверка плана на выполнение ограничений:
340+50=390-выполнено
400+60+60=520-выполнено
220=220-выполнено
260=260-выполнено
210=210-выполнено
400=400-выполнено
340+220=560-выполнено
50+60+260+210=580-выполнено
60=60-выполнено
Вывод: Минимальный суммарный грузооборот 310 600 тыс.т-км.
Из пункта отправления В вывоз всех грузов составил 400 тыс.тонн, т.е. из В в Л-400 тыс.т. Из пункта Г вывоз всех грузов составил 560 тыс.т., т.е. из Г в К-340 тыс.т, в М-220 тыс.т. Из пункта Е вывезли 580 тыс.т., т.е. из Е в К-50 тыс.т., в Л-60 тыс.т, в Н-260 тыс.т, в П-210 тыс.т. Из дополнительного пункта А вывезено 60 тыс.т, т.е. из А в Л-60 тыс.т.
В пункт назначения К ввоз составляет 390 тыс.т., т.е. из Г в К-340 тыс.т., из Е в К-50 тыс.т.. В пункт Л должны ввезти 520 тыс.т.(ВЛ-400 тыс.т., ЕЛ-60 тыс.т, АЛ-60 тыс.т). В пункт М должны ввезти 220 тыс.т.(ГМ-220 тыс.т.). В пункт Н должны ввезти 260 тыс.т.(ЕН-260 тыс.т.). В пункт П должны ввезти 210 тыс.т.(ЕП-210 тыс.т.).