Mavzu: Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini yechishning simpleks usulini C++ da bajarish

3-qadam. Tuzilgan (3) sistemani va (2) maqsad funksiyani quyidagi simpleks jadvalga kiritamiz.

Bazis o‘zgaruvchilar	Ozod had	Erkin o‘zgaruvchilar
		-x1	-x2	...	-xn
xn+1	b1	a11	a12	...	a1n
xn+2	b2	a21	a22	...	a2n
....	....	...	...	...	...
xn+m	bm	am1	am2	...	amn
F	0	-c1	-c2	...	-cn

Agar bu jadvlda F satrdagi barcha erkin o‘zgaruvchilarga mos keluvchi elementlar, ya’ni -c₁, -c₂, ...,-c_n lar musbat bo‘lsa bu jadvalga mos keluvchi reja (0,0,...,0, b₁, b₂, ..., b_m,) optimal reja bo‘ladi.

4-qadam.Agar F satrda manfiy elementlar mavjud bo‘lsa, u holda bu reja optimal bo‘lmaydi va biz boshka tayanch rejaga o‘tamiz, ya’ni mumkin bo‘lgan rejalar ko‘pyoqinig boshqa uchiga.bu ishni kuyidagicha amalga oshiramiz: F satrdagi eng kichik manfiy son joylashgan ustun xal qiluvchi ustunbo‘ladi va bu ustun elementlari uchun ( F satrdagi elementdan tashkari) simpleks nisbatlarni hisoblaymiz (xar bir ozod hadni unga mos keluvchi hal kiluvchi ustun elementiga nisbati). Hosil bo‘lgan nisbatlardan eng kichigiga mos keluvchi element hal qiluvchi element bo‘ladi.

5-qadam.Hal qiluvchi element yordamida simpleks jadvalni o‘zgartiramiz. Bu ishdan maqsad hal elementga mos keluvchi satrdagi bazis o‘zgaruvchi va ustunda turgan erkin o‘zgaruvchilar almashadi. (jadvalni almashtirish algoritmi misolda tushuntiriladi).

3. Halq xo‘jaligining ko‘p soxalarini ayrim masalalari (ishlab chikarishni rejalashtirish, chorva mollari uchun optimal ozuqa tayyorlash, ekin erlaga mineral o‘g‘itlar solish masalalari va h.q.,) aynan chiziqli programmalash masalasiga keltirilib shu simpleks usul bilan echiladi. Quyidagi masalani ko‘raylik.

MasalaQog‘oz ishlab chiqaruvchi kombinat ishlab chikarish rejasini bajarish bilan birga xom ashyolarni barcha turidan tejab qoldi. YA’ni 50 tonna sillyuloza, 80 tonna yog‘och massasi va 2 tonna kaolin xom ashyolari ortib qoldi. Quyidagi jadvalda barcha turdagi qog‘ozlarni 1tonnasini ishlab chikarish uchun sarf qilinadigon xom ashyolarni normalari (kg) va buqog‘ozlarni sotishdan qoladigan foyda miqdorlari keltirilgan.