Muhammad Al-Xorazmiy nomdagi Toshkent Axborot-Texnologiyalari universiteti Algoritmlarni loyihalash fanidan

Chiziqli dasturlash masalasini yechishning grafik usuli
Faqat ikkita o’zgaruvchini o'z ichiga olgan chiziqli dasturlash masalalarni grafik usul bilan samarali hal qilish mumkin. Haqiqiy amaliyotda bunday muammolar kamdan-kam uchraydi. Keyinchalik, grafik usul yechimning rasmiy tavsifini ta'minlaydi va katta (CH.D.M)ni hal qilishda foydalaniladigan asosiy tushunchalarni kengroq o'rganadi.
Chiziqli dasturlash masalasining grafik usulda yechish ketma-ketligi
1-bosqich. Berilgan masalani chiziqli dasturlash masala sifatida shakllantirish.
2-bosqich. Berilgan ma’lumotlar asosida koordinatalar tekisligida x₁ va x₂ o’qlardan kesib o’tuvchi to’g’ri chiziqlarni aniqlab, sohalarni belgilab olamiz.
3-bosqich. Ajratilgan soha burchaklarida x₁ va x₂ nuqtalarni aniqlab, maqsad funksiyasiga qo’yamiz. Maqsad funksiya qiymatlaridan eng maqbulini(min yoki max) tanlab olamiz.

Misol 3.
Z = 2x + 3y maqsad funksiyasining maksimum qiymatini toping.
Chegaraviy shartlar quyidagicha berilgan:
x + y 30, y 3, 0 y 12, x - y 0, va 0 x 20.


Yechish
Birinchi navbatda koordinatalar sistemasida x 0, y 0 ekanligini belgilab olamiz.
Koordinatalar sistemasida x + y 30, y 3, y 12, x y va x 20, chegaralarni belgilab, ABCDE shaklni aniqlaymiz.
Shakl uchlaridagi nuqtalar A(3, 3), B (20, 3), C(20, 10), D(18, 12) va E(12, 12) bo’ladi.
Shakl uchlaridagi Z ning qiymatlari Z(A) = 15, Z(B) = 49, Z(C)= 70, Z(D)=72, va Z(E) = 60
D nuqtada Z maksimum qiymatga erishadi. Z(D)=72. Bu nuqtada x va y ning qiymatlari x = 18, y = 12 ga teng.

Masalaning berilishi:

15-

X	x1	x2	X3	X4	X5	X6	Xn
y1	8	3	4	7	1	0	352
y2	3	2	7	6	0	-1	276
y3	2	6	2	5	0	0	216
L	15	17	18	15	0	0	0

Masalaning Zeydel usuli yordamida yechilgan dasturi
#include
#include
using namespace std;
int main(){
int i,j,n;
double c,c1;
cout<<"Zeydel usulida hisoblash\nTenglamalar sonini kiriting\n n=";
cin>>n;
float a[n+1][n+1],b[n+1],x[n+1],x1[n+1],l[n+1],z=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
cout<<"a["<>a[i][j];
}
for(i=1;i<=n;i++)
{ cout<<"b["<>b[i];
}
cout<<"maqsad funksiyadagi noma`lumlarning oldidagi koeffitsiyentlarni kiriting.";
for(i=1;i<=n;i++)
{ cout<<"l["<>l[i]; }
for(i=1;i<=n;i++){
c=a[i][i];
for(j=1;j<=n;j++)
a[i][j]=a[i][j]/c;
b[i]=b[i]/c;
x[i]=b[i]; }
L1: for(i=1;i<=n;i++) a[i][i]=0;
for(i=1;i<=n;i++)
{ c1=0;
for(j=1;j<=n;j++) c1+=a[i][j]*x[j];
x1[i]=b[i]-c1; }
for(i=1;i<=n;i++)
if(fabs(x[i]-x1[i])>0.01) goto L2;
goto L3;
L2: for(i=1;i<=n;i++) x[i]=x1[i];
goto L1;
L3: cout<<"tenglamalar sistemasining yechimlari\n";
for(i=1;i<=n-1;i++){ cout< z+=l[i]*x[i];}
cout<<"maqsad funksiya="< return 0; }