O’zbekiston Respublikasi Toshkent Shahridagi Muhammad Al

O’zbekiston Respublikasi Toshkent Shahridagi Muhammad Al-Xorazmiy
nomidagi Toshkent Axborot Texnologiyalari Universiteti
Telekommunikatsiya Texnologiyalari fakulteti
MUSTAQIL ISH
Fan nomi:
Algoritmlash va loyihalash
Guruh:042 –19
Bajardi: Roxatov I
Tekshirdi: Mamadaliyev X

Mavzu: Chiziqli dasturlash masalalari kanonik ko‘rinishi.
Chiziqli dasturlash masalasining umumiy qo’yilishini bir necha formalarda (shakllarda) yozish mumkin.

1. 
   
   Vektorlar shaklida yozilishi. Ushbu belgilashlarni kiritamiz:
   C = (c₁,c₂,...,c_n), X = (x₁,x₂,...,x_n) bo’lib, CX = cx₁ + c₂x₂ +... + c_nx_n skalyar ko’paytma bo’lsin. Bu holda chiziqli dasturlash masalasini vektor ko’rinishda quyidagicha ifodalash mumkin:
   
   Z = CX
   

chiziqli funksiya minimumga ega bo’ladigan X vektorning


^A1 ^x1 + ^A2^x2 + ... + ^An^xn = ^A0 ^{, X} > ^0 (4)
shartlarni qanoatlantiruvchi qiymatini toping.

1. 
   
   Matritsa shaklida yozilishi.
   

AX = A₀, X > 0 shartlarni qanoatlantiruvchi Z = CX chiziqli funksiya minimum qiymatga ega bo’ladigan X vektorning qiymatini toping, bunda


C = (cj,c₂,...,c_n) satr matritsa, X =
ustun matritsa va A = (a_tj) sistema

• 
  
• 
  
  ^xn у
  

matritsasi hamda A_n =

0

V ^bn у

ustun matritsa bo’ladi.
A¹

1. 
   
   Yig’indi belgisi orqali yozilishi.
   

n

• 
  
  a x = b , i = 1,2,...,m; x > 0, j = 1,2,...,n
  

ij j j j

j=1

n
shartlarni qanoatlantiruvchi Z = V^c_jx_j chiziqli funksiya minimumga ega


j=1
bo’ladigan x_j o’zgaruvchilarning qiymatini toping.

1. 
   
   ta’rif. (2) va (3) shartlarni qanoatlantiruvchi X = (x₁, x₂,..., x_n) vektorga chiziqli dasturlash masalasining mumkin bo’lgan yechimi yoki qisqacha rejasi (plani) deyiladi.
   
2. 
   
   ta’rif. (4) yoyilmaga kiruvchi x larning musbat hadli A_i (i = 1,2,...,m) vektorlari chiziqli bog’lanmagan bo’lsa, X = (x₁,x₂,...,x_n) rejaga tayanch reja (yechim) deyiladi.
   

A_i (i = 1,2,...,m) vektorlar m o’lchovli bo’lganligi uchun tayanch reja ta’rifidan ko’rinadiki, uning musbat hadli koeffitsiyentlari m dan katta bo’lmaydi.

1. 
   
   ta’rif. Tayanch reja (yechim) m ta musbat komponentlarga ega bo’lsa, unga maxsusmas, aks holda maxsus reja deyiladi.
   
2. 
   
   ta’rif. Chiziqli funksiya minimum (maksimum) qiymatga ega bo’ladigan reja (yechim)ga chiziqli dasturlash masalasining optimal rejasi (yechimi) deyiladi.
   

Chiziqli dasturlash masalasi yechimining ayrim xossalarini qaraymiz:

1. 
   
   chiziqli dasturlash masalasi cheklash shartlari sistemasining rejalari
   

(mumkin bo’lgan yechimlari) to’plami bo’sh to’plamni yoki Rn fazoning qavariq to’plamini tashkil etadi;

1. 
   
   chiziqli dasturlash masalasining rejalari to’plami bo’sh to’plam bo’lmasa va maqsadli funksiya bu to’plamda yuqoridan (quyidan) chegaralangan bo’lsa, masala maksimum (minimum) optimal yechimga ega bo’ladi;
   
