Т оптимизация әдістері пәнінен практикум

280 ақшалай бірлік мөлшерінде минималды табысты алу үшін, бірінші тасымалдаушы 60 бірлікке тең жүкті, екінші тұтынушыға жіберуі тиіс, екінші тасымалдаушы үшінші (20 бірлік) және төртінші (60 бірлік) тұтынушылар арасында жүкті бөледі, үшінші тасымалдаушы бірінші тұтынушыға – 40 бірлік, үшінші тұтынушыға – 60 бірлік қорды жібереді.

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын солтүстік-батыс бұрышы әдісімен табу.

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын солтүстік-батыс бұрышы әдісімен табу.

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын кіші элементтер әдісімен табу.

Берілген жүк тасымалдау есебінің тиімді шешімін потенциалдар әдісімен табу.

Берілген жүк тасымалдау есебінің тиімді шешімін потенциалдар әдісімен табу.

1. 
   Жүк тасымалдау есебінің жалпы қойылымы неде?
   
2. 
   Жүк тасымалдау есебінің ашық және жабық түрлеріне анықтама беріңіз.
   
3. 
   Жүк тасымалдау есебінің бастапқы тірек жоспары дегеніміз не?
   
4. 
   Жүк тасымалдау есебінің бастапқы тірек жоспары қалай табылады?
   
5. 
   Цикл дегеніміз не?
   
6. 
   Циклды құрастыру ережелерін анықтаңыз.
   
7. 
   Потенциалдар әдісінің алгоритмын атап өтіңіз.
   

A) егер барлық тұтынушылардың талаптары толық орындалуға тиісті болса

B) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен көп болса

C) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен аз болса

D) B және C жауаптары

E) дұрыс жауабы жоқ

**********
1.2. Жүк тасымалдау есебі қай жағдайда жабық деп аталады?

A) егер барлық тұтынушылардың талаптары толық орындалуға тиісті болса

B) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен көп болса

C) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен аз болса

D) B және C жауаптары

E) дұрыс жауабы жоқ

**********
1.3. Жүк тасымалдау есебінің бастапқы тірек жоспарын қай әдістермен табуға болады?

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) потенциалдар әдісімен

D) А және B жауаптары

E) А, B және С жауаптары

**********
1.4. Жүк тасымалдау есебінің шешімі қай әдіспен табылады?

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) потенциалдар әдісімен

D) А және B жауаптары

E) А, B және С жауаптары

**********
1.5. Берілген жүк тасымалдау есебінің анықталған тірек жоспарға сәйкес тасымалдау шығыны нешеге тең?

A) 120

C) 520

E) 510

A) 500

C) 575

E) 555

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) қосалқы әдіс

D) потенциалдар әдісі

E) аппроксимация әдісі

**********
1.8. Жүк тасымалдау есебінің бастапқы тірек жоспары қай әдіспен анықталған?

B) солтүстік-батыс бұрышы әдісімен

C) қосалқы әдіс

D) потенциалдар әдісі

E) аппроксимация әдісі

**********

A) _ij=u_i+c_ij+v_j+x_ij

B) _ij=u_i+c_ij-v_j+x_ij

C) _ij=u_i+c_ij-v_j

D) _ij=u_i+c_ij-x_ij

E) _ij=u_i+c_ij+v_j-x_ij

**********
1.10. Жүк тасымалдау есебі берілген.

A) 2

C) 1

E) -1

Бүтінсандық есептің қойылымы келесіде: F=∑c_jx_j функцияның келесі шарттар

∑a_jx_j=b_i, i=1,m

x_j≥0, x_j€N, j=1,n

орындалған кезде максималды мәнін табу

Егер де бүтінсандық шарты кейбір айнымалыларға ғана қойылатын болса, онда есеп жартылай бүтінсанды болып есептелінеді.

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

Гомор әдісінің алгоритмы

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

мұнда J-бос айнымалылардың индекстері. Барлық коэффициенттерді және бос айнымалыны (1) екі қосылғышқа бөлу – бүтін және бөлшек.

