Muhammad Al-Xorazmiy nomidagi Axborot texnologiyalar Universiteti

.Simpleks jadval usuli

Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo‘lib, ketma-ket yaqinlashish usuli yordamida x₁,x₂, . . .x_n o‘zgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasiga maksimal (yoki minimal) qiymat beradi.

Quyidagi chiziqli dasturlash masalasi berilgan bo‘lsin:

Masalani yechish uchun simpleks jadval quramiz va simpleks usuli g‘oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.

Bu yerda x_n+i - ozod o‘zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o‘zgaruvchilardan farqlash uchun mos ravishda y₁,y₂, . . .y_m deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz b_i0=b_i; b_i,j=a_i,j; b_0j=c_j. Bu belgilashlar asosida quyidagi simpleks jadval deb ataluvchi jadvalni 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.

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 boshlang‘ich 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 b_r0 bo‘lsin. Shu b_r0 element turgan r satr qaraladi. Agar satr elementlaridan hammasi 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 elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya'ni

.

Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi b_r0/b_rs bo‘lsin. U holda shu b_rs element turgan satr hal qiluvchi satr deyiladi, b_rs elementning o‘zi esa hal qiluvchi element bo‘ladi.

2.Hal qiluvchi ustun va satr o‘zgaruvchilari o‘rinlari almashtiriladi, (ya'ni x_s va y_s 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 .

3.2.Hal qiluvchi satr elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya'ni .

3.3.Hal qiluvchi element 1 ga tenglashtirilib o‘ziga bo‘linadi, ya'ni .

3.4.Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.

ёки

Yangi jadvalda bґ_ij -elementni hisoblashda eski jadvaldan b_ij, b_is ,b_rj, b_rs elementlarini topish quyidagicha bo‘ladi:

b_ij - bґ_ij elementning eski jadvaldagi unga mos element;

b_is -b_ij element turgan satr bilan b_r hal qiluvchi element ustuni kesishmasidagi element;

b_rj -b_ij element turgan ustun bilan b_rs hal qiluvchi element satri kesishmasidagi element;

b_rs - hal qiluvchi element.

BO‘	1	-x1	-x2	. . .	-yr	. . .	-xn
y1	b’10	b’11	b’12	. . .	b’1s	. . .	b’1n
y2	b’20	b’21	b’22	. . .	b’2s	. . .	b’2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
xs	b’r0	b’r1	b’r2	. . .	b’rs	. . .	b’rn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	b'm0	b’m1	b’m2	. . .	b’ms	. . .	b’mn
Z	b’00	b’01	b’02	. . .	b’0s	. . .	b’0n

4.Yangi topilgan simpleks jadvalda tayanch plan mavjud bo‘lsa ikkinchi bosqichga, ya'ni optimal planni topishga o‘tiladi, aks holda yuqoridagi jarayon yangi jadval uchun toki tayanch plan topilguncha qayta takrorlanadi.

C++ dastur