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

Chiziqli dasturlashning asosiy masalalari.
1. Masalaning umumiy qo‘yilishi.
Chiziqli dasturlash masalasi umumiy holda quyidagicha ifodalanadi:
_{ } (1)
_{ }, …, _{ } (2)
_{ } (3)
(1) va (2) shartlarni qanoatlantiruvchi noma’lumlarning shunday qiymatlarini topish kerakki, ular (3) chiziqli funkstiyaga minimal (maksimal) qiymat bersin. Masalaning (1) va (2) cheklamalariuning chegaraviy shartlari deb, (3) chiziqli funksiya esa masalaning maqsad funksiyasi deb ataladi.
Masaladagi barcha cheklama shartlar va maqsad funksiya chiziqli ekanligi ko‘rinib turibdi. Shuning uchun ham (1) - (3) masala chiziqli dasturlash masalasi deb ataladi.¹
Konkret masalalarda (1) shart tenglamalar sistemasidan, «_{ }» yoki «_{ }» ko‘rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo‘lishi mumkin. Lekin ko‘rsatish mumkinki (1)-(3) ko‘rinishdagi masalani osonlik bilan quyidagi ko‘rinishga keltirish mumkin:
_{ } (4)
_{ }, …, _{ } (5)
_{ } (6)
(4) – (6) ko‘rinish chiziqli dasturlash masalasining kanonik ko‘rinishi deb ataladi. Bu masala vektorlar yordamida quyidagicha ifodalanadi:
_{ } (7)
_{ } (8)
_{ } (9)
Buyerda



(4)-(6) masalaning matritsa ko‘rinishdagi ifodasi quyidagicha yoziladi:
_{ } (10)
_{ } (11)
_{ } (12)
Buyerda_{ }=(_{ }) –satr-vektor, A = (_{ }) (4) sistema koeffistientlari-dan tashkil topgan matritsa; _{ } va_{ }–ustun-vektorlar.
(4)-(7) masalani yig‘indilar yordamida ham ifodalash mumkin:
_{ } (13)
_{ } (14)
_{ } (15)