Simpleks jadval. Chiziqli programmalashtirish masalasining optimal yechimini simpleks usuli yordamida topish

Bazis yechim	Sj	Bj	Asosiy nomaъlumlar				Qўo’shimcha nomaъlumlar
			x1	x2	x3	x4	x5	x6	x7	x8
	С1s=520	С2s=460	С3s=300	С4s=190	С5s= 0	С6s=0	С7s=0	С8s=0
x5	sС5=0	408	12	13	7	4	1	0	0	0	34
x6	sС6=0	380	11	10	8	4	0	1	0	0	34,5
x7	sС7=0	268	8	6	5	3	0	0	1	0	33,5
x8	sС8=0	180	6	3	4	2	0	0	0	1	30
Zj -Cj		0	-520	-460	-300	-190	0	0	0	0

Boshlang’ich simpleks jadvalidagi indeks qatorida manfiy sonlar mavjud. Demak, dastlabki tayanch reja optimal yechim emas.
Hal qiluvchi ustunni tanlash
ChDM maksimumga yechilsa indeks qatoridagi manfiy sonlarning абсалютabsolyut qiymati bўo’yicha eng kattasi olinadi. Agar masala minimumga yechilsa indeks qatoridagi musbat sonlarning eng kattasi olinadi.
Boshlang’ich simpleks jadvalidagi indeks qatordan kўo’rinib turibdiki x₁ ustun hal qiluvchi ustun bўo’ladi.
Chunki, max│-520; -460;-300; -190│ = 520
Iqtisodiy mazmuni. Maъlumki 520 soni indeks qatorida keltirilgan sonlarning eng kattasi bўo’lib, u bir bosh sog’in sigirni sotishdan olinadigan daromadni ifodalaydi. Shuning uchun sog’in sigirlarni boqishnirejaga kiritish mantiqan maqsadga muvofiq bўo’ladi. Demaq x₁ (sog’in sigirlar) nomaъlum bazis yechimga yaъni rejaga kiritiladi.
Hal qiluvchi satrni tanlash
Buning uchun (b_j)ozod hadlar ustunidagi sonlar, hal qiluvchi ustun (x₁) ning mos koeffisiyentlari (a_ij)ga bўo’linadi va hosil bўo’lgan қиймаларqiymatlar ustunga yoziladi. Bu sonlarning eng kichigi joylashgan satr hal qiluvchi satr bўo’ladi.
Demak, b₁ : a₁₁= 408 : 12= 34; b₂ : a₂₁= 380 : 11= 34,5;
b₃ : a₃₁= 268 : 8= 33,5; b₄ : a₄₁= 180 : 6= 30.
Bu qiymatlar ichida eng kichigi 30 va u x₈ satrda joylashgan. Demak, x₈ satr hal qiluvchi satr hisoblanadi.
x₈ nomaъlum bazisdan chiqarilib ўo’rniga x₁ nomaъlum bazisga kiritiladi
Iqtisodiy mazmuni. Xujalik bўo’yicha konsentrat ozuqalarning hajmi 408 s ga teng bўo’lsa, bir bosh sog’in sigirga bir yil davomida 12 s ozuqa birligida konsentrat talab qilinadi. Konsentrat ozuqa resurlari yil davomida b₁ : a₁₁= 408 : 12= 34 bosh sog’in sigirni boqishga yetadi. Bu kўo’rsatkichlar mos ravishda shirali ozuqalarda 34,5 dag’al xashaklar bўo’yicha 33,5 va pichan bўo’yicha 30 ga teng bўo’ladi.
Agar hal qiluvchi satr qilib boshqa satr olinsa, ozod hadlar ustuniga yoziladigan konsentratlarning yetishmovchiligi yuzaga keladi. Natijada masala nomaъlumlarning nomanfiylik sharti bajarilmaydi.Ҳал қилувчи элементни танлаш
Ҳал қилувчи устун ва сатр кесишишида жойлашган сон ҳал қилувчи элемент бўлади. Бизнинг масалада ҳал қилувчи элемент a₄₁= 6.
 Янги симплекс жадвалига ўтиш
Ҳал қилувчи устун, ҳал қилувчи сатр ва ҳал қилувчи элемент топилгач янги симплекс жадвалидаги ҳамма сонлар Жорданнинг чиқариш усули ёрдамида топилади, яъни:
1) ҳал қилувчи сатрдаги ҳамма элементлар ҳал қилувчи элементга бўлинади ва ишораси ўзгартирилмасдан ёзилади;
2) ҳал қилувчи устундаги қолган ҳамма элементлар ўрнига ноль ёзилади.
3) қолган ҳамма элементлар қуйидаги тўғри тўртбурчак формуласи ёрдамида топилади:
ёки . (Бу ерда i ≠ r, j ≠ k)
2-жадвал
a_rk элемент ўрнида ҳосил қилинадиган b_rk элементни тўғри тўртбурчак формуласи билан топиш учун ЧДМни симплекс жадвалидан фрагмент


1.18. Chiziqli programmalashtirishda ikkilanish nazariyasi
Har bir ChDM boshqa bir masala bilan uzviy bog’langan bўo’lib u ikkilangan masala deb; dastlabkisi esa boshlang’ich yoki yoki berilgan masala deb ataladi. Berilgan va ikkilangan masalalarning uzviy bog’langanligi shundaki, ulardan birining yechimini bevosita boshqasini yechish orqali ham olish mumkin. Yaxshi ishlab chiqilgan chiziqli dasturlashning matematik apparati, nafaqat optimal rejalarni topishni, balki berilgan va ikkilangan masalalarning xossalariga asoslangan holda iqtisodiy mazmunga ega bўo’lgan xulosalar chiqarishga imkoniyat yaratadi.
Resurslarni optimal taqsimlash masalasini kўo’rib chiqaylik. Aytaylik korxona n ta turdagi P₁, P₂, P₃,…,P_n mahsulotlar ishlab chiqarish uchun m hil S₁, S₂, S₃,…,S_m xom-ashyo resurslariga ega bўo’lsin (1-jadval).
1-jadval.

Xom-ashyo turi	Xom –ashyo resursi	Mahsulot turi
		P1	P2	P3	…	Pn
S1	b1	a11	a12	a13	…	a1n
S2	b2	a21	a22	a23	…	a2n
…	…	…	…	…	…	…
Sm	bm	am1	am2	am3	…	amn
Bir birlik mahsulotdan olinadigan foyda:		c1	c2	c3	…	cn

