Chiziqli dasturlash masalalarini yechishning simplek usuli

CHIZIQLI DASTURLASH MASALALARINI
YECHISHNING SIMPLEK USULI

R E J A:
1.Kirish.
2.Simpleks jadval tuzish.
3.Masalaning boshlang‘ich tayanch planini tuzish.
4.Optimal planni topish.
1.Kirish
Oldingi ma’ruzamizda aytganimizdek, chiziqli dasturlash masalasining optimal planini uning barcha planlaridan tashkil topgan qavariq to‘plamning chetki nuqtalari orasidan qidirish kerak. Bunday nuqtalar soni yoki boshqacha aytganda tayanch planlar soni n dan m tadan tuzilgan Cnm gruppalash orqali aniqlanadi. Masaladagi nomalumlar soni n va tenglamalar soni m katta bo‘lganda barcha (mumkin bo‘lgan ) tayanch planlarning optimalligini tekshirib chiqish ancha qiyin bo‘ladi. Shuning uchun tayanch planlarni tartib bilan tekshirib chiqib, ular ichidan optimal planni aniqlab beruvchi yechish sxemasining berilishi talab qilinadi.
Chiziqli dasturlash masalasini yechishning bunday sxemalaridan biri bu Simpleks usulidir. Bu usul boshlang‘ich tayanch plandan chekli sondagi iteratsiyadan keyin optimal planni hosil qilish yo‘lini ko‘rsatadi va har bir navbatdagi iteratsiya oldingisiga nisbatan optimal planga yaqinroq planni beradi. Yechish jarayoni optimal yechim topilguncha yoki masalaning chiziqli funksiyasi chekli ekstimum qiymatga ega emasligi aniqlanguncha davom ettiriladi. Bu usul hozirgi kunda keng miqiyosda ishlatilib SHEHMlar uchun uning amaliy paket dasturlari ishlab chiqilgan.
2.Simpleks jadval tuzish
Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo‘lib, ketma ket yaqinlashish usuli yordamida x1,x2, . . .xn o‘zgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasigi maksimal (yoki minimal) qiymat beradi.
Quyidagi funksionalga maksimum qiymat beruvchi chiziqli dasturlash masalasi berilgan bo‘lsin.
n
aij x j  bi , (i 1,m)
j1

x j  0 ( j 1,n)

n
Z ci xi  max
j1
Masalani yechish uchun simpleks jadval quramiz va simpleks usuli g‘oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.
 a11x1  a12x2 ... a1s xs ... a1nxn  xn1  b1
 a21x1  a22x2 ... a2s xs ... a2nxn  xn2  b2

 .........................................................................
am1x1  am2x2 ... ams xs ... amnxn  xnm  bm


x j  0 (i 1,m) ( j 1,n)
Z  c1x1 c2x2 ...cnxn  max
Bu yerda xn+i - bazis o‘zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o‘zgaruvchilardan farqlash uchun mos ravishda y1,y2, . . .ym deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz bi0=bi; bi,j=ai,j; b0j=cj. Bu belgilashlar asosida simpleks jadval tuzamiz.

BO‘	1	-x1	-x2	. . .	-xs	. . .	-xn
y1	b10	b11	b12	. . .	b1s	. . .	b1n
y2	b20	b21	b22	. . .	b2s	. . .	b2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ys	br0	br1	br2	. . .	brs	. . .	brn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	bm0	bm1	bm2	. . .	bms	. . .	bmn
Z	b00	b01	b02	. . .	b0s	. . .	b0n

Chiziqli dasturlash masalasini simpleks usul yordamida yechish ikki bosqichdan iborat:
1.Boshlang‘ich tayanch planni topish.
2.Tayanch planlar ichidan masalaning optimal planini topish.
3.Masalaning tayanch planini tuzish Boshlang‘ich tayanch planni topish quyidagi algoritm bo‘yicha bajariladi:
1.Simpleks jadvaldan hal qiluvchi elementni topish:
1.1.Hal qiluvchi elementni topish oldin hal qiluvchi ustunni topishdan boshlanadi. Buning uchun ozod hadlar ustuniga qaraladi. Agar ozod xadlar ustunidagi elementlar hammasi musbat bo‘lsa, bu boshlanQich plan tayanch plan bo‘ladi va ikkinchi etapga o‘tiladi. Agar manfiy element mavjud bo‘lsa ulardan modul bo‘yicha eng kattasi tanlanadi(agar bitta bo‘lsa shu element o‘zi olinadi). Misol uchun aytaylik bu element br0 bo‘lsin. Shu br0 element turgan r satr qaraladi. Agar satr elementlaridan xammasi musbat bo‘lsa, masalaning yechimi mavjud bo‘lmaydi (bu holda hisoblashlar shu joyda to‘xtatiladi). Agar satrda manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa o‘zi olinadi). Shu element turgan ustun hal qiluvchi ustun deyiladi. Misol uchun bu s-chi ustun bo‘lsin.
1.2.Hal qiluvchi satr topiladi. Ozod xadlarni hal qiluvchi ustun elementlarga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya’ni
 b10 ; b20 ; ... ; br0 ; ... ;bm0 .
min b1s b2s brs bms 

Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi brs/br0 bo‘lsin. U holda shu brs element turgan satr hal qiluvchi satr deyiladi, brs elementning o‘zi esa hal qiluvchi element bo‘ladi.
2.Hal qiluvchi ustun va satr o‘zgaruvchilari o‘rinlari almshtiriladi, (yani xs va ys yangi jadvalda o‘rinlari almashadi).
3.Jadvalda simpleks almashtirish bajariladi.
3.1.Hal qiluvchi ustun elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya’ni bis' bis /brs (i  r).
3.2.Hal qiluvchi satr elementlari xal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya’ni brj' brj /brs (j  s).
3.3.Hal qiluvchi element 1 ga tenglashtirilib o‘ziga bo‘linadi, ya’ni brs' 1/brs.
3.4.Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.
' bijbrsbbisbrj bij'  bij  bisbrj ; i  r, j  s bij  yoki brs
rs
Yangi jadvalda b´ij -elementni hisoblashda eski jadvaldan bij, bis ,brj, brs elementlarini topish quyidagicha bo‘ladi:
bij - b´ij elementning eski jadvaldagi unga mos element;
bis -bij element turgan satr bilan brs hal qiluvchi element ustuni kesishmasidagi element;
brj -bij element turgan ustun bilan brs hal qiluvchi element satri kesishmasidagi element; brs - hal qiluvchi element.