Optimallashtirish masalasi va uning matematik modeli

Chiziqli programmalash masalasining matematik modeli
Chiziqli dasturlash matematik dasturlashning asosiy qismlaridan biri bo‘lib, ko‘p o‘zgaruvchlii funksiyalarning ekstremumlarini topishni o‘rganadi va iqtisodiy-matematik modellarni tekshirishda matematik apparat bo‘lib hisoblanadi.
Ko‘p o‘zgaruvchlii funksiyaning minimum yoki maksimumi izlanayotganda o‘zgaruvchilarga ko‘p cheklanishlar qo‘yiladi. Bu cheklanishlarning har xil turlariga qarab chiziqli programalash masalasi uch xil ko‘rinishda yoziladi: simmetrik, kanonik va standart. Chiziqli programmalash masalasining qo‘yidagi ixtiyoriy shaklda yozilgan matematik modelini qaraymiz.
Matematik model qo‘yidagicha talqin qilanadi: Tenglamalar yoki tengsizliklar sistemasini qanoatlantiruvchi o‘zgaruvchilarining shunday manfiy bo‘lmagan qiymatlarini topish talab qilinadiki, bunda o‘zgaruvchilarning chiziqli funksiyasi bo‘lgan miqdor (maqsad funksiyasi) eng katta (eng kichik) qiymatga ega bo‘lsin (erishsin).
Ushbu matematik modelni vektor ko‘rinishida quyidagicha yozish mumkin
Agar maqsad funksiyasi iqtisodiy faktorlarni ifodalasa, u holda funksiyaning maksimum qiymati izlanadi, aks holda minimumni izlash kerak bo‘ladi.
1-ta’rif. Cheklanishlar sistemasini qanoatlantiruvchi xar qanday yechimlar to‘plami mumkin bo‘lgan yechimlar to‘plami deyiladi.
2-ta’rif. Maqsad funksiyasiga maksimal (yoki minimal) qiymat beruvchi mumkin bo‘lgan yechim masalaning optimal deyiladi.
Masalaning cheklanishlarini sharti tengsizlik bo‘lib maqsad funksiyasining maksimum yoki minimumini topish ko‘rinishi standart chiziqli dasturlash masalasi deyiladi.
U holda bunday masalaga kanonik ko‘rinishda berilgan chiziqli dasturlash masalasi deyiladi.
Chiziqli dasturlash masalasi yechimlarining xususiyatlari
 
Chiziqli dasturlash masalalari xususmiyatlarini bayon etishdan oldin qavariq to‘plamlar va qavariq funksiyaalar tushunchalariga to‘xtalib o‘tamiz.
1-ta’rif. n o‘lchovli fazoda berilgan X to‘plam ixtiyoriy x1 va x2 nuqta bilan birga shu nuqtalarni birlashtiruvchi kesmani ham o‘z ichida saqlasa, unga qavariq to‘plam deyiladi.