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

MatLab dasturida optimallashtiruvchi modellarni yechish
MatLabda optimallashtiruvchi modellarni yechish uchun modelni matritsaviy ko'rinishda yozib olish kerak. 3.1-paragrafda berilgan masalani MatLabda yechish uchun uning modelini matritsaviy ko'rinishini yozamiz. Chegaralovchi shartlarning matritsasini tuzishda noma'lumlar soni 4×5=20 va tenglamalar soni 4+5=9 ekanligiga etibor berish kerak, Demak, chegaralovchi shartlarning matritsasi 9×20 o'lchovli matritsadir. Modelda c_ij va x_ij i=1,2,3,4, j=1,2,3,4,5 larni bir indeksli ko'rinishda (c_i va x_i i=1,2,. . .,20) yozilsa matritsani tuzish tushinarliroq bo'ladi. Buning uchun oldin masala uchun belgilashlarni quyidagi jadvalda keltiramiz.

bj ai

b1

b2

b3

b4

b5

a1

x1

x2

x3

x4

x5

c1

c2

c3

c4

c5

a2

x6

x7

x8

x9

x10

c6

c7

c8

c9

c10

a3

x11

x12

x13

x14

x15

c11

c12

c13

c14

c15

a4

x16

x17

x18

x19

x20

c16

c17

c18

c19

c20

Bu yerda indeksdagi 10, 11, . . .,20 lar bitta sonlar, ular 2 raqam emas. Shu belgilashlarga ko'ra chegaraviy shatlar quyidagicha yoziladi:
x₁+ x₂ + x₃ + x₄ + x₅ =100 x₃+ x₈ + x₁₃ + x₁₈ =100
x₆+ x₇ + x₈ + x₉ + x₁₀ =250 x₄+ x₉ + x₁₄ + x₁₉=100
x₁₁+ x₁₂ + x₁₃ + x₁₄ + x₁₅ =200 x₅+ x₁₀ + x₁₅ + x₂₀ =250
x₁₆+ x₁₇ + x₁₈ + x₁₉ + x₂₀ =300 x₁ ≥ 0, x₂ ≥0, . . ., x₂₀ ≥ 0,
x₁+ x₆ + x₁₁ + x₁₆ =200
Maqsad funksiya esa masalada berilgan qiymatlar bo'yicha quyidagicha yoziladi:
10x₁+7 x₂ + 4x₃ + x₄ + 4x₅ +2x₆+ 7x₇ +10 x₈ +6 x₉ +11 x₁₀ +
8x₁₁+ 5x₁₂ + 3x₁₃ + 2x₁₄ + 2x₁₅ +11x₁₆+ 8x₁₇ + 12x₁₈ +16 x₁₉ + 13x₂₀ →min
Model koeffitsiyentlarini quyidagi jadvalga joylashtiramiz

Chegaraviy shartlarning matritsasi A																				B
1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0		100
0	0	0	0	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0		250
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	0	0	0	0	0		200
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1		300
1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0		200
0	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0	0		200
0	0	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0		100
0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0		100
0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1		250
Maqsad funksiya koeffitsiyentlari vektori C
10	7	4	1	4	2	7	10	6	11	8	5	3	2	2	11	8	12	16	13

