Чизиқли программалаштириш масаласи. Чизиқли программалаштириш масаласини ечиш усуллари. Чизиқли программалаштиришда иккиланма назария

Чизиқли программалаштириш масаласини график усулда ечиш
Чизиқли программалаштириш масаласини график усулда ечиш, бу унинг ечимларини икки ўлчовли фазода геометрик тасвирлашдан иборат.
Чегаравий шартлари тенгсизликлар кўринишида берилган, чизиқли программалаштириш масаласини кўриб чиқамиз.
Чизиқли функциянинг максимал қийматини аниқланг
(4)
чегаравий шартларда


(5)


(6)
(5) ва (6) чегаравий шартларни қаноатлантирувчи тартибланган сонлар тўплами, таянч ечим дейилади. Агар (5) тенгсизликлар системаси, (6) шартда, ҳеч бўлмаганда битта ечимга эга бўлса, у биргаликда, аксинча эса биргаликда эмас деб юритилади.
текисликда чизиқли программалаштириш масаласи берилган бўлсин, мақсад функция

чегаравий шартларда



Чизиқли тенгсизликлар системасини кўриб чиқамиз

Системадаги ҳар бир тенгсизликнинг геометрик маъноси, текисликдаги чегараси тўғри чизиқдан иборат бўлиб, бу эса ярим текисликни аниқлайди. Номаълумларнинг манфий бўмаслик шарти, чегаравий шартлар билан аниқланади. Система биргаликда, шунинг учун ярим текисликлар кесишиб, уларнинг умумий кесишган соҳаси, координаталари берилган системанинг ечимларидан иборат, қавариқ кўпбурчак бўлади. Бу нуқталар (ечимлар) тўплами, ечимлар кўпбурчаги дейилиб, у нуқта, нур, кесма, кўпбурчак, чегараланмаган кўпбурчакли соҳа бўлиши мумкин.
Агар сиетемадаги (5), (6) чегаравий шартларда бўлса, у ҳолда ҳар бир тенгсизликнинг геометрик маъноси, уч ўлчовли фазодаги ярим текисликдан иборат бўлиб, чегаравий текислик формула, ярим фазонинг манфий бўмаслик шартлари, мос равишда чегаравий текисликлар орқали аниқланади. Агар система биргаликда бўлса, у ҳолда бу ярим фазолар кесишиб, уларнинг умумий кесишган соҳаси, кўпёқли ечим дейилади. Кўпёқли ечим, нуқта, нур, кесма, кўпбурчак, кўпёқ, кўпёқ чегараланмаган кўпбурчакли соҳа бўлиши мумкин.
Булардан келиб чиқиб, чизиқли программалаштириш масаласини геометрик талқини шундан иборатки, бунда кўпёқли ечимлардан шундай бирини танлаш керакки, унинг координаталари, чизиқли функцияга минимал қиймат берсин. Бунда, масаланинг мумкин бўлган ечимлар соҳаси деганда, кўпёқли ечимнинг барча нуқталари тушунилади.
Чизиқли программалаштириш масаласини график усул билан ечишда, мақсад функциянинг экстремал қийматини топиш учун, текисликдаги, вектордан фойдаланилади. У деб белгиланади. Бу вектор мақсад функциянинг тез ўсиш йўналишини кўрсатади, У қуйидагига тенг

Бунда ва - мос равишда ва ўқлардаги бирлик векторлардир. Демак, векторнинг координаталари, мақсад функция номаълумлари олдидаги коэффициентлардан иборат экан.

Чизиқли программалаштириш масаласини график усулда ечиш алгоритми

1. 
   Масаланинг чегаравий шартларидан, унинг мумкин бўлган ечимлар соҳаси аниқланади.
   
2. 
   векторни қурамиз.
   
3. 
   векторга перпендикуляр бўлган, сатҳ чизиғи ўтказилади.
   
4. 
   Максимум масалада, сатҳ чизиғи вектор йўналиши бўйича, минимум масалада эса вектор йўналишига қарама-қарши сурилади. Бу суриш, сатҳ чизиғи билан мумкин бўлган ечимлар соҳасининг ягона умумий нуқтаси ҳосил бўлгунча, давом эттирилади. Бу нуқта, мумкин бўлган ечимлар соҳасида, мақсад функциянинг экстремум нуқтаси бўлади, яъни чизиқли программалаштириш масаласининг оптимал ечимидир.
   
5. 
   Мақсад функцияниг қийматини, экстремум нуқталарнинг координаталари орқали аниқлаймиз.
   

Агар сатҳ чизиғи, мумкин бўлган ечимлар соҳасининг бирор томонига параллел бўлса, у ҳолда чизиқли программалаштириш масаласи чексиз ечимлар соҳасига эга.
Агар мумкин бўлган ечимлар соҳаси, чексиз соҳа бўлса, мақсад функция чегараланмаган бўлади.
Мумкин бўлган ечимлар соҳасининг чегаравий шартлари қарама-қарши бўлса, чизиқли программалаштириш масаласи ечимга эга эмас.
Чизиқли программалаштириш масаласининг оптимал ечимини аниқлашда қуйидаги вазиятлар бўлиши мумкин:

• 
  масала ягона ечимга эга (1-расм);
  
• 
  масала чексиз кўп ечимлар тўпламига эга (2-расм);
  
• 
  функция юқоридан чегараланган эмас, яъни экстремал қийматга эга эмас (3-расм);
  
• 
  масаланинг чегаравий шартлари биргаликда эмас, яъни мумкин бўлган ечимлар соҳаси бўш тўпламдан иборат (4-расм).
  

0