1. ChDMning qo’yilishi ChDMni yechishning simpleks usuli

7-ma’ruza. Chiziqli dasturlash masalalarining yechishda simpleks usul algoritmi va uning tahlili
Reja:
1. ChDMning qo’yilishi
2. ChDMni yechishning simpleks usuli

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: