O’zbekiston Respublikasi Toshkent Shahridagi Muhammad Al

O’zbekiston Respublikasi Toshkent Shahridagi Muhammad Al-Xorazmiy
nomidagi Toshkent Axborot Texnologiyalari Universiteti
Telekommunikatsiya Texnologiyalari fakulteti
MUSTAQIL ISH


Fan nomi:
Algoritmlash va loyihalash
Guruh: 042 –19
Bajardi: Mirbabayev R
Tekshirdi: Mamadaliyev X

Mavzu: Chiziqli dasturlash masalasi uchun yechim, optimal yechim, uni topishda geometrik usul. Xoffman daraxtlari.

Chiziqli dasturlash modelining matematik tavsifi. Chiziqli dasturlash masalasini simpleks usulida yechish Chiziqli dasturlash modelining umumiy korinishi

Eng oddiylari chiziqli deterministik modellardir. Ular nazorat o'zgaruvchilarning chiziqli shakli shaklida o'rnatiladi ( NS):
W = a 0 + a 1 x 1 + … + a k x k
shaklning chiziqli cheklovlari ostida
b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ b j , j = 1,…, q 1 ;
c 1 j x 1 + c 2 j x 2 + … + c kj x k = c j , j = 1,…, q 2 ;
d 1 j x 1 + d 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .
Cheklovlarning umumiy soni m = q 1 + q 2 + q 3 o'zgaruvchilar sonidan oshib ketishi mumkin (m> k). Bundan tashqari, odatda o'zgaruvchilarning ijobiyligi sharti kiritiladi ( x i ³ 0).
Chiziqli model uchun javob yuzasi giperplan... Masalan, quyidagi shakldagi ikkita o'zgaruvchining chiziqli modelini ko'rib chiqing:
W =–2x 1 –3x 2 (2.2)
quyidagi cheklovlar ostida

(2.3)

