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

2. Asosiy tushuncha va ta’riflar.
1-ta’rif. Berilgan (4)-(6) masalaning joiz yechimi yoki rejasi deb, uning (4) va (6) shartlarini qanoatlantiruvchi_{ }vektorga aytiladi.
2-ta’rif. Agar joiz rejalar to‘plamiga tegishli bo‘lgan _{ } vektorning (n-m) ta koordinatasi (n – noma’lumlar soni, m – tenglamalar soni) nolga teng bo‘lib, qolgan m ta koordinatalariga mos kelgan shart vektorlar (masalan, _{ } vektorlar) chiziqli erkli bo‘lsa, u holda_{ } joiz reja bazis (asosiy) reja deyiladi.
3-ta’rif. Agar_{ } bazis rejadagi musbat koordinatalar soni m ga teng bo‘lsa, u holda bu reja aynimagan bazis reja, aks holda aynigan bazis reja deyiladi.
4-ta’rif. Chiziqli funktsiya (6) ga eng kichik qiymat beruvchi _{ } bazis reja masalaning optimal rejasi yoki optimal yechimi deyiladi.
5-ta’rif._{ }, _{ }vektorlarning qavariq kombinatsiyasi deb

shartlarni qanoatlantiruvchi

vektorga aytiladi. _{ }–o‘lchovli fazodagi har bir _{ } vektorga koordinatalari _{ } bo‘lgan nuqta mos keladi. Shuning uchun bundan keyin _{ } vektorni n –o‘lchovli fazodagi nuqta deb qaraymiz.
6-ta’rif. Agar n o‘lchovli vector fazodagi S to‘plam o‘zining ixtiyoriy _{ } va _{ } nuqtalari bilan bir qatorda bu nuqtalarning qavariq kombinatsiyasidan iborat bo‘lgan

nuqtani ham o‘zichiga olsa, ya’ni _{ } bo‘lsa, bu to‘plam qavariq to‘plam deb ataladi.²
Chiziqli dasturlash masalasi ustida quyidagi tengkuchli almashtirishlarni bajarish mumkin.
1. _{ }ni_{ }ga aylantirish. Har qanday chiziqli dasturlash masalasini kanonik ko‘rinishga keltirish uchun (1) tengsizliklar sistemasini tenglamalar sistemasiga va _{ }ni_{ }ga aylantirish kerak. _{ }ni_{ }ga keltirish uchun, _{ }ni teskari ishora bilan olish, ya’ni_{ } =_{ } yoki _{ }=_{ } ko‘rinishda olish yetarlidir.
2. Tengsizliklarni tenglamaga aylantirish. n noma’lumli
_{ } (16)
chiziqli tengsizlikni qaraymiz. Bu tengsizlikni tenglamaga aylantirish uchun uning kichik tomoniga nomanfiy o‘zgaruvchini, ya’ni _{ }ni qo‘shamiz.
Natijada n+1 noma’lumli chiziqli tenglamaga ega bo‘lamiz:
_{ } (17)
(16) tengsizlikni tenglamaga aylantirish uchun qo‘shilgan _{ } o‘zgaruvchi qo‘shimcha o‘zgaruvchi deb ataladi.