Cal011-L2 guruh talabasi Abdisalomov

_{M UHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI}

CAL011-L2 guruh talabasi Abdisalomov

Avazbekning algoritmlarni loyihalash

fanidan 2-labaratoriya ishi

Mavzu: dasturlash masalalari (CPM) larni echishda Simplex usul mohiati va chiziqli dasturlash masalalari bo'yicha topshiriqlarni bajarish.

1-VARIANT

Tekshirdi: Nasriddinov Saloxiddin

1-VARIANT

1-

F(x) = 20x ₁ +23x ₂ +22x ₃ → maks

	7x 1	+5x 2	+3x 3	≤ 169
	3x 1	+4x 2	+6x 3	= 139
	2x 1	+3x 2	+5x 3	= 106

F(x) = 20x ₁ +23x ₂ +22x ₃ +0x ₄ -Mx ₅ -Mx ₆ → maksimal

	7x 1	+5x 2	+3x 3	+x 4	= 169
	3x 1	+4x 2	+6x 3	+x 5	= 139
	2x 1	+3x 2	+5x 3	+x 6	= 106

1-Simpleks jadval

B	Cb	P	x 1		x 2	x 3 ↓	x 4		x 5	x 6	Q
			20		23	22	0		-M	-M
x 4	0	169	7		5	3	1		0	0	56.33
x 5	-M	139	3		4	6	0		1	0	23.17
x 6 ←	-M	106	2		3	5	0		0	1	21.2
maks		-245 mln		-5M-20	-7M-23	-11M-22		0	0	0

Ustun asosining elementlari (B):

B ₁ = x ₄ ;
B ₂ = x ₅ ;
B ₃ = x ₆ ;

Cb ustun elementlari:

Cb ₁ = 0;
Cb ₂ = -M;
Cb ₃ = -M

O'zgaruvchan o'zgaruvchilarning qiymatlari va P ustuni:

P ₁ = 169; P ₂ = 139; P ₃ = 106;

x _1,1 = 7; x _1,2 = 5; x _1,3 = 3; x _1,4 = 1; x _1,5 = 0; x _1,6 = 0; x _2,1 = 3; x _2,2 = 4;

x _2,3 = 6; x _2,4 = 0; x _2,5 = 1; x _2,6 = 0; x _3,1 = 2; x _3,2 = 3; x _3,3 = 5; x _3,4 = 0;
x _3,5 = 0; x _3,6 = 1;

Maqsad funksiyasi qiymati:

