Chiziqli programmalash masalasini simpleks usulida yechish

3-MAVZU
CHIZIQLI PROGRAMMALASH MASALASINI SIMPLEKS USULIDA YECHISH
REJA

1. 
   Vektorlarning bazis vektorlar bo‘yicha yoyilmasi. Bir bazisdan ikkinchisiga o‘tish.
   
2. 
   Chiziqli tenglamalar sistemasining nomanfiy yechimlari orasidan berilgan chiziqli funksiyaga ekstremal qiymat beruvchi yechimni aniqlash.
   
3. 
   Simpleks usul.
   

Tayanch iboralar: Tayanch plan, optimal plan, simpleks usul, bazis vektor, sun’iy bazis o‘zgaruvchi
Yuqorida ko‘rganimizdek, chiziqli programmalash masalasining optimal planini uning barcha planlaridan tashkil topgan qavariq to‘plamning chetki nuqtalari orasidan qidirish kerak. Bunday nuqtalar soni yoki boshqkacha aytganda masaladagi tayanch planlar soni dan tadan tuzilgan gruppalash orqali aniqlanadi. Masaladagi noma’lumlar soni va tenglamalar soni katta bo‘lganda barcha tayanch planlarning optimalligini tekshirib chiqish ancha qiyin bo‘ladi. Shuning uchun tayanch planlarni tartib bilan tekshirib chikib, ular ichidan optimal planni aniqlab beruvchi yechish sxemasini berilishi talab qilinadi.
Chiziqli programmalash masalasini yechishning bunday sxemalaridan biri simpleks usuldir. Bu usul boshlang‘ich tayanch plandan chekli sondagi iteratsiyadan keyin optimal planni hosil kilish yo‘lini ko‘rsatadi va har bir navbatdagi iteratsiya oldingisiga nisbatan optimal planga yakinrok planni beradi. Yechish jarayoni optimal yechim topilguncha yoki masalaning chiziqli funksiyasi chekli minimumga ega emasligi aniqlanguncha davom ettiriladi.
1. Masalaning tayanch planlarini tuzish. Dastlab berilgan chiziqli programmalash masalasida ta o‘zaro chiziqli bog‘liq bo‘lmagan birlik vektorlar mavjud deb faraz qilamiz. Umumiylikni buzmagan holda bu vektorlar birinchi ta vektordan iborat deylik. U holda masala quyidagi ko‘rinishda bo‘ladi:
(1)
(2)
(3)
(1) sistemani vektor formada yozamiz:
(4)
bu yerda
,

vektorlar o‘lchovli vektor fazodagi o‘zaro chiziqli bog‘liq bo‘lmagan birlik vektorlardan iborat bo‘lib, bu fazoning bazisini tashkil qiladi. (1) da o‘zgaruvchilarni bazis o‘zgaruvchilar, o‘zgaruvchilarni esa bazis bo‘lmagan o‘zgaruvchilar deb qabul qilib, bazis bo‘lmagan o‘zgaruvchilarni nolga tenglaymiz. Natijada:
(5)
boshlang‘ich planni hosil qilamiz . (5) planga quyidagi
(6)
yoyilma mos keladi. Bu yoyilmadagi vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi sababli, topilgan boshlang‘ich (5) plan tayanch plan bo‘ladi.
Endi boshlang‘ich plandan foydalanib, yangi tayanch planni topish mumkinligini ko‘rsatamiz. vektorlar o‘lchovli vektor fazoning bazisini tashkil qilgani uchun vektorlarning ixtiyoriysini bazis vektorlar orqali faqat bir xil yoyilmasini topish mumkin, ya’ni
(7)
Faraz qilaylik, birorta vektor, masalan ning yoyilmasidagi koeffitsiyentlardan kamida bittasi (masalan, ) noldan farqli bo‘lsin:
(8)
Ixtiyoriy ( - hozircha noma’lum son)ni olib, (8) tenglikning ikki tomonini unga ko‘paytirib, hosil bo‘lgan natijani (6) dan ayiramiz. Natijada quyidagi tenglikka ega bo‘lamiz:
(9)
Agar bo‘lsa,
vektor plan bo‘ladi. bo‘lganligi sababli, planning komponentlari manfiy bo‘lmaydi, shuning uchun bo‘lgan komponentalarni ko‘ramiz. Demak, shunday topishimiz kerakki bo‘lganda

bo‘lsin. Bundan

plan ixtiyoriy

tengsizlikni qanoatlantiruvchi uchun plan bo‘ladi. Lekin tayanch plan o‘z ichiga ta komponentani olmaydi, shuning uchun plandagi kamida bitta komponentani nolga aylantirish kerak. Faraz qilaylik,

bo‘lsin. Bu holda planning komponentasi bo‘ladi. ning qiymatini (9) ga qo‘yib qo‘yidagi yoyilmani hosil qilamiz:
Bu yoyilmaga

plan mos keladi. Demak, yangi planning komponentalari kuyidagicha aniqlanar ekan:
(10)
Bundan keyingi tayanch planni hosil qilish uchun bazisga kirmagan ixtiyoriy vektorning bazis vektorlar orqali yoyilmasini aniqlash hamda shunday sonni topish kerakki, uning yordamida yangi vektor bazisga kirsin va eski bazis vektorlardan birortasi bazisdan chiqsin. Shunday qilib, yangi tayanch planlari hosil qilish jarayoni bazisga kiritiladigan va bazisdan chiqariladigan vektorni tanlashdan iboratdir. Bazisga kiritiladigan vektorni tanlash kriteriysi simpleks usulning asosiy elementlaridan biri hisoblanadi. Agar bazisga kiritilayotgan vektorning yoyilmasida barcha bo‘lsa, (9) yoyilmadagi birorta vektorni bazisdan chiqaruvchi ni topib bo‘lmaydi. Bu holda plan musbat komponentlarni o‘z ichiga oladi. vektorlar sistemasi esa o‘zaro chiziqli bog‘liq bo‘lib qavariq ko‘pburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. Bu nuqtada esa chiziqli funksiya o‘zining minimum qiymatiga erisholmaydi. Bu holda chiziqli funksiya quyidan chegaralanmagan bo‘ladi.
M i s o l . Berilgan masalaning tayanch planini tuzing va yangi tayanch planga o‘ting:


Sistemani vektor formada yozamiz:

Bu yerda - bazis vektorlar, bazis o‘zgaruvchilar, - bazis bo‘lmagan o‘zgaruvchilar. Bazis bo‘lmagan o‘zgaruvchilarga nol qiymat berib boshlang‘ich planni topamiz.
Bu planga
(11)
yoyilma mos keladi. Yangi planga o‘tish uchun ixtiyoriy, kamida bita musbat komponentalik bazis bo‘lmagan vektorni (masalan, ni) olamiz va uning bazis vektorlar orqali
(12)
yoyilmasini yozamiz. Bu ifodaning ikki tomonini songa ko‘paytirib, natijani (11) dan ayiramiz va quyidagiga ega bo‘lamiz:
. (13)
Bazisdan chiqarilayotgan vektorni aniqlash uchun

ni topamiz.
qiymatni (13) ga qo‘yib, vektorni bazisdan chiqaramiz va quyidagi yoyilmaga ega bo‘lamiz:

Bu yoyilmaga

plan mos keladi. Endi ning o‘rniga ni bazisga kiritamiz. Bu vektorning bazis vektorlar bo‘yicha yoyilmasi:
(14)

14. 
    ifodaning ikki tomonini songa ko‘paytirib, natijani (11) dan ayirib quyidagiga ega bo‘lamiz:
    

Bu yoyilmadan ko‘rinadiki, birorta ham vektorni bazisdan chiqarib bo‘lmaydi. Bu yoyilmaga mos keluvchi

plan tayanch plan bo‘lolmaydi, chunki u 4 ta musbat komponentani o‘z ichiga olib qavariq ko‘pburchakning ichki nuqtasini ifodalaydi. Bu planda chiziqli funksiyaning qiymatini hisoblasak:

bo‘ladi. ning qiymatini cheksiz orttirib borilsa ning qiymati cheksiz ravishda qamayib boradi, ya’ni chiziqli funksiya chekli minimumga ega bo‘lmaydi.
2. Optimallik kriteriysi. Optimal yechimni topish. Quyidagi
(15)

(16)
chiziqli programmalash masalasining plandagi mavjud va ular xosmas deb faraz qilamiz. Masalaning tayanch plan va unga mos keluvchi o‘zaro chiziqli bog‘liq bo‘lmagan. vektorlar sistemasi ma’lum bo‘lsin. U holda
(17)
va
(18)
Bu yerda chiziqli funksiyaning tayanch plandagi qiymati, chiziqli funksiyaning koeffitsiyentlari. vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi sababli ixtiyoriy bazis bo‘lmagan vektorning bu vektorlar orqali faqat bitta yoyilmasini topish mumkin:
(19)
Bu vektorga chiziqli funksiyaning
(20)
qiymati mos keladi. vektorga mos keluvchi chiziqli funksiyaning koeffitsentini bilan belgilaymiz. U holda quyidagi teoremalar o‘rinli bo‘ladi.
1- t ye o r ye m a . Agar tayanch planda tayinlangan j uchun tengsizlik o‘rinli bo‘lsa, X₀ plan optimal plan bo‘lmaydi va shunday X plan topish mumkin bo‘ladiki, uning uchun