Axborot texnologiyalari universiteti samarqand filiali kompyuter injiniring fakulteti

3. Shartli optimallashtirish usullari
Chiziqli dasturlash
Chiziqli dasturlash deganda chiziqli tenglik va tengsizliklar sistemasi bilan aniqlangan to‘plamlardagi chiziqli funksiyalarni muammolar va minimallashtirish (yoki maksimallashtirish) masalalarini o‘rganuvchi ekstremal muammolar nazariyasining bo‘limi tushuniladi. Umumiy holatda chiziqli dasturlash masalasi quyidagicha tuzilgan. Chiziqli shaklning maksimal (minimal) ni aniqlovchi x* (x*1, ..., x*n) vektorini toping.
f(x)  с₁x₁ + с₂x₂+...+с_nx_n
cheklovlar bilan:
a₁₁x₁ + … a_1nx_n   b₁;
. . . . . . . . . . . . . . . . . . .
a_m1x₁ + … a_mnx_n   b_m;
a_m+1x₁+… a_m+1,nx_n   b_m+1;
. . . . . . . . . . . . . . . . . . .
a_kx₁ + … a_knx_n   b_m;
a_k+1 x₁ + … a_k+1nx_n   b_m;
 
a_m+1x₁ + … a_m+1,nx_n   b_m+1;
. . . . . . . . . . . . . . . . . .
a_lx₁ + … a_lnx_n   b_l;
x_i   0; i   1, …, n.
Tengsizlik shartlarining har biri giper tekislik bilan chegaralangan yarim fazoni belgilaydi. Yarim bo'shliqlarning kesishishi qavariq n o'lchovli politop Q ni hosil qiladi. Tenglik shartlari n o'lchovli fazodan (n-l) o'lchovli tekislikni ajratib turadi, uning Q sohasi bilan kesishishi qavariq (n-l)-ni beradi. o'lchovli politop G. Chiziqli shaklning ekstremal qiymati (agar u mavjud bo'lsa) ko'pburchakning ba'zi bir cho'qqilarida erishiladi. Degeneratsiya ostida unga ko'pburchakning chekkasi yoki yuzining barcha nuqtalarida erishish mumkin. Yuqoridagilarni hisobga olgan holda, chiziqli dasturlash muammosini hal qilish uchun ko'pburchakning uchlaridagi funktsiya qiymatlarini hisoblash va bu qiymatlar orasida eng katta yoki eng kichikni topish nazariy jihatdan etarli. Biroq, amaliy masalalarda G mintaqasidagi cho'qqilar soni shunchalik kattaki, ularni kompyuter yordamida ham ko'rish mumkin emas. Shuning uchun chiziqli dasturlash masalalarini yechishning maxsus sonli usullari ishlab chiqilgan bo'lib, ular asosan ikki shakldagi masalalarni yozishdan iborat [3].