F(X) = x1+x2 maqsad funksiyasining minimal qiymatini quyidagi shartlar-cheklovlar ostida aniqlaymiz

O'zbekiston Respublikasi Axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi

Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti

Algoritmlarni Loyihalash

Laboratoriya ishi

Bajardi: G’aniboyev Dilshod

Toshkent-2021

1. 
   F(X) = x1+x2 maqsad funksiyasining minimal qiymatini quyidagi shartlar-cheklovlar ostida aniqlaymiz.
   

x₁-2x₂+x₃=2
x₁-x₂+2x₃=1
x₁-x₂+x₃=5

Ushbu muammoning cheklashlar-tenglik tizimining kengaytirilgan matritsasi:

1 -2 1 2 1 -1 2 1 1 -1 1 5

1. Asosiy o'zgaruvchi sifatida x1 ni tanlashingiz mumkin.

Ruxsat beruvchi element RE=1. X1 o'zgaruvchisiga mos keladigan satr x1 qatorning barcha elementlarini RE=1 faollashtiruvchi elementga bo'lish orqali olinadi. Yoqish elementi o'rniga biz 1 ni olamiz. X1 ustunining qolgan kataklarida biz nollarni yozamiz.
Boshqa barcha elementlar 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 - (A * B) / RE
STE - eski rejaning elementi, RE - hal qiluvchi element (1), A va B - eski rejaning elementlari, STE va RE elementlari bilan to'rtburchaklar hosil qiladi.
Keling, har bir elementning hisobini jadval ko'rinishida keltiramiz:

1 : 1	-2 : 1	1 : 1	2 : 1
1-(1*1):1	-1-(-2*1):1	2-(1*1):1	1-(2*1):1
1-(1*1):1	-1-(-2*1):1	1-(1*1):1	5-(2*1):1

Biz yangi matritsani olamiz:

1	-2	1	2
0	1	1	-1
0	1	0	3

2. Asosiy o'zgaruvchi sifatida x2 ni tanlashingiz mumkin.

Ruxsat beruvchi element RE=1. X2 o'zgaruvchisiga mos keladigan chiziq x2 chizig'ining barcha elementlarini RE=1 faollashtiruvchi elementga bo'lish orqali olinadi. Yechish elementi o'rniga biz 1 ni olamiz. X2 ustunining qolgan kataklarida biz nollarni yozamiz.
Boshqa barcha elementlar to'rtburchaklar qoidasi bilan belgilanadi.
Keling, har bir elementning hisobini jadval ko'rinishida keltiramiz:

1-(0*-2):1	-2-(1*-2):1	1-(1*-2):1	2-(-1*-2):1
0 : 1	1 : 1	1 : 1	-1 : 1
0-(0*1):1	1-(1*1):1	0-(1*1):1	3-(-1*1):1

Biz yangi matritsani olamiz:

1	0	3	0
0	1	1	-1
0	0	-1	4

3. Asosiy o'zgaruvchi sifatida x3 ni tanlashingiz mumkin.

Ruxsat beruvchi element RE=-1. X3 o'zgaruvchisiga mos keladigan chiziq x3 chizig'ining barcha elementlarini RE=-1 hal qiluvchi elementga bo'lish orqali olinadi. Yechish elementi o'rniga biz 1 ni olamiz. X3 ustunining qolgan kataklarida biz nollarni yozamiz.
Boshqa barcha elementlar to'rtburchaklar qoidasi bilan belgilanadi.
Keling, har bir elementning hisobini jadval ko'rinishida keltiramiz:

1-(0*3):-1	0-(0*3):-1	3-(-1*3):-1	0-(4*3):-1
0-(0*1):-1	1-(0*1):-1	1-(-1*1):-1	-1-(4*1):-1
0 : -1	0 : -1	-1 : -1	4 : -1

Biz yangi matritsani olamiz:

1	0	0	12
0	1	0	3
0	0	1	-4

Tizim identifikatsiya matritsasiga ega bo'lganligi uchun biz asosiy o'zgaruvchilar sifatida X = (1,2,3) ni olamiz.

Biz asosiy o'zgaruvchilarni qolganlari bilan ifodalaymiz:
x1 = 12
x2 = 3
x3 = -4
Ularni maqsad funktsiyasiga almashtiring: F(X) = (12)+(3) yoki F(X) = 15,
Biz asosiy o'zgaruvchilarni qolganlari bilan ifodalaymiz:
x1 = 12
x2 = 3
x3 = -4

Ularni maqsad funktsiyasiga almashtiring: F(X) = (12)+(3) yoki F(X) = 15,

x1=12
x2=3
x3=-4
Hisob-kitoblarda Fc = 15 qiymati vaqtincha hisobga olinmaydi.
Ushbu tenglamalar tizimining A = a(ij) koeffitsientlari matritsasi quyidagi ko'rinishga ega:

1 0 0 0 1 0 0 0 1

A =

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: x1, x2, x3
Erkin o'zgaruvchilar 0 ga teng deb faraz qilsak, biz birinchi asosiy chiziqni olamiz:
X0 = (12,3,-4)
Asosiy yechim, agar u salbiy bo'lmasa, ruxsat etilgan deb ataladi.

Asos	B	x1	x2	x3
x1	12	1	0	0
x2	3	0	1	0
x3	-4	0	0	1
F(X0)	0	0	0	0

Simpleks usulining asosiy algoritmiga o'tamiz.

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

Asos	B	x1	x2	x3
x1	12	1	0	0
x2	3	0	1	0
x3	-4	0	0	1
F(X1)	0	0	0	0

Asosiy o'zgaruvchilar orasida salbiy qiymatlar mavjud. Maqsad funktsiyasi cheklangan emas. Hech qanday yechim yo'q.

Olingan rejada asosiy o'zgaruvchilar qiymatlari orasida salbiy qiymatlar mavjud. Shuning uchun F(X) maqsad funksiyasi ruxsat etilgan rejalar to‘plami bilan chegaralanmagan, ya’ni. F(X) → ∞ va masalaning yechimi yo‘q.

2.Funksiyaning minimal qiymatini toping: F = - 2 x₁ + x₂

3 x1 - 2 x2 ≤ 12
2 x1 + 3 x2 ≥ 6
- x1 + 2 x2 ≤ 8
x1 ≥ 0 x2 ≥ 0 cheklovlarga muvofiq.

1 qadam.
Cheklashlar sistemasining 1 ta tengsizligini yechamiz.

3 x1 - 2 x2 ≤ 12
Biz to'g'ri chiziq chizishimiz kerak: 3 x1 - 2 x2 ≤ 12
x1 =0 => - 2 x2 = 12 => x2 = -6 bo'lsin
x2 =0 => 3 x1 = 12 => x1 = 4 bo'lsin
Ikki nuqta topildi: (0, -6) va (4 ,0)

Endi biz topilgan ikkita nuqta orqali (1) to'g'ri chiziqni chizishimiz mumkin.

Keling, tengsizlikka qaytaylik.

3 x1 - 2 x2 ≤ 12

Biz tengsizlikni faqat x2 chap tomonda bo'lishi uchun o'zgartirishimiz kerak.
- 2 x2 ≤ - 3 x1 + 12
x2 ≥ 3/2 x1 - 6

Tengsizlik belgisi ≥

Shuning uchun biz to'g'ri chiziq ustidagi nuqtalarni hisobga olishimiz kerak (1).
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 x1 + 3 x2 ≥ 6

Biz to'g'ri chiziq chizishimiz kerak: 2 x1 + 3 x2 = 6

x1 =0 => 3 x2 = 6 => x2 = 2 bo'lsin

x2 =0 => 2 x1 = 6 => x1 = 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 x1 + 3 x2 ≥ 6

Biz tengsizlikni faqat x2 chap tomonda bo'lishi uchun o'zgartirishimiz kerak.

3 x2 ≥ - 2 x1 + 6

x2 ≥ - 2/3 x1 + 2

Tengsizlik belgisi ≥
Shuning uchun biz to'g'ri chiziq ustidagi nuqtalarni hisobga olishimiz kerak (2).

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.

- x1 + 2 x2 ≤ 8

Biz to'g'ri chiziq chizishimiz kerak: - x1 + 2 x2 = 8

x1 =0 => 2 x2 = 8 => x2 = 4 bo'lsin

x2 =0 => - x1 = 8 => x1 = -8 bo'lsin

Ikki nuqta topildi: (0, 4) va (-8 ,0)

Endi topilgan ikkita nuqta orqali (3) to‘g‘ri chiziq chizamiz.

Keling, tengsizlikka qaytaylik.

- x1 + 2 x2 ≤ 8

Biz tengsizlikni faqat x2 chap tomonda bo'lishi uchun o'zgartirishimiz kerak.

2 x2 ≤ x1 + 8
x2 ≤ 1/2 x1 + 4

Tengsizlik belgisi ≤

Shuning uchun biz to'g'ri chiziq ostidagi nuqtalarni hisobga olishimiz kerak (3).

Keling, ushbu natijani oldingi rasm bilan birlashtiramiz.

Endi bizda rasmda ko'rsatilgan mumkin bo'lgan echimlar hududi mavjud.

4-qadam
Biz C = (-2, 1) vektorini chizishimiz kerak, uning koordinatalari F funksiyaning koeffitsientlari.

5-qadam
Pastki o'ng burchakdan yuqori chap 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 echimlar mintaqasini oxirgi marta kesib o'tgan nuqtada maksimal qiymatga ega.

F funktsiyasi A nuqtada minimal qiymatga ega. (rasmga qarang)

A nuqtaning koordinatalarini topamiz.

A nuqta bir vaqtning o'zida to'g'ri chiziqda (1) va to'g'ri chiziqda (3) joylashgan.

3 x1 - 2 x2 = 12 => x1 = 10
- x1 + 2 x2 = 8 x2 = 9

F funksiyaning A nuqtadagi qiymatini hisoblaymiz (10,9).

F (A) = -2 * 10 + 1 * 9 = -11

NATIJA:
x1 = 10

x2 = 9
F min = -11