|
7-Mavzu: Chiziqli dasturlash. Chiziqli dasturlash algoritmlari
Reja:
Chiziqli dasturlash
Chiziqli dasturlash masalalari
Chiziqli dasturlashning asosiy teoremalari
Chiziqli dasturlash usullari
Chiziqli dasturlash
Chiyiziqli dasturlash (ChD) – birinchi va puxta o'rganilgan matematik dasturlash bo'limlaridan biri. Bu "matematik dasturlash" fanining o'zi rivojlana boshlagan chiziqli dasturlash edi. Ushbu fan nomidagi "dasturlash" atamasi "kompyuter uchun dasturlash (ya'ni dastur tuzish)" atamasi bilan hech qanday aloqasi yo'q, chunki "chiziqli dasturlash" intizomi kompyuterlardan matematik, muhandislik, iqtisodiy va boshqa muammolarni echishda keng foydalanila boshlangan vaqtdan oldin ham paydo bo'lgan.
"Chiziqli dasturlash" atamasi ingliz tilidagi "chiziqli dasturlash" ning noto'g'ri tarjimasidan kelib chiqqan. "Dasturlash" so'zining ma'nolaridan biri bu rejalashtirish, rejalashtirishdir.
Shuning uchun ingliz tilidagi "chiziqli dasturlash" ning to'g'ri tarjimasi "chiziqli dasturlash" emas, balki "chiziqli rejalashtirish" bo'lishi kerak, bu esa fanning mazmunini aniq aks ettiradi. Shu bilan birga, chiziqli dasturlash, nochiziqli dasturlash, matematik dasturlash va boshqalar. adabiyotimizda umumiy qabul qilingan va shuning uchun saqlanib qoladi.
Shunday qilib, chiziqli dasturlash Ikkinchi Jahon Urushidan keyin paydo bo'ldi va matematiklar, iqtisodchilar va muhandislarning e'tiborini keng amaliy qo'llash imkoniyati va matematik uyg'unlik tufayli jalb qildi va tez rivojlana boshladi.
Chiziqli dasturlash masalalari. Haqiqiy olamning chiziqli tasviri gipotezasiga asoslanishi mumkin bo'lgan chiziqli dasturlash o'sha jarayonlar va tizimlarning matematik modellarini echishda qo'llaniladi.
Chiziqli dasturlash iqtisodiy muammolarni echishda, masalan, boshqaruv va ishlab chiqarishni rejalashtirishda ishlatiladi; uskunalarni kemalarga, ustaxonalarga optimal joylashtirishni aniqlash vazifalarida; yuklarni tashishning optimal rejasini aniqlash vazifalarida (transport vazifasi); ramkalarni optimal taqsimlash muammolarida va boshqalar.
Chiziqli dasturlash (СhD) muammosi, yuqorida aytib o'tilganidek, chiziqli funktsiyaning minimal yoki maksimal qiymatini chiziqli cheklovlar ostida topishdir.
LP muammosi umumiy shaklda (ma'lum ma'noda) kanonik (standart) shakldagi LP bilan bog'liq muammolarni kamaytiradi. Bu boshlang'ich muammodan (umumiy shaklda) yangi LP muammosini (umumiy shaklda) qurishning umumiy usulining mavjudligini anglatadi, uning har qanday optimal echimi asl muammoning optimal echimiga aylantiriladi va aksincha.
(Aslida, bu vazifalar o'rtasidagi aloqa yanada yaqinroq). Shunday qilib, biz umumiy yoki yo'qolgan holda, LP bilan bog'liq muammolarni kanonik yoki standart ko'rinishda o'rganish imkoniyatiga ega bo'lamiz. Shuni hisobga olgan holda, keyingi LP bilan bog'liq muammolarimiz asosan kanonik shakldagi muammolarga bag'ishlanadi.
Chiziqli dasturlash usullari yordamida echiladigan vazifalar doirasi ancha keng. Masalan,
ishlab chiqarishni rejalashtirishda resurslardan maqbul foydalanish muammosi;
aralashtirish muammosi (mahsulot tarkibini rejalashtirish);
omborlarda saqlash uchun turli xil mahsulotlarning maqbul kombinatsiyasini topish vazifasi (inventarizatsiyani boshqarish yoki "xalta muammosi");
transport vazifalari (korxona joylashgan joy, tovarlar harakati tahlili)
Chiziqli dasturlash bu matematik dasturlashning eng rivojlangan va keng qo'llaniladigan qismidir (bundan tashqari, ichiga quyidagilar kiradi: butun, dinamik, nochiziqli, parametrik dasturlash). Bu quyidagicha izohlanadi:
Ko'p sonli iqtisodiy muammolarning matematik modellari kerakli parametrlarga nisbatan chiziqli;
Ushbu turdagi vazifalar hozirgi kunda eng ko'p o'rganilgan. Uning uchun ushbu vazifalar echiladigan maxsus uslublar va tegishli kompyuter dasturlari ishlab chiqilgan;
Bir qator echimlarni topishda ko'plab chiziqli dasturlash muammolari keng qo'llaniladi;
boshlang'ich shakllantirishda chiziqli bo'lmagan ba'zi muammolar, bir qator qo'shimcha cheklashlar va taxminlardan so'ng, chiziqli bo'lishi mumkin yoki ularni chiziqli dasturlash usullari bilan hal qilinishi mumkin bo'lgan shaklga qisqartirishi mumkin.
Har qanday chiziqli dasturlash muammosining iqtisodiy-matematik modeliga quyidagilar kiradi: maqbul qiymatni (maksimal yoki minimal) topish kerak bo'lgan ob'ektiv funktsiya; chiziqli tenglamalar yoki tengsizliklar tizimi ko'rinishidagi cheklovlar; o'zgaruvchilardan negativ bo'lmaganlik talabi.
Umuman masala quyidagicha yoziladi:
(1) (2), (3)
Vazifa (2) va (3) shartlarga rioya qilgan holda (1) funktsiyaning maqbul qiymatini topishdir.
Cheklovlar tizimi (2) muammoning funktsional cheklovlari, va cheklovlar (3) to'g'ridan-to'g'ri deb nomlanadi.
(2) va (3) cheklovlarni qondiradigan vektorga chiziqli dasturlash masalasining yo'l qo'yiladigan echimi (rejasi) deyiladi. (1) funktsiyaning maksimal (minimal) qiymatiga erishadigan rejasi eng maqbul(optimal) deb nomlanadi.
Do'stlaringiz bilan baham: | 
