Chiziqli dasturlash nazariyasi

Chiziqli programmalashtirish nazariyasi. Chiziqli programmalashtirish masalasiga misollar Reja: Chiziqli programmalashtirish nazariyasi. Chiziqli programmalashtirish masalasiga misollar Chiziqli programmalashtirish nazariyasi. Chiziqli programmalashtirish masalasiga misollar. ChP masalalarining qo'yilishi va yozilishi. Poliedrda berilgan chiziqli funksiyaning maksimumi yoki minimumini topish masalasi chiziqli programmalashtirish masalasi (ChPM) deyiladi. Demak, ChPMni (1) bu yerda A(m,n),, ko'rinishda yozish mumkin. Mazkur masalaning joiz to'plamini alohida (2) ko'rinishda yozish mumkin. Teorema 1. Chiziqli programmalashtirish masalasining har qanday lokal yechimi global yechim bo'ladi. Shu tasdiqni nazarda tutib, kelgusida chiziqli programmalashtirish masalasining shunchaki yechimi haqida gapiramiz. (2) masala yechimlarining X* to'plami yakka poliedr bo'ladi, chunki, agar bu to'plam bo'sh bo'lmasa, bu to'plam (3) ko'rinishda tasvirlanadi, bu yerda f-(1) masalaning qiymati, yani (1) ko'rinishdagi ChPM masalasi chiziqli programmalashtirishning bosh masalasi (ChPBM) deyiladi. Joiz to'plami bilan bir-biridan farq qiladigan boshqa shakldagi chiziqli programmalashtirish masalalari ham bor. Bunda ilgarigidek, A(m,n),, deb hisoblaymiz. ChPning standart masalasi (ChPSM) (4) ChPning kanonik masalasi (ChPKM) (5) ChPning umumiy masalasi (ChPUM) (6) Chiziqli programmalashtirishning minimumni topishga doir masalarida ham shu kabi yozuvlardan foydalaniladi, faqat barcha tengsizliklar ko'rinishda yoziladi. Ko'rinib turibdiki, (1), (4) va (5) masalalarning har biri (6) ChPUMning xususiy xossalaridir. K=m va sq0 bo'lsa (1) masala, kqm va sqn bo'lsa, (4) masala, k=0 va sqn bo'lsa, (5) masala hosil bo'ladi. O'z navbatida ChPUM ham qolgan uchta masaladan biri ko'rinishida yozilishi mumkin. Masalan, agar (6) masalada tengliklar o'rniga unga teng kuchli bo'lgan (7) tengsizliklarni ko'llasak, (6) masala bosh masala ko'rinishini oladi. Agar shunga qo'shimcha tarzda o'zgaruvchilarni (8) tarzda almashtirsak, u holda (6) masala standart shaklga keladi. Endi ko'shimcha o'zgaruvchilarni olaylik, bu o'zgaruvchilar maqsad funksiyasida nol koeffitsentli bo'lib, formal qatnashadi. Agar (6) dagi tengsizliklarni (9) ko'rinishda yozib va (8) ko'rinishdagi o'zgaruvchilarni almashtirishni qo'llasak, (6) masala kanonik masalaga aylanadi. Umuman aytganda, chiziqli programmalashtirishning har qanday masalasini u yoki bu shaklda yozish mumkin. Chiziqli programmalashtirish masalasiga misollar. ChPMga ko'plab misol keltirish mumkin. Shulardan uchtasini misol keltiramiz. 1-misol (ishlab chiqarishni rejalashtirish masalasi). Bitta korxona n ta tovar ishlab chiqaradi, va bunga m ta xom ashyo sarflaydi. quyidagilar malum: -tovarning bir birlik miqdorini ishlab chiqarish uchun zarur bo'lgan i xom ashyoning miqdori ; bi - i - xom ashyoning korxonadagi zaxirasi bi0 ; cj -j - tovar birlik miqdorining narxi cj0. Ishlab chiqarish texnologiyasi chiziqli, yani xom ashyo sarfi ishlab chiqarish xajmi bilan to'g'ri proportsional o'sadi. xj-j - tovarning ishlab chiqarish rejasi xajmini belgilaydi. U holda (10) Bundan tashqari, quyidagi tabiiy cheklash ham bor: (11) X tovarning umumiy narxi (12) bilan yoziladi. Ishlab chiqarishni rejalashtirish masalasi ...