2x 1 + 3x£ 2 18;
x 1 – 4x 2 £ 4;
–2x 1 + x£ 2;
NS 1 ³ 0; x 2 ³ 0.
Yaroqli qiymatlar diapazoni (ta'rif sohasi) OABCD model uchun (2.2) cheklovlar (2.3) orqali hosil bo'ladi (2.2-rasm). Javob yuzasi tekis ko'pburchakdir OA "B" C "D"(2.2-rasm, b).

Cheklovlarning ma'lum nisbati uchun mumkin bo'lgan echimlar to'plami mavjud bo'lmasligi mumkin (bo'sh). Bunday to'plamga misol rasmda ko'rsatilgan. 2.3. To'g'ridan-to'g'ri AS va Quyosh yuqoridan ruxsat etilgan qiymatlar oralig'ini cheklash. Uchinchi cheklov to'g'ri chiziqning pastki qismidan ruxsat etilgan qiymatlar oralig'ini kesib tashlaydi AB. Shunday qilib, barcha uchta cheklovni qondiradigan umumiy maydon yo'q.
Chiziqli modellar juda oddiy va shuning uchun, bir tomondan, muammoni sezilarli darajada soddalashtirishni nazarda tutsa, boshqa tomondan, ular hal qilishning oddiy va samarali usullarini ishlab chiqishga imkon beradi.
DLA ni o'rganishda chiziqli modellar kamdan-kam qo'llaniladi va deyarli faqat muammolarning taxminiy tavsifi uchun.
Chiziqli modellar chiziqli bo'lmagan modellarni bosqichma-bosqich yaqinlashtirish uchun ishlatilishi mumkin (muammoni chiziqlilashtirish). Ushbu uslub, ayniqsa, o'rganilayotgan makonning kichik joylarini o'rganishda samaralidir. Chiziqli bo'lmagan javob yuzasining alohida bo'limlarini chiziqli model bilan ko'rsatish chiziqli taktikalar deb ataladigan optimallashtirish usullarining katta guruhining asosini tashkil qiladi.
Chiziqli modellarni o'rganish qiyin emas. Xususan, har bir o'zgaruvchining shakl modelining xususiyatlariga ta'siri
W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k
uning koeffitsientlari bilan ifodalanadi:
, i = 1,…, k.
Optimal chiziqli modelni topish uchun V opt samarali simpleks usulini ishlab chiqdi.
Eng oddiy xarajat modellari ba'zan chiziqli bo'lganlarga qisqartiriladi, ular qilingan xarajatlar to'plami sifatida qaraladi.
Bunday modelga misol klassik hisoblanadi transport xarajatlari modeli (transport muammosi)(2.4-rasm).

U yerda k ishlab chiqarish punktlari
(i = 1,…, k) va m iste'mol nuqtalari
(j = 1,…, m) ba'zi mahsulotlar. Har birida ishlab chiqarilgan mahsulot miqdori k ishlab chiqarish nuqtalari teng a i; har birida talab qilinadigan mahsulot miqdori m iste'mol nuqtalariga teng b j.
Umumiy ishlab chiqarish va iste'molning tengligi qabul qilinadi:
dan tashilgan mahsulot miqdori i- ishlab chiqarish punkti j-inchi iste'mol nuqtasiga teng x ij; ushbu mahsulot birligini tashish narxi - ij bilan.
Transportning umumiy qiymati BILAN S berilgan chiziqli model:

quyidagi cheklovlar ostida

Chiziqli modellarga chiziqli differentsial tenglamalar (oddiy yoki qisman hosilalar) shaklidagi modellar ham kiradi.
Chiziqli oddiy differensial tenglama n-buyurtma shakliga ega
Dastlabki shartlar quyidagicha yoziladi
Chiziqli qisman differentsial tenglama shaklga ega
Qisman differensial tenglama ko'rinishida berilgan model boshlang'ich va chegaraviy shartlarni (F funktsiyani aniqlash sohasi chegarasidagi shartlarni) o'z ichiga oladi. t)).
2.3. Eng oddiy matematik modelni o'rganish
gaz turbinali dvigatelning ishlashi
Gaz turbinali dvigatel (GTE) zamonaviy samolyotlarning asosiy elektr stantsiyasidir.
GTE diagrammasi rasmda ko'rsatilgan shaklga ega. 2.5.


Bu yerda 1 - kirish diffuzeri; 2 - kompressor; 3 - yonish kamerasi; 4 - turbina;
5 - chiqish nozli.
GTE ish tsikli quyidagi bosqichlarni o'z ichiga oladi:
1) Tezlik bilan kelayotgan V diffuzor orqali havo oqimi kompressorga kiradi.
2) Turbina bilan bir xil valda aylanadigan kompressor yonish kamerasiga kiradigan havoni siqadi.
3) Yonilg'i (kerosin) doimiy ravishda siqilgan havo bilan aralashtiriladigan yonish kamerasiga AOK qilinadi.
4) Yonish natijasida hosil bo'lgan gaz turbinaga kiradi, bu uning tezligini tezlashtiradi V.
5) Bu tezlikda gaz nozul orqali atmosferaga tashlanadi.
Shu sababli V > V, tortish kuchi hosil bo'ladi R bu samolyotga atmosferada parvoz qilish imkonini beradi.
Dvigatelni boshqarish tugmachasini (gaz kelebeğini boshqarish) harakatlantirish orqali yonish kamerasiga yonilg'i quyish tezligini o'zgartirish orqali bosim kuchi o'zgartiriladi. Gaz kelebeğini boshqarishning ma'lum bir burchagi d bo'ylab harakatlanishi uchuvchi tomonidan qo'lda yoki parvoz paytida ACS signallariga muvofiq aktuator yordamida amalga oshiriladi. D gaz kelebeği qiymatining oshishi kuchning oshishiga olib keladi R, va pasayish bu kuchning pasayishi hisoblanadi.
GTE murakkab texnik tizim bo'lib, unda ko'plab fizik va kimyoviy jarayonlar sodir bo'ladi. Dvigatel barcha turdagi avtomatlashtirish moslamalari, turbinaning qanotlarini aylantirish va sovutish tizimlari va boshqalar bilan jihozlangan. Tabiiyki, GTE ishlashining matematik tavsifi ham juda og'ir bo'ladi, jumladan qisman differentsial tenglamalar tizimlari, oddiy differentsial tenglamalar, transsendental funktsiyalar, raqamli dvigatelni boshqarish tizimining algoritmlari. Bunday modellar gaz turbinali dvigatelni loyihalash jarayonida qo'llaniladi.
Parvozni boshqarish muammolarini hal qilish uchun oddiyroq GTE modeli qo'llaniladi, bu surish kuchiga bog'liq. R gaz kelebeği d burchagidan, gaz kelebeği og'ishi. Tortishish kuchini o'zgartirish jarayoni oddiy differensial tenglama bilan tavsiflanadi:
 , (2.11)
bu erda t> 0 - dvigatelning vaqt konstantasi, konstruktiv xarakteristikalar bilan bir qatorda, atrof-muhit havosining harorati, uning namligi va boshqa tashqi omillarga ham bog'liq; k[kg / deg] - mutanosiblik koeffitsienti.
(2.11) tenglamaning dastlabki sharti quyidagicha yoziladi
R(0) = R 0 . (2.12)
Shunday qilib, (2.11) tenglama boshlang'ich shart (2.12) bilan birga oddiy differensial tenglama shaklida yozilgan GTE operatsiyasining eng oddiy matematik modeli 1th buyurtma.
Tomonlar nisbatini aniqlash uchun k eksperimental ma'lumotlar asosida qurilgan gaz kelebeğining aylanish burchagiga surishning bog'liqligini kalibrlash grafiklaridan foydalanilgan. Grafikning qiyaligi kerakli koeffitsientga teng.