Xom-ashyo resurslari soni (m), mahsulot turlari soni (n) dan kam (m) bўo’lsin.
1.19. Ikkilangan masalaning qo’yilishi. Ikkilangan masalani qurish usullari.
Berilgan ChDMni modelini tuzishамиз
Masalaning qўo’yilishi. Korxonada ishlab chiqarishning shunday optimal rejasini tuzish talab qilinadiki, olinadigan foyda maksimal bўo’lsin.
Masalaning yechilishi.
x₁- nomalumP₁ mahsulot turining soni, x₂nomalum- P₂ mahsulot turining soni, … , x_nnomalum- P_n mahsulot turining soniniifodalasin.
1) b₁- xom-ashyo resursidan: x₁ - mahsulotni ishlab chiqarish uchun a₁₁ birlik, x₂- mahsulotni ishlab chiqarish uchun a₁₂ birlik, …, x_n - mahsulotni ishlab chiqarish uchun a_n1 birlik sarf bўo’ladi. Sarf bўo’lgan xom-ashyo resurslari йиғиндсиyig’indisi a₁₁x₁+ a₁₂x₂ + a₁₃x₃ +… a_1nx_n ga teng bўo’lib, bu yig’indi b₁- xom-ashyo resursidan oshib ketmasligi lozim, yaъni
a₁₁x₁+ a₁₂x₂ + a₁₃x₃ +… a_1nx_n  b₁
2) b₂- xom-ashyo resursidan: x₁ - mahsulotni ishlab chiqarish uchun a₂₁ birlik, x₂- mahsulotni ishlab chiqarish uchun a₂₂ birlik, …, x_n - mahsulotni ishlab chiqarish uchun a_n2 birlik sarf bўo’ladi. Sarf bўo’lgan xom-ashyo resurslari йиғиндсиyig’indisi a₂₁x₁+ a₂₂x₂ + a₂₃x₃ +… a_2nx_n ga teng bўo’lib, bu yig’indi b₂- xom-ashyo resursidan oshib ketmasligi lozim, yaъni:
a₂₁x₁+ a₂₂x₂ + a₂₃x₃ +… a_2nx_n  b₂
3) b_m - xom-ashyo resursidan: x₁ - mahsulotni ishlab chiqarish uchun a_m1 birlik, x₂- mahsulotni ishlab chiqarish uchun a_m2 birlik, …, x_n - mahsulotni ishlab chiqarish uchun a_nm birlik sarf bўo’ladi. Sarf bўo’lgan xom-ashyo resurslari йиғиндсиyig’indisi a_m1x₁+ a_m2x₂ + a_m3x₃ +… a_mnx_n ga teng bўo’lib, bu yig’indi b_m- xom-ashyo resursidan oshib ketmasligi lozim, yaъni:
a_m1x₁+ a_m2x₂ + a_m3x₃ +… a_mnx_n  b_m
Resurslarning taqsimlanishi ushbu tengsizliklar sistemasini tashkil qiladi:
a₁₁x₁+ a₁₂x₂ + a₁₃x₃ +… a_1nx_n  b₁
a₂₁x₁+ a₂₂x₂ + a₂₃x₃ +… a_2nx_n  b₂ (1)
… … … … … … … …
a_m1x₁+ a_m2x₂ + a_m3x₃ +… a_mnx_n  b_m
x_{1 , 2 , 3 , . . . , n}  0, (2)
Z_max = c₁x₁+c₂x₂+c₃x₃+...+ c_nx_n. (3)
Maqsad funksiyasi x₁ , x₂ ,…, x_n sondagi tayyor mahsulotlarni ishlab – chiqarishdan olinadigan maksimal foydani ifodalaydi.
Demak, biz korxonada resurslarni optimal taqsimlashni ChDMni tuzdik.

 II. Ikkilangan ChDMning modelini tuzish

Aytaylik boshqa bir tashkilot, qaralayotgan korxonaning barcha resurslarini sotib olishga qaror qilgan bўo’lsin. Bunday hollarda korxonadan sotib olinadigan resurslarni optimal bahosini belgilash zaruriyati tug’iladi.
Bu yerda quyidagi obъyektiv talablarni hisobga olish zarur bўo’ladi:
1) sotib oluvchi tashkilot, korxona resurslarining umumiy bahosini arzon (minimal) bўo’lishiga harakat qiladi;
2) har bir resurs turi shunday summadan kam bўo’lmagan miqdorda baholanishi kerak bўo’ladiki, qaysikim u korxona resurslaridan ishlab chiqiladigan mahsulotlaridan olinadigan foydaga teng bўo’lsin.
Masalaning qўo’yilishi. Korxonaning ishlab chiqarish resurslarini optimal bahosi aniqlansin. Bu resurslarining umumiy bahosi minimal bўo’lsin.
Masalaning yechilishi.
Asosiy nomaъlumlarning belgilanishi: u₁ nomalum– S₁ turdagi a₁₁ birlik mahsulotning bahosi, m.s; u ₂ nomalum– S₂ turdagi a₂₁ birlik mahsulotning bahosi; u ₃ nomalum– S₃ turdagi a₃₁ birlik mahsulotning bahosi; u_m – S_m turdagi a_m1 birlik mahsulotning bahosi .
Birinchi shartga kўo’ra xom-ashyo resurslarining umumiy bahosi ushbu kattalik F_min= b₁u₁+ b₂u₂+ b₃u₃+…. b_mu_m (3∙) bilan ifodalaniladi.

Ikkinchi shart talablariga kўo’ra:

