9 маъруза. Chiziqli dasturlashning asosiy masalalari: kanonik va standart shakldagi masalalar. Chiziqli dasturlash masalasining geometrik talqini. Chiziqli dasturlash masalasi optimal yechimini grafik usulda topish

1-misol. Masalani grafik usulda eching.




Yechish. Yechimlardan tashkil topgan qavariq ko‘pburchak yasash uchun koordinatalar sistemasida



chiziqlar yasaymiz (5-rasm).

5-rasm.
Berilgan tengsizliklarni qanoatlantiruvchi yechim shtrixlangan OABC to‘rtburchakni tashkil qiladi. Endi koordinatalar boshidan _{ }=(2,5) vektorni yasaymiz va unga perpendikulyar bo‘lgan to‘g‘ri chiziq o‘tkazamiz. Bu to‘g‘ri chiziq

tenglama orqali ifodalanadi. Uni _{ } vektor yo‘nalishida o‘ziga parallel siljitib boramiz. Natijada chiziqli funksiyaga maksimal qiymat beruvchi C(3;0) nuqtani topamiz. Bu nuqtaning koordinatalari x₁ =3, x₂=0 masalaning optimal echimi bo‘ladi va _{ } bo‘ladi.
2-misol. Berilgan chiziqli dasturlash masalasini grafik usulda yeching.




Yechish. Yechim ko‘pburchagini hosil qilamiz. Uning uchun koordinatalar sistemasida



to‘g‘ri chiziqlar yasaymiz (6-rasm).

6-rasm
Rasmdan ko‘rinadiki, yechimlar ko‘pburchagi yuqoridan chegaralanmagan. Koordinata boshidan _{ }(2:2) vektorni yasaymiz va unga perpendikulyar bo‘lgan to‘g‘ri chiziq o‘tkazamiz. Bu chiziq

tenglama orqali ifodalanadi.
Shakldan ko‘rinadiki, masalada maqsad funksiyaning maksimum qiymati yuqoridan chegaralanmagan ekan.⁵
3-misol. Masalani grafik usulda eching.




Masalani yuqoridagi usul bilan echib quyidagi shaklga ega bo‘lamiz (7-rasm):

7-rasm.
Rasmdan ko‘rinadiki, yechimlar to‘plami chegaralanmagan, lekin optimal yechim mavjud va u A nuqta koordinatalaridan iborat.

1Prof. SaraBilley.DiscreteMathematicalModeling. UniversityofWashington, WinterQuarter, 2011, pp.73-87.

2Prof. SaraBilley.DiscreteMathematicalModeling. UniversityofWashington, WinterQuarter, 2011, pp.73-87.

3Prof. SaraBilley.DiscreteMathematicalModeling. UniversityofWashington, WinterQuarter, 2011, pp.73-87.

4Prof. Sara Billey.Discrete Mathematical Modeling. University of Washington, Winter Quarter, 2011, pp.73-87.

5Prof. Sara Billey.Discrete Mathematical Modeling. University of Washington, Winter Quarter, 2011, pp.73-87.