(2.11) tenglamaning (2.12) boshlang'ich sharti bilan integrallashi surish kuchining vaqt o'tishi bilan qanday o'zgarishini aniqlash imkonini beradi (2.6-rasm).
Gaz kelebeği burilsa, surish R ortadi va keyin ma'lum bir chegara qiymatida barqarorlashadi, ya'ni. GTE - inertial ob'ekt.
Tortishish kuchi chegarasi uning o'zgarish tezligi nolga teng bo'lganda (2.11) dan olamiz:
 . (2.13)
Ko'tarilish davomiyligi dvigatelning t vaqt konstantasi qiymatiga bog'liq. Jarayon qachon barqaror hisoblanadi t = t og'iz, surish surish kuchining chegaraviy qiymatining besh foizli yo'lak deb ataladigan qismiga kirganda (2.6-rasm). Qanchalik ko'p t bo'lsa, vosita shunchalik inertial va shuning uchun ko'proq t og'iz

Shaklda. 2.7 t = 0,5 da gaz kelebeği burilish burchagi funktsiyasi sifatida surish kuchining harakatini ko'rsatadi.
Uchish paytida tortish kuchi, gaz kelebeği 10 ° ga burilganda, uchinchi soniyada barqaror holatga keladi va 3390 kg ga etadi. Uchishdan o'n soniya o'tgach, gaz kelebeği 20 ° ga burilsa, tortish kuchi 6780 kg ga o'rnatiladi va yana o'n soniyadan so'ng, gaz kelebeği 30 ° ga burilsa, tortishish 10170 kg ga o'rnatiladi. Tortishish kuchining chegaraviy qiymati
14270 kg.

Shunga o'xshash ma'lumotlar.