MatLabda linprog funksiyasining х = linprog(f,A,b,Aeq,beq,lb,ub) yozilishidan foydalanamiz. Bu yerda f maqsad funksiya koeffitsiyentlari, A va B bizning misolda mavjud emas, chunki ular kichik belgisi bilan yozilgan shartlar matritsasi. Ular o'niga bo'sh matritsa - ochilgan va yopilgan kvadrat qavslar [ ] ni yozamiz. Aeq, beq lar teng belgisi bilan yozilgan shartlar matritsasi, ular yuqoridagi jadvalda keltirildi. Bizning model uchun x= linprog(f,[],[],a,b,l) ko'rinishda funksiyani kiritish mumkin. Buni berishdan oldin f, a, b, l massivlar qiymatini kiritish kerak.
>>f=[10, 7, 4, 1, 4, 2, 7, 10, 6, 11, 8, 5, 3, 2, 2, 11, 8, 12, 16, 13 ];
>>a1=[1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
>>a2=[0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0];
>>a3=[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0];
>>a4=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1];
>>a5=[1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0];
>>a6=[0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0]
>>a7=[0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0];
>>a8=[0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0];
>>a9=[0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1];
>>a=[a1; a2; a3; a4; a5; a6; a7; a8; a9];
>>b=[100; 250; 200; 300; 200; 200; 100; 100; 250];
>>l=zeros(1,20);
>> x= linprog(f,[],[],a,b,l)
Natija :
3.1-rasm. MatLabda transport masalasining yechimi.
Bu yerda adashmaslik uchun A matritsaning har bir satri alohida kiritildi va a=[a1; a2; a3; a4; a5; a6; a7; a8; a9] orqali bitta matritsaga birlashtirildi.


MathCad dasturida optimallashtiruvchi modellarni yechish

MathCADda optimal yechimni aniqlash

Transport masalasining modelini bir indeksli ko'rinishda yozib MatLabda yechish mumkinligini ko'rdik. Endi indeksdan foydalanmasdan yozilgan modelni MathCADda yechish mumkin ekanligini ko'ramiz. Buning uchun oldin masala uchun belgilashlarni quyidagi jadvalda keltiramiz.

bj ai

b1

b2

b3

b4

b5

a1

c1

c2

c3

c4

c5

x1

x2

x3

x4

x5

a2

c6

c7

c8

c9

c10

x6

x7

x8

x9

x10

a3

c11

c12

c13

c14

c15

x11

x12

x13

x14

x15

a4

c16

c17

c18

c19

c20

x16

x17

x18

x19

x20

