Ii bob. Simpleks usuli va uning dasturiy ta’minoti chiziqli programmalash va simpleks usuli

a₁₁x₁ + a₁₂x₂ + a₁₃ x₃  b₁ ,

a₂₁x₁ + a₂₂x₂ + a₂₃ x₃  b₂ , (2.3.1)

a₃₁x₁ + a₃₂x₂ + a₃₃ x₃  b₃ ,

х_{1 , 2 ,3}  0

Ushbu tengsizliklar sistemasini tenglamalar sistemasiga keltirish uchun qo’shimcha o’zgaruvchilar kiritganda so’ng u quyidagi ko’rinishga ega bo’ladi:

a₁₁x₁ + a₁₂x₂ + a₁₃ x₃ + y₁ = b₁ ,

a₂₁x₁ + a₂₂x₂ +a₂₃ x₃ + y₂ = b₂ ,

a₃₁x₁ + a₃₂x₂ + a₃₃ x₃ + y₃ = b₃ . (2.3.2)

Z_mах = c₁x₁+c₂x₂+ c₃ x₃ +c₄ y₁+c₅ y₂+ c₆ y₃ =

=c₁x₁+c₂x₂+ c₃ x₃ +0y₁+0y₂+0y₃ .
Endi (2.3.2) da berilganlarni simpleks jadvalga joylashtirsak, u quyidagi ko’rinishga keladi :

2.3.1-jadval

Bazis o’zgaruv-chilar	Cj	Bi	х1	х2	x3
			с1	с2	c3
Y1	С4	b1	a11	a12	a13
Y2	с 5	b2	a21	a22	a23
Y3	С6	b3	a31	a32	a33
Zj - Cj		0	- с1	- с2	- сn

Ana shu jadvalni biz DELPHI formasida yaratamiz. Buning uchun Delphining Additional komponentlar palitrasidagi Stringgrid komponentasidan foydalanamiz. Dasturda ishlayotganda o’zgaruvchilar o’rnida aniq sonlar qo’yiladi. Shuning uchun quyidagi misolni qaraymiz.

Z_mах =x₁+2x₂+ 3x₃

x₁ + 2x₂ + 3 x₃  14 ,

2x₁ + 2x₂ +3 x₃  21 , (2.3.3)

x₁ + x₂ + 2 x₃  22,

х_{1 , 2 ,3}  0

Endi Delphi ekranida shu tenglamalar sistemasi va 2.3.1-jadvaldan foydalanib jadval hosil qilamiz. Buning uchun Stringgrid komponentasi yordamida jadval tashlab, unda 7 ta ustun, 6 ta satr hosil qilamiz.

2.3.1-chizma. Stringrid jadvalini formaga tashlash.

Ma’lumki, simpleks usulida bir necha jadvallar hosil qilinadi. Biz hozir 1-chi jadvaldan ishni boshlayapmiz. Endi 2.3.1-jadvaldagi ko’rinishni ushbu jadvalda hosil qilamiz. Buning uchun jadval kataklariga kerakli so’zlarni kiritib, sonlarni kiritish uchun quyidagi dastur qismini yozamiz:

BAZIS[1]:='Y1';BAZIS[2]:='Y2';BAZIS[3]:='Y3';XB[1]:='X[1]'; XB[2]:='X[2]';XB[3]:='X[3]'; FOR I:=1 TO 3 D BEGIN

STRINGGRID1.Cells[0,1+I]:=BAZIS[I];STRINGGRID1.Cells[2+I,0]:=XB[I]; END; STRINGGRID1.Cells[6,0]:='B[I]/A[I,J]';

STRINGGRID1.Cells[0,0]:='BAZIS'; STRINGGRID1.Cells[1,0]:='C[J]';

STRINGGRID1.Cells[2,0]:='B[J]';STRINGGRID2.Cells[6,0]:='B[I]/A[I,J]';

STRINGGRID2.Cells[0,0]:='BAZIS'; STRINGGRID2.Cells[1,0]:='C[J]';

