Государственная
Бюджетное Профессиональное Образовательное Учреждение
Салаватский
Индустриальный Колледж
Научная
работа
Тема:
«Транспортная задача»
Выполнил:
Николаев
Алек
Группа 1С1
Руководитель:
Волоцкова
Р. Р.
2015г.
Оглавление.
1.Введение
2-3
2.Метод
северо-западного угла 4-5
3.Метод
минимальной стоимости 5-6
4.Распредилительный
метод 6-11
5.Метод
потенциалов 11-17
6. Заключение
18
7. Литература.
Ссылки 19
8. Приложение
Введение
Транспортные
задачи служат для распределения товаров между поставщиками и потребителями,
таким образом, чтобы общая стоимость этого распределения была минимальной.
Цель:
Требуется найти
оптимальный план транспортировки готового продукта из конечного числа пунктов
поставки с заданными объёмами производства в конечное число пунктов потребителя
с известными объёмами потребностей.
Постановка задачи:
Задача
исследовательской работы – расчёт транспортной задачи методом
северо-западного угла;
методом минимальной стоимости;
распределительным методом; методом
потенциала со следующим условием:
Четыре поставщика представляют услуги четырём потребителям, каждый по своим
тарифам. Поставщики:
4 крупные хлебопекарни г. Белебей Потребители:
Крытый рынок; Колхозный рынок; Зелёный рынок; гор торг. Готовый продукт: хлеб
из пшеничной муки высшего сорта. ГОСТ 27842-88. Масса нетто 0,45 кг. Срок
хранения: 1)72 ч в упаковке 2)24 ч без упаковки. (Приложение 1)
Определим тарифы Cij перевозки
единицы груза из баз поставщиков всем потребителям.
1)
100 км - 8 л
1
км - х л
Х=
= 0,08 л на 1 км
2)
0,08 * 25 = 2 рубля на 1 км
3) 
=0,057 А1→В1
=0,051 А1→В2
=0,048 А1→В3,А1→В4
4) 
=0,01 А2→В1,А2→В2
=0,02 А2→В3,А2→В4
5) 
=0,08 А3→В2
=0,0027 А3→В1
=0,01 А3→В3,А3→В4
6) 
=0,02 А4→В1
=0,025 А4→В2
=0,01 А4→В3
=0,007 А4→В4
Метод
северо-западного угла
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
2370
|
|
А1
630
|
 5,7
440
|
5,1
 190
|
4,8
|
4,8
|
|
|
А2
370
|
1
|
1
 370
|
2
|
2
|
|
|
А3
740
|
0,3
|
1
 640
|
1
 100
|
1
|
|
|
А4
550
|
2
|
2,5
|
1
 170
|
0,7
380
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
|
|
2290
|
|
|
Просматривается
матрица тарифов перевозок С, начиная с левого верхнего угла (клетки). В эту
клетку записывается величина D=min(A,B)
. Она вычитается из запасов и потребностей соответствующего склада и магазина.
Обнулившаяся строка или столбец исключается из рассмотрения, затем процесс
опять повторяется для левой верхней клетки оставшейся матрицы и так до тех пор
пока весь запас товаров не будет исчерпан.
Проверим необходимое и достаточное условие разрешимости задачи.
∑а=630+370+740+550=2290; ∑b=440+1200+270+460=2370.
Так как ∑а<∑b, то есть 2290<2370,то
модель данной транспортной задачи имеется открытой. Для того, чтобы получить
закрытую модель введём условного поставщика с объёмом 80.Так как потребность
рынков удовлетворены и весь груз вывезен из хлебопекарен, то первый опорный
план соответствует системе ограничений транспортной задачи. Число занятых
клеток таблицы – 8, а должно быть m+n-1=8.
Значит, опорный план является невырожденным. Найдём целевую функцию:f(x)=5,7*400+190*5,1+1*370+64*1+1100*1+170*1+380*0,7=5023
Метод
минимального элемента
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
2370
|
|
А1
630
|
5,7
|
5,1
450
|
4,8
180
|
4,8
|
|
|
А2
370
|
1
|
1
370
|
2
|
2
|
|
|
А3
740
|
0,3
440
|
1
300
|
1
|
1
|
|
|
А4
550
|
2
|
2,5
|
1
90
|
0,7
460
|
|
|
Условный
поставщик
80
|
|
0
80
|
|
0
|
|
|
2290
|
|
|
Алгоритм метода
минимального элемента состоит в следующем. Просматривается вся матрица
перевозок, и из неё выбирается позиция с наименьшим значением тарифа С, затем
просматриваются значения наличия запасов на складе А и потребности у
потребителя В, затем в данную клетку записывается величина D=min(A,B).
Из запасов соответствующего склада и потребностей магазина вычитается величина D.
Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего
рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то
этот столбец исключается из дальнейшего рассмотрения. Может быть случай, когда
одновременно исключаются и строка и столбец, этот случай называется
вырожденным. В дальнейшем весь процесс повторяется до тех пор, пока не будет
исчерпан весь запас товаров на складах и не будет удовлетворена потребность
всех магазинов.
1)
Переменной х13 соответствует
клетка с минимальной стоимостью перевозки с13 =0,3. Х31=min{740,440}=440.Столбец
1 исключается из дальнейшего рассмотрения, а наличие груза у третьего
поставщика уменьшается на 740-440=300
2)
Х44=min{550,460}=С44=0,7
3)
Х32= min{740-440,1200}=
min{300,1200}=300;С32=1
4)
Х43= min{550-460,270}=
min{90,270}=90;С43=1
5)
Х22= min{370,1200-300}=
min{370,900}=370;С22=1
6)
Х13= min{630,270-90}=
min{630,180}=180;С13=4,8
7)
Х12= min{630-180,530}=
min{450,530}=450;С12=5,1
Проверка
f(x)=440
* 0,3 + 450 * 5,1 + 370 * 1 + 300 * 1 + 80 * 0 + 180 * 4,8 + 90 * 1 + 460 *
0,7=4373 Метод
минимального элемента даёт решение более близкое к оптимальному, чем применение
метода северо-западного угла.
Распределительный метод
Алгоритм решения:
прежде всего отыскивается какое-то решение задачи — исходный опорный план.
Затем посредством специальных показателей опорный план проверяется на
оптимальность. Если план оказывается не оптимальным, переходят к другому плану.
При этом второй и последующие планы должны быть лучше предыдущего. Так за
несколько последовательных переходов от не оптимального плана приходят к
оптимальному. Рассмотрим первый опорный план.
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
2370
|
|
А1
630
|
 
5,7
440
|
5,1
190
|
4,8
|
4,8
|
|
|
А2
370
|
1
|
 1
370
|
2
|
2
|
|
|
А3
740
|
0,3
|
1
 640
|
1
 100
|
1
|
|
|
А4
550
|
2
|
2,5
|
1
170
|
0,7
380
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
|
|
2290
|
|
|
1) Выберем
максимальную оценку свободной клетки А2В1:
Для этого в перспективную
клетку А2В1 поставим знак “+”, а в остальных вершинах
многоугольника чередующиеся знаки “-”, “+”, “-”. Цикл таков А2В1→А2В2→А1В2→А1В1
-5,7
+5,1
1-1+5,1-5,7=-0,6; -0,6<0 – перспективный, то есть годный
+1 -1
2) А4В2:
-1 +1
2,5-1+1-1=1,5>0 – не год.
+2,5 -1
3) А2В3:
-1 +2
2-1+1-1=1>0 – не год.
+1 -1
4) А2В4:
-1 +1
1-,7+1-1=0,3<0 – не год.
+1 -0,7
5) А3В1:-5,7
+5,1
0,3-1+5,1-5,7=-1,3
– перспективный
+0,3 -1
Из грузов стоящих
в минусовых клетках, выберем наименьший min{440,640}=440.
440 прибавляем к объёмам грузов, стоящих в плюсовых клетках и 440 вычитаем из
объёмов грузов в минусовых клетках. В результате получим новый опорный план.
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
2370
|
|
А1
630
|
5,7
|
5,1
 630
|
4,8
|
4,8
|
|
|
А2
370
|
  1
|
1
 370
|
2
|
2
|
|
|
А3
740
|
0,3
440
|
1
 200
|
1
 100
|
1
|
|
|
А4
550
|
2
|
2,5
|
1
170
|
0,7
380
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
|
|
2290
|
|
|
1) А2В1:
+1 -1
1-1+1-0,3=0,7>0 – не год.
-0,3 +1
2) А2В3:
-1 +2
2-1+1-1=1>0 – не год.
+1 -1
3) 
А3В4:
-1 +1
1-0,7+1-1=0,3>0 – не год.
+1 -0,7
4) А4В2:
-1 +1
2,5-1+1-1=1,5 >0 – не год.
+2,5 -1
5) А1В1:
+5,7 -5,1
5,7-5,1+1-0,3=1,3>0 – не год.
-0,3 +1
6) А1В3:
-5,1 +4,8
4,8-1+1-5,1=-0,3<0 – перспективный
+1 -1
7) min{100,630}=100
.
Составим новый опорный план.
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
2370
|
|
А1
630
|
5,7
|
5,1
  530
