Algoritmlarni loyihalash fanidan 2-laboratiya ishi bajardi: Muxtarov Nizomiddin toshkent – 2022 Simpleks usuli

OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI


ALGORITMLARNI LOYIHALASH fanidan
2-LABORATIYA ISHI


Bajardi:Muxtarov Nizomiddin

TOSHKENT – 2022
Simpleks usuli.
Simpleks jadvalidan foydalanib, chiziqli dasturlashning to'g'ridan-to'g'ri masalasini simpleks usuli bilan yechamiz.
O'ng tomonda salbiy qiymatlar mavjud bo'lganligi sababli, biz tegishli qatorlarni (-1) ga ko'paytiramiz. Quyidagi cheklash shartlarida F(X) = -x ₁ +3x ₂ +2x ₃
maqsad funksiyasining minimal qiymatini aniqlaymiz .
-x₁-x₂-2x₃≤5
2x₁-3x₂+x₃≤3
x₁-5x₂+6x₃≤5
Birinchi mos yozuvlar rejasini qurish uchun biz qo'shimcha o'zgaruvchilarni kiritish orqali tengsizliklar tizimini tenglamalar tizimiga qisqartiramiz ( kanonik shaklga o'tish ). 1-maʼno tengsizligida (≤) biz x ₄
asosiy oʻzgaruvchini kiritamiz . 2-ma'no tengsizligida (≤) biz x ₅ asosiy o'zgaruvchini kiritamiz . 3-ma'no tengsizligida (≤) biz x ₆ asosiy o'zgaruvchini kiritamiz .
-x₁-x₂-2x₃+x₄ = 5
2x₁-3x₂+x₃+x₅ = 3
x₁-5x₂+6x₃+x₆ = 5
Ushbu tenglamalar tizimining A = a(ij) koeffitsientlari matritsasi quyidagi ko'rinishga ega:

A =

-1 -1 -2 1 0 0 2 -3 1 0 1 0 1 -5 6 0 0 1

Asosiy o'zgaruvchilar - bu cheklovlar tizimining faqat bitta tenglamasiga kiritilgan va bundan tashqari, birlik koeffitsientiga ega bo'lgan o'zgaruvchilar.
Tenglamalar sistemasini asosiy o‘zgaruvchilarga nisbatan yechamiz: x ₄ , x ₅ , x ₆ Erkin o‘zgaruvchilar 0 ga teng
deb faraz qilsak , birinchi mos yozuvlar rejasini olamiz: X0 = (0,0,0,5,3,5 ) salbiy emas.

Asos	B	x1	x2	x3	x4	x5	x6
x4	5	-1	-1	-2	1	0	0
x5	3	2	-3	1	0	1	0
x6	5	1	-5	6	0	0	1
F(X0)	0	1	-3	-2	0	0	0

Simpleks usulining asosiy algoritmiga o'tamiz.
Takrorlash №0 .
1. Optimallik mezonini tekshirish .
Joriy bazaviy chiziq optimal emas, chunki indeks qatorida ijobiy koeffitsientlar mavjud.
2. Yangi asosiy o'zgaruvchining ta'rifi . Biz x ₁
o'zgaruvchisiga mos keladigan ustunni etakchi sifatida tanlaymiz , chunki bu eng katta koeffitsientdir. 3. Yangi erkin o'zgaruvchining ta'rifi . D _i qiymatlarini satrlar bo'yicha bo'linish qismi sifatida hisoblang: b _i / a _i1 va ulardan eng kichigini tanlang:
min (- , 3 : 2 , 5 : 1 ) = 1¹/₂
Shuning uchun 2-chi qator yetakchilik qilmoqda.
Yechish elementi (2) ga teng va yetakchi ustun va yetakchi qatorning kesishmasida joylashgan.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	5	-1	-1	-2	1	0	0	-
x5	3	2	-3	1	0	1	0	^3/2
x6	5	1	-5	6	0	0	1	5
F(X1)	0	1	-3	-2	0	0	0

4. Simpleks jadvalini qayta hisoblash .
Biz simpleks jadvalining keyingi qismini tashkil qilamiz. X ₅ o'zgaruvchisi o'rniga x ₁ o'zgaruvchisi 1-rejaga kiradi . 1-rejadagi x ₁
o'zgaruvchisiga mos keladigan chiziq 0-rejaning x ₅ chizig'ining barcha elementlarini RE=2 faollashtiruvchi elementga bo'lish yo'li bilan olinadi. Yechish elementi o'rniga biz 1 ni olamiz. X ₁ ustunining qolgan kataklarida biz nollarni yozamiz. Shunday qilib, yangi rejada 1 qator x ₁ va ustun x ₁ to'ldiriladi . 1-yangi rejaning boshqa barcha elementlari, shu jumladan indeks qatorining elementlari to'rtburchaklar qoidasi bilan belgilanadi.

Buni amalga oshirish uchun eski rejadan to'rtta raqamni tanlang, ular to'rtburchakning uchlarida joylashgan va har doim RE ning faollashtiruvchi elementini o'z ichiga oladi.
NE = SE - (А*В)/RE
STE - eski rejaning elementi, RE - hal qiluvchi element (2), A va B - eski rejaning elementlari, STE va RE elementlari bilan to'rtburchaklar hosil qiladi.
Keling, har bir elementning hisobini jadval ko'rinishida keltiramiz:

B	x1	x2	x3	x4	x5	x6
5-(3*-1):2	-1-(2*-1):2	-1-(-3*-1):2	-2-(1*-1):2	1-(0*-1):2	0-(1*-1):2	0-(0*-1):2
3 : 2	2 : 2	-3 : 2	1 : 2	0 : 2	1 : 2	0 : 2
5-(3*1):2	1-(2*1):2	-5-(-3*1):2	6-(1*1):2	0-(0*1):2	0-(1*1):2	1-(0*1):2
0-(3*1):2	1-(2*1):2	-3-(-3*1):2	-2-(1*1):2	0-(0*1):2	0-(1*1):2	0-(0*1):2

Biz yangi simpleks jadvalini olamiz:

Asos	B	x1	x2	x3	x4	x5	x6
x4	^13/2	0	^-5/2	^-3/2	1	^1/2	0
x1	^3/2	1	^-3/2	^1/2	0	^1/2	0
x6	^7/2	0	^-7/2	^11/2	0	^-1/2	1
F(X1)	^-3/2	0	^-3/2	^-5/2	0	^-1/2	0

1. Optimallik mezonini tekshirish .
Indeks qatori qiymatlarining hech biri ijobiy emas. Shuning uchun ushbu jadval optimal vazifa rejasini belgilaydi.
Simpleks jadvalining yakuniy versiyasi:

Базис	B	x1	x2	x3	x4	x5	x6
x4	^13/2	0	^-5/2	^-3/2	1	^1/2	0
x1	^3/2	1	^-3/2	^1/2	0	^1/2	0
x6	^7/2	0	^-7/2	^11/2	0	^-1/2	1
F(X2)	^-3/2	0	^-3/2	^-5/2	0	^-1/2	0

Optimal rejani quyidagicha yozish mumkin:
x₁ = 1¹/₂, x₂ = 0, x₃ = 0
F(X) = -1*1¹/₂ + 3*0 + 2*0 = -1¹/₂
Eslatma : _1. Simpleks jadvallari qanday usul bilan qayta hisoblab chiqiladi ? To'rtburchaklar qoidasi (Iordaniya o'zgarishlari usuli) qo'llaniladi. 2. Har safar indeks qatoridan maksimal qiymatni tanlash kerakmi? Siz tanlay olmaysiz, lekin bu loop algoritmiga olib kelishi mumkin. 3. n-ustundagi indeks qatorida nol qiymati. Bu nimani anglatadi?
Nol qiymatlari asosga kiritilgan o'zgaruvchilarga mos kelishi kerak. Agar optimal dizayn simpleks jadvalining indeks qatorida bazisga kiritilmagan erkin o'zgaruvchiga tegishli nol bo'lsa va bu nolni o'z ichiga olgan ustun kamida bitta ijobiy elementni o'z ichiga olgan bo'lsa, u holda muammo optimal dizaynlar to'plamiga ega.
Belgilangan ustunga mos keladigan erkin o'zgaruvchini algoritmning tegishli bosqichlarini bajarish orqali asosga qo'shish mumkin. Natijada, asosiy o'zgaruvchilarning boshqa to'plamiga ega bo'lgan ikkinchi optimal reja olinadi.

