Chiziqli programmalashtirish masalasini kanonik shakllari

Chiziqli programmalashtirish masalasini kanonik shakllari

Amaliyotning koʻpgina sohalarida optimallash masalalari echilib, quyidagi xossalarga ega boʻlishi mumkin:

Samaradorlik koʻrsatkichi (maqsad funksiyasi) F oʻzgaruvchilarga nisbatan chiziqli munosabatda boʻladi.
(1.2.1)
Shuningdek, chegaraviy shartdagi oʻzgaruvchilar ham chiziqli munosabatda boʻladi.
(1.2.2)
n-oʻzgaruvchlar soni, m-tenglamalar soni.
Chiziqli programmalashtirish masalasining qoʻyilishi quyidagichadir: Oʻzgaruvchilar qatori larning shunday nomanfiy echimlari topilsinki, , u ikkinchi shartni qanoatlantirib, maqsad funksiyasini (1.2.1-formula) maksimum yoki minimumga erishtirsin.
Agarda oʻzgaruvchilar 2-shartni bajarsa, bunday echim mumkin boʻlgan echimlar deyiladi. bu echimlar 1-shartni ham qanoatlantirsa, bunday echim optimal echim deyiladi.
Chiziqli programmalashtirish masalasi 3 xil koʻrinishda ifodalash mumkin boʻladi.

1. 
   Standart (≤). Bunda chegaraviy shartlar tengsizliklar sistemasi shaklida boʻladi.
   
2. 
   Kanonik (=, F→min). Bunda chegaraviy shartlar tenglamalar sistemasi shaklida boʻladi.
   
3. 
   Umumiy (≥). Bunda chegaraviy shartlar tenglamani va tengsizliklardan iborat boʻladi.
   

Matematikadan ma’lumki, tenglamalar sistemasini echimini topish qulay. SHuning uchun asosan optimallash masalasi kanonik koʻrinishga keltiriladi.
Chiziqli programmalashtirish masalasini echishda tengsizliklar sistemasi asosan kononik koʻrinishga keltiriladi. Agarda chegaraviy shart standart koʻrinishda berilsa, qoʻshimcha oʻzgaruvchilar kiritilib, kanonik koʻrinishga keltiriladi.
=>
standart koʻrinish kanonik koʻrinish
Agar F→min oʻrniga F→min boʻlsa,u holda F→max “-1” ga koʻpaytiriladi. Agarda tengsizlik koʻrinishda boʻlsa,qoʻshimcha oʻzgartirish kiritiladi. Umumiy koʻrinishdan kononik koʻrinishga oʻtish quyidagicha amalga oshiriladi:
=>
Bu tenglamalar sistemasining echimi umumiy echim deyiladi. Uning xususiy echimini topish uchun yangi kiritilgan oʻzgaruvchilarga nisbatan tenglamalar sistemasi tuziladi.
=>
Bu erda - erkin oʻzgaruvchilar, - bazis oʻzgaruvchilar.
Bazis echimlarni topish uchun erkin oʻzgaruvchilarga nol (0) qiymat beriladi va bazis echim topiladi.
Tenglamalar sistemasi echimining turli usullari mavjud. Ulardan keng tarqalgani oʻzgaruvchilarni yoʻqotish usuli.

1. 
   Oʻzgaruvchilarni ketma-ket yoʻqotish usuli (Gauss usuli).
   
2. 
   Oʻzgaruvchilarni toʻliq yoʻqotish usuli (Gauss – Jordano usuli) va xakozo.