Maks _P = (Cb ₁ * P ₀₁ ) + (Cb ₁₁ * P ₂ + (Cb ₂₁ * P ₃ = (0 * 169)) + (-M * 139) + (-M * 106) = -245M;
Baholangan nazorat o'zgaruvchilari:
Maks _x 1 = ((Cb ₁ * x _1,1 ) + (Cb ₂ * x _2,1 ) + (Cb ₃ * x _3,1 ) ) - k _x 1 = ((0 * 7) + (-M * 3) + (-M * 2) ) - 20 = -5M-20;
Maks _x 2 = ((Cb ₁ * x _1,2 ) + (Cb ₂ * x _2,2 ) + (Cb ₃ * x _3,2 ) ) - k _x 2 = ((0 * 5) + (-M * 4) + (-M * 3) ) - 23 = -7M-23;
Maks _x 3 = ((Cb ₁ * x _1,3 ) + (Cb ₂ * x _2,3 ) + (Cb ₃ * x _3,3 ) ) - k _x 3 = ((0 * 3) + (-M * 6) + (-M * 5) ) - 22 = -11M-22;
Maks _x 4 = ((Cb ₁ * x _1,4 ) + (Cb ₂ * x _2,4 ) + (Cb ₃ * x _3,4 ) ) - k _x 4 = ((0 * 1) + (-M * 0) + (-M * 0) ) - 0 = 0;
Maks _x 5 = ((Cb ₁ * x _1,5 ) + (Cb ₂ * x _2,5 ) + (Cb ₃ * x _3,5 ) ) - k _x 5 = ((0 * 0) + (-M * 1) + (-M * 0) ) - -M = 0;
Maks _x 6 = ((Cb ₁ * x _1,6 ) + (Cb ₂ * x _2,6 ) + (Cb ₃ * x _3,6 ) ) - k _x 6 = ((0 * 0) + (-M * 0) + (-M * 1) ) - -M = 0
Q ustunli elementlar:
Q ₁ = P ₁ / x _1,3 = 169 / 3 = 56,33;
Q ₂ = P ₂ / x _2,3 = 139 / 6 = 23,17;
Q ₃ = P ₃ / x _3,3 = 106 / 5 = 21,2;
Bazisdan Q ning eng kam ijobiy qiymatiga ega bo'lgan o'zgaruvchini chiqaramiz.
Bazisdan olingan o'zgaruvchiga mos keladigan chiziq va bazisga kiritilgan o'zgaruvchiga mos keladigan ustunning kesishmasida hal qiluvchi element joylashgan.
Ushbu element bizga keyingi iteratsiya jadvalining elementlarini hisoblash imkonini beradi.

2-Simpleks jadval

B	Cb	P		x 1 ↓		x 2		x 3		x 4		x 5		x 6		Q
				20		23		22		0		-M		-M
x 4 ←	0	105.4		5.8		3.2		0		1		0		-0,6		18.17
x 5	-M	11.8		0,6		0.4		0		0		1		-1.2		19.67
x 3	22	21.2		0.4		0,6		1		0		0		0.2		53
maks			-11,8M+466,4		-0,6M-11,2		-0,4M-9,8		0		0		0		2,2M+4,4

Ustun asosining elementlari (B)
_{Oldingi iteratsiyaning hisob-kitoblari natijalari uchun biz x 6} asosidan o'zgaruvchini olib tashlaymiz va uning o'rniga x ₃ ni qo'yamiz . Boshqa barcha hujayralar o'zgarishsiz qoladi.

Cb ustun elementlari

Ushbu ustunning har bir katagi tegishli qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng.
Cb ₁ = 0;
Cb ₂ = -M;
Cb ₃ = 22;

O'zgaruvchan o'zgaruvchilarning qiymatlari va P ustuni

(Oldingi iteratsiya ma'lumotlari dastlabki ma'lumotlar sifatida olinadi)

Barcha kataklarni bazaga kiritilgan o'zgaruvchiga mos keladigan nol bilan to'ldiring:

(Rezolyutsiya elementi o'zgarishsiz qoladi)
x _1,3 = 0;
x _2,3 = 0;
Biz oldingi jadvaldagi hal qiluvchi elementi bo'lgan qatorni joriy jadvalga o'tkazamiz, uning qiymatlarini element bo'yicha hal qiluvchi elementga ajratamiz:
P ₃ = P ₃ / x _3,3 = 106 / 5 = 21,2;
x _3,1 = x _3,1 / x _3,3 = 2 / 5 = 0,4;
x _3,2 = x _3,2 / x _3,3 = 3 / 5 = 0,6;
x _3,3 = x _3,3 / x _3,3 = 5 / 5 = 1;
x _3,4 = x _3,4 / x _3,3 = 0 / 5 = 0;
x _3,5 = x _3,5 / x _3,3 = 0 / 5 = 0;
x _3,6 = x _3,6 / x _3,3 = 1/5 = 0,2;
Qolgan bo'sh katakchalar, hisoblar qatori va Q ustunidan tashqari, hal qiluvchi elementga nisbatan to'rtburchaklar usuli yordamida hisoblanadi:
P ₁ = (P ₁ * x _3,3 ) - (x _1,3 * P ₃ ) / x _3,3 = ((169 * 5) - (3 * 106)) / 5 = 105,4;
P ₂ = (P ₂ * x _3,3 ) - (x _2,3 * P ₃ ) / x _3,3 = ((139 * 5) - (6 * 106)) / 5 = 11,8;
x _1,1 = ((x _1,1 * x _3,3 ) - (x _1,3 * x _3,1 )) / x _3,3 = ((7 * 5) - (3 * 2)) / 5 = 5,8;
x _1,2 = ((x _1,2 * x _3,3 ) - (x _1,3 * x _3,2 )) / x _3,3 = ((5 * 5) - (3 * 3)) / 5 = 3,2;
x _1,3 = ((x _1,3 * x _3,3 ) - (x _1,3 * x _3,3 )) / x _3,3 = ((3 * 5) - (3 * 5)) / 5 = 0;
x _1,5 = ((x _1,5 * x _3,3 ) - (x _1,3 * x _3,5 )) / x _3,3 = ((0 * 5) - (3 * 0)) / 5 = 0;
x _1,6 = ((x _1,6 * x _3,3 ) - (x _1,3 * x _3,6 )) / x _3,3 = ((0 * 5) - (3 * 1)) / 5 = -0,6;
x _2,1 = ((x _2,1 * x _3,3 ) - (x _2,3 * x _3,1 )) / x _3,3 = ((3 * 5) - (6 * 2)) / 5 = 0,6;
x _2,2 = ((x _2,2 * x _3,3 ) - (x _2,3 * x _3,2 )) / x _3,3 = ((4 * 5) - (6 * 3)) / 5 = 0,4;
x _2,3 = ((x _2,3 * x _3,3 ) - (x _2,3 * x _3,3 )) / x _3,3 = ((6 * 5) - (6 * 5)) / 5 = 0;
x _2,5 = ((x _2,5 * x _3,3 ) - (x _2,3 * x _3,5 )) / x _3,3 = ((1 * 5) - (6 * 0)) / 5 = 1;
x _2,6 = ((x _2,6 * x _3,3 ) - (x _2,3 * x _3,6 )) / x _3,3 = ((0 * 5) - (6 * 1)) / 5 = -1,2;
Maqsad funksiyasi qiymati
Maqsad funktsiyasining qiymatini Cb ustunini elementlar bo'yicha P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz.
Maks _P = (Cb ₁ * P ₀₁ ) + (Cb ₁₁ * P ₂ + (Cb ₂₁ * P ₃ = (0 * 105,4)) + (-M * 11,8) + (22 * 21,2) = -11,8M + 466,4;

Baholangan nazorat o'zgaruvchilari

Biz har bir boshqariladigan o'zgaruvchi bo'yicha hisob-kitoblarni o'zgaruvchi ustunidagi qiymatni elementlar bo'yicha, Cb ustunidagi qiymatga ko'paytirish, mahsulotlarning natijalarini jamlash va ularning yig'indisidan maqsad funktsiyasi koeffitsientini ayirish orqali hisoblaymiz. bu o'zgaruvchi.
Maks _x 1 = ((Cb ₁ * x _1,1 ) + (Cb ₂ * x _2,1 ) + (Cb ₃ * x _3,1 ) ) - k _x 1 = ((0 * 5,8) + (-M * 0,6) + (22 * 0,4) ) - 20 = -0,6M-11,2;
Maks _x 2 = ((Cb ₁ * x _1,2 ) + (Cb ₂ * x _2,2 ) + (Cb ₃ * x _3,2 ) ) - k _x 2 = ((0 * 3,2) + (-M * 0,4) + (22 * 0,6) ) - 23 = -0,4M-9,8;
Maks _x 3 = ((Cb ₁ * x _1,3 ) + (Cb ₂ * x _2,3 ) + (Cb ₃ * x _3,3 ) ) - k _x 3 = ((0 * 0) + (-M * 0) + (22 * 1) ) - 22 = 0;
Maks _x 4 = ((Cb ₁ * x _1,4 ) + (Cb ₂ * x _2,4 ) + (Cb ₃ * x _3,4 ) ) - k _x 4 = ((0 * 1) + (-M * 0) + (22 * 0) ) - 0 = 0;
Maks _x 5 = ((Cb ₁ * x _1,5 ) + (Cb ₂ * x _2,5 ) + (Cb ₃ * x _3,5 ) ) - k _x 5 = ((0 * 0) + (-M * 1) + (22 * 0) ) - -M = 0;
Maks _x 6 = ((Cb ₁ * x _1,6 ) + (Cb ₂ * x _2,6 ) + (Cb ₃ * x _3,6 ) ) - k _x 6 = ((0 * -0,6) + (- M * -1,2) + (22 * 0,2) ) - -M = 2,2M+4,4;