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

Сызықты программалау есебін негізгі түріне келтіру:

min Z=-x₁+5x₂+2x₄-3x₅

x₁-x₂+x₄+2x₅≤2,

x₁+2x₂-x₃+x₅≤3,

2x₁-x₂+x₃+2x₄≤6,

-5x₁+x₂+x₅≥8

x_j≥0 (j=1,5)

Сызықты программалау есебін негізгі түріне келтіру:

max Z=-x₁+x₂-2x₃+x₄

x₁-x₂-x₃+2x₄≤6,

-x₁+x₂+2x₃+x₄≥8,

2x₁+2x₂-x₃+3x₄≤10,

-3x₁+5x₂+3x₃-x₄=15

x_j≥0 (j=1,4)

Сызықты программалау есебін негізгі түріне келтіру:

min Z=x₁-x₂-2x₃

x₁-2x₂+x₃≥4,

-3x₁+x₂+x₃≤9,

2x₁+3x₂+3x₃=10

x_j≥0 (j=1,3)
Тапсырма 4.

Сызықты программалау есебін негізгі түріне келтіру:

max Z=-x₁+x₂+2x₃

x₁-x₂+x₃≥2,

5x₁+2x₂-x₃≥10,

2x₁-2x₂+x₃≥7,

x_j≥0 (j=1,3)
Тапсырма 5.

Сызықты программалау есебін негізгі түріне келтіру:

max Z=-x₁+x₂-2x₃+x₄

2x₁-x₂-3x₃+2x₄≤4,

-2x₁+4x₂+2x₃+x₄≤8,

2x₁+x₂-x₃+3x₄≤15,

x_j≥0 (j=1,4)
Бақылау сұрақтары

1. 
   Сызықты программалау есебінің жалпы түрін анықтаңыз.
   
2. 
   Сызықты программалау есебінің негізгі түрін анықтаңыз.
   
3. 
   Сызықты программалау есебінің симметриялық түрін анықтаңыз.
   
4. 
   Сызықты программалау есебінің математикалық моделі дегеніміз не?
   
5. 
   Сызықты программалау есебінің негізгі қойылымы. Негізгі формасының ерекшеліктері неде?
   
6. 
   Үш жазу формасының эквиваленттігі неде және осы формаларды бір-біріне аудару әдістерін атап өтіңіз.
   

1.1. Экстремалды есептерді және олардың шешу әдістерін қарастыратын математикалық пән қалай аталады?

А) сызықты программалау;

В) математикалық программалау;

С) сызықты емес программалау;

D) квадраттық программалау;

Е) дөнес программалау.

**********

А) сызықты программалау;

В) математикалық программалау;

С) сызықты емес программалау;

D) квадраттық программалау;

Е) дөнес программалау.

**********
1.3. Егер СП есебінде бір ғана функция сызықты емес болса, математикалық программалау тарауы қалай аталады?

А) сызықты программалау;

В) математикалық программалау;

С) сызықты емес программалау;

D) квадраттық программалау;

Е) дөнес программалау.

**********
1.4. Математикалық программалаудың кең тараған тарауы қалай аталады?

А) сызықты программалау;

В) математикалық программалау;

С) сызықты емес программалау;

D) квадраттық программалау;

Е) дөнес программалау.

**********
1.5. F=∑c_jx_j функцияның максималды (минималды) мәнін

∑a_ijx_j≤b_i (i=1,k)

∑a_ijx_j=b_i (i=k+1,m) x_j≥0, (j=1,l, где l≤n), мұнда a_ij,b_i,c_j – берілген шамалар, k≤m шарттар орындалған кезде, анықтайтын СП есебі қалай аталады?

А) СП стандартты есебі;

В) СП жалпы есебі;

С) СП негізгі есебі;

D) СП классикалық есебі;

Е) СП тиімді есебі.

**********
1.6. F=∑c_jx_j функцияның максималды мәнін келесі шарттар орындалған кезде

∑a_ijx_j=b_i (i=1,m) x_j≥0, (j=1,n) анықтайтын СП есебі қалай аталады?

А) СП стандартты есебі;

В) СП жалпы есебі;

С) СП негізгі есебі;

D) СП классикалық есебі;

Е) СП тиімді есебі.

**********

