Chiziqli dasturlashtirish

Chiziqli programmalashtirish Reja: 1. Chiziqli programmalashtirish masalasining qo'yilishi va uning turli formalarda ifodalanishi. 2. Chiziqli programmalashtirish masalasining geometrik talqini va uni grafik usulda yechish. 3. Chiziqli programmalashtirish masalasining yechishning simpleks usuli. 2.4. Chiziqli programmalashtirish masalasining yechishning simpleks jadvallar usuli. 5. sun'iy bazis usuli. Chiziqli programmalashtirish masalasining qo'yilishi va uning turli formalarda ifodalanishi Chiziqli programmalashtirish ishlab chiqarishni rejalashtirish va boshqarish kabi masalalarni maqbuliy yechimini aniqlashda qo'llaniladi.Chiziqli programmalashtirish ishlab chiqarishni rejalashtirish va boshqarishda rejaning berilgan shart va mumkin bo'lgan variantlarining orasidan optimal variantini topishga imkon beradi. Chiziqli programmalashtirishning qo'llaniladigan eng muhim sohasi ishlab chiqarish tarmoqlarini iqtisodiy tomondan boshqarishdir. Shuning uchun chiziqli programma-lashtirish iqtisodiy rejalashtirish hamda boshqarish masala-larini yechishda qo'llaniladi. Chiziqli programmalashtirishning umumiy masalasi simpleks usuli bilan echiladi. Chiziqli programmalashtirishning bu usuli yordamida qurilish, texnik va iqtisodiy masalalarning optimal yechimi topiladi. Simpleks usulining boshqa usullardan afzalligi shundaki, u o'lchov birligining bir xil bo'lishini talab qilmaydi. Bu usul yordamida yechimni optimal darajaga ko'taradi. Chiziqli programmalashtirishning umumiy masalasi matematik ko'rinishda quyidagicha ifodalanadi: Shunday o'zgaruvchilarning manfiy bo'lmagan qiymatlari aniqlanib, chiziqli ko'rinishdagi maqsad funksiya (1) ekstremal (eng katta yoki eng kichik) qiymatga erishib, quyidagi chiziqli cheklanish shartlari bajarilsin, (2) hamda nomalum o'zgaruvchilarning qiymatlari manfiy bo'lmasin (3). Bunda munosabat belgisi bo'lib, ular dan iborat. lar oldindan berilgan o'zgarmas sonlardir. (1) - (3) formulalarni quyidagicha ham yozish mumkin: (1|) (2| ) (3 | ) Ushbu masala vektor ko'rinishida quyidagicha yoziladi. Agar vaorqali ifodalansa, u holda chiziqli programmalashtirishng umumiy masalasi (1| |) (2| |) (3| |) shaklida yoziladi. 1-ta'rif. Tenglamalar yoki tengsizliklar sistemasining istalgan manfiy bo'lmagan yechimi o'rinli yechim deyiladi. 2-ta'rif. Maqsad funksiyaga talab qilingan maksimum (yoki minimum), qiymat beruvchi o'rinli yechim optimal yechim deyiladi. Eslatma.Iqtisodiy masalalarni yechishdan oldin eng avvalo qo'yilgan masalaning mohiyatini to'liq aks ettiradigan iqtisodiy - matematik modellarini qurish lozimdir. 2.2. Chiziqli programmalashtirish masalasining geometrik talqini va uni grafik usulda yechish. Tekislikda chiziqli programmalashtirish masalasi berilgan bo'lib, (1) funksiyaning cheklanish tengsizliklari sistemasini (2) qanoatlantiradigan eng kichik qiymatini topish talab qilingan bo'lsin. (2) tengsizliklar sistemasini birgalikda deb faraz qilsak, u holda bu tengsizliklarning har biri va to'g'ri chiziqlar bilan, yechimlarning manfiy emaslik shartlari esa to'g'ri chiziqlar bilan yarim tekisliklarni tashkil etadi va bu yarim tekisliklar bir - biri bilan kesishib, o'rinli yechimlar to'plami bo'lgan birorta ko'pburchakni tashkil qiladi. (1) maqsad funksiyaning har bir qiymatida birorta to'g'ri chiziqning tenglamasini ifoda etadi. . (3) Xususiy holda bo'lsa, bu to'g'ri chiziq = 0 (4) ko'rinishda bo'lib, koordinata boshidan o'tadi. Endi qo'yilgan masala quyidagicha bayon qilinadi. Mumkin bo'lgan yechimlar to'plamidan ko'pburchakning shunday ...