Главная / Математика / Научная работа по математике на тему "Транспортная задача"

Научная работа по математике на тему "Транспортная задача"

hello_html_3c0d4aa7.gifhello_html_43cbbb7a.gifhello_html_m38f10217.gifhello_html_5effed40.gifhello_html_509511d7.gifhello_html_m5779b02c.gifhello_html_1cc73dbe.gifhello_html_m6085ff34.gifhello_html_7d51556b.gifhello_html_m424fe948.gifhello_html_3e9a323a.gifhello_html_48e06d6e.gifhello_html_3c68c348.gifhello_html_m1b637803.gifhello_html_m147e0020.gifhello_html_m147e0020.gifhello_html_350a2fe4.gifhello_html_69ddb69e.gifhello_html_mf335914.gifhello_html_m38ddf964.gifhello_html_54e7e68d.gifhello_html_63a13e50.gifhello_html_7fe6d770.gifhello_html_62dd6b6c.gifhello_html_73220623.gifhello_html_m420c849d.gifhello_html_m420c849d.gifhello_html_7dc4ead7.gifhello_html_7dc4ead7.gifhello_html_488a98a9.gifhello_html_37a14522.gifhello_html_mc9d605b.gifhello_html_m56113914.gifhello_html_6e540806.gifhello_html_m297a6621.gifhello_html_m297a6621.gifhello_html_m297a6621.gifhello_html_m297a6621.gifhello_html_4d6f31d9.gifhello_html_1d85a921.gifhello_html_m26cd3755.gifhello_html_185e7c5f.gifhello_html_7efee21a.gifhello_html_4d5766bc.gifhello_html_m106a88d3.gifhello_html_m19222112.gifhello_html_me661ffd.gifhello_html_719f25d2.gifhello_html_25d11dbc.gifhello_html_25d11dbc.gifhello_html_m386501c8.gifhello_html_m19118fc1.gif

Государственная Бюджетное Профессиональное Образовательное Учреждение

Салаватский Индустриальный Колледж









Научная работа

Тема: «Транспортная задача»

Выполнил:

Николаев Алек

Группа 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 км - х л

Х= hello_html_m1b70a31c.gif = 0,08 л на 1 км

  1. 0,08 * 25 = 2 рубля на 1 км

3) hello_html_21debdc4.gif=0,057 А1→В1

hello_html_m710e622d.gif=0,051 А1→В2

hello_html_7d85d29b.gif=0,048 А1→В31→В4

4) hello_html_m60aead3e.gif=0,01 А2→В12→В2

hello_html_2849221f.gif=0,02 А2→В32→В4

5) hello_html_m339caf3.gif=0,08 А3→В2

hello_html_m21a58237.gif=0,0027 А3→В1

hello_html_m339caf3.gif=0,01 А3→В33→В4

6) hello_html_m1bc5f068.gif=0,02 А4→В1

hello_html_39b62570.gif=0,025 А4→В2

hello_html_3181647a.gif=0,01 А4→В3

hello_html_m6d88f91b.gif=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) Каждому поставщику А1234;условному(то есть каждой строке),поставим в соответствие некоторые числа α1; α2; α3; α4; α5, называемые потенциалами для А1234 и условного поставщика обозначим через β1- потенциал для потребителей. Крытого рынка; β2 –для Зелёного рынка; β3 – для колхозного рынка; β4 – для гор торга.

2) Для каждой незаполненной клетки, то есть для каждой небазисной переменной, рассчитываем так называемые косвенные тарифы Сij= αi + βj всегда должно быть m+n-1=8 загружённых клеток Sij=Cij-(αi+ βj) – разность. 3) С11=α11 Пусть α1=0,тогда β1= С11-α1=5,7-0=5,7

С12=α12 β2=С12-α1=5,1-0=5,1

С22=α22 £2=С222=1-5,1=-4,1

С32=α32 £3=С32-β2=1-5,1=-4,1

С33=α33 β3=С33-α3=1-(-4,1)=5,1

С43=α43 £4=С43-β3=1-5,1=-4,1

С44=α44 β4=С44-α4=0,7-(-4,1)=4,8

С54=α54 £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







  1. В виде графа

А1 В1

А2 В2

А3 В3

А4 В4

Затраты поставщика А1 на транспортировку готового продукта выше, чем у других поставщиков.

Поэтому А1 стоит разработать наиболее рациональные пути и способы транспортирования хлеба, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это сократит время передвижения товаров, уменьшит затраты поставщика А1, связанные с осуществлением процессов снабжения хлеба.









Литература

1.А. В. Кузнецов, Н. И. Холод, Л. С. Костевич

Руководство к решению задач по математическому программированию.

Минск: Высшая школа,1978,-с. 110

2. Сарычева Е. Н. Линейное программирование. Учебное пособие.

Уфа: РИОРУНМЦМОРБ,2008,- с. 72

3.Упражнения и задачи по алгебре и линейному программированию. Учебное пособие. Куйбышевский плановый институт. Кафедра высшей математики. 1976

4.Бронштейн И. Н., Семендяев К.А.

Справочник по математике. - М; Наука, 1986







Научная работа по математике на тему "Транспортная задача"
  • Математика
Описание:

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

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

Требуется найти оптимальный план транспортировки готового продукта из конечного числа пунктов поставки с заданными объёмами производства в конечное число пунктов потребителя с известными объёмами потребностей.

Постановка задачи:

Задача исследовательской работы – расчёт транспортной задачи                              методом северо-западного угла;                                                                         методом минимальной стоимости;                                                              распределительным методом;                                                                            методом потенциала со следующим условием:                                                        Четыре поставщика представляют услуги четырём потребителям, каждый по своим тарифам.                                                                                                   

Поставщики: 4 крупные хлебопекарни г. Белебей                                         Потребители: Крытый рынок; Колхозный рынок; Зелёный рынок; гор торг. Готовый продукт: хлеб из пшеничной муки высшего сорта. ГОСТ 27842-88. Масса нетто 0,45 кг. Срок хранения: 1)72 ч в упаковке 2)24 ч без упаковки. 

Определим тарифы Cijперевозки единицы груза из баз поставщиков всем потребителям.

 

В данной работе изложены основные подходы и методы решения транспортной задачи.

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

 

 

     

 

       

 

       
         

    

 

Затраты поставщика А1 на транспортировку готового продукта выше, чем у других поставщиков.

Поэтому А1 стоит разработать наиболее рациональные пути и способы транспортирования хлеба, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это сократит время передвижения товаров, уменьшит затраты поставщика А1, связанные с осуществлением процессов снабжения хлеба.                       

 


 

 

 

 

Автор Волоцкова Резеда Радиковна
Дата добавления 18.03.2015
Раздел Математика
Подраздел Другое
Просмотров 319
Номер материала 58335
Скачать свидетельство о публикации

Оставьте свой комментарий:

Введите символы, которые изображены на картинке:

Получить новый код
* Обязательные для заполнения.


Комментарии:

↓ Показать еще коментарии ↓