Mavzu: Jarayon matematik modelini tuzishda eng kichik kvadratlar usulidan foydalanish Maqsad

5-laboratoriya ishi.
Mavzu: Jarayon matematik modelini tuzishda eng kichik kvadratlar usulidan foydalanish
Maqsad: Talabalar chiziqli dasturlash masalasi qo’yilishini o’rganishi, matematik modelini qurishni o’rganishi, transport masalasini bazis reajasini tuzish usullari bilan ishlashni o‘rganishi, bu usullar haqida bilim va ko‘nikmalarga ega bo‘lishi hamda mustaqil masalalar yechishi va shu masalaga mos algoritmlar qura olishi kerak.
Laboratoriya ishini bajarish uchun zarur jihozlar. Zarur dasturiy ta’minot (C++ dasturlash tili kompilyatori, matn muharriri) o‘rnatilgan personal kompyuter, laboratoriya ishini bajarish bo‘yicha (ushbu) uslubiy ko‘rsatma

Zarur nazariy ma’lumotlar.

Dantsig yaratgan simpleks usul har bir tenglamada bittadan ajratilgan no’malum (bazis o’zgaruvchi) qatnashishi shartiga asoslangan. Boshqacha aytganda, ChD masalasida m ta o’zaro chiziqli erkli vektorlar mavjud deb qaraladi. Umumiylikni buzmagan holda bu vektorlar birinchi m ta P₁,P₂,…,P_m vektorlardan iborat bo’lsin, deylik. U holda masala quyidagi ko’rinishda bo’ladi:
(5.1)
x₁≥ 0, x₂ ≥ 0, …, x_n ≥ 0, (5.2)
Y = c₁x₁ + c₂x₂+ … + c_nx_n → min. (5.3)
(5.1) sistemani vektor shaklida yozib olaylik:
P₁x₁ + P₂x₂+ … + P_mx_m + P_m+1x_m+1+ … + P_nx_n = P₀, (5.4)
bu erda

, , …, , ,…, , .
P₁, P₂, …, P_m vektorlar sistemasi m-o’lchovli fazoda o’zaro chiziqli erkli bo’lgan birlik vektorlar sistemasidan iborat. Ular m o’lchovli fazoning bazisini tashkil qiladi. Ushbu vektorlarga mos keluvchi x₁,x₂,…,x_m o’zgaruvchilarni «bazis o’zgaruvchilar» deb ataladi.
x_m+1, x_m+2,…, x_n – bazis bo’lmagan (erkli) o’zgaruvchilar. Agar erkli o’zgaruvchilarga 0 qiymat bersak, bazis o’zgaruvchilar ozod hadlarga teng bo’ladi. Natijada X₀ =(b₁,b₂,…,b_m, 0,…, 0) yechim hosil bo’ladi. Bu yechim boshlang’ich joiz yechim bo’ladi. Ushbu yechimga x₁P₁+x₂P₂+…+x_mP_m = P₀ yoyilma mos keladi. Bu yoyilmadagi P₁, P₂, …, P_m vektorlar o’zaro erkli bo’lganligi sababli topilgan joiz yechim bazis yechim bo’ladi.
Dantsig usulida simpleks jadval quyidagi ko’rinishda bo’ladi:

chiziqli funktsiyadagi koeffitsientlardan tashkil topgan vektor, ya’ni
C_baz=(c₁,c₂,...,c_m) (5.5)
Jadvalda har bir P_j vektorning ustiga x_j noma’lumning chiziqli funktsiyadagi koeffitsienti c_j yozilgan. m+1- qatorga esa x₁,x₂,…,x_m bazis o’zgaruvchilardagi chiziqli funktsiyaning qiymati
(5.6)
hamda bazis yechimning optimallik mezonini baholovchi son

(i=1,…,m; j=1,…,n) (5.7)
yozilgan. Bazis o’zgaruvchilarga mos keluvchi P₁, P₂, …, P_m vektorlar bazis vektorlar deb belgilangan. Bu vektorlar uchun ∆_j=Z_j-s_j=0 (j=1,…,m) bo’ladi. Agar barcha ustunlarda ∆_j ≤ 0 bo’lsa, u holda X=( x₁,x₂,…,x_m) = (b₁,b₂,…,b_m) yechim optimal yechim bo’ladi. Bu yechimdagi chiziqli funktsiyaning qiymati Y₀ ga teng bo’ladi.

shartni qanoatlantiruvchi P_k vektorni bazisga kiritib, bazisdan
(5.8)
shartni qanoatlantiruvchi P_l vektorni chiqarish kerak bo’ladi. Bu holda alk element hal qiluvchi element sifatida belgilandi. Shu element joylashgan l-qatordagi P_l vektor o’rniga u joylashgan ustundagi P_k vektor bazisga kiritiladi. P_l vektorning o’rniga P_k vektorni kiritish uchun simpleks jadval quyidagi formulalar asosida almashtiriladi.

Simpleks jadval almashgandan so’ng yana qaytadan ∆_j≤0 baholar aniqlanadi. Agar barcha j lar uchun ∆_j≤0 bo’lsa, optimal yechim topilgan bo’ladi. Aks holda topilgan bazis reja boshqa bazis reja bilan almashtiriladi. Bunda quyidagi teoremalarga asoslanib ish ko’riladi: