2-ma’ruza. Chiziqli programmalash-tirishning umumiy masalasi va uni geometrik talqini reja

2-MA’RUZA. CHIZIQLI PROGRAMMALASH-TIRISHNING UMUMIY MASALASI VA UNI GEOMETRIK TALQINI
REJA:

1. 
   Chiziqli programmalashtirish masalasining umumiy qo’yilishi.
   
2. 
   Chiziqli programmalash masalasining kanonik ko‘rinishi.
   
3. 
   Chiziqli programmalash masalasini grafik usulda yechish.
   

REJA:
TAYANCH IBORALAR: tayanch plan, aynimagan tayanch plan, aynigan tayanch plan, optimal yechim.
Chiziqli programmalash masalasining umumiy ko‘rinishi
Chiziqli programmalash masalasi umumiy holda quyidagicha ifodalanadi:
(1)
(2)
(3)
(2) va (3) shartlarni qanoatlantiruvchi noma’lumlarning shunday qiymatlarini topish kerakki, ular (3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (1) va (2) shartlari uning chegaralovchi shartlari yoki cheklovlar deb, (1.3.3) chiziqli funksiya esa masalaning maqsad funksiyasi deb ataladi. Masaladagi (1) shartning chap tomoni va maqsad funksiyasi noma’lumlarga nisbatan chiziqli ekani ko‘rinib turibdi. Shuning uchun ham (1), (3) masala chiziqli programmalash masalasi deb ataladi.
Konkret masalalarda (1) shart tenglamalar sistemasidan, yoki ko‘rinishdagi tengsizliklar sistemasidan iborat bo‘ladi. Ba’zi masalalarda (1) shart tenglamalar va tengsizliklar sistemasidan iborat bo‘lishi ham mumkin. Ammo ko‘rsatish mumkinki, (1)-(3) ko‘rinishdagi masala osonlik bilan quyidagi ko‘rinishga keltiriladi:
(1`)
(2`)
(3`)
(1`)–(3`) ko‘rinish chiziqli programmalash masalasining kanonik ko‘rinishi (shakli) deb ataladi.
Berilgan (1`) –(3`) masala vektorlar yordamida quyidagicha ifodalanadi:
(4)
(5)
(6)
Bu yerda
,
vektor qator,
vektor ustun.
Berilgan (1`) –(3`) masalaning matritsa yordamidagi ifodasi bunday:
(7)
(8)
(1.3.9)
Bu yerda matritsa qator, koeffitsiyentlardan tashkil topgan matritsa:
ustun matritsalar.
Berilgan (1`) –(3`) masalani yig‘indilar yordamida ifodalash ham mumkin:
(10)
(11)
(12)
1- ta’rif. Berilgan (1`)-(3`) masalaning mumkin bo‘lgan yechimi yoki plani deb, uning (1), (2) shartlarini qanoatlantiruvchi vektorga aytiladi.
2- ta’rif. Agar (4) yoyilmadagi musbat koeffitsiyentli vektorlar o‘zaro chiziqli bog‘liq bo‘lmasa, plan tayanch plan deyiladi.
3- ta’rif. tayanch plandagi musbat komponentalar soni m ga teng bo‘lsa, bu plan ayinimagan tayanch plan, aks holda aynigan tayanch plan deyiladi.
4- ta’rif. Chiziqli funksiya (3`) ga eng kichik yoki eng katta qiymat beruvchi kanonik plan masalaning optimal plani yoki optimal yechimi deyiladi.

ni ga aylantirish

Har qanday chiziqli programmalash masalasini (1`)-(3`) ko‘rinishga keltirish uchun (1) tengsizliklarni tenglamalarga va ni ga aylantirish kerak. (maksimumini topish talab qilingan funksiyani) (minimumini topish talab qilingan funksiya) ga keltirish uchun ni teskari ishora bilan olish, ya’ni

yoki
ko‘rinishda olish yetarlidir.
Haqiqatan ham, har qanday funksiyaning maksimumi shu funksiya minimumining teskari ishora bilan olingan qiymatiga teng, ya’ni
hamda

noma’lumlarning bir xil qiymatlarigina o‘zaro teng bo‘lishini ko‘rsatish mumkin.
Aytilgan fikrlarning to‘g‘riligini bir argumentli funksiyaning geometrik tasviri yordamida ko‘rsatish mumkin. nuqtada funksiya maksimumga, - funksiya esa minimumga erishadi, shu bilan birga (1- shakl). Shunday qilib, agar masalaning maqsad funksiyasi ko‘rinishda berilgan bo‘lsa, uni ga va aksincha, ni ga aylantirish mumkin.


u







x

1- shakl.