2. 
   
   chiziqli dasturlash masalasining optimal yechimi mavjud bo’lsa, bu
   

yechim mumkin bo’lgan yechimlar to’plamining chegaraviy nuqtalarida bo’ladi.

1. 
   
   Chiziqli dasturlash masalasining geometrik talqinini (tasvirini) n = 2, ayrim hollarda n = 3 bo’lganda ifodalash mumkin. Chiziqli dasturlash masalasi quyidagicha berilgan bo’lsin:
   

• 
  
  2x1 + 3x2 < 9, x_l — 2x₂ < 2. x_l + x₂ < 8, x₁ > 0, x₂ > 0
  

tengsizliklar sistemasini qanoatlantiruvchi x₁ va x₂ o’zgaruvchilarning shunday qiymatini topish kerakki, f = x₁ — x₂ funksiya maksimum qiymatga ega bo’lsin.
Yechish. 1) — 2x_x + 3x₂ < 9 tengsizlik bilan aniqlanadigan geometrik tasvirni aniqlaymiz. Buning uchun oldin — 2x_x + 3x₂ = 9 to’g’ri chiziqni x₁Ox₂ koordinat tekisligida yasaymiz. Ma’lumki, to’g’ri chiziq A (0;3) va B (—4,5;0) nuqtalardan o’tadi.

Endi — 2x_l + 3x₂ < 9 tengsizlikka mos geometrik tasvirni aniqlash uchun, berilgan tengsizlikka koordinatlar boshi O (0;0) nuqtaning koordinata-larini qo’yamiz: — 2 • 0 + 3 • 0 < 9 yoki 0 < 9 tengsizlik bajariladi, shuning uchun

• 
  
  2xj + 3x₂ < 9 tengsizlik bilan aniqlanadigan geometrik tasvir koordinatlar boshi, O (0;0) nuqtani o’z ichiga olgan yarim tekislikdan iborat bo’ladi.
  

1. 
   
   
   1-chizma
   
   3) x_x + x₂ = 8 to’g’ri chiziq A₂ (0;8), B₂ (8;0) nuqtalardan o’tadi.
   Xuddi yuqoridagidek kolgan tengsizliklarga mos kelgan yarim tekisliklarni yasaymiz. x_x — 2x₂ = 2, bu to’g’ri chiziq Aj (0;—1), B_l (2;0) nuqtalardan o’tadi. x_x — 2x₂ < 2, 0 — 2 • 0 < 2,0 < 2 tengsizlik bajariladi.
   

x₁ + x₂ < 8, 0 + 0 < 8, 0 < 8 bo’ladi.

1. 
   
   x₁ > 0, x₂ > 0 yarim tekisliklarni ham yasaymiz:
   

