Yozgan 2-mustaqil ishi

Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Telekomunikatsiya fakulteti 414-20 guruh talabasi O`rinboyev Samandarning chiziqli algebra fanidan

Yozgan 2-mustaqil ishi

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

Reja :

1 Kirish.

2 chiziqli dasturlash masalalari .

3. Simpleks usul xakida kiskacha umumiy maʼlumot

4. Simpleks usulning algoritmi

5. Baʼzi masalalarni simpleks usul yordamida yechish

6. Mustakil yechish uchun tavsiya kilingan misollar

7.Xulosa

8.Foylanilgan adabyotlar

1.Chiziqli programmalash sohasini ilk prinsiplari L.V. Kontorovichni “Matematicheskiye metod organizatsii i planirovaniya proizvodstva” nomli ishlarida uchraydi(1939y), 1947 ylda esa amerika olimi Dansig tomonidan chiziqli programmalash masalasini umumiy qoʻyilgan.

Biz bilamizki chiziqli programmalash masalasi bu chizikli funksionalni koʻp oʻlchovli fazoda chiziqli cheklovlarni qanoatlantirgan holda minimum yoki maksimum qiymatini topishdan iborat. Bu masaladagi xar bir chiziqli cheklovlar n- oʻlchovli fazoni (n-1)- oʻlchovli yarim fazosi boʻladi, demak bundan chikadiki barcha chiziqli cheklovlarni umumiy yechimi (mumkin boʻlgan rejalar toʻplami) n- oʻlchovli fazoda qavariq koʻpyoq boʻladi.

Simpleks usul chiziqli programmalash masalasini mumkin boʻlgan rejalar toʻplami boʻlgan koʻpyoqni uchlari orasidan optimal yechimni topish usulidir. Agar masalani oʻzgaruvchilar soni n-ta cheklovlar soni m-ta boʻlsa u holda koʻpyoqning uchlari soni Snm –ga teng boʻladi, bu yesa katta son boʻlib, burchaklarni birma-bir tekshirib chiqish maqsadga muofiq emas.

2. Umumiy holda berilgan kuyidagi chiziqli programmalash masalasini koʻraylik:

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

. . . . . . . . . . . . . (1)

am1x1+am2x2+…+amnxn≤bm,

x1, x2, . . . , xn≥0 shartlarni qanoatlantirgan holda F=c1x1+c2x2+…+cnxn (2) maqsad funksiyaga maksimal qiymat beruvchi x1, x2, . . . , xn larni topish kerak.

1-qadam. Berilgan (1) tengsizliklar sistemasida yangi xn+1, xn+2, . . . , xn+m, musbat oʻzgaruvchilar kiritib barcha tengsizliklarni tengliklarga aylantirib olamiz. Bu yerda yangi kiritilgan oʻzgaruvchilarni iktisodiy maʼnosi: shu oʻzgaruvchi katnashgan tengsizlikga mos keluvchi xom ashyoni ortib qolgan miqdoridir. Demak n+m- oʻzgaruvchili m-ta chiziqli tenglamalar sistemasini xosil qildik va bu sistemada xn+1, xn+2, . . . , xn+m – oʻzgaruvchilar faqat bittadan tenglamada bir koeffitsiyet bilan ishtirok etadi.

2-qadam. Xosil boʻlgan tenglamalar sistemada xn+1, xn+2, . . . , xn+m – oʻzgaruvchilarni bazis oʻzgaruvchilar, x1, x2, . . . , xn –oʻzgaruvchilarni esa erkin oʻzgaruvchilar deb olamiz va bazis oʻzgaruvchilarni erkin oʻzgaruvchilar orqali ifodalaymiz.

xn+1 = b1 -a11x1-a12x2-…-a1nxn

xn+2 = b2 -a21x1-a22x2-…-a2nxn

. . . . . . . . . . . . . (3)

xn+m = bm-am1x1-am2x2-…-amnxn,

bu yerda x1, x2, . . . , xn –oʻzgaruvchilarni barchasiga 0 qiymat bersak

xn+1, xn+2, . . . , xn+m – oʻzgaruvchilar mos ravishda b1, b2, ..., bm –qiymatlarni qabul qiladi va (0,0,...,0, b1, b2, ..., bm,) birinchi tayanch reja boʻladi.

3-qadam. Tuzilgan (3) sistemani va (2) maqsad funksiyani

quyidagi simpleks jadvalga kiritamiz.

Agar bu jadvlda F satrdagi barcha erkin oʻzgaruvchilarga mos keluvchi elementlar, yaʼni -c1, -c2, ...,-cn lar musbat boʻlsa bu jadvalga mos keluvchi reja (0,0,...,0, b1, b2, ..., bm,) 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 ustun boʻ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, yekin yerlaga mineral oʻgʻitlar solish masalalari va h.q.,) aynan chiziqli programmalash masalasiga keltirilib shu simpleks usul bilan yechiladi. Quyidagi masalani koʻraylik.

Masala Qogʻ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.

nomlari sillyuloza yogʻochmassasi Kaolin daromad

Tipografiya qogʻozi 306 829 20 10

Muqova qogʻozi 424 627 18 12

Yozuv qogʻozi 510 518 12 16

Қолган хом ашёлардан қоғозларни хар бир туридан канча миқдорда ишлаб чиқарилса комбинат энг юқори даромад олади ва қайси турдаги хом ашёлардан қанча миқдорда ортиб қолади.