Simpleks usul algoritmi. Reja: Simpleks usul algoritmining tuzulishi

f+0x1-x2+3x3+0x4-2x5+0x6=0 ko‘rinishda yozib olaylik.

Agar (2) da x2=0, x3=0, x5=0 desak, x1=7, x4=12, x6=10 bo‘lib, birinchi bazis echimimiz x1=7, x2=0, x3=0, x5=0, x6=10 ko‘rinishda bo‘lib, f maqsad funksiyaning bu bazis echimga mos kelgan qiymati f=0 bo‘lishi ravshan.

• 
  Agar (2) da x2=0, x3=0, x5=0 desak, x1=7, x4=12, x6=10 bo‘lib, birinchi bazis echimimiz x1=7, x2=0, x3=0, x5=0, x6=10 ko‘rinishda bo‘lib, f maqsad funksiyaning bu bazis echimga mos kelgan qiymati f=0 bo‘lishi ravshan.
  
• 
  Endi birinchi bazis echimga mos kelgan birinchi simpleks jadvalini tuzaylik.
  

Bazis o‘zgar	Ozod hadlar	x1	x 2	x 3	x 4	x 5
x 6
X 1	7	1	3	-1	0	2	0
X 4	12	0	-2	4	1	0	0
X 6	10	0	-4	3	0	8	1
f	0	0	-1	3	0	-2	0

1-simpleks jadvali.

Qo‘yilgan masalaning eng kichik qiymati izlanayotganda, oxirgi yo‘ldagi elementlarning ichidagi eng kichik musbat son olinai. Bizda esa bu son 3 bo‘lgani uchun, 3 turgan ustun hal qiluvchi ustun bo‘ladi. Nazariyaga ko‘ra 7 ni -

• 
  Qo‘yilgan masalaning eng kichik qiymati izlanayotganda, oxirgi yo‘ldagi elementlarning ichidagi eng kichik musbat son olinai. Bizda esa bu son 3 bo‘lgani uchun, 3 turgan ustun hal qiluvchi ustun bo‘ladi. Nazariyaga ko‘ra 7 ni -
  
• 
  1 ga bo‘lish mumkin emas, shuning uchun
  

Demak, 4 turgan yo‘l hal qiluvchi yo‘l bo‘lib, 4 esa, hal qiluvchi element bo‘ladi. Qulaylik uchun 4 ni 1 ga aylantiraylik, buning uchun hal qiluvchi yo‘lni ga ko‘paytiramiz.

• 
  Demak, 4 turgan yo‘l hal qiluvchi yo‘l bo‘lib, 4 esa, hal qiluvchi element bo‘ladi. Qulaylik uchun 4 ni 1 ga aylantiraylik, buning uchun hal qiluvchi yo‘lni ga ko‘paytiramiz.
  

Bazis o‘zgar	Ozod hadlar	x1	x 2	x 3	x 4	x 5	x 6
X 1	7	1	3	-1	0	2	0
X 4	3	0	-1/2	1	¼	0	0
X 6	10	0	-4	3	0	8	1
f	0	0	-1	3	0	-2	0

Endi hal qiluvchi ustundagi -1 ; 3 va 3 sonlarni nolga aylantiraylik. Buning uchun hal qiluvchi yo‘l elementlarini mos ravishda 1 va -3 ga ko‘paytirib, birinchi, uchinchi va to‘rtinchi yo‘l elementlariga qo‘shsak, natijada 2-simpleks jadvali hosil bo‘ladi.

• 
  Endi hal qiluvchi ustundagi -1 ; 3 va 3 sonlarni nolga aylantiraylik. Buning uchun hal qiluvchi yo‘l elementlarini mos ravishda 1 va -3 ga ko‘paytirib, birinchi, uchinchi va to‘rtinchi yo‘l elementlariga qo‘shsak, natijada 2-simpleks jadvali hosil bo‘ladi.
  

Bazis o‘zgar	Ozod hadlar	x1	x 2	x 3	x 4	x 5	x 6
X 1	10	1	5/2	0	1/4	2	0
X 3	3	0	-1/2	1	1/4	0	0
X 6	1	0	-5/2	0	-3/4	8	1
f	-9	0	1/2	0	-3/4	-2	0

2-simpleks jadvali.

Biz maqsad funksiyaning eng kichik qiymatini izlayotganimiz uchun oxirgi, ya’ni f turgan yo‘lda musbat son bo‘lishi kerak emas. Bizda esa bitta 1/2 son bor. SHuning uchun 1/2 turgan ustun hal qiluvchi ustun bo‘lib, bu ustunda 5/2 yagona musbat son bo‘lgani uchun, u hal qiluvchi element bo‘lib, yo‘li esa hal qiluvchi yo‘l bo‘ladi va bazis o‘zgaruvchi x1 ning o‘rniga x2 o‘tadi. Endi 5/2 ni 1 ga aylantiraylik. Buning uchun birinchi yo‘l elementlarini 2/5 ga ko‘paytiramiz.

• 
  Biz maqsad funksiyaning eng kichik qiymatini izlayotganimiz uchun oxirgi, ya’ni f turgan yo‘lda musbat son bo‘lishi kerak emas. Bizda esa bitta 1/2 son bor. SHuning uchun 1/2 turgan ustun hal qiluvchi ustun bo‘lib, bu ustunda 5/2 yagona musbat son bo‘lgani uchun, u hal qiluvchi element bo‘lib, yo‘li esa hal qiluvchi yo‘l bo‘ladi va bazis o‘zgaruvchi x1 ning o‘rniga x2 o‘tadi. Endi 5/2 ni 1 ga aylantiraylik. Buning uchun birinchi yo‘l elementlarini 2/5 ga ko‘paytiramiz.
  

Bazis o‘zgar	Ozod hadlar	x1	x 2	x 3	x 4	x 5	x 6
X 2	4	2/5	1	0	1/10	4/5	0
X 3	3	0	-1/2	1	1/4	0	0
X 6	1	0	-5/2	0	-3/4	8	1
f	-9	0	1/2	0	-3/4	-2	0

Bazis o‘zgar	Ozod hadlar	x1	x 2	x 3	x 4	x 5	x 6
x 2	4	2/5	1	0	1/10	4/5	0
x 3	5	1/5	0	1	3/10	2/5	0
x 6	11	1	0	0	-1/2	10	1
f	-11	-1/5	0	0	-4/5	-12/5	0

3-jadvaldan ko‘rinadiki, oxirgi f turgan yo‘lda musbat sonlar yo‘q. Demak, f maqsad funksiyaning qiymatini boshqa kamaytirish mumkin emas. Haqiqatan oxirgi jadvaldan ko‘rinadiki, uchinchi bazis echim
bo‘lib, qo‘yilgan masalaning eng kichik qiymatini ifodalaydi.
f=x2-3x3+2x5