∑h_ijx_j≥f_t (2) теңсіздігі Гомори қимасы деп аталады. Қосымша шарт келесі түрге ие болады:

∑h_ijx_j-x_n+1≥f_t (3)

3. 
   (3) теңдікті алдында шешілген есепке қосып, сызықты программалау есебінің жаңа түрін анықтаймыз, оны қайта симплекс әдісімен шешеміз. Егер де оның шешімі бүтінсандық болса, осы шешім бастапқы есептің бүтінсандық шешімі болып табылады. Егер де шешім бүтінсандық болмаса, онда жаңа Гомори қимасын анықтап, әрі қарай сәйкесінше жалғастырады.
   

Берілген функцияның F=2X₁+2X₂ келесі шарттар орындалған кезде

2X₁-X₂≤7

-X₁+2X₂≤3

X₁, X₂≥0, X₁, X₂€N максимум мәнін табу.

Шешімі:

Есепті бүтінсандық шартына қарамастан, симплекс әдісімен шешеміз. Алдынала есепті негізі түріне келтіру.

2X₁-X₂+Х₃=7

-X₁+2X₂₊X₄=3

Хт=(17/3; 13/3; 0; 0), F_max=20.

Шешім бүтінсандық емес, сондықтан Гомори қимасын анықтаймыз. Соңғы симплекс кестесінен бірінші теңдеуді аламыз, себебі Х1 айнымалысының бөлшегі ең жоғары (17/3=2/3, 13/3=1/3)

Х₁+2/3Х₃+1/3Х₄=17/3

Қима келесі түрге ие болады 2/3X₃+1/3X₄≥2/3 немесе 2/3X₃+1/3X₄-X₅=2/3, мұнда Х₅≥0.

Осы соңғы шартты соңғы симплекс кестесінің шарттарын қосып, жаңа есепті анықтаймыз:

X₁+2/3X₃+1/3X₄=17/3

X₂+1/3X₃+2/3X₄=13/3

2/3X₃+1/3X₄-X₅=2/3

X_j≥0, j=1,5

Есептің шешімін симплекс әдісімен табамыз.

Базис	Сб	В	2	2	0	0	0
			Х1	Х2	Х3	Х4	Х5
		17/3	1	0	2/3	1/3	0
Х1	2	13/3	0	1	1/3	2/3	0
Х2	2	2/3	0	0	2/3	1/3	-1
Х1	2	5	1	0	0	0	1
Х2	2	4	0	1	0	½	½
Х3	0	1	0	0	1	½	-3/2
j		18	0	0	0	1	3

Хт=(5; 4; 1; 0; 0), F_max=18.

Анықталған шешім бүтінсанды, бастапқы есептің шешімі Хт=(5; 4), F_max=18.

Есеп 2.

19/3м³ ауданды кәсіпорын цехнде қосалқы құрылғы қою үшін берілд. Екі түрлі құрылғыны сатып алу үшін кәсіпорын 10мың руб. жұмсай алады. Құрылғының I ші түрінің бір комплекті 1000 руб. Тұрады, ал II түрі 3000 руб. тұрады. Құрылғының I-ші түрінің бір комплекті бірінші ауысым екі бірлікке, ал II түрдің бір комплекі өнімнің шығаруын төрт бірлікке өсіреді. Құрылғының I-ші түрінің орнату үшін 2м² аудан қажет, ал II-ші түрдің орнату үшін 1м² аудан қажет екенің біле тұра, қосалқы құрылғының қайсысы өнімнің максималды өсуіне мүмкіндік туғызатының анықтау.

Есептің математикалық моделін құрастырамыз. Кәсіпорын х₁ комплект I-ші түрлі және х₂ II-ші түрлі құрылғыны алды деп санайық. Онда х₁ және х₂ айнымалылары келесі теңсіздікті қанағаттандыру керек:

Егер кәсіпорын көрсетілген мөлшерде құрылғыны алса, онда өнім шығарылымы мынаны құрайды