Транспорт есебінің оптимал шешімі
Қазақстан Республикасының білім және ғылым министрлігі
БҚОББ «Орал газ, мұнай және салалық технологиялар
«Математика және информатика»
ПЦК-сы
Курстық жұмыс
Пәні: «Өндірістік және экономикалық процестерді
Тақырыбы: «Транспорттық есеп»
Орындаған: СТ– 441 топ оқушысы
Нуртазина Н.Н
Тексерген: жетекші Лукпанова Д.М
Орал 2007
Мазмұны
І. Кіріспе ...............................................................................................................3
ІІ. Негізгі бөлім
2.1. Транспорт есебінің моделі ...........................................................................5
2.2. Алғашқы таяныш жоспарларды анықтау ...................................................7
2.3. Транспорт есебінің оптимал шешімі.
Потенциалдар әдісі .......................................................................................9
2.4. Excel программасының көмегімен транспорттық
есептің шешімін табу ....................................................................................16
ІІІ. Қорытынды ....................................................................................................20
ІV. Қолданылған әдебиеттер ..............................................................................21
Кіріспе
Қазіргі қоғамда болып жатқан ақпараттық дамудың өңделу, жеткізілу,
Модельдеу – қазіргі заманғы ғылыми танымның басқарушы принципі.
Компьютерлік математикалық модельдеу информатика пәнімен технологиялық жағынан байланысады.
Сондай-ақ, ЭММ пәнін оқып үйрену кезінде математикалық программалау
Математикалық программалау шектеулі ресурстарды барынша тиімді пайдаланып, қойылған
Әдетте математикалық программалау есебі екі бөліктен атап айтсақ,
Математикалық программалаудың 2 түрі бар: сызықтық программалау және
Математикалық программалаудың қазіргі кезде көбінесе сызықтық теңсіздіктер немесе
Сызықтық программалаудың транспорт есептері экономикалық процестерді зерттеулер мен
2.1. Транспорт есебінің моделі
Транспорт есебінің математикалық қойылуы:
m жабдықтаушыда біркелкі өнім (жүк) жинақталған және оның
Егер xij деп і жабдықтаушысынан j
Жабдықтау-шылар Тұтынушылар Жабдықтау- шылар
В1 В2 ... Вn
А1 С11
Х11 С12
Х12 … C1n
X1n a1
А2 С21
Х21 C22
X22 … C2n
X2n a2
... ... … … … … Аm
Xm1 Cm2
Xm2 … Сmn
Хmn am
b1 b2 … bm
Бұл кестеде есептің негізгі үлестіру кестесі деп аталады.
шарт орындалатын болса, онда бұндай есепті транспорт есебінің
Транспорт есебінің моделінің жалпы түрі төмендегідей жазылады:
мақсат функциясына минимал мән әперетін және мына:
i =1, 2, ... , m
, j = 1, 2, ... , n
xij = 0, i = 1, 2, …
шарттарын қанағаттаныратын Х = (Хij)mxn жүк тасымалдау жоспарын
Мысалы. Кестеде берілген транспорт есебінің моделін құру
аi bj 20 30 40
60 5 6 3
50 2 4 8
Шешуі: і – ші жабдықтаушыдан j – ші
тұтыну мөлшері бойынша,
хij ≥ 0 (i=1, 2, 3)
теріс еместік шарты.
Мақсат функциясы:
Ғ(х) = 5х11 + 6х12 + 3х13 +
Ескерту: Жабдықтаушылар қоры бойынша шектеулер теңсіздіктер түрінде берілген,
2.2. Алғашқы таяныш жоспарларды анықтау
Транспорт есебінің алғашқы таяныш жоспарын табудың бірнеше қарапайым
Келесі транспорт есебінің алғашқы таяныш шешімін «солтүстік-батыс бұрышы»
аi bj 90 40 50
100 7
90 3
10 4 5
70 5 7
30 3
40 6
80 1 6 5
10 3
70
Шешуі: 1. «Солтүстік – батыс бұрышы» әдісінде кестені
Осы таяныш жоспарға сәйкес сызықтық функционалдың мәнін немесе
Ғ(x'T) = 90*7 + 10*3 + 30*7 +
Шешуі: 2. «Минимал элемент» әдісінде транспорт тарифы ескеріледі.
Қажеті немесе жабдықтаушыдағы жүктің қоры xij = ai
аi bj 90 40 50
100 7 3
40 4 5
60
70 5
10 7
3
50 6
10
80 1
80 6 5
3
Нәтижесінде айнымаған келесі жоспарды аламыз:
Сәйкес сызықтық функционалының мәні:
Ғ(х''т) = 40*3 + 60*5 + 10*5 +
Сызықтық функционалдың екі әдіс бойынша табылған мәндерін салыстырып,
Ғ(х'т) =125, Ғ(х''т) =760.
Әрине, бұдан барлық уақытта «минимал элемент» әдісі бойынша
2.3. Транспорт есебінің оптимал шешімі.
Потенциалдар әдісі
Алғашқы таяныш жоспар табылғаннан соң потенциалдар әдісінің көмегімен
Жоғарыда келтірілген әдістердің бірімен алғашқы таяныш жоспар алынады.
Табылған жоспардың оптимал екенін тексеру үшін потенциалдар системасы
Әрбір бос клетка үшін ui + vj >cij
Егер кемінде бір бос клетка үшін ∆ij=(ui +
λ –санын табу үшін жоғарыда анықталған (1, k)
Үлестіруге тиісті жүк мөлшерін (-) таңбасы бар клеткаларда
k - - контурдың (-) пен белгіленген белгілеген
Табылған жаңа жоспар қайтадан тексеріледі. Ол үшін 2-6
2-есеп. Бірінші есептегі «Солтүстік-батыс бұрышы» әдісімен алынған таяныш
аі bj 90 40 50 70 ui
100 7
90 3
10
u1= 0
70 5 7
30
40
u2 = 4
ui 1
+ 8
5
10
70
u3 = 6
vj
v1 = 7
v2 = 3
v3 = -1
v4 = -3
Шешуі: Алынған таяныш жоспар айнымаған. u1= 0 деп
u1 + v1 = 7
u1 + v2 = 3 v2 =
u2 + v2 = 7 u2 =
u2 + v3 = 3 v3
u3 + v3 = 5 u3
u3 + v4 = 3 v4
Потенциалдар жүйесі құрылды:
U = (0; 4; 6); V
Барлық бос клеткалар үшін ∆ij= (ui + vj)
∆13 = u1 + v3 – c13 =
∆14 = u1 + v4 – c14 =
∆21 = u2 + v1 – c21 =
∆24 = u2 + v4 – c24 =
∆31 = u3 + v1 – c31 =
∆32 = u3 + v1 – c32 =
Анықталған барлық ∆ij – дің мәндерін қарастыра келіп,
Үлестірілуі тиіс жүк мөлшері λ – ны мына
Жаңа жоспарды анықтау үшін контурдың (+) таңбалы
λ = 10 – ды қосып, ал (-)
аі bj 90 40 50 70 ui
100 7
90 3
20
u1= 0
70 5 7
20
50
u2 = 4
80 1
10 8
5
3
70
u3 = -6
vj
v1 = 7
v2 = 3
v3 = -1
v4 = 9
Алынған жоспар айнымаған, себебі жабық клеткалар саны m
Ғ=80*7+20*3+20*7+50*3+10*1+70*3=560+60+140+150+10+210=1130
Жаңа жоспарды оптималдыққа тексеру үшін потенциалдарды анықтаймыз.
u1=0
u1 + v1 = 7
u1 + v2 = 3 v2 =
u3 + v1 = 1 u2 =
u2 + v2 = 7 v3
u2 + v3 = 3 u3
u3 + v4 = 3 v4
Бос клеткалар үшін ∆ij – дің мәндерін анықтаймыз:
∆13 =-5 0,
∆24 =7
Транспорт есебінің моделі
Сызықтық программалау есептері және оларды шешу әдістері
СЫЗЫҚТЫҚ ПРОГРАММАЛАУ ЕСЕПТЕРІ
Жүк тасымалдау тиімді моделдеу
Өндірістік және экономикалық процессті модельдеу
Математикалық және сызықтық программалаудың электронды оқулықтарын пайдалану арқылы білім беру деңгейін көтеру
Сызықты программалау есебін сиплекс әдісімен шешу
Тасымалдау есебі ұғымы
Сызықтық программалаудың негізгі есебі
Тасымалдаудың жүк айналымы