Shunday qilib, berilgan tengsizliklar sistemasini qanoatlantiradigan mumkin bo’lgan yechimlar to’plami - ОАСДВ yechimlar ko’pburchagini hosil qildik. Ma’lumki, bu to’plam qavariq to’plamdan iborat, ya’ni birinchi xossa baj ariladi (1 -chizma).
Endigi masala bu to’plamning shunday nuqtasini topish kerakki, F = x₁ - x₂ chiziqli funksiya max qiymatga ega bo’lsin. Tekislikda F bir xil qiymatlar qabul qiladigan nuqtalarning joylanishini topamiz. Buning uchun F = a deb olamiz. Bu holda x₁ - x₂ = a tenglama hosil bo’lib, bu F funksiya bir xil a qiymat qabul qiladigan to’g’ri chiziqdir. a ning o’rniga har xil
qiymatlar qo’yish bilan £ parallel to’g’ri chiziqlarni hosil qilamiz. Bu to’g’ri chiziqlarning har biriga sath chizig’i (ya’ni funksiya bir xil qiymatlar qabul qiluvchi to’g’ri chiziq) deyiladi.
Chiziqli funksiya koeffitsiyentlaridan tuzilgan q(1, -1) vektorni qaraymiz.
Bu vektorga perpendikulyar £ chiziqni o’tkazamiz (bu sath chiziqlardan biri) va uni o’ziga parallel mumkin bo’lgan yechimlar to’plami bilan kesishmay qolguncha siljitamiz. Bu yerda, masalada maksimal qiymat topilishi kerak bo’lsa, vektorning yo’nalishi bo’yicha, minimal qiymat topilishi kerak bo’lsa, vektorning yo’nalishiga qarama-qarshi tomonga siljitiladi.
£ to’g’ri chiziqni o’ziga-o’zini parallel qanchalik siljitilmasin, bari bir mumkin bo’lgan yechimlar to’plamini kesib o’taversa, chiziqli funksiya yuqoridan (minimal qiymatlar uchun quyidan) chegaralanmagan bo’ladi va
optimal yechimga ega bo’lmaydi. Qaralayotgan masalada £ chiziqni parallel siljitilganda ОАСДВ mumkin bo’lgan yechimlar to’plami bilan D nuqtada oxirgi umumiy nuqtada ega bo’lib, bu nuqtada funksiya maksimal qiymatga ega bo’ladi. Ma’lumki, bu nuqta x₁ - 2x₂ = 2, x₁ + x₂ = 8 to’g’ri chiziqlarning kesishgan nuqtasi bo’lib, ularni birgalikda yechib nuqtaning koordinatalarini aniqlaymiz:
f x₁ - 2 x₂ = 2 [ x₁ + x₂ = 8 2

3x1 = 18, x1 = 6, 6 - 2x₂ = 2, - 2x2 = -4, x₂ = 2 .

Shunday qilib, D nuqtaning x₁ = 6, x₂ = 2 koordinatalari masala yechimi bo’ladi.


F = 6 - 2 = 4.
max

Bu bilan chiziqli dasturlash masalasining 3-xossaning ham bajarilishini ko’rsatdik.

1. 
   
   Chiziqli dasturlash masalasini yechishning simpleks usuli. Payqash mumkinki, yechimlar ko’pburchagining shunday burchak nuqtasi mavjudki, bu nuqtada chiziqli funksiya optimal qiymatga ega bo’ladi. Yechimlar ko’pburchagining har bir burchak nuqtasiga birorta tayanch yechim mos keladi.
   

Tayanch yechim m ta chiziqli bog’lanmagan vektorlar sistemasi orqali aniqlanib, bu sistemada n ta A₁,A₂,...,A_n vektorlar qatnashadi. Optimal yechimni topish uchun faqat tayanch yechimlar tekshiriladi. Bunday masalada tayanch yechimlar sonining yuqori chegarasi Cm guruhlashlar soni bilan aniqlanadi. m va n lar katta sonlar bo’lganda optimal yechimni, hamma tayanch yechimlarni saralab (tekshirib) topish juda katta murakkablikka olib keladi. Shuning uchun, biror tartiblangan sxema bo’yicha bir tayanch yechimdan ikkinchi tayanch yechimga o’tish algoritmiga ega bo’lishga to’g’ri keladi. Bunday sxema bo’lib, simpleks usul hisoblanadi.
Chiziqli dasturlash masalasini simpleks usul bilan yechishga ko’pincha rejani (yechimni) ketma-ket yaxshilash usuli ham deb yuritiladi. Bunday atalishida usulning asosiy g’oyasi, quyidagi ketma-ket amalga oshiriladigan qadamlardir:

1. 
   
   qadam, boshlang’ich mumkin bo’lgan yechim topiladi;
   
2. 
   
   qadam, topilgan yechimning optimalligi tekshiriladi;
   
3. 
   
   qadam, yechim optimal bo’lmasa, 2-qadamda optimal yechimga yaqinroq boshqa mumkin bo’lgan yechimga o’tiladi. Keyin, yana 2-qadamga va hakozo optimal yechim olinguncha davom ettiriladi. Masala yechimga ega bo’lmasa yoki maqsadli funksiya yechimlar ko’pburchagida chegaralanmagan bo’lsa, simpleks usul bilan yechish jarayonida buni aniqlash imkoniyati yaratiladi.