2.3 Сызықтық программалау есебінің қойылуы және оның құрылымы

сызықтық теңдеулер мен теңсіздіктерден тұратын, айнымалысы бар

(1.7)

жүйе және

(1.8)

функциясы берілсін.

(1.7) жүйеде алдымен теңсіздік, содан кейін теңдік берілген. Егер осы теңсіздіктер мен теңдіктер бастапқы берілуінде басқаша орналасса, орындарын ауыстыру нәтижесінде айтылған түрге келтіруге болады. Жүйенің сол жағы оң жағынан кіші не тең болсын дейміз, егер қандай да бір теңсіздікте керісінше болса, онда сол теңсіздікті «-1»-ге көбейту арқылы қажетті таңбамызды аламыз.

Осы берілгендерді ескеріп сызықтық программалау есебінің қойылуын жазайық.

(1.8) сызықтық функция тиімді (яғни, максималды немесе минималды) мәнді қабылдайтындай және

, (1.9)

шартын қанағаттандыратындай (1.7) жүйенің шешімін табу қажет.

(1.7) жүйе шектеулер жүйесі деп, (1.8) - функциясы сызықтық функция немесе мақсат функциясы деп, ал (1.9) шарт теріс еместік шарты деп аталады.

Экстремумды іздеу типін таңдау салыстырмалы сипатта болады. Себебі, функциясының максимумын іздеу функциясының минимумын іздеумен пара-пар.

(1.9) шартты қанағаттандыратын, (1.8) сызықтық функция тиімді мәнді (максималды немесе минималды) қабылдайтындай (1.7) шектеулер жүйесінің шешімі тиімді шешім (немесе тиімді жоспар) деп аталады.

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

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

а) тек қана теңсіздіктерден тұрса, онда сызықтық программалау есебі стандартты немесе симметриялы;

ә) тек қана теңдіктерден тұрса, онда сызықтық программалау есебі канондық немесе негізгі;

б) теңдеулер мен теңсіздіктерден тұрса, онда сызықтық программалау есебі жалпы түрде берілген деп аталады.

Кез келген сызықтық программалау есебін канондық түрге келтіруге болады. Айталық, сызықтық программалау есебі стандартты түрде берілсін:

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

Қарастырылып отырған есепте барлық теңсіздіктердің таңбасы « » болғандықтан, қосымша айнымалылар «+» таңбасымен енгізіледі, ал егер теңсіздіктердің таңбасы « » болса, онда қосымша айнымалылар «-» таңбасымен енгізіледі.

2.4 Сызықтық программалау есебінің геометриялық интерпретациясы

Екі айнымалысы бар стандартты формада берілген (1.7)-(1.9) есепті қарастырайық. айнымалылар саны теңдеулер санынан 2-ге артық, яғни болған жағдайдағы канондық формадағы есепті осындай стандартты формаға келтіруге болады.

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

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

. (1.10)

Деңгей сызығы өмірде кеңінен қолданылады, мысалы, ауа райының карталарындағы ирек сызық - изотермалар деңгейінің, географиялық карталардағы параллельдер – ендік деңгейінің сызығы және т.б.

Айталық, қандай да бір облыстың, мысалы елдің немесе материктің ең шеткі солтүстік нүктесін табу керек болсын. Бұл ең үлкен ендігі бар нүкте болады, яғни ең үлкен ендігі (деңгейі) бар параллельдер (деңгей сызығы) арқылы өтетін нүкте.

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

Функцияның деңгей сызығының (1.10) теңдеуі – түзу сызықтың деңгейі. Әр түрлі деңгейде сызықтың бұрыштық коэффициенттері тек қана және коэффициенттерінің арасындағы қатынастармен анықталады және демек, тең болатындықтан деңгей сызықтары параллель болады. Сонымен, функциясының деңгей сызығы көбінесе координаталар осіне қандай да бір бұрыш жасап орналасқан «параллельдер» болып табылады.

Сызықтық функцияның деңгей сызығының маңызды қасиеті – осы сызықты бір жаққа қарай параллель жылжытқанда тек қана өседі, басқа жаққа жылжытқанда тек қана кемиді.

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

,

шектеулер жүйесін, теріс еместік шартты қанағаттандыратындай

мақсат функциясының экстремумын табу керек.

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

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

2. Компоненттері мақсат функциясының айнымалыларының коэффициенттері болатын векторын тұрғызамыз.

3. Жарамды шешімдер облысы арқылы өтетін векторына перпендикуляр деңгей сызығының үйірін тұрғызамыз.

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

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

Ескерту: Бұл жерде алгоритмнің бірінші қадамына қатысты келесі жағдайлар болуы мүмкін.

1. Жарамды шешімдер облысы – құр жиын. Бұл жағдайда шектеулер жүйесінің үйлесімсіздігінен сызықтық программалау есебінің тиімді шешімі болмайды.

2. Жарамды шешімдер облысы – жалғыз нүктеден тұрады. Бұл жағдайда сызықтық программалау есебінің жалғыз ғана тиімді шешімі болады.

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

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

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

,

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

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

1.1-мысал.

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

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

Шығарылуы.

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

1.1. Шектеулердегі теңсіздіктерді теңдіктерге алмастырамыз

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

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

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

1.1-сурет	1.2-сурет

2. мақсат функциясының векторын (ол үшін нүктесін белгілеп координаталар бас нүктесімен қосамыз) тұрғызамыз.

3. Жарамды шешімдер облысы арқылы өтетін векторына перпендикуляр деңгей сызығының үйірін тұрғызамыз.

4. Максимум және минимум мәндерді беретін деңгей сызықтарын анықтауымыз керек.

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

4.2. Мақсат функциясын минимизациялау есебінде векторының бағытында жарамды шешімдер облысы арқылы өтетін ең жақын қашықта орналасқан деңгей сызығын (минимум мәнді береді) таңдаймыз. Ол А нүктесі арқылы өтетін деңгей сызығы болатынын 1.3-суреттен байқауға болады.

1.3-сурет

5. Экстремум нүктелерін және мақсат функциясының максимум, минимум мәндерін анықтау керек.

5.1. Экстремум (С және А) нүктелерінің координаталарын табу керек.

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

Осыдан А нүктесінің координаталары: А .

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

.

С нүктесінің координаталары С .

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

; .

Жауабы: , .

1.2-мысал.

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

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

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

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

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

.

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

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

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

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

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

Экстремум (O және B) нүктелерінің координаталарын табу керек.

O нүктесі координаталар бас нүктесі; B нүктесі және түзулерінің қиылысуында орналасқан.

O нүктесінің координаталары .

B нүктесінің координаталарын табу үшін

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

1.4-cурет

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

_, .

Жауабы: , .

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

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

(ABCD төртбұрышының) деңгей сызығымен беттесетін қабырғасы (AD) өзара параллель, яғни түрінде берілгенін байқауға болады.

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

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

1.6-cурет	1.7-cурет

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

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

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

1.8-cурет	1.9-cурет

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

3-лекция. Симплекс әдісі