Identifikatsiyalash

1.3.1 Simpleks-analitik usuli

Dastlab berilgan chizikli programmalash masalasining chegaraviy shartlarida m ta oʻzaro chiziqli bogʻlik boʻlmagan birlik vektorlar mavjud deb faraz qilamiz. Umumiylikni buzmagan holda bu vektorlar birinchi m ta P₁, P₂,... ,P_m vektordan iborat deylik. U holda masala quyidagi koʻrinishda boʻladi:

x₁+a_1,m+1 x_m+1+...+a_1nx_n=b₁
x₂+a_2,m+1 x_m+1+...+a_2nx_n=b₂ (1.3.1)
.......................................
x_m+a_mm+1 x_m+1+...+a_mnx_n=b_m
x₁³0, x₂³0,..., x_m³0, x_m+1³0,...., x_n³0 (1.3.2)
y_min=c₁x₁+ c₂x₂+.... +c_nx_n (1.3.3)
(1.3.1) sistemani vektor formada yozamiz:
P₁x₁+ P₂x₂+...+ P_mx_m+ P_m+1x_m+1+...+ P_nx_n= P₀ (1.3.4)
P₁, P₂,...,P_m vektorlar n oʻlchovli vektor fazodagi oʻzaro chiziqli bogʻliq boʻlmagan birlik vektorlardan iborat boʻlib, bu fazoning bazisini tashkil qiladi. (1.3.1) da x₁,x₂,...,x_m oʻzgaruvchilarni bazis oʻzgaruvchilar, x_m+1,x_m+2,...,x_m oʻzgaruvchilarni esa bazis boʻlmagan (ozod) oʻzgaruvchilar deb qabul qilib, bazis boʻlmagan oʻzgaruvchilarni nolga tenglaymiz. Natijada:
X₀=(x₁=b₁, x₂=b₂,...;x_m=b_m, x_m+1=0,..., x_n=0) (1.3.5)
Boshlangʻich planni hosil qilamiz. (1.3.5) planga quyidagi
x₁P₁+x₂P₂+...+x_mP_m=P₀ (1.3.6)
yoyilma mos keladi. Bu yoyilmadagi P₁, P₂,..., P_m vektorlar oʻzaro chizikli bogʻliq boʻlmagan vektorlar boʻlganligi sababli, topilgan boshlangʻich (1.3.5) plan tayanch plan boʻladi.
Endi boshlangʻich plandan foydalanib, yangi tayanch planni topish mumkinligini koʻrsatamiz. P₁, P₂,..., P_m vektorlar n oʻlchovli vektor fazoning bazisini tashkil qilgani uchun P₁, P₂,..., P_n vektorlarning ixtiyoriysini (P_j) bazis vektorlar orqali faqat bir xil yoyilmasini topish mumkin, ya’ni
P_j =x_1jP₁+ x_2jP₂ +...+ x_mjP_m, (1.3.7)
Faraz qilaylik, birorta vektor, masalan P_m+1ning yoyilmasidagi koeffitsientlardan kamida bittasi (masalan, x_1,m+1) noldan farqli boʻlsin:
P_m+1=P₁ x_{1 m+1} +P ₂ x _{2 m+1} +…+P _m x _{m m+1} (1.3.8)
Ixtiyoriy q>0 (q-xozircha noma’lum sonni olib, (1.3.8) tenglikning ikki tomonini oʻnga koʻpaytirib, hosil boʻlgan natijani (1.3.6) dan ayiramiz. Natijada quyidagi tenglikka ega boʻlamiz:
P₁(x₁-q x_1,m+1)+ P₂(x₂-q x_2,m+1)+...+
+P_m(x_m-q x_m,m+1)+ q P_m+1)=P₀ (1.3.9)
Agar x₁-q x_1,m+1³0, x₂-q x_2,m+1³0, ..., x_m-q x_m,m+1³ 0 boʻlsa,
X₁=( x₁-qx_1,m+1, x₂-qx_2,m+1, ..., x_m-qx_m,m+1, 0,0,...,0)
vektor plan boʻladi. q>0 boʻlganligi sababli, X₁ planning komponentalari manfiy boʻlmaydi, shuning uchun x_2,m+1>0 boʻlgan komponentalarni quramiz. Demak, shunday q>0 topishimiz kerakki, xama I lar uchun
x_{i ,m+1}>0 boʻlganda x_i-qx_{i ,m+1}³0
boʻlsin. Bundan
0£q£
X₁ plan ixtiyoriy

Tengsizlikni kanoatlantiruvchi q uchun plan boʻladi. Lekin tayanch plan oʻz ichiga m+1 ta komponentani olmaydi, shuning uchun X₁ plandagi kamida bitta komponentani nolga aylantirish kerak. Faraz kilaylik,
q=q₀= =
boʻlsin. Bu xolda X₁ planning k komponentasi x_k- q x_k,m+1=0 boʻladi. q ning qiymatini (1.3.9) ga quyib kuyidagi yoyilmani hosil qilamiz:

bu yoyilmaga
X₁=( x₁-q₀x_1,m+1, x₂-q₀x_2,m+1, ..., x_k-1-q₀x_k-1,m+1, 0,
x_k+1-q₀ x_k+1,m+1,..., x_m-q₀ x_m,m+1, q₀)
plan mos keladi. Demak, yangi planning komponentalari quyidagicha aniqlanar ekan:
(1.3.10)
Bundan keyingi tayanch planni hosil qilish uchun bazisga kirmagan ixtiyoriy vektorning P₁, P₂,..., P_m bazis vektorlar orqali yoyilmasini aniqlash xamda shunday soni topish kerakki, uning yordamida yangi vektor bazisga kirsin va eski bazis vektorlardan birortasi bazisdan chiqsin. Shunday qilib, yangi tayanch planlarni hosil kilish jarayoni bazisga kiritiladigan va bazisdan chiqariladigan vektorni tanlashdan iboratdir. Bazisga kiritiladigan vektorni tanlash kriteriysi simpleks usulning asasiy elementlaridan biri hisoblanadi. Agar bazisga kiritilayotgan P_m+1 vektorning yoyilmasida barcha x_i,m+1£0 boʻlsa, (1.3.9) yoyilmadagi birorta vektorni bazisdan chiqaruvchi q>0 ni topib boʻlmaydi. Bu xolda X₁ plan m+1 musbat komponentalarni oʻz ichiga oladi. P₁, P₂,..., P_m, P_m+1 vektorlar sistemasi esa oʻzaro chiziqli bogʻliq boʻlib qavariq koʻpburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. Bu nuqtada esa chiziqli funksiya oʻzining minimum qiymatiga erisholmaydi. Bu holda chiziqli funksiya quyidan chegaralanmagan boʻladi.