3.2.2 Өзгешеленген базистік шешімнің пайда болуы

2.4-мысал.

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

Шығарылуы. Шектеулер жүйесін канондық түрге келтіреміз:

Бірінші итерациялық қадам.

1.1. н.а. ;

н.е.а. .

1.2.

1.3. Алғашқы базистік шешімді табамыз:

, ; .

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

- шешуші теңдеу – бірінші теңдеу. Сонымен, айнымалысы негізгі айнымалыға, айнымалысы негізгі емес айнымалыға көшеді.

Екінші итерациялық қадам.

2.1. н.а. ;

н.е.а. .

2.2. Негізгі айнымалыларды негізгі емес айнымалылар арқылы өрнектейміз:

2.3. Базистік шешімді анықтаймыз:

.

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

, сонымен, екінші теңдеу – шешуші теңдеу болып табылады.

Үшінші итерациялық қадам.

3.1. н.а. ;

н.е.а. .

3.2.

3.3. Базистік шешім: .

3.4. Табылған базистік шешім жарамды.

3.5. мақсат функциясын негізгі емес айнымалылар арқылы өрнектеп, оның мәнін есептейміз:

,

; , .

3.6. айнымалысын негізгі айнымалыға көшіреміз.

3.7. Айнымалылардың теріс емес шартын пайдаланамыз:

түрінде анықталады.

3.8. болғанда айнымалысы және айнымалысы нөлге айналады, және осы екі айнымалының біреуін (кез келгенін) негізгі емес айнымалыға көшіреміз. Екінші теңдеу шешуші теңдеу болып табылады.

Төртінші итерациялық қадам.

4.1. н.а. ;

н.е.а. .

4.2.

4.3. Базистік шешім (4, 0, 0, 9, 0) – ерекшеленген базистік шешім болып табылады, негізгі айнымалының компоненті ( ) нөлге тең.

4.4. Базистік шешім жарамды.

4.5. ,

; , .

4.6. Тиімділік критерийі орындалмайды. Сондықтан, мәні максимум емес. Басқа жарамды базистік шешімге көшеміз. Оң таңбалы коэффициент жалғыз, осы коэффициентке сәйкес айнымалысын негізгі айнымалыға көшіреміз.

4.7. Айнымалылардың теріс еместік шартын пайдаланамыз:

Сонымен, .

4.8. болғанда айнымалысы нөлге айналады, және оны негізгі емес айнымалыға көшіреміз. Үшінші теңдеу шешуші теңдеу болып табылады.

Бесінші итерациялық қадам.

5.1. н.а. ;

н.е.а. .

5.2.

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

5.4. Базистік шешім жарамды.

5.5. , .

, .

5.6. Мақсат функциясында оң таңбалы коэффициенті бар негізгі емес айнымалы кездеседі. Сондықтан, мәні максимум емес. Басқа жарамды базистік шешімге көшеміз. Оң таңбалы коэффициент жалғыз, осы коэффициентке сәйкес айнымалысын негізгі айнымалыға көшіреміз.

5.7. Айнымалылардың теріс еместік шартын пайдаланамыз:

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

Жауабы. .

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

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

3.2.3 Ақырлы оптимумның жоқ болуы ( немесе )

Алдыңғы тақырыпта қарастырылған есептің минимум мәнін анықтайық.

2.5-мысал.

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

Шығарылуы. 2.4-мысалда екінші итерациялық қадамда жарамды базистік шешімді анықтаған болатынбыз (сол мәліметтерді пайдаланып, есепті әрі қарай жалғастырамыз):

3.1. н.а. ;

н.е.а. .

3.2. Негізгі айнымалыларды негізгі емес айнымалылар арқылы өрнектейміз:

3.3. Базистік шешім: .

3.4. Табылған базистік шешім жарамды.

3.5. , , .

3.6. Тиімділік критерийі орындалмайды. Теріс коэффициентті айнымалысын негізгі айнымалыға көшіреміз.

3.7. Айнымалылардың теріс еместік шартын пайдаланамыз:

. Қарастырып отырған теңдеу айнымалысының өсуіне шек қоймайды, сондықтан функциясының мәні шектелмеген және теріс, яғни .

Жауабы. .

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