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

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

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

1 2 3 4 5 6 7

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

ә) Жарамды шешімдер облысы – жалғыз нүктеден тұрады. Бұл жағдайда сызықтық программалау есебінің жалғыз ғана тиімді шешімі болады.
б) Жарамды шешімдер облысы – дөңес көпбұрыш. Бұл жағдайда есептің тиімді шешімін табу үшін көпбұрыштың барлық бұрыштық нүктелерінің координаталарын тауып, барлық бұрыштық нүктелердегі мақсат функциясының мәнін есептеп, солардың ішіндегі ең үлкенін (немесе ең кішісін) таңдау керек. Сәйкес бұрыштық нүктенің координаталары тиімді шешім болып табылады.
Әрине, тиімді шешімге сәйкес бұрыштық нүктені графикалық түрде бірден табуға болатын басқа да тәсіл бар. Айталық, - қандай да бір сан болсын. түзуі мақсат функцияның деңгей сызығы болып табылады. Осы түзудің әрбір нүктесінде мақсат функция мәніне тең бір ғана мәнді қабылдайды. Мақсат функцияның

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

кесіндінің кез келген нүктесі тиімді шешім болады.

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

1-мысал.

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

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

Шығарылуы.
1. Жарамды шешімдер облысын құрамыз:
1.1. Шектеулердегі теңсіздіктерді теңдіктерге алмастырамыз

2. Алынған теңдеулер бойынша түзулер тұрғызамыз (1-сурет)

1-сурет
3. Ыңғайлы болу үшін берілген теңсіздіктер жүйесін нөмірлейміз:

4. Жоғарыдағы теорема бойынша теңсіздіктердің шешімі жартыжазықтықты береді. Осы жартыжазықтықты анықтау үшін еркін алынған бақылау нүктесін аламыз. Айталық берілген шектеулер-теңсіздіктер үшін (0,0) нүктесі ыңғайлы болып табылады. Бақылау нүктесін теңсіздіктердің орнына қойып теңсіздіктің шешімі қай жартыжазықтықта екенін айқындаймыз. Алынған жартыжазықтықтарда белгілеудің нәтижесінде дөңес ABCD төртбұрышын аламыз (2-сурет).

2-сурет

2. мақсат функциясының градиент-векторын тұрғызамыз (ол үшін нүктесін белгілеп координаталар бас нүктесімен қосып, вектор тұрғызамыз).
3. Жарамды шешімдер облысы арқылы өтетін векторына перпендикуляр деңгей сызығының үйірін тұрғызамыз.
4.1. Мақсат функциясын максимизациялау есебінде векторының бағытында жарамды шешімдер облысы арқылы өтетін ең алыс қашықта орналасқан деңгей сызығын (максимум мәнді береді) таңдау керек. 3-суреттен көріп отырғанымыздай бұл С нүктесі.
4.2. Мақсат функциясын минимизациялау есебінде векторының бағытында жарамды шешімдер облысы арқылы өтетін ең жақын қашықта орналасқан деңгей сызығын (минимум мәнді береді) таңдаймыз, ол А нүктесі.

3-сурет

5.1. Экстремум (С және А) нүктелерінің координаталарын табу керек.
А нүктесінің координаталарын анықтау үшін А нүктесі қандай қандай түзулердің қиылысуында орналасқанын қараймыз. Біздің есепте А нүктесі және түзулердің қиылысуында орналасқан. Осы теңдеулерден алынған теңдеулер жүйесін шешеміз. Алынған шешім А нүктесінің координаталарын береді.

Осыдан А .
Осылайша С нүктесінің координаталарын анықтаймыз. С нүктесі және түзулердің қиылысуында орналасқан.

.

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

,
.

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

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

1 2 3 4 5 6 7