a) P₁ mahsulotlarni ishlab chiqarishda a₁₁ birlik xom- ashyo resursi u₁ bahoda, a₂₁ birlik xom- ashyo resursi u₂ bahoda, a₃₁ birlik xom- ashyo resursi u₃ bahoda va nihoyat a_m1 birlik xom- ashyo resursi u_m bahoda sarf bўo’ladi. Demak, bu xom-ashyo rusurslarining bahosi a₁₁u₁+ a₂₁u₂+ a₃₁u₃+…+ a_m1u_m dan iborat bўo’lib va u c₁ dan kam bўo’lmasligi lozim, yaъni:
a₁₁u₁+ a₂₁u₂+ a₃₁u₃+…+ a_m1u_m ≥ c₁.
b) P₂ mahsulotlarni ishlab chiqarishda a₁₂ birlik xom- ashyo resursi u₁ bahoda, a₂₂ birlik xom- ashyo resursi u₂ bahoda, a₃₂ birlik xom- ashyo resursi u₃ bahoda va nihoyat a_m2 birlik xom- ashyo resursi u_m bahoda sarf bўo’ladi. Demak, bu xom-ashyo rusurslarining bahosi a₁₂u₁+ a₂₂u₂+ a₃₂u₃+…+ a_m2u_m dan iborat bўo’lib va u c₂ dan kam bўo’lmasligi lozim, yaъni:
a₁₂u₁+ a₂₂u₂+ a₃₂u₃+…+ a_m2u_m ≥ c₂.
c) P_m mahsulotlarni ishlab chiqarishda a_1n birlik xom- ashyo resursi u₁ bahoda, a_2n birlik xom- ashyo resursi u₂ bahoda, a_3n birlik xom- ashyo resursi u₃ bahoda va nihoyat a_mn birlik xom- ashyo resursi u_m bahoda sarf bўo’ladi. Demak, bu xom-ashyo rusurslarining bahosi a_1nu₁+ a_2n u₂+ a_3nu₃+…+ a_mnu_m dan iborat bўo’lib va u c_m dan kam bўo’lmasligi lozim, yaъni:
a_1nu₁+ a_2n u₂+ a_3nu₃+…+ a_mnu_m ≥ c_m.
Masalaning iqtisodiy mazmuniga kўo’ra baholarning manfiy bўo’lishi mumkin emas:
u₁ ≥ 0, u₂ ≥ 0, u₃ ≥ 0, u₄ ≥ 0.
Natijada ikkilangan masalaning ChDM umumiy kўo’rinishi quyidagicha bўo’ladi:
a₁₁u₁+ a₂₁u₂+ a₃₁u₃+…+ a_m1u_m ≥ c₁.
a₁₂u₁+ a₂₂u₂+ a₃₂u₃+…+ a_m2u_m ≥ c₂.
… … … … … … … … …
a_1nu₁+ a_2n u₂+ a_3nu₃+…+ a_mnu_m ≥ c_n. (1∙)
u₁ ≥ 0, u₂ ≥ 0, u₃ ≥ 0, …, u_m ≥ 0. (2∙)
F_min= b₁u₁+ b₂u₂+ b₃u₃+…. b_mu_m (3∙)
Bu ikkita masala juftligi ham amalda chiziqli dasturlashning mustaqil masalalari bўo’lib, ular bir – biriga bog’liq bўo’lmagan holda yechilishi mumkin. Lekin, масалларmasalalardan birining simpleks usuli bilan aniqlanadigan optimal rejasi, иikinchisining ham yechimi bўo’lishi mumkin.
Berilgan masalaning maksimum qiymati ikkilangan masalaning minimum qiymatiga teng bўo’ladi, yaъni: Z_max =F_min
Bu masalalarning optimal yechimlari ўo’zaro quyidagi teorema asosida bog’langan bўo’ladi.
Teorema. Agar berilgan masalada yoki unga ikkilangan masaladan birortasi optimal yechimga ega bўo’lsa, u holda ikkinchisi ham yechimga ega bўo’ladi hamda bu masalalardagi chiziqli funksiyalarning ekstremal qiymatlari ўo’zaro teng bўo’ladi, yaъni Z_min = F_max