Тәжірибелік жұмыс №3 Сызықтық бағдармалау әдістері.

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

Сызықты бағдарламалау есебінің математикалық түрі келесідей болады:

мұнда F-мақсаттық функция, келесі шарттарда

мұндағы x_j – ізделген белгісіз шама.

Матрицалық белгілерде есеп келесі түрде көрсетілуі мүмкін:

Функцияны минимизациялау (максимизациялау) : F=CX

Берілген шектеулерде :

Сызықты бағдарламалау есептерін оның оптималды жоспарын табу немесе оптималды жоспарының болмауын дәлелдеу деп ұғамыз.

1. Сызықтық бағдарламалау есебін графикалық әдіспен шешу

;

Шешу жолы:

Мақсаттық функцияның максимальды мәнін табу F = 7X1+6X2 => max,

шектеулері:

2x1+5x2≥10 (1)

5x1+2x2≥10 (2)

x2≤6 (3)

+x2≤5 (4)

Теңсіздіктердің графиктерин сызылып, шешу облысын анықтаталады, (жартылай жазықтарды штрихпен белгіленеді). (Сурет 1.)

Сурет 1.

Шешу облыс копбұрыштың шектері анықталады. (Сурет 2.)

Сурет 2.

Мақсаттық функция F = 7X1+6X2 => max.

F = 0: F = 7X1+6X2 = 0. – түзу сызыкты сызылады. Графикте бұл түзу сызық пунктир сызықпен белгіленді (сурет 3)

Сурет 3.

x2=0

2x1+5x2≥10

Бұл теңдеудің шешімі: x1 = 5, x2 = 0

Мақсаттық функцияның максималдық шешімі: F(X) = 7*5 + 6*0 = 35

Тапсырмалар

1. ; 2. ;

3. ; 4. ;

5. ; 6. ;

7. ; 8. ;

9. ; 10. ;

2. Сызықты бағдарламалау есептерінің симплекс-әдісімен шешу

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

одан басқа негізгі шектеулер жүйесі бірлік базистен тұруы қажет.

Мысал, Мақсаттық функция болатындай х₁,х₂ табу қажет, шектеулері келесідей

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

1 қадам. Есепті каноникалық түрге келтіреміз.

Теңсіздіктен теңдікке ауысу үшін шектеулерге х₃,х₄ балансты айнымалыны енгіземіз

х₃,х₄ – бірлік базис. Бірінші Симплекс кестесін толтырамыз:

Кесте №1

Базистік айнымалылар	Бос мүшелер	Х1	Х2	Х3	Х4
Х3	1700	3	4	1	0
Х4	1600	2	5	0	1
-Z	0	-2	-4	0	0

2 Қадам. Информацияны іздену

• Соңғы жолда теріс кіші мәнді таңдаймыз: -4. Х2 бағанын негізгі немесе жүргізуші деп айтамыз.

• Негізгі баған коэффициентіне бос мүшенің оң қатынасының арасынан кішісін табамыз: 320 (1700/4=425; 1600/5=320). Х4 жолын негізгі деп айтамыз. Негізгі баған мен негізгі жол қиылысындағы элементті негізгі немесе жүргізуші элемент деп атаймыз.

3 Қадам. Информацияны түрлендіру. Симплекс кестені қайта есептеу келесі алгоритм бойынша жүргізіледі:

• Х2 және Х4 бос және базисті айнымалылардың орнын алмастырамыз.

• Негізгі жолдың жаңа элементтері сәйкес келетін элементтердің негізгі элементке бөлуімен табылады: 1600/5=320; 2/5=0,4; 1/5=0,2.

• Жаңа симплекс кестенің барлық қалған элементтері келесі жолмен анықталады: алдыңғы кестенің сәйкес келетін элементінен берілген элементтің негізгі баған мен жолдың негізгі жолға бөлінген проекциясы алынады:

және әрі қарай осылай.

Кесте №2

Базистік айнымалылар	Бос мүшелер	Х1	Х2	Х3	Х4
Х3	420	1.4	0	1	-0.8
Х4	320	0.4	1	0	0.2
-Z	1280	-0.4	0	1	0.8

4 Қадам. Информацияны іздеу. Егер соңғы жолдың барлық элементтері оң болса, онда шешім табылды.

Егер теріс элемент болса онда 2 қадамнан бастап операцияларды қайталаймыз да симплекс кестені қайта есептейміз:

Кесте №3

Базистік айнымалылар	Бос мүшелер	Х1	Х2	Х3	Х4
Х3	360	1	0	0.71	-0.57
Х4	200	0	1	-0.29	0.43
-Z	1400	0	0	0.29	0.57

Соңғы жолдың барлық элементтері оң, яғни біз оптималды шешім таптық:

х₁=300, х₂=200, Z=1400.

Сызықты бағдарламалау есептерін MS Excel құралдарының көмегімен шешу.

Жұмыстың мақсаты: Шешім іздеу (Поиск решения) MS Excel функциясы арқылы сызықты бағдарламалау есептерін шешуді үйрену.

Жұмыстың орындалуына нұсқау:

1. MS Excel программасын қосу. Жұмыс парағының ұяшығына есептің шартын енгізіңіз:

2. Сервис-Поиск решения меню командасы. Диалогты терезені келесідей толтырыңыз:

Добавить батырмасын басқаннан кейін шектеулер енгізіледі

3. Шешімді алу үшін Поиск решения диалогты терезесінен Выполнить пернесін басыңыз.

Тапсырмалар

1. ; 2. ;

3. ; 4. ;

5. ; 6. ;

7. ; 8. ;

9. ; 10. ;