|
§ 3 Chiziqli dasturlash masalasining kanonik shakli
|
| bet | 3/8 | | Sana | 18.05.2024 | | Hajmi | 87,93 Kb. | | #241394 |
Bog'liq Chiziqli dasturlash modelining umumiy ko§ 3 Chiziqli dasturlash masalasining kanonik shakli
Muammoning matematik modeli kanonik shaklga ega bo'lishi kerak.
Agar cheklash tizimi faqat tenglamadan iborat bo'lsa va barcha o'zgaruvchilar manfiy bo'lmagan shartni qanoatlantirsa, u holda masala kanonik shaklga ega bo'ladi.
Agar tizimda kamida bitta tengsizlik bo'lsa yoki biron bir o'zgaruvchi manfiy bo'lmagan shart bilan cheklanmagan bo'lsa, u holda muammo standart shaklga ega bo'ladi. Muammoni kanonik shaklga keltirish uchun sizga kerak:
tengsizliklardan tenglamaga quyidagicha o'ting: tengsizliklarning chap tomoniga tengsizlik uchun (+1) koeffitsientli qo'shimcha o'zgaruvchini kiritamiz (
) va (-1) tengsizlik uchun () qo'shimcha o'zgaruvchilar maqsadli noanfiylik bilan o'rnatilmaydi, keyin u ikkita manfiy bo'lmagan o'zgaruvchilarning farqi bilan almashtiriladi, ya'ni: = - (
Kanonik shaklning umumiy ko'rinishi:
I bob Masalani simpleks usulida yechish
Simpleks usuli - bu rejani (yechimni) ketma-ket takomillashtirish usuli bo'lib, eng samarali va har qanday chiziqli dasturlash masalasini hal qilishda qo'llaniladi.
Usulning nomi lotincha simplecx dan olingan - oddiy, chunki. Boshlang'ich mintaqadan muammoning maqbul echimlari eng oddiy shaklga ega edi. Usulning g'oyalari rus matematigi Kontarovich L.V. 1939 yilda va keyin bu g'oya 1949 yilda J. Danzig tomonidan ishlab chiqilgan va ishlab chiqilgan.
Simpleks usuli optimal yechimni topish yoki uning mavjud emasligini isbotlash uchun chekli qadamlarni bajarish imkonini beradi.
§ 1 Muammo bayoni
Korxona ishlab chiqarish jarayonida I, ę, ÍęI 3 turdagi dastgohlardan foydalanadi. Shu bilan birga, xom ashyo, mehnat resurslari sarflanadi, qo'shimcha xarajatlar hisobga olinadi.
Har qanday chiziqli dasturlash masalasini kanonik shakldagi chiziqli dasturlash masalasiga keltirish mumkin. Buning uchun, umumiy holatda, siz maksimallashtirish muammosini minimallashtirish muammosiga qisqartirish imkoniyatiga ega bo'lishingiz kerak; tengsizlik cheklovlaridan tenglik cheklovlariga o'tish va noaniqlik shartiga bo'ysunmaydigan o'zgaruvchilarni almashtirish. Ayrim funksiyani maksimallashtirish qarama-qarshi belgi bilan olingan bir xil funktsiyani minimallashtirishga teng va aksincha.
Chiziqli dasturlash masalasini kanonik shaklga keltirish qoidasi quyidagicha:
agar dastlabki masalada chiziqli funktsiyaning maksimalini aniqlash talab etilsa, u holda ishorani o'zgartirish va bu funktsiyaning minimalini izlash kerak;
agar cheklovlarning o'ng tomoni manfiy bo'lsa, unda bu cheklov -1 ga ko'paytirilishi kerak;
agar cheklovlar orasida tengsizliklar mavjud bo'lsa, u holda qo'shimcha manfiy bo'lmagan o'zgaruvchilarni kiritish orqali ular tenglikka aylantiriladi;
ba'zi o'zgaruvchan bo'lsa x j hech qanday belgi cheklovlari yo'q, keyin u (maqsad funktsiyasida va barcha cheklovlarda) ikkita yangi salbiy bo'lmagan o'zgaruvchilar orasidagi farq bilan almashtiriladi:
|
| |