Bu yergadi c1,c2, . . .,c20, x1,x2, . . .x20 lar har biri o'zgaruvchilar, massiv elementlari emas. Shu belgilashlarga ko'ra maqsad funksiya quyidagicha yoziladi:
10x1+7 x2 + 4x3 + x4 + 4x5 +2x6+ 7x7 +10 x8 +6 x9 +11 x10 +8x11 + 5x12 + 3x13 + 2x14 + 2x15 +11x16+ 8x17 + 12x18 +16 x19 + 13x20 →min
chegaraviy shatlar esa quyidagicha yoziladi:
x1+ x2 + x3 + x4 + x5 =100 x2+ x7 + x12 + x17 =200
x6+ x7 + x8 + x9 + x10 =250 x3+ x8 + x13 + x18 =100
x11+ x12 + x13 + x14 + x15 =200 x4+ x9 + x14 + x19=100
x16+ x17 + x18 + x19 + x20 =300 x5+ x10 + x15 + x20 =250
x1+ x6 + x11 + x16 =200 x1≥0, x2≥0, . . ., x20≥0
Buni MathCAD da yechish uchun dastlab noma'lumlarga boshlang'ich qiymat berish kerak. Bu masalada 20ta noma'lum bo'lgani uchun, ularning hammasiga alohida o'zlashtirish operatori yoziladi. Nomanfiylik shartini yozishda ham 20 ta shartni har birini yozish kerak. Funksiyalar argumentini yozish ham zerikarli, chunki 20 ta o'zgaruvchini hammasini yozish kerak bo'ladi.(3.2-rasm)
3.2-rasm. MathCadda transport masalasining modelini massivsiz yozishlishi.
3.3-rasm. MathCadda transport masalasining modelini yechimi.
Bu ko'rinishdan foydalanish soddaroq va yoqqol ko'zga tashlanuvchan. Faqat uni yozib chiqish biroz zerikarli. Kiritishni tezlatish uchun nusxasini olib qo'yishdan foydalanish mumkin.
Bu masalani Mathlabda massiv o'zgaruvchilardan foydalanib yechich mumkin, albatta. Faqat bunda model qisman matritsaviy ko'rinishda yoziladi xalos: noma'lum o'zgaruvchiga beriladigan boshlang'ich qiymat, nomanfiylik sharti, funksiya argumentini yozish massiv bo'yicha sodda yoziladi.
Excel dasturuda chiziqli dasturlash masalasini simpleks usulda yechish.
Bu chizili dasturlash masalalarini MS EXCEL dasturi yordamida yechishni ko‘rib chiqamiz. Izoh va boshlangʻich ma’lumotlarni ishchi sohaning katakcha(yacheyka)lariga joylashtirish.
Boshlangʻich ma’lumotlarni ishchi sohaga turli qulay tartibda joylashtirish mumkin. Shulardan bir koʻrinishini koʻrib chiqamiz.
A, C, E, G ustunlardagi hamma katakchalarda masalani yechilishiga ta’sir qilmaydigan tushuntirish izohlari keltirilgan.
B2…B13, D10…D12, F10…F12 katakchalariga chap tomondagi matnga mos sonli ma’lumot kiritilgan.
H2…H4 katakchalarga nol soni, qidirilayotgan x₁, x₂ va x₃ uchun boshlangʻich qiymat sifatida berilgan. H7 katakchada maqsad funksiyaning formulasi kiritilsa: =B2*H2+B3*H3+B4*H4, boshlangʻich qiymatlar nol bo‘lganda funksiya qiymati ham nol boʻladi.
B16…B19 katakchalarga tengsizlikning cheklanish chap qismi joylashtirilgan:
=B10*H2+D10*H3+F10*H4,
=B11*H2+D11*H3+F11*H4,
=B12*H2+D12*H3+F12*H4,
=H2+H3+H4,
bu qiymatlar qidirilayotgan o‘zgarivchilarning nol qiymatida nolga teng.
1.“Поиск решения” buyrug‘ini ishga tushirish va unga boshlang‘ich ma’lumotlarni kiritish.
Uskunalar panelida “Поиск решения” buyrug‘i yo‘q bo‘lsa, Файл  Параметры  Надстройки buyrug‘ini ishga tushuramiz va “Поиск решения” buyrug‘ni tanlaymiz.
“Перейти…” tugmasi bosiladi va buyruq uskunalar paneliga joylashtiriladi.
“Поиск решения” buyrugʻi bosilganda “Параметры поиска решения” muloqat darchasi ochiladi. Maqsad finksiya(Оптимизировать цельевую функцию)ning adresini H7 katakcha ko‘rsatiladi. “До:” ko‘rsatmasidan “Максимум” belgilanadi.
“Изменяя ячейки переменных” qatoriga qidirilayotgan x₁, x₂ va x₃ o‘zgaruvchilar katakchalari ko‘rsatiladi: H2, H3 va H4.Cheklanishlarni o‘rnatish uchun “Добавить” tugmasi bosiladi.

“Добавление ограничения” muloqat darchasida quyidagi cheklanishlar o‘rnatiladi va “Добавить” tugmasi bosiladi.

So‘ngi cheklanish o‘rnatilganida “OK” tugmasi bosiladi va “Параметры поиска решения” muloqat darchasi ochiladi.
“Параметры” muloqat darchasiпa ma’lumotlar kiritish.
“Выберите метод решения” darchasida Simpleks usuli tanlanadi. “Параметры” tugmasi bosiladi va muloqat darchasi ochiladi.
“Параметры” darchasi quyidagicha to‘ldiriladi:
“OK” tugmasi bosiladi va “Параметры поиска решения” muloqat darchasi ochiladi.
Natijani olish.
“Параметры поиска решения” muloqat darchasida “Найти решение” tugmasi bosilganda, MS EXCEL dasturi hisoblashni boshlaydi va ishchi sohada natijalar qiyidagicha hosil bo‘ladi.

Umumiy ko'rinishdagi optimallashtiruvchi modelni kanonik ko'rinishga keltirish

Chegaraviy shartlarga kiritiladigan qo'shimcha o'zgaruvchilar uchun olingan natijalar ma'nosi