Сызықытық программалау Модель ұғымы. Модельдеудің түрлері

жүктеу/скачать 349.97 Kb.

бет	7/7
Дата	13.04.2023
өлшемі	349.97 Kb.
	#472216
түрі	Программа

1 2 3 4 5 6 7

12 13 лек сыз программалау

Жауабы: , .

2-мысал

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

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

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

Айнымалылардың теріс еместік шартын пайдалансақ,

1-мысалды шығарған алгоритм бойынша есепті әрі қарай шығарамыз.

Жарамды шешімдер облысын құрамыз:

ол үшін шектеулер жүйесіндегі теңсіздіктерді теңдеулерге алмастырамыз:

алынған теңдеулер бойынша түзулер тұрғызамыз;

(0,0) бақылау нүктесінің көмегімен әрбір теңсіздік бойынша жарты жазықтықтарды анықтаймыз.
Алынған жартыжазықтықтарды біріктіру нәтижесінде дөңес OABCD - көпбұрышты аламыз. Мақсат функциясының градиент-векторының көмегімен экстремум нүктелерін анықтаймыз. 1.4-суреттен көріп отырғанымыздай бұл B (max) және O (min) нүктелері.
Экстремум (O және B) нүктелерінің координаталарын табу керек.
O нүктесі координаталар бас нүктесі; B нүктесі және түзулерінің қиылысуында орналасқан.
O нүктесінің координаталары .
B нүктесінің координаталарын табу үшін

теңдеулер жүйесін шешеміз: ;

Осы нүктелердегі мақсат функциясының мәнін табамыз.

,
.
Жауабы:
, .

4-cурет

Практикада сызықтық программалау есебін графикалық әдіспен шығару барысында әр түрлі жағдайлар кездеседі. Солардың кейбір жағдайларының графигін талдайық:
5-cуретте мақсат функциясының градиент-векторына жүргізілген перпендикуляр деңгей сызығының үйірінің бірі жарамды шешімдер обылысы - ABCD төртбұрышының бір қабырғасымен беттеседі. Бұл, айталық, мақсат функциямыз жалпы жағдайда түрінде берілсе, онда жарамды шешімдер облысының (ABCD төртбұрышының) деңгей сызығымен беттесетін қабырғасы (AD) өзара параллель, яғни түрінде берілгенін байқауға болады.

,

_5-cурет

Бұл жағдайда берілген есепті минимизациялайтын болсақ, осы төртбұрыштың беттесетін (AD) қабырғасындағы барлық нүктелерде мақсат функциясы минималды мәнді қабылдайды, яғни, егер, A нүктесінің координаталары , D нүктесінің координаталарын деп алсақ, онда AD кесіндісінің нүктелері теңдеуімен беріледі, мұндағы . Сонда, ізделінді жауабымыздың мәні: , тиімді шешімдерінің ақырсыз жиынында немесе ; мұндағы және бұл жағдайда балама оптимум бар деп айтады; ал максимизациялау есебінде B нүктесінде максимал мәнді қабылдайды. B нүктесінің координаталарын деп алсақ, онда .

6-cуретте минимизациялау есебін қарастырсақ, онда деңгей сызығын сызықтық функцияның кему (градиент-векторға қарама-қарсы бағытта) бағытында жылжытсақ, онда деңгей сызығы барлық кезде шешімнің көпбұрышымен қиылысады, демек, сызықтық функция шексіз кемиді.

6-cурет

Сонымен сызықтық функцияның ақырлы оптимумы жоқ, яғни
.

Осы жағдайда максимизациялау есебін қарастырсақ, онда деңгей сызығын сызықтық функцияның өсу (градиент-вектормен бағыттас) бағытында жылжытсақ, онда деңгей сызығы барлық кезде шешімнің көпбұрышымен қиылысады, демек, сызықтық функция шексіз артады және бұл жағдайда да сызықтық функцияның ақырлы оптимумы болмайды, яғни,

7-суретте 5-суреттегі жағдайға ұқсас. Бұл жағдайда есептің шешімі: минимизациялау есебінде AD кесіндісінің барлық нүктелері; максимизациялау есебінде BC кесіндісінің барлық нүктелері.

Әрі қарай талдауды оқырмандардың өздеріне ұсынамыз.

1.7-сурет

7-cурет
8-суретте жарамды шешімдер облысы бос жиын, демек шексіздіктер жүйесі үйлесімсіз, яғни есептің оптимумы жоқ.

9-суретте жарамды шешімдер облысы A нүктесін береді, және бұл нүктеде сызықтық функцияның оптимумы болады.

8-сурет

А
9-сурет

жүктеу/скачать 349.97 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7