O`zbekiston respublikasi axborot texnologiyalari

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Algoritmlarni loyihalash fanidan

LABORATORIYA ISHI 2

Bajardi :
Tekshirdi:

Toshkent-2022

20-variant

1. 
   13x₁+17x₂+14x₃+x₄=533
   
2. 
   10x₁+12x₂+16x₃+x₅=462 (2)
   
3. 
   18x₁+13x₂+11x₃+x₆=532
   

L = 41x₁+42x₂+41x₃+0x₄+0x₅+0x_6→max

2 masala yechimi 1 masala uchun ham yechim bo’ladi.

x4,x5,x6 lar maqsad funsiyasiga xech qanday tasir qilmadydi.
2 masaladagi bazisda o’zgaruvchilarning qiymati x₄ =533, x₅=462, x₆=532 bo’ladi.
Bu holatda L = 0 bo’ladi bu esa 1 masala shartini qanoatlantirmaydi.

1. 
   Masala normative:
   

(13 17 14)
A= (10 12 16) det = 834
(18 13 11)
Учун тескари матрицани топамиз
(-38/417 -5/834 52/417)
A^-1=(89/417 -109/834 -34/417)
(-43/417 137/834 -7/417)
(2) Масалани матрица кўринишида ифодалаб икки тарафдан А^-1  га кўпайтириб юборамиз. Бу холда
X₁-38/417X₄-5/834+6/417X₆=6
X₁+89/417X₄-109/834X₅-34/417X₆=13
X₁-43/417X₄+137/834X₅-7/417X₆=17
L = 41x₁+42x₂+41x₃+0x₄+0x₅+0x_6→max
кўринишни олади. (3) Масала ҳам (1), (2) масалага эквивалент бўлиб унинг ечимлари бўлади.
Бунда мақсад функцияси максимал қиймати L_max=741
эканлигини кўрамиз.
Айнан шу масалани Симплекс усулида ечиш жараёнини кўриб чиқайлик. Биринчи Симплекс жадвал (2) масала асосида тузилади:

Basis	Ci	41	42	41	0	0	0	bi	Ᵹi
		A1	A2	A3	A4	A5	A6
A4	0	13	17	14	1	0	0	533
A5	0	10	12	16	0	1	0	462
A6	0	45	13	11++	0	0	1	532
	∆j	-41	-42	-41	0	0	0	0

x₁=x₂=x₃=0, x₄=533 x₅ =462, x₆=532

4- Симплекс жадвал

Basis	Ci	41	42	41	0	0	0	bi	Ᵹi
		A1	A2	A3	A4	A5	A6
A4	15	1	0	0	-0.81	0.87	0.127	15.011
A5	10	0	1	0	0.787	-1.19	0.064	9.94
A6	12	0	0	1	-1.66	-2.1	0.106	12.201
	∆j	0	0	0	1.72	1.235	1.654	741.18

Оптимал ечим бўлади. Мақсад функцияси қиймати бу холда ўз максимал қиймати Lmax =741.18 га эришади.

4- Симплекс жадвал қийматларини (3) масала коэффицентлари билан солиштирсак улар бир хил эканлигини кўрамиз (фарқ ҳисоблашдаги яхлитлаш хатолиги ҳисобига). Бундан албатта 1- усул маъқул экан деган хулосага бориш керак эмас. Тескари матрица топиш жараёни анча меҳнат талаб қилади. Ундан ташқари танланган базис оптимал бўлмай қолса барчасини башқатдан бажаришга тўғри келади.
Агар масала

Кўринишда берилган бўлса, мумкин бўлган базислар сони m N C n формула бўйича ҳисобланади. Хаттоки биз кўрган (2) масалада ҳам n=6; m=3 N= C₆³  20 та вариант бор. Симплекс усул эса хар қадамда аввалгисидан самаралироқ базисни танлаш йўлидан боради. Шунинг учун бу усулда барча базисларни кўриб чиқишга зарурат қолмайди. Симплекс усули афзалликларидан яна бири, бу усулда бир йўла эгизак масала ечимлари ҳам хосил бўлар экан. Берилган (1) масала учун эгизак масала тузамиз:

4. 
   13y₁+11y₂+15y₃+y4=15
   
5. 
   17y₁+14y₂+12y₃+y5=10 (5)
   
6. 
   15y₁+12y₂+13y₃+y₆=12
   

Q = 45y₁+37y₂+40y₃→min
Чизиқли программалаш масалалар учун иккиланганлик теоремасига кўра (1) масала ечими мавжуд бўлса эгизак масала (5) нинг ҳам ечими мавжуд бўлади ва Lmax = Qmin бўлади. Агар масала симплекс усулида ишланса сўнгги жадвал охирги қаторга сунъий базис усулларида эгизак масала ечимлари келиб чиқар экан. Бизнинг мисолда
y₁=1.72, y₂= 1.235, y₃=1.654
Бу қийматларда Q ни ҳисоблансин. min Q  741.18 келиб чиқади, яъни Lmax = Qmin орадаги фарқ, яна яхлитлаш хатоликлари ҳисобига пайдо бўлган дейиш мумкин.