|
Reja: Simpleks usulining dasturiy ta’minoti
|
| bet | 1/2 | | Sana | 26.05.2023 | | Hajmi | 1.11 Mb. | | #65285 |
Bog'liq taqdimot mustaqil ish al, Taqdimot ex
Chiziqli dasturlash masalalarini yechishning simpleks usuli algoritmi va uni tahlil qilish. Hisoblash geometriyasi.
Reja:
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.
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.
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.
Simpleks usuli
Simpleks usuli Chiziqli dasturlash masalalarini hal qilishning keng tarqalgan usuli. Usul o'z nomini "simpleks" so'zidan oldi, bu eng oddiy konveks ko'pburchakni bildiradi, uning uchlari soni har doim bo'shliq o'lchamidan bittaga ko'p. Simpleks usuli AQSHda 1940-yillarning oxirida matematik J.Dansig tomonidan ishlab chiqilgan.
Simpleks usuli (3.1) tipidagi kanonik chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimini olish, maqsad funktsiyasini (3.3) keyinchalik minimallashtirish (maksimallashtirish) va shu tarzda qidirilayotgan o'zgaruvchilarning optimal qiymatlarini topishni o'z ichiga oladi. x 1, x 2 ... x n.
Simpleks usulining g'oyasi shundan iboratki, hisoblash jarayonida birinchi asosiy yechimdan ikkinchi, uchinchi va boshqalarga ketma-ket o'tish. deb atalmish orqali oddiy transformatsiyalar. O'zgartirishlar simpleks jadvallar shaklida amalga oshiriladi, bu esa hisob-kitoblarni sezilarli darajada soddalashtiradi va tezlashtiradi.
Bu juda muhim, chunki ko'rsatilgan o'zgaruvchining diapazonini aniqlash va uning maksimal qiymatini almashtirish o'rniga, boshqa erkin o'zgaruvchilarning nol qiymatlarida har qanday erkin o'zgaruvchining mumkin bo'lgan eng katta qiymatiga mos keladigan ma'lum bir salbiy bo'lmagan yechimni topish uchun. mumkin bo'lgan qiymatni umumiy yechimga kiritish uchun ushbu o'zgaruvchini asosiy sifatida qabul qilish va tizimni yangi asosga o'tadigan simpleks transformatsiyasiga topshirish kifoya, bu esa hisob-kitoblarni sezilarli darajada osonlashtiradi.
Simpleks jadvallari yordamida hisob-kitoblar qulay tarzda amalga oshiriladi. Bir jadvaldan ikkinchisiga o'tish bir iteratsiyaga, ya'ni bir asosdan ikkinchisiga o'tishga to'g'ri keladi, shu bilan birga maqsad funktsiyasining qiymati kamayadi. Muayyan miqdordagi iteratsiyalar uchun ular maqsad funktsiyasining optimal (minimal yoki maksimal) qiymati olinadigan asosga o'tadi
|
| |