constraints:

		2 x1	+	x2	≤	10
		-2x1	-	3x2	≤	6
		2 x1	+	4x2	≥	8

x₁ ≥ 0 x₂ ≥ 0

Yechim:
Koordinatalari cheklash tizimining barcha tengsizliklarini qanoatlantiradigan nuqtalar mumkin bo'lgan yechimlar mintaqasi deyiladi.
Ushbu muammoning mumkin bo'lgan yechimlari mintaqasini topish uchun cheklash tizimining har bir tengsizligini echish kerak. (1-bosqich - 4-bosqichga qarang)
Javobni olish uchun oxirgi ikki qadam kerak.
(5-bosqich - 6-bosqichga qarang)
Bu standart yechim rejasi. Agar amalga oshirish mumkin bo'lgan yechimlar mintaqasi nuqta yoki bo'sh to'plam bo'lsa, yechim qisqaroq bo'ladi.
Ushbu muammoni hal qilish rejasini rasmlarda ko'ring
Muammoning sharti bo'yicha: x1 ≥ 0 x2 ≥ 0.
Endi bizda rasmda ko'rsatilgan mumkin bo'lgan echimlar hududi mavjud.

№1 qadam
Cheklashlar sistemasining 1 ta tengsizligini yechamiz.
2 x ₁ + x ₂ ≤ 10
Biz to'g'ri chiziq chizishimiz kerak: 2 x ₁ + x ₂ = 10
x ₁ =0 => x ₂ = 10 bo'lsin
x ₂ =0 => 2 x ₁ = 10 => x ₁ = 5 bo'lsin
Ikki nuqta topildi: (0, 10) va (5 ,0)
Endi biz topilgan ikkita nuqta orqali (1) to'g'ri chiziqni chizishimiz mumkin.
Keling, tengsizlikka qaytaylik.
2 x ₁ + x ₂ ≤ 10
Biz tengsizlikni faqat x ₂ chap tomonda bo'lishi uchun o'zgartirishimiz kerak.
x ₂ ≤ - 2 x ₁ + 10
Tengsizlik belgisi ≤
Shuning uchun (1) to'g'ri chiziq ostidagi nuqtalarni hisobga olishimiz kerak.
Keling, ushbu natijani oldingi rasm bilan birlashtiramiz.
Endi bizda rasmda ko'rsatilgan mumkin bo'lgan echimlar hududi mavjud.

№2 qadam
Cheklovlar sistemasining 2 ta tengsizligini yechamiz.
- 2 x ₁ + 3 x ₂ ≤ 6
Biz to'g'ri chiziq chizishimiz kerak: - 2 x ₁ + 3 x ₂ = 6
x ₁ =0 => 3 x ₂ = 6 => x ₂ = 2 bo'lsin
x ₂ =0 => - 2 x ₁ = 6 => x ₁ = -3 bo'lsin
Ikki nuqta topildi: (0, 2) va (-3 ,0)
Endi biz topilgan ikkita nuqta orqali (2) to'g'ri chiziqni chizishimiz mumkin.
Keling, tengsizlikka qaytaylik.
- 2 x ₁ + 3 x ₂ ≤ 6
Biz tengsizlikni faqat x ₂ chap tomonda bo'lishi uchun o'zgartirishimiz kerak.
3 x ₂ ≤ 2 x ₁ + 6
x ₂ ≤ 2/3 x ₁ + 2
Tengsizlik belgisi ≤
Shuning uchun (2) to'g'ri chiziq ostidagi nuqtalarni hisobga olishimiz kerak.
Keling, ushbu natijani oldingi rasm bilan birlashtiramiz.
Endi bizda rasmda ko'rsatilgan mumkin bo'lgan echimlar hududi mavjud.

№3 qadam
Cheklovlar sistemasining 3 ta tengsizligini yechamiz.
2 x ₁ + 4 x ₂ ≥ 8
Biz to'g'ri chiziq chizishimiz kerak: 2 x ₁ + 4 x ₂ = 8
x ₁ =0 => 4 x ₂ = 8 => x ₂ = 2 bo'lsin
x ₂ =0 => 2 x ₁ = 8 => x ₁ = 4 bo'lsin
Ikki nuqta topildi: (0, 2) va (4 ,0)
Endi topilgan ikkita nuqta orqali (3) to‘g‘ri chiziq chizamiz.
Keling, tengsizlikka qaytaylik.
2 x ₁ + 4 x ₂ ≥ 8
Biz tengsizlikni faqat x ₂ chap tomonda bo'lishi uchun o'zgartirishimiz kerak.
4 x ₂ ≥ - 2 x ₁ + 8
x ₂ ≥ - 1/2 x ₁ + 2
Tengsizlik belgisi ≥
Shuning uchun biz (3) to'g'ri chiziq ustidagi nuqtalarni hisobga olishimiz kerak.
Keling, ushbu natijani oldingi rasm bilan birlashtiramiz.
Endi bizda rasmda ko'rsatilgan mumkin bo'lgan echimlar hududi mavjud.


№4 qadam
Koordinatalari F funksiyaning koeffitsientlari bo'lgan C = (2, 3) vektorini chizishimiz kerak.


№5 qadam
Pastki chap burchakdan yuqori o'ng burchakka C vektoriga perpendikulyar "qizil" to'g'ri chiziqni o'tkazamiz .
F funktsiyasi "qizil" to'g'ri chiziq birinchi marta amalga oshirilishi mumkin bo'lgan echimlar mintaqasini kesib o'tgan nuqtada minimal qiymatga ega.
F funksiyasi "qizil" to'g'ri chiziqning mumkin bo'lgan yechimlar mintaqasini oxirgi marta kesib o'tgan nuqtada maksimal qiymatga ega.
F funktsiyasi A nuqtada maksimal qiymatga ega. (rasmga qarang)
A nuqtaning koordinatalarini topamiz.
A nuqta bir vaqtning o'zida to'g'ri chiziqda (1) va to'g'ri chiziqda (2) joylashgan.

		2 x 1	+	x 2	=	10	=>	x 1 = 3
		- 2 x 1	+	3 x 2	=	6		x 2 = 4

F funksiyaning A nuqtadagi qiymatini hisoblaymiz (3,4).
F (A) = 2 * 3 + 3 * 4 = 18

Natija:
x ₁ = 3

x ₂ = 4
F _max = 18
Izoh: agar F funktsiyasi A nuqtada maksimalga ega ekanligiga shubha tug'ilsa, qiziqtiruvchi nuqtada F funksiyaning qiymatini topib, uni F (A) bilan solishtirish kerak.


.