∑a_ijx_j≤b_i (i=1,m)

x_j≥0, (j=1,n) анықтайтын СП есебі қалай аталады?

А) СП стандартты есебі;

В) СП жалпы есебі;

С) СП негізгі есебі;

D) СП классикалық есебі;

Е) СП тиімді есебі.

**********
1.8. СП есебінің барлық шарттарын қанағаттандыратын, Х=(Х1,Х2,...Хn), сандар жиынтығы қалай аталады?

А) тиімді жоспар;

В) тірек жоспар;

С) мүмкіндік шешім;

D) көп бұрышты шешім;

Е) көп жақты шешім.

**********
1.9. СП мақсатты функциясы максималды (минималды) мәніне ие болатын жағдайда, Х*=(Х1*,Х2*,...Хn*) жоспар қалай аталады?

А) тиімді жоспар;

В) тірек жоспар;

С) мүмкіндік шешім;

D) көп бұрышты шешім;

Е) көп жақты шешім.

**********
1.10. СП есебі берілген: F=2Х₁-3Х₂max (1)

Х₁+2Х₂≤14

-5Х₁+3Х₂≤15 (2)

4Х₁+6Х₂≥24 (3)

Х₁,Х₂≥0

СП есебінің (2) және (3) функциялары қалай аталады?

А) мақсатты функция;

В) тиімді шешім;

С) есептің шектеулері (шарттары);

D) тірек жоспары;

Е) мүмкіндік шешім.

**********

Графиктік әдіс есептің геометриялық мәнінде негізделген және көбінесе екіөлшемді жазықтық есептерін шешуде қолданылады.

Симплекс әдісі – сызықты программалау есептерінің барлық өлшемді түрлерін есептеуге пайдаланатын әдіс. Егер де СП есебіне айнымалылар саны өтек өп болса, бұл жағдайда компьютерлік программалар арқылы есептің тиімді шешімін табады. Мысалы, Excel көмегімен.

Симплекс әдісі сызықты программалау есептерінің шешімін табу үшін әмбебап әдіс.

1. 
   Есепті негізгі түрге келтіру.
   
2. 
   Шектеулер жүйесінің теріс емес базисті шешімін анықтау.
   
3. 
   Бос айнымалылардың бағаларын есептеу ∆_j=∑c_ih_ij-c_j, j=1,n, мұнда h_ij – бос айнымалылардың алдындағы коэффициенттер х_j, c_i- мақсатты функциядағы базисты айнымалылардың коэффициенттері, c_j – мақсатты функциядағы бо айнымалының коэффициенті.
   
4. 
   Табылған тірек шешімді тиімділік шартына тексеру:
   

Б) егер де бір ғана баға ∆_j<0, ал сәйкесінше айнымалының коэффициенттерінің ішінде оң сан болмаса, онда есептің тиімді шешімі жоқ деп айтуға болады

В) егер де бір ғана баға ∆_j<0, ал сәйкесінше айнымалының коэффициенттерінің ішінде бір ғана оң сан болса, онда табылған шешім тиімді емес, және басқа базисты таңдап, оны жақсартуға болады. Егер де теріс бағалар бірнеше болса, онда базис ретінде бағалардың абсолютті мәні ең жоғары көрсеткіш арқылы айнымалыны таңдаймыз.

1. Ескерту. СПЕ минимумға ұмтылатын жағдайда тиімділік критериі ретінде бағалардың терістігі саналады.

2. Ескерту. СПЕ мақсатты функция максимумы және минимумы жалпы болып саналады.
Есеп 1.

Берілген СП есебін симплекс әдісімен шешу.

F=2,4X₁+1,6X₂→max

0,8X₁+1,6X₂+X₃=4,8

1,6X₁+0,8X₂+X₄=6,4

X₂+X₅=2

X₁,X₂,X₃,X₄,X₅≥0
Шешімі:

Теңдіктер жүйесін векторлық түрде жазамыз.

Х1,Х2,Х3,Х4,Х5 векторлар арасында 3 бірлік векторлар болғандықтан, есептің бастапқы тірек жоспарын жазуға болады.

Хт=(0;0;4,8;6,4;2)

Бастапқы тірек жоспарын тиімділік шарытан тексереміз, ол үшін бірінші симплекс кестені құрастырамыз: