Сызықтық бағдарламалау есебі

 

 

Нәтижеде алынған В кестедегі солтүстік –батыс бұрышындағы толтырылмаған ұяшық x₁₂ болып табылады. Оның мәні мына шарттан анықталады: x₁₂=min(a₁- b₁, b₂).

Айталық, x₁₂= a₁ - b₁, бұл жағдайда қалған барлық ұяшықтар нольге тең: x_1i=0,  (i= ). Ұяшық   a₁ - b₁  астына * белгі қоямыз. Ал  b₂ орнына  b₂ –( a₁- b₁)  жазамыз.

 

 

Жоғарыда сипатталған  алгоритмді келесі мысалда көрсетеміз.

                                                                                                                    

Кесте C

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	x11	x21	x31	180
B2	x12	X22	x32	30
B3	x13	X23	x33	250
B4	x1n	X2n	x3n	120
Қорлар	140	300	140	580

 

Мұнда 140, 300, 140  жүктер тасымалдау станцияларында болып, ал 180, 30, 250, 120 жүктер қабылдау станцияларында орналасқан.

Солтүстік-батыс бұрыш  ұяшығындағы  x₁₁ – A₁ станциядан  B₁ станцияға тасымалданған жүк көлемі және былайша анықталады:

 

x₁₁ = min(a₁, b₁)= min(140, 180)=140.

 

A₁  станцияда жүк қалмағаны үшін,  басқа станцияларға жүк тасымалданбайды:   x₁₂ = x₁₃ = x₁₄ = 0. B₁ станциядағы жүк көлемі мынаған тең: 180 – 140 = 40.

Нәтижеде келесі кестені аламыз:

 

                                                                                                             Кесте D

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	140	x21	x31	40
B2	0	x22	x32	30
B3	0	x23	x33	250
B4	0	x2n	x34	120
Қорлар	*	300	140	580

 

 

Келесі солтүстік-батыс бұрыш ұяшығы x₂₁ болып табылады. Ұяшық x₂₁ мәні былайша анықталады: x₂₁ = min(a₂, b₁)=min(300, 40)=40. Енді B₁ станция жүкке қажеттілігі толық қамтылды: (140 + 40) = 180. Сондықтан x₃₄=0 деп аламыз. Қалдық жүк a₂  мынаған тең: 300-40=260 бірлік жүк. Нәтижеде Кесте E аламыз:   

 

                                                                                                         Кесте E

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	140	40	0	*
B2	0	x22	x32	30
B3	0	x23	x33	250
B4	0	x2n	x34	120
Қорлар	*	260	140	580

 

 

Мұнда мына ұяшықты толтыру  қажет: x₂₂ = min(a₂, b₂) = min(260,30) = 30, x₃₂ = 0. Бірақ A₂ станцияда  260 – 30=230 бірлік жүк қалды және ал басқа ұяшықтар мәні мынаған тең: x₂₃ = min(a₂, b₃)= min(230, 250)=230, x₂₄=0; x₃₃=20; x₂₁=120.

Нәтижеде Кесте F аламыз. F кесте солтүстік-батыс бұрыш  әдісімен құрылған жүкті тасымалдаудың бастапқы жоспарын сипаттайды. Ұяшықтарды солтүстік-батыс бұрыш  әдісімен толтыруда c_ij  қаражаттар есептелінбеді. Сондықтан құрылған бастапқы жоспар тиімді деп есептеуге болмайды:      

 

                                                                                                           Кесте F

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	140	40	0	120
B2	0	30	0	30
B3	0	230	20	250
B4	0	0	120	120
Қорлар	*	260	140	580

 

 

 

 

2.2. Бастапқы жоспарды анықтаудағы ең кіші нарық әдісінің алгоритмі

 

Бұл әдісте ұяшықты  толтыру солтүстік бұрыштан емес, ал жүкті тасымалдауға кетткен ең кіші қаражаттан бастайды. Егер барлық ұяшықтар жүкті тасымалдауға кетткен  қаражаттары бірдей болса, бұл жағдайда ұяшықты толтыруды кез-келген ұяшықтан бастауға болады. Ең кіші нарық әдісті жоғарыда айтылған мысалда көреміз және бастапқы жоспарды анықтап, функционалдың мәнін есептейміз. Функционал мәнін екі әдіспен алынған мәндердің ішінен кішісін таңдаймыз. Сондықтан мына кестеден бастаймыз:

                                                                                              Кесте G

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	x11 3	x21 2	x31 4	180
B2	x12 5	x22 6	x32 7	30
B3	x13 6	x23 5	x33 8	250
B4	x14 8	x24 3	x34 4	120
Қорлар	140	300	140	580

 

Ең кіші қаражат A₂ станциядан B₁ станцияға тасымалданған жүк қаражаты болғандықтан кестені толтыруды x₂₁ ұяшықтан бастау қажет: x₂₁= min(300, 180)=180. B₁ станция жүкпен толық қамтылды, сондықтан нәтижеде алатынымыз: x₁₁= x₃₁=0. Ал A₂ станцияда  120 бірлік жүк қалды. Нәтижеде Кесте G аламыз:

                                                                                                         Кесте G

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	0 3	180 2	0 4	*
B2	x12 5	x22 6	x32 7	30
B3	x13 6	x23 5	x33 8	250
B4	x14 8	x24 3	x34 4	120
Қорлар	140	120	140	580

 

Келесі ең кіші қаражаты болған ұяшық x₂₄ болып, былайша анықталады:        

x₂₄ = min(a₂, b₄)=min(120,120). Бұл амалдарды қайта-қайта жалғастырып, келесі кестені аламыз:

                                                                                                                 Кесте I

Тасымалдау  станциялары	A1	A2	A3	Қабылдай алатын жүктер көлемі
Қабылдау станциялары
B1	0  3	180 2	0 4	*
B2	30 5	0 6	0 7	30
B3	110 6	0 5	140 8	250
B4	0 8	120 3	0 4	120
Қорлар	140	300	140	580

Солтүстік батыс  бұрыш әдісі бойынша есептелінген функционал мәні

F= 2*180 +5*30 + 6*110 + 8*140 +3*120 =2650$, ал ең кіші нарық әдіс бойынша есептлінген мәні F= 3*140 +2*40 + 6*30 + 5*230 +8*20 + 4*120 =2470$. Сондықтан бастапқы жоспар ретінде ең кіші нарық әдісі бойынша алынған жоспарды алуға болады.

Қорытынды

 

 

Кез келген есеп үшін математикалық моделі құрылып, моделдің ақиқатығын тексеру мақсатында, тексеріп көреміз. Сондықтан пакеттерді қолдануға болады. Мысалы үшін Excel пакетінде түрлі экономикалық есептерді қиыншылықсыз шешіп, нәтижелер алуға болады. Олар сызықтық бағдарламалаудың есебінің шығарылуын қамтамасыз етеді.

Курстық жұмыста жүкті  тиімді тасымалдау есебінің математикалық модлі қаралып, оны шешу әдісі- потенциалдар әдісін қолдану үшін бастапқы эоспарды анықтау мәселері қарастырылды. Бастапқы жоспарды анықтаудағы екі әдіс: солтүстік батыс бұрыш, ең кіші қаражат әдістері толығымен сипатталып, мысалдармен алгоритмдердің күрделігі айқындалды.

Қорыта айтқанда бұл  моделді басқа саладағы есептерге  қолдануға болады. Бірақ қолдануда бастапқы жоспарды анықтау ерекше орын алады. Бастапқы жоспарды (бастапқы және шекералық шарттарды) анықтамай тұрып, қойылған есептің дұрыс шешімін алу мүмкін емес. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пайдаланылған әдебиеттер

 

1. Банди Б. Основы линейного программирования. -М.: Радио и связь, 1983. -176 с.
2. Каримов А.К. Математикалық моделдеудің өмірдегі орны.-Алматы:Қазақ университеті, 2001.-357б.
3. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. –М.: Наука, 1977. –367 с.    
4. Вершинин О.Е. Компьютер для менеджера. -М.: Высшая школа, 1990. -240 с.
5. Еремин И.И., Астафьев Н.Н. Введение в теории  линейного и выпуклого программирования. –М.: Наука, 1976. –191 с.
6. Карасев А.Н., Кремер Н.Ш., Савельева Т.Н. Математические  методы в экономике. -М.: Наука, 1987. –330 с.   
7. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. -М.: Высшая школа, 1980. –540 с.
8. Лищенко В.Л.  Линейное и нелинейное программирования.           -М.: Наука, 1987. –220 с.
9. Распин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. Теория, методы и приложения. -М.: Радио и связь, 1982. –239 с.
10. Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование. Теория,  методы и приложения. -М.: Наука, 1969. –424 с.
11. Файсман А. Профессиональное программирование на Турбо-Паскале. –М.: Мир, 1992.
12. Мартин Дж. Организация баз данных в вычислительных системах. –М.: Мир, 1980-425с.
13. Цикритзис Д., Лоховски Ф. Модели данных. –М.: Финансы и статистика, 1985-215с.