Chiziqli dasturlash masalalarida qoʻllaniladigan modellar. Chiziqli dasturlash masalalarining umumiy qo'yilishi

Ko’rsatma
Berilgan chiziqli dasturlash masalasini grafik usulda yeching.
x₁ + 2x₂ = 3; x₁ - x₂ = 2; x₁ =0; x₂=0; Y = 2x₁ + 2x_2.
Yechish. Echimlar ko’pburchagini hsil qilamiz. Uning uchun koordinatalar sistemasida
x₁ + 2x₂ = 3, x₁ - x₂ = 2, x₁ =0, x₂=0
to’g`i chiziqlarni yasaymiz:

SHakldan ko’rinadiki, echimlar ko’pburchagi yuqoridan chegaralanmagan. Koordinata boshidan N(2;2) vektorni yasaymiz va unga perpendikulyar bo’lgan to’g`i chiziq o’tkazamiz. Bu chiziq 2x₁ + 2x₂=const tenglama orqali ifodalanadi. SHakldan ko’rinadiki, masalada maqsad funktsiyaning maksimum qiymati yuqoridan chegaralanmagan ekan.


Chiziqli dasturlash masalalarini yechish metodlari.
Mathcadda chiziqli dasturlash masalasi yechishda maximize va minimize funksiyalaridan foydalanish mumkin. Bu funksiyalar umumiy holda quyidagi ko‘rinishda yoziladi:
Maximize(F,)
Minimize(F,)
Mathcadda chiziqli dasturlash masalasini yechish quyidagicha bajariladi (1-rasm):
1.Mathcadni ishga tushurgandan so‘ng, maqsad funksiyasi yoziladi, masalan f(x,y)= va o‘zgaruvchilarning boshlang‘ich qiymati kiritiladi.
2.Given kalit so‘zi yoziladi.
3.Tengsizliklar tizimi va cheklanishlar kiritiladi.
4.Biror o‘zgaruvchiga maximize yoki inimize funksiyasi yuboriladi.
5.Shu o‘zgaruvchi yozilib tenglik kiritiladi. Natija vektor ko‘rinishida hosil bo‘ladi.
6.Maqsad funksiyasi qiymatini hisoblash uchun, masalan f(p0,p1) yozilib tenglik belgisi kiritiladi.
Keltirilgan tartibda quyidagi modelni yechimini aniqlanshni ko’ramiz:
1) Maqsad funksiyasi:
x1+x2+x3+x4+x5min
2) Chegaraviy shartlar:
x1+x2≥80
x1+2x3+x4≥120
x2+x4+3x5≥102
3) Noma’lumlarni nomanfiylik shartlari
x1≥0 x2≥0 x3≥0 x4≥0 x5≥0
Bu modelni MathCAD oynasiga quyidagi ko’rinishda yozib yechish mumkin:
x1:=1 x2:=0 x3:=0 x4:=0 x5:=0
F(x1,x2,x3,x4,x5):= x1+x2+x3+x4+x5

Given

x1+x2≥80
x1+2x3+x4≥120
x2+x4+3x5≥102
x1≥0 x2≥0 x3≥0 x4≥0 x5≥0
P:=Minimize(F, x1,x2,x3,x4,x5)
Yechim:

Bu yerda F funksiya argumentlariga topilgan P ning qiymatlarini qo'yib maqsad funksiya qiymati hisoblangan.MatLABda linprog funksiyasi chiziqli dasturlash masalasini yechish imkonini beradi.

Funksya quyidagi shakllardan birida yoziladi:
х = linprog(f,A,b,Aeq,beq)
х = linprog(f,A,b,Aeq,beq,lb,ub)
х = linprog(f,A,b,Aeq,beq,lb,ub,x0)
х = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval] = linprog(...)
[x,fval,exitflag] = linprog(...)
[x,fval,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)
Buyerda f – maqsad funksiyaning koeffitsiyentlaridan tuzilgan matritsa, x – noma’lum vektor o’zgaruvchi, fval – maqsad funksiya qiymati, exitflag,output,lambda hisoblashlarni yakunlanishi xaqida qo’shimcha ma’lumotlar. A matritsa va b vektor kichik yoki teng belgisi bilan berilgan (А*x<=b) chegaraviy shartlardagi koeffitsentlar va ozod xadlardan tuzilgan matritsa va vektordir. Aeq matritsa, beq vector esa faqat teng belgisi bilan berilgan (Aeq*x=beq) chegaraviy shartlardagi koeffitsentlar va ozod xadlardan tuzilgan matritsa va vektordir. lb, ub vektor parametrlar x vektor o’zgaruvchning mumkin bo’lgan eng katta va eng kichik qiymatlaridir (lb<=x<=ub). x0 – boshlangich qiymat.
Agar chegaraviy shartlar katta yoki teng belgisi bilan, maqsad funksiya maksimum sharti bilan berilgan bo’lsa ularni (-1)ga kopaytirib talab etilgan ko’rinishga keltirilib olinadi.
1-Misol.
f(х) = - 5 x₁ – 4 x₂ – 6 x₃ -min
х₁ - х₂ + х₃ ≤ 20 ,
3 x₁ + 2 x₂ + 4 x₃ ≤ 42
3 x₁ + 2 x₂ ≤ 42
0 ≤ x₁ , 0 ≤ x₂ , 0 ≤ x₃.
Bu masala matlabda quyidagicha yechiladi:
>> f = [ -5, -4, -6];
>> A = [1 -1 1; 3 2 4; 3 2 0];
>> b = [20; 42; 30];
>> lb = zeros(3,1);
>> [x, fval,] = linprog(f, A, b, [ ], [ ], lb)
Natija quyidagicha chiqadi:
x =
0.0000
15.0000
3.0000
fval =
-78.0000
2-Misol
f(x₁,x₂,x₃) = 40 x₁ + 30 x₂ + 20 x₃ -max
Chegaraviy shartlar
4 x₁ + 3,4 x₂ + 2 x₃ ≤ 340
4,75 x₁ + 11 x₂ + 2 x₃ ≤ 700
x₁ + x₂ + x₃ = 100
x₁ ≥ 20, x₂ ≥ 20, x₃ ≥ 20
Bu masala matlabda quyidagicha yechiladi:
>>f=[40;30;20];
>>A=[4 3.4 2; 4.75 11 2];
>>b=[340;700];
>>Aeq=[1 1 1];
>>beq=[100];
>>lb=[20;20;20];
>> [x,fval]=linprog(-f,A,b,Aeq,beq,lb)
Natija quyidagicha chiqadi:
x =
56.0000
20.0000
24.0000
fval =
-3.3200e+003