|
4,8
 100
|
4,8
|
|
|
А2
370
|
  1
|
1
370
|
2
|
2
|
|
|
А3
740
|
0,3
440
|
1
300
|
1
|
1
|
|
|
А4
550
|
2
|
2,5
|
1
170
|
0,7
380
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
|
|
2290
|
|
|
1)А3В1:
+1 -1
1-1+1-0,3=0,7>0
– не год.
-0,3 +1
2)А2В3:
+5,1 -4,8
2-4,8+5,1-1=1,3>0 – не год.
-1 +2
3) А3В3:+5,1
-4,8
5,1-4,8+1-1=0,3>0 – не год.
-1 +1
4) А1В4:-4,8
+4,8
4,8-4,8+1-,7=0,3>0 – не год
+1 -0,7
5) А1В1:+5,7
-5,1
-0,3 +1 5,7-5,1+1-0,3=1,3>0
– не год.
f(x)=440*0,3+530*5,1+370*1+300*1+100*4,8+170*1+380*0,7+80*0=4421
Метод
потенциалов
При пользовании методом потенциалов для
решения транспортной задачи отпадает наиболее трудоёмкий элемент
распределительного метода: поиски циклов с отрийательной ценой.Алгоритм решения
транспортной задачи методом потенциалов:1.Взять любой опорный план перевозок, в
котором отмечены m+n-1
базисных клеток (остальные клетки свободные). 2.Определить для этого плана
платежи (αi и
βj)
исходя из условия, чтобы в любой базисной клетке псевдо стоимости были равны
стоимостям. Один из платежей можно назначить произвольно, например, положить
равным нулю. 3.Подсчитать псевдо стоимости Cij=
αi
+ βj для
всех свободных клеток. Если окажется, что все они не превышают стоимостей, то
план оптимален. 4.Если хотя бы в одной клетке псевдо стоимость превышает
стоимость, следует приступить к улучшению плана путём переброски перевозок по
циклу, соответствующему любой свободной клетке с отрицательной ценой (для
которой псевдо стоимость больше стоимости). 5.После этого заново подсчитываются
платежи и псевдо стоимости, и, если план ещё не оптимален, процедура улучшения
повторяется до тех пор, пока не будет найден оптимальный план.
|
Потр.
Пост.
|
Крытый
рынок
(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
Потенциал
строк
αi
|
|
|
А1
630
|
5,7
 440 -
|
5,1
+ 190
|
4,8
|
4,8
|
α1=0
|
|
|
А2
370
|
1
|
1
370
|
2
|
2
|
α2=-4,1
|
|
|
А3
740
|
0,3 0,3 +
|
1
-
640
|
1
100
|
1
|
α3=-4,1
|
|
|
А4
550
|
2
|
2,5
|
1
170
|
0,7
380
|
α4=-4,1
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
α5=-4,8
|
|
|
Потенциал
Столбцов
βj
|
β1=5,7
|
β2=5,1
|
β3=5,1
|
β4=4,8
|
|
|
|
|
f=5023
1) Каждому
поставщику А1;А2;А3;А4;условному(то
есть каждой строке),поставим в соответствие некоторые числа α1;
α2; α3; α4; α5, называемые
потенциалами для А1;А2;А3;А4
и условного поставщика обозначим через β1-
потенциал для потребителей. Крытого рынка; β2 –для
Зелёного рынка; β3 – для колхозного рынка; β4 – для гор
торга.
2) Для каждой
незаполненной клетки, то есть для каждой небазисной переменной, рассчитываем
так называемые косвенные тарифы Сij=
αi + βj
всегда должно быть m+n-1=8
загружённых клеток Sij=Cij-(αi+
βj)
– разность. 3)
С11=α1+β1 Пусть α1=0,тогда
β1= С11-α1=5,7-0=5,7
С12=α1+β2
β2=С12-α1=5,1-0=5,1
С22=α2+β2
£2=С22-β2=1-5,1=-4,1
С32=α3+β2
£3=С32-β2=1-5,1=-4,1
С33=α3+β3
β3=С33-α3=1-(-4,1)=5,1
С43=α4+β3
£4=С43-β3=1-5,1=-4,1
С44=α4+β4
β4=С44-α4=0,7-(-4,1)=4,8
С54=α5+β4
£5=С54-β4=0-4,8=-4,8
|
клетка
|
разность
|
|
А1В3
|
S13=4,8-(0+5,1)=-0,3<0
|
|
А1В4
|
S14=4,8-(0+4,8)=0
|
|
А2В1
|
S21=1-(-4,1+5,7)=-0,6<0
|
|
А2В3
|
S23=2-(-4,1+5,1)=1
|
|
А2В4
|
S24=2-(-4,1+4,8)=1,3
|
|
А3В1
|
S31=0,3-(-4,1+5,7)=-1,3<0
– самая перпект.
|
|
А3В4
|
S34=1-(-4,1+4,8)=0,3
|
|
А4В1
|
S41=2-(-4,1+5,7)=0,4
|
|
А4В2
|
S42=2,5-(-4,1+5,1)=1,5
|
|
А5В1
|
S51=0-(-4,8+5,7)=-0,9<0
|
|
А5В2
|
S52=0-(-4,8+5,1)=-0,3<0
|
|
А5В3
|
S53=0-(-4,8+5,1)=-0,3<0
|
Из всех свободных
клеток А1В3; А2В1; А3В1;
А5В1; А5В2; А5В3
самая перспективная клетка А3В1.
-5,4
+5,1
0,3-1+5,1-5,7=-1,3<0
+0,3 -1 min{440;640}=
440
Получим новый опорный план.
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
Потенциал
строк
αi
|
|
|
А1
630
|
5,7
|
5,1
 630 -
|
4,8
+
|
4,8
|
α1=0
|
|
|
А2
370
|
1
|
1
370
|
2
|
2
|
α2=-4,1
|
|
|
А3
740
|
0,3
440
|
1
200 +
|
1
- 100
|
1
|
α3=-4,1
|
|
|
А4
550
|
2
|
2,5
|
1
170
|
0,7
380
|
α4=-4,1
|
|
|
Условный
поставщик
80
|
|
|
|
0
80
|
α5=-4,8
|
|
|
Потенциал
Столбцов
βj
|
β1=4,4
|
β2=5,1
|
β3=5,1
|
β4=4,8
|
|
|
|
f=4451
|
|
клетка
|
разность
|
|
А1В1
|
S11=5,7-(4,4+0)=1,3
|
|
А1В3
|
S13=4,8-(0+5,1)=-0,3<0 – самая
перспект.
|
|
А1В4
|
S14=4,8-(0+4,8)=0
|
|
А2В1
|
S21=1-(-4,1+4,4)=0,7
|
|
А2В3
|
S23=2-(-4,1+5,1)=1
|
|
А2В4
|
S24=2-(-4,1+4,8)=1,3
|
|
А3В4
|
S34=1-(-4,1+4,8)=0,3
|
|
А4В1
|
S41=2-(-4,1+4,4)=1,7
|
|
А4В2
|
S42=2,5-(-4,1+5,1)=1,5
|
|
А5В1
|
S51=0-(-4,8+5,7)=0,4
|
|
А5В2
|
S52=0-(-4,8+4,4)=-0,3<0
|
|
А5В3
|
S53=0-(-4,8+5,1)=-0,3<0
|
Выберем клетку А1В3
как самую перспективную.
-5,1
+5,1 4,8-1+1-5,1=-0,3<0
+1
-1 min{630;100}=100
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
Потенциал
строк
αi
|
|
А1
630
|
5,7
|
5,1
 530 -
|
4,8
100 +
|
4,8
|
α1=0
|
|
А2
370
|
1
|
1
370
|
2
|
2
|
α2=-4,1
|
|
А3
740
|
0,3
440
|
1
300
|
1
|
1
|
α3=-4,1
|
|
А4
550
|
2
|
2,5
|
1
-
1
170
|
0,7
+ 380
|
α4=-3,8
|
|
Условный
поставщик
80
|
|
+
|
|
0
-
80
|
α5=-4,5
|
|
Потенциал
Столбцов
βj
|
β1=4,4
|
β2=5,1
|
β3=4,8
|
β4=4,5
|
|
f=440*0,3+530*5,1+370*1+300*1+100*4,8+170*1+380*0,7+80*0=4421
|
клетка
|
разность
|
|
А1В1
|
S11=5,7-(4,4+0)=1,3
|
|
А1В4
|
S14=4,8-(0+4,5)=0,3
|
|
А2В1
|
S21=1-(-4,1+4,4)=0,7
|
|
А2В3
|
S23=2-(-4,1+4,8)=1,3
|
|
А2В4
|
S24=2-(-4,1+4,5)=1,6
|
|
А3В3
|
S33=1-(-4,1+4,8)=0,3
|
|
А3В4
|
S34=1-(-4,1+4,5)=0,6
|
|
А4В1
|
S41=2-(-3,8+4,4)=1,4
|
|
А4В2
|
S42=2,5-(-3,8+5,1)=1,2
|
|
А5В1
|
S51=0-(-4,5+4,4)=0,1
|
|
А5В2
|
S52=0-(-4,5+5,1)=-0,5<0 – самый
перспект.
|
|
А5В3
|
S53=0-(-4,5+4,8)=-0,3<0
|
-5,1 +4,8
-1
+0,7 С52=0-5,1+4,8-1+0,7-0<0
min{530;80}=80
+0 -0
|
А1
630
|
5,7
|
5,1
450
|
4,8
180
|
4,8
|
α1=0
|
|
А2
370
|
1
|
1
370
|
2
|
2
|
α2=-4,1
|
|
А3
740
|
0,3
440
|
1
300
|
1
|
1
|
α3=-4,1
|
|
А4
550
|
2
|
2,5
|
1
90
|
0,7
460
|
α4=-3,8
|
|
Условный
поставщик
80
|
|
80
|
|
0
|
α5=-5,1
|
|
Потенциал
Столбцов
βj
|
β1=4,4
|
β2=5,1
|
β3=4,8
|
β4=4,5
|
|
|
Потр.
Пост.
|
Крытый
рынок(B1)
440
|
Зелёный
рынок(B2)
1200
|
Колхозный
рынок (В3)
270
|
Гор
торг (В4)
460
|
Потенциал
строк
αi
|
|
клетка
|
разность
|
|
А1В1
|
S11=5,7-(4,4+0)=1,3
|
|
А1В4
|
S14=4,8-(0+4,5)=0,3
|
|
А2В1
|
S21=1-(-4,1+4,4)=0,7
|
|
А2В3
|
S23=2-(-4,1+4,8)=1,3
|
|
А2В4
|
S24=2-(-4,1+4,5)=1,6
|
|
А3В1
|
S31=2-(-3,8+4,4)=1,4
|
|
А3В2
|
S32=2,5-(-3,8+5,1)=1,2
|
|
А3В3
|
S33=1-(-4,1+4,8)=0,3
|
|
А3В4
|
S34=1-(-4,1+4,5)=0,6
|
|
А4В1
|
S41=0-(-5,1+4,4)=0,7
|
|
А4В3
|
S42=0-(-5,1+4,8)=0,3
|
|
А4В3
|
S43=0-(-5,1+4,5)=0,6
|
f=4373
Так как все разности положительные, то
получен оптимальный план перевозки. Ответ:4373
Заключение
В данной работе
изложены основные подходы и методы решения транспортной задачи.
Данная задача
имеет один оптимальный план поставки груза. Покажем это:
1) В
виде матрицы
|
|
В1
|
В2
|
В3
|
В4
|
|
А1
|
0
|
450
|
180
|
0
|
|
А2
|
0
|
370
|
0
|
0
|
|
А3
|
440
|
300
|
0
|
0
|
|
А4
|
0
|
0
|
90
|
460
|
2) В
виде графа
А1
В1
А2
В2
А3
В3
А4
В4
Затраты поставщика А1
на транспортировку готового продукта выше, чем у других поставщиков.
Поэтому А1 стоит
разработать наиболее рациональные пути и способы транспортирования хлеба,
устранить чрезмерно дальние, встречные, повторные перевозки. Всё это сократит
время передвижения товаров, уменьшит затраты поставщика А1,
связанные с осуществлением процессов снабжения хлеба.
Литература
1.А.
В. Кузнецов, Н. И. Холод, Л. С. Костевич
Руководство
к решению задач по математическому программированию.
Минск:
Высшая школа,1978,-с. 110
2.
Сарычева Е. Н. Линейное программирование. Учебное пособие.
Уфа:
РИОРУНМЦМОРБ,2008,- с. 72
3.Упражнения
и задачи по алгебре и линейному программированию. Учебное пособие. Куйбышевский
плановый институт. Кафедра высшей математики. 1976
4.Бронштейн
И. Н., Семендяев К.А.
Справочник
по математике. - М; Наука, 1986
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.