STRINGGRID2.Cells[2,0]:='B[J]';X[1]:='1';X[2]:='2';X[3]:='3'; C[1]:='0';C[2]:='0'; C[3]:='0'; B[1]:=14; B[2]:=21; B[3]:=22;

FOR I:=1 TO 3 DO BEGIN

STRINGGRID1.Cells[2+I,1]:=X[I];STRINGGRID1.Cells[1,1+I]:=C[I];

STRINGGRID1.Cells[2,1+I]:=FLOATTOSTR(B[I]); END;

A[0,0]:=B[1];A[1,0]:=1; A[2,0]:=2; A[3,0]:=3;

A[0,1]:=B[2];A[1,1]:=2; A[2,1]:=2; A[3,1]:=5;

A[0,2]:=B[3];A[1,2]:=1; A[2,2]:=1; A[3,2]:=2;A[0,3]:=0;

A[1,3]:=-STRTOFLOAT(X[1]);A[2,3]:=-STRTOFLOAT(X[2]);A[3,3]:=-STRTOFLOAT(X[3]);

FOR I:=0 TO 3 DO FOR J:=0 TO 3 DO

STRINGGRID1.Cells[2+J,2+I]:=FLOATTOSTR(A[J,I]);

Ushbu dastur qismi ishlaganda 2.3.1-chizmadagi chizma quyidagi ko’rinishni oladi:

2.3.2-chizma. Jadval ma’lumotlar bilan to’ldirilgan hol.

Bu yerda biz bir va ikki o’lchovli massivlardan foydalandik. Simpleks usulining algoritmi bo’yicha oxirgi, maqsad satrini qaraymiz. Jadval ana shu satrda manfiy element qolmaguncha qayta hisoblab boriladi. Maqsad satr, ya’ni jadvaldagi oxirgi satrdan absolyut qiymati bo’yicha eng kattasini topishimiz kerak. Bizning misolda bu -3, ya’ni x[3] satri. Bu bilan biz hal qiluvchi satrni topgan bo’lamiz. Buning uchun quyidagi dastur qismini yozamiz:

ShowMessagePos('HAL QILUVCHI USTUNNI TOPISH', 600,500);

P:=0; J_USTUN:=0; FOR I:=1 TO 3 DO

IF P>A[I,3] THEN BEGIN P:=A[I,3];J_USTUN:=I; END;

MEMO1.Lines.Add('HAL QILUVCHI USTUN');

MEMO1.Lines.Add(FLOATTOSTR(P)+' '+INTTOSTR(J_USTUN));

Bu dastur qismi yordamida hal qiluvchi ustun nomeri aniqlanadi. Keyingi ish bu hal qiluvchi satrni topish. Buning uchun tenglamalar sistemasidagi ozod hadlar ustunidagi sonlar hal qiluvchi ustun elementlariga bo’linib chiqilib, B[i]/A[I,j] sarlavhali ustunga yoziladi. Ana shu ishlar uchun yozilgan dastur qismi quyidagicha:

ShowMessagePos('HAL QILUVCHI SATRNI TOPISH', 600,500);

//satr:=inputbox('A','B','HAL QILUVCHI SATRNI TOPISH');

FOR J:=0 TO 2 DO BEGIN

Stringgrid1.Cells[6,2+J]:=FLOATTOSTRF(A[0,J]/A[J_USTUN,J],ffFixed,5,2);

FOR I:=1 TO 2 DO

IF ABS(P)>ABS(BA[I]) THEN BEGIN P:=BA[I];J_SATR:=I; END;

Topilgan qiymatlar jadvalga yoziladi. Bu holdagi jadval ko’rinishi quyidagicha:

2.3.3-chizma. Hal qiluvchi satr va hal qiluvchi elementni aniqlash.

Ushbu chizmadan ko’rinadiki, hal qiluvchi satr 4,20 soni turgan satr va hal qiluvchi element 5, ya’ni hal qiluvchi ustun va hal qiluvchi satr kesishgan katakdagi son.

Algoritm bo’yicha keyingi ish hal qiluvchi satrdagi elementlar hal qiluvchi elementga bo’lib chiqiladi, hal qiluvchi ustun elementlar esa 0 bilan to’ldiriladi. Ushbu ishlarni bajarish uchun dastur qismi quyidagicha:

BUFER:=X[J_USTUN];C[J_SATR+1]:=BUFER; BUFER:=XB[J_USTUN];

XB[J_USTUN]:=BAZIS[J_SATR+1]; BAZIS[J_SATR+1]:=BUFER;

FOR I:=1 TO 3 DO BEGIN

STRINGGRID2.Cells[0,1+I]:=BAZIS[I]; STRINGGRID2.Cells[2+I,0]:=XB[I];

STRINGGRID2.Cells[1,1+I]:=C[I];

Bu ishlar endi keying 2-jadvalda bajariladi. Bu yerda hal qiluvchi ustundagi x[3] basis ustunidagi Y2 bilan almashtiriladi. Jadvalning qolgan elementlari Jordan-Gauss almashtirishi bilan topiladi. Jordan-Gauss almashtirish formulasi quyidagi ko’rinishga ega:

(2.3.4)

Ushbu formulalar bilan qiymatlarni hisoblash uchun quyidagi dastur qismini yozamiz:

FOR R:=0 TO 3 DO BEGIN FOR K:=0 TO 3 DO BEGIN

IF SITA[ITA]<>K THEN BEGIN IF J_SATR<>R THEN BEGIN

B1[R,K]:=(A[R,K]*A[J_SATR,J_USTUN]-A[R,J_USTUN]*A[J_SATR,K])/A[J_SATR,J_USTUN];

END; end; end;

Dastur bajarilib, qiymatlar jadvalga yozilgandan so’ng hosil bo’lgan ko’rinish quyidagicha:

2.3.4-chizma. 2-jadval elementlar bilan to’ldirilgan hol.

Endi 2.3.4-chizmadagi jadvalning maqsad, ya’ni oxirgi satriga qarasak, bitta manfiy element qolgan. Demak yana jadval almashtirishini bajarishimiz kerak. Buning uchun 2-jadvaldan foydalanib hal qiluvchi ustunni aniqlaymiz. Bu ustun x[2] ustuni ekani ko’rinib turibdi, lekin uni dasturda ham aniqlaymiz. So’ng B[J] ustunidagi elementlarni shu hal qiluvchi ustun elementlariga ketma-ket bo’lib chiqamiz. Bo’lib chiqish natijalari 2.3.4-chizmada ko’rsatilgan. Jadvaldan ko’rinadiki, hal qiluvchi satr bu 1,75 soni turgan satr, buni dastur orqali ham aniqlaymiz. Demak, hal qiluvchi element bu 0,80. Demak,ushbu ustunni 0 bilan to’ldirib, satr elementlarini esa hal qiluvchi elementga bo’lib chiqamiz. Hal qiluvchi ustun sarlavhasi X[2] ni hal qiluvchi satr sarlavhasi Y1 bilan almashtiramiz. Jadvalning qolgan elementlarini Jordan-Gauss chiqarish algoritmi orqali hisoblaymiz. Ushbu barcha o’zgarishlarni endi 3-jadvalga joylashtiramiz. Agar barcha ishlarni bajarsak, 3-jadval quyidagicha bo’ladi:

2.3.5-chizma. 3-jadval elementlari to’ldirilgan hol.

Endi ushbu jadval maqsad satriga qarasak, manfiy elementlar qolmagan. Demak optimal echim topilgan, uning qiymati 14 ga teng. Buni C[J] ustunidagi elementlarni B[J] ustunidagi elementlarga ko’paytirib qo’shib chiqsak ham, shu son chiqishidan ko’rishimiz mumkin:

2*1,75+3*3,50=3,5+10,5=14.

Sunday qilib, optimal echim topildi. Optimal echimni topishda biz 3 ta jadval hosil qildik. Demak, biz Delphi formasiga 3 ta Stringgrid jadvalini tashlar ekanmiz. Undan tashqari sarlavhalarni yozish uchun Label komponentasidan foydalanamiz. Birinchi jadvalda asosan boshlang'ich ma'l’motlar’yoziladi. Ularni tahrirlash imkoniyatini berish uchun StringGrid1 komponentasining Properties xossasi Options bo’limini aktivlashtirib, Goediting satridagi FALSE so’zini TRUE so’zi bilan almashtiramiz.