3.1. Umumiy chiziqli dasturlash masalasi
Chiziqli dasturlash- bu matematik dasturlashning eng rivojlangan bo'limi bo'lib, uning yordamida chiziqli ulanishlar va cheklovlar bilan ekstremal masalalarni tahlil qilish va yechish amalga oshiriladi.
Chiziqli dasturlash bir qator evristik (taxminan) yechim usullarini o'z ichiga oladi, ular berilgan sharoitlarda ishlab chiqarish muammolarining barcha mumkin bo'lgan echimlaridan eng yaxshisini, optimalini tanlashga imkon beradi. Bu usullarga quyidagilar kiradi - grafik, simpleks, potentsial usul (modifikatsiyalangan taqsimlash usuli - MODI), Xichkova, Kreko, Vogelga yaqinlashish usuli va boshqalar.
Ushbu usullarning ba'zilari umumiy nom - tarqatish yoki tashish usuli bilan birlashtirilgan.
Chiziqli dasturlashning vatani Rossiyadir. Chiziqli dasturlash bo'yicha birinchi ishlar bo'lajak akademik L.V. Kantorovich 1939 yilda nashr etilgan. 1975 yilda u chiziqli dasturlash usullarini ishlab chiqqani uchun iqtisod bo'yicha Nobel mukofotiga sazovor bo'lgan. Akademik L.Vning aksariyat asarlaridan beri. Kantorovich transport muammolarini hal qilishga bag'ishlangan, shuni aytish mumkinki, ko'rsatilgan Nobel mukofoti ham Rossiya transport fanining xizmatlarini tan oladi.
Avtomobil transportida 1960-yillardan boshlab ko'plab eng muhim ishlab chiqarish muammolarini hal qilish uchun chiziqli dasturlash usullari qo'llanila boshlandi, xususan: yuklarni tashish masofasini qisqartirish; optimal tashish sxemasini tuzish; eng qisqa harakat yo'nalishlarini tanlash; har xil, lekin bir-birini almashtiradigan tovarlarni tashish vazifalari; smenali kunlik rejalashtirish; kichik partiyadagi yuklarni tashishni rejalashtirish; avtobuslarni marshrutlarga taqsimlash va boshqalar.
Chiziqli dasturlash modelining xususiyatlari quyidagilardan iborat:
Maqsad funktsiyasi va cheklovlar chiziqli bog'liqliklar (tenglik yoki tengsizlik) bilan ifodalanadi;
Bog'liqlar soni har doim noma'lumlar sonidan kamroq (noaniqlik sharti);
Kerakli o'zgaruvchilarning manfiy emasligi. Chiziqli dasturlash modelini qisqartirilgan shaklda yozishning umumiy shakli quyidagicha:
Toping NS ij ≥ 0 (j = 1, 2 ... n) quyidagi turdagi cheklovlar ostida:
Ushbu cheklovlar maqsad funktsiyasini minimallashtiradi (yoki maksimal darajaga keltiradi).
Chiziqli dasturlash modelini yozishning standart shakli chiziqli tenglamalar tizimida yozilgan kanonik shaklda, ya'ni chiziqli tenglik shaklida, manfiy bo'lmagan sonlarda:
a 11 x 1 + a 12 x 2 + ... + a 1 n x n = b 1;
a 21 x 1 + a 22 x 2 + ... + a 2 n x n = b 2 ; (3.1)
……………………………..
a m x 1 + a m 2 x 2 +… + a mn x n = b m ..
Agar model manfiy bo'lmagan sonlarda tengsizliklar ko'rinishida yozilsa, ya'ni u shaklga ega.
a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;
a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)
……………………………..
a m x 1 + a m 2 x 2 +… + a mn x n ≤ b m, ..
keyin bu rekord kamayadi kanonik qo'shimcha o'zgaruvchilarni kiritish orqali (3.1) shakl x n +1> 0 (i=1,2…m) tengsizlikning chap tomoniga (yoki tengsizlik belgisi boshqa tomonga yo'naltirilgan bo'lsa, o'zgaruvchilar sonini bekor qilish). Qo'shimcha o'zgaruvchilar asosni tashkil qiladi.
Chiziqli dasturlash masalasini echishning standart shakli maqsad funktsiyasini minimallashtiradigan manfiy bo'lmagan sonlardagi chiziqli tenglamalar tizimining echimlarini topishdir. Bunday holda, maqsad funktsiyasi shaklga ega
L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3,3)
qayerda s 1, s 2 ... s n- maqsad funksiya koeffitsientlari L o'zgaruvchilar bilan NS j.
Qo'shimcha o'zgaruvchilar maqsad funktsiyasiga nol koeffitsientlar bilan kiradi.
Maqsad funksiyasini maksimallashtirish holatida L maqsad funktsiyasining o'zgaruvchilari belgilari teskari bo'lishi kerak va biz yana minimallashtirish muammosiga kelamiz, ya'ni. almashtirish orqali bir vazifa boshqasiga qisqartiriladi L- L yoki maks L= min (- L).
Chiziqli tenglamalar tizimining asosiy yechimi (3.1) asosiy bo'lmagan o'zgaruvchilarga nol qiymatlar berilgan yechimdir.
Bazisga kiritilgan o'zgaruvchilar manfiy bo'lmagan asosiy yechim ruxsat etilgan deb ataladi.
Optimal yechim - bu maqsad funktsiyasini (3.3) maksimallashtirish (yoki minimallashtirish) mumkin bo'lgan echimdir.
Har bir chiziqli dasturlash masalasi boshqasiga mos keladi, bu ikki chiziqli dasturlash muammosi deb ataladi. Dualga nisbatan asl muammo to'g'ridan-to'g'ri deyiladi. To'g'ridan-to'g'ri va ikkilamchi masalalar juftlikni hosil qiladi, ular chiziqli dasturlashda qo'sh juftlik deb ataladi. To'g'ridan-to'g'ri va qo'sh juftlik to'g'ridan-to'g'ri masala kanonik shaklda yozilsa, assimetrik juftlikni, masalaning shartlari tengsizliklar bilan yozilsa, simmetrik juftlikni hosil qiladi.
Ikkilamchi masalaning matematik modelini tuzish qoidalari matritsalarni hisoblash qoidalariga asoslanadi.
Ikkilik tushunchasi chiziqli dasturlash masalalarini tahlil qilishda keng qo'llaniladi. Ikkilik xususiyati har bir alohida holatda batafsil ko'rib chiqiladi.
3.2. Grafik-analitik usul
Grafoanalitik usul chiziqli dasturlashning eng oddiy usullaridan biridir. U chiziqli dasturlashning mohiyatini, uning geometrik talqinini aniq ochib beradi. Uning kamchiligi shundaki, u 2 yoki 3 ta noma'lumli masalalarni yechishga imkon beradi, ya'ni tor doiradagi masalalar uchun qo'llaniladi. Usul analitik geometriya qoidalariga asoslanadi.
Ikki o‘zgaruvchili masalani yechish x 1 va x 2, bu masala ma'nosida manfiy bo'lmasligi kerak, Dekart koordinata tizimida bajariladi. Tenglamalar x 1= 0 va x 2= 0 - birinchi kvadrant koordinata tizimining o'qlari
Keling, muayyan misol yordamida hal qilish usulini ko'rib chiqaylik.