O‘zbekiston respublikasi oliy va o’rta maxsusta’lim vazirligi

Eslatma. (1) va (2) sistemalarda bo’lishi shart emas, lekin tenglik bajarilishi talab qilinadi.
tonna ko’mirni tashish xarajati so’m bo’lganidan hamma ko’mirni tashish xarajati

so’mni tashkil etadi.
Demak, (1) va (2) larni birgalikda olish bilan tuzilgan 9 ta nomaʼlumli 6 ta tenglamalar sistemasining manfiymas, yaʼni birorta ham noldan kichik bulmagan yechimlaridan shunday

yechimni tanlashimiz lozimki, bunda f formadagi o’zgaruvchilarning qiymatlarida bu forma eng kichik qiymatga ega bo’lsin.
Masalan, konlarning soni bilan korxonalarning soni ixtiyoriydir va ular bir-biriga teng bo’lishi shart emas. Umuman, konlar korxonalar uchun hollardan biri bajarilishi mumkin.
2. Parhez masalasi. Masalaning sharti quyidagicha: Ikki xil va oziq-ovqat mahsulotida iste`mol moddalar (yog’, kraxmal, oqsil) bor. mahsulot birligidagi iste`mol moddaning miqdori bo’lib, bu moddaga organizmdagi kundalik talab miqdori dir. mahsulot birligining narxi so’m.
Quyidagi masalani echish lozim: mahsulotni shunday xi miqdorda olish kerakki, organizmning isteʼmol moddalarga talabi qoniqtirilsin va ovqatning narxi eng arzon bo’lsin.
Ravshanki, ovqatning umumiy narxi so’mdir. va mahsulotlardagi moddaning umumiy miqdori ga, moddaniki ga va moddaniki ga teng bo‘lib, ular mos ravishda lardan kam bo‘lmasligi, yaʼni

tengsizliklar sistemasi o’rinli bo’lishi kerak.
(4) sistemaning manfiymas yechimlaridan shunday yechimini tanlashimiz lozimki, u f chiziqli formaga eng kichik qiymatni bersin.
3. Boylik manbalaridan foydalanish masalasi. Korxona hom ashyo, asbob – uskuna va hokazolar kabi boylik manbalariga ega bo’lsin. Bu korxonaning o’lchov birliklari bilan miqdorda olingan uch xil boylik manbalari (resurslari) mavjud. Korxona ikki xil va mol (tovar) ishlab chiqaradi. , mollar birligini ishlab chiqarish uchun , , boylik manbalari birligining tasi talab qilinadi. , mollar birligidan korxona so’m daromad oladi. Korxonada , , boylik manbalari jamg’armasi miqdori dan iborat.
Korxonaning eng ko’p daromad olish masalasi qo’yiladi.
Ishlab chiqarilgan va mahsulot miqdorini mos ravishda va orqali belgilasal, korxonaning daromadi so’mni tashkil etadi. Ikkala mahsulotni ishlab chiqarishda foydalanilgan , , boylik manbalarining umumiy miqdori bo’lib, u dan ortmasligi kerak.
Demak, masalani yechim uchun

sistemaning shunday manfiy bo’lmagan yechimini topish kerakki, u f chiziqli funksiyaga eng katta qiymat bersin .
Bu masalada xam , , boylik manbalarining va ishlab chiqariladigan , mahsulotlarning m va n soni har qancha bo‘lishi, yaʼni m>n, m=n, m < n bo‘lishi mumkin.
Birinchi masalada (1) va (2) dan tuzilgan tenglamalar sistemasi, shuningdek, ikkinchi va uchinchi masalalarda (4) va (5) tengsizliklar sistemalari bu masalalarning cheklanishlari deyiladi.
Boshqacha aytganda, ular bu masalalarning cheklanish tenglamalari va cheklanish tengsizliklari deb ataladi.
Tenglamalar yoki tengsizliklar sistemasining istalgan manfiy bo‘lmagan yechimi o‘rinli yechim deyiladi. f formata talab qilingan eng katta (yoki eng kichik) qiymat beruvchi o‘rinli yechim esa optimal yechim deyiladi. Optimal yechim mavjud bo‘lsa, u yagona bo’lishi shart emas. Optimal yechimlar cheksiz ko‘p bo‘lishi mumkin.

3-§. Simpleks usul

Chiziqli programmalash masalasini yechishning muhim usuli simpleks usuldir. Bu masalada cheklanish tenglamalari nomalumlarga nisbatan yechilgan, ya`ni




ko’rinishda olingan bo’lib, bo’lsin.
f chiziqli formada ham larni (1) lar orqali ifodalab, uni

ko’rinishga keltiriamiz va bu formaning minimumini topish masalasini qo’yamiz.
(1) dagi noma`lumlar to’plami chiziqli programmalash masalasining bazisi deyiladi va u ko’rinishida belgilanadi. larning o’zini basis noma`lumlar, larni esa ozod noma`lumlar deb ataymiz. noma`lumlarga qiymatni bersak, (1) dan larni hosil qilamiz. Shunday qilib,

yechim hosil bo’ladi. f ning bu yechimdagi qiymati ga teng.
Quyidagi ikki hol ro’y berishi mumkin:

1. 
   (2) da hamma sonlari manfiymas, yani
   

U vaqtda f forma shartda minimum qiymatga erishadi, ya`ni M bazisning (3) yechimi optimal bo’ladi, chunki biror va lar uchun bo’lib, , kelib chiqadi.
II. (2) da sonlar orasida manfiylari bor bo’lsin. Masalan, deylik. U vaqtda va deb olib, ning qiymatini orttira borish hisobiga ning qiymatini kamaytirish mumkin. Lekin bu ishda ehtiyotkorlik kerak, chunki bu holda (1) lardan kelib chiqadigan




tenglamalardagi larning hech qaysisi manfiy bo’lib qolmasin.
Bu yerda ham quyidagi ikkita hol ro’y beradi:
A. (4) da hamma sonlar musbatmas. U vaqtda uchun bo’lganidan ga asosan …, bo’ladi. Demak, da va bo’lgani sababli ni cheksiz orttira borish bilan min ga kelamiz. Bundan esa f formaning minimumga erishmasligi ko’rinadi.
B. (4) da sonlar orasida musbatlari bor. Masalan, U holda da ga dan ortiq qiymat berish mumkin emas, chunki aks holda bo’lib qoladi. Bunda ekanligi ravshan. Bunday kasrlar orasida eng kichigi bo’lsin. Bunda son hal qiluvchi element deyiladi.
Qisqalik uchun belgilash kiritaylik. (4) da ni gachagina orttira olamiz, chunki aks holda bo’lishini ko’rdik.
Ozod noma`lumlarga

Qiymatlarni berib, bazis noma`lumlarni aniqlaymiz:






Endi quyidagi yangi bazisga o’tamiz:

Bunga mos bazis yechim (6) va (5) lardan tuziladi, (1) sistema va (2) formani yangi bazisga moslab yozamiz. Buning uchun (1) dagi

tenglamani ga nisbatan yechamiz, ya`ni

va bu ifodani (1) ga qo’yamiz. Hosil bo’lgan yangi sistemani

ko’rinishda yozamiz. Bu bazisning ifodalarining f ga qo’yib, uni

ko’rinishida keltiramiz.
Bu bilan jarayonning birinchi qadami tugaydi. Keying qadam yana shu birinchi qadamni, ya`ni (8) va (7) larga nisbatan I yoki II holni, undan keyin II A yoki II B ni takrorlashdan iborat bo’ladi va h.k.
Shunday qilib, Simpleks usul quyidagi jarayonni ifodalaydi:
1. Cheklanish — tenglamalar sistemasini (1) ga, chiziqli formani esa (2) ko‘rinishga keltiramiz.
2. Agar (2) da hamma koeffitsiyentlar manfiymas bo‘lsa, M bazisning yechimi optimal bo‘lib, bu yechimda f forma minimumga erishadi.
3. (2) da lar orasida manfiylari mavjud, masalan, desak qiymatlarda (1) sistema (4) ko‘rinishni oladi. Agar (4) da hamma koeffitsiyentlar musbat bo‘lsa, kelib chiqadi, yaʼni f funksiya minimumga erishmaydi.
4. (4) dagi koeffitsiyentlarning musbatlari mavjud, yaʼni desak, sonlar orasida eng kichigi ni olamiz. (1) sistemaning ga nisbatan yozilgan tenglamasidan ni aniqlab, (1) sistemani yangi bazisga nisbatan yozib, (7) ni hosil qilamiz. f formani esa (8) ko‘rinishda ifodalaymiz. Yangi ozod nomaʼlumlar (5) dan iborat bo‘ladi. (8) va (7) larga asoslanib, yuqorida bayon etilgan jarayon takrorlanadi.