Ushbu ishdan talabalarga “Iqtisodiy-matematik usullar” va “Jarayonlar tadqiqoti” fanlarini o’tishda ko’rgazmali vosita sifatida foydalanish mumkin. Talabalarga tushunarli bo’lishi uchun ana shu 3 ta jadvalni bitta ekranda joylashtiramiz. Bunda 1-jadvalda boshlang’ich ma’lumotlar joylashtirilgan va hal qiluvchi ustun va hal qiluvchi satr topilgan. 2-jadvalda endi hal qiluvchi ustun 0 va 1 lar bilan to’ldirilgan. Bunday Delphi muhiti endi quyidagi ko’rinishlarni oladi:

2.3.6-chizma. StringGrid jadval xossalarini o’zgartirish.

2.3.7-chizma. Barcha jadvallarni bitta ekran boylab joylashtirish.

Tuzilgan dastur grafik interfeysi talabalarga tushunarli bo’lishi uchun bitta ekranda bir necha jadvallar hosil qilindi. Ajratilgan ustun, satr ko’zga tezda tashlanishi uchun ularni ranglash effektidan ham foydalanish mumkin.

2-bob bo’yicha xulosa qilib shuni aytish mumkinki, simpleks usuli algoritmi juda qiziq va dasturlashning umumiy tomonlarini qamrab olgan ekan. Ushbu algorotm bo’yicha dastur tuzib men shunga amin bo’ldim.

Xulosa
Ilmiy tadqiqotlarda modellashtirish, ayniqsa matematik modellashtirish katta ahamiyat kasb etadi. Bunda ayniqsa iqtisodiy masalalar ko’rilayotgan bo’lsa, regressiyali- korrelyatsiyali tahlil qilish uchun jarayon matematik modelni tuzish kerak bo’ladi. Buning uchun matematik modellashtirish bosqichlarini bilish kerak.

Matematik modellashtirish unsurlaridan bo’lgan chiziqli programmalash masalasi birinchi navbatda iqtisodiy masalalarda, resurslar taqsimoti va ulardan foydalanishning optimal usullarini izlashda yuzaga keldi. Bunday masalalarda o‘zgaruvchilar soni juda ko‘p bo‘lishini e’tiborga olish zarur. Shuning uchun ham ularni yechish algoritmlarini zamonaviy hisoblash texnikasisiz amalga oshirish qiyin. Chiziqli programmalashtirish masalalarini yechishda EHM larning qo‘llanilishi iqtisodda matematik usullarni qo‘llash uchun keng imkoniyat yaratdi.

Ana shularni hisobga olib va dars jarayonida talabalarga tushunarli bo’lishi uchun ushbu bitiruv-malakaviy ishida chiziqli dasturlash masalasini simpleks usulida echishning qulay foydalanuvchi grafik interfeysiga ega dasturi ishlab chiqildi.

Ushbu malakaviy bitiruv ishida qo’yilgan vazifalarni bajarish mobaynida men avvalo shu mavzuga oid bir qancha yangi adabiyotlar bilan tanishdim. Ayniqsa yaqindagina Respublika miqyosida Toshkent shahridagi ''Turon-Iqbol'' bosmaxonasida chop etilgan Buxoro muxandislik texologiyasi instituti Informatika va AT kafedrasi professori SH. R. Muminovning ''Matematik modellar va usullar'' o’quv qo’llanmasi menda yaxshi taasurot qoldirdi. Qo’llanmada mavzular ketma-ketligi ravon, qariyb har bir mavzudagi materillar bo’yicha EXCEL elektron jadvalida yoki Paskal tilida dasturlar keltirilgan. Ushbu qo’llanmaning Respublika tanlovida g’olib bo’lgani ham bejiz emas ekan.

Shuningdek Internetdan olingan Eshmatov M. Raisov, J.K. Karimov, L. Turayeva, X.N. Karimovlarning matematik modellashtirish va chiziqli programmalashtirish bo’yicha uslubiy qo’llanmasidan ham foydalandim. Buning uchun ularga minnatdorchilik bildiraman.

Matematik modellashtirish yordamida dasturlarni ishlab chiqishning ahamiyati beqiyos ekanini bulib oldim, binobarin, hisoblash tajribalari faqat tabiiy va texnik fanlarning hamma sohalari bo’yicha yangi bilimlar olishni quvvatli vositasi bo’lib qolmasdan balki iqtisod, sotsiologiya, siyosat, harbiy ishda, ishlab chiqarishni rivojlantirishda va yangi texnikadan foydalanishni takomllashtirishda ham zaruriy shart bo’lib hisoblanadi.

Har qanday tajribaning asosiy bosqichlaridan biri tajriba ma`lumotlarini qayta ishlashdir. Bu bosqichda o’rganilayotgan ob`ekt yoki hodisaning matematik modeli yaratiladi.

Ushbu bitiruv malakaviy ishida matematk modellashtirish bo’limlaridan biri bo’lgan chiziqli dasturlash masalasini simpleks usulda echishning nazariy asoslari o’rganib chiqildi, bu usulga asoslanib algoritm va dastur tuzildi, Delphi muhitida chiziqli dasturlash masalasini simpleks usulda echishning interfaol usulda grafik rejimdagi ko’rinishi yaratildi.

Ushbu ishda ana shu ketma-ketlikning asosiy bosqichlari keltirilgan. Ulardan iqtisodiy masalalarni echishda, oily ta’lim muassasalarida ''Matematik modellashtirish '' kurslari mavzularini o’tishda foydalanish mumkin.

Ushbu ishlarni bajarish jarayonida men matematik modellar qurishni, chiziqli dasturlash masalasini simpleks usulda echishning yo’llarini, dasturda ishlatiladigan asosiy strukturalarni yanada yaxshi o’zlashtirib oldim. Olgan bilimlarimni kelajak hayotimda albatta qo’llayman. Bitiruv malakaviy ishini bajarish jarayonida to’plangan materiallardan maktabda, litsey yoki kollejda o’z mehnat faoliyatimda albatta foydalanaman.

Foydalanilgan adabiyotlar to’plami

1. 
   Ковалев М.Я. Примеры решения типичных задач по курсу « Исследований операций ». Минск 2004. 284 с.
   
2. 
   Ne’matov A. Va b. “Matematik dasturlash va optimallash usullari”. Uslubiy qo’llanma. T.: TTYESI bosmaxonasi, 2008. 98 b.
   
3. 
   Е.С. Ванцель Исследование операции. М., Знание, 1976 г. 64с.
   
4. 
   В.В. Морозов, А.Г. Сухарев, В.В. Федоров. Исследований операции в задачах и упражнениях. М.,Высшая школа, 1986 г. 400с.
   
5. 
   Вагнер Г. Основы исследований операции. Т. 1–3. М.: Мир. 1972-73. 345 c.
   
6. 
   Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 185 c.
   
7. 
   Таха Х. Введение в исследование операций. Т. 1, 2. М.: Мир. 1981. 235 c.
   
8. 
   Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. Учебное пособие для студентов вузов, обучающиеся по специальности»Прикладная математика» . М.: «Наука»,190 с.
   
9. 
   Nazirov Sh.A., Musayev M.M. va b. Delphi tilida dasturlash asoslari. O’quv qo’llanma. Toshkent-2008. 277 bet.
   
10. 
    Самарский А.А., Михайлов А.П. Математическое моделирование. Идеи. Методы. Примеры. –М.: ФИЗМАТЛИТ, 2005, -280 стр.
    
11. 
    Жалолов О.И., Хаятов Х.У., Жалолов Ф.И. Delphi муҳитида дастурлаш. Ўқув-услубий қўлланма. Бухоро.:”Бухоро-Тур-Ризо”, 2008. 154 б.