Muhammad al- xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mustaqil ish

1. Vektorlar shaklida yozilishi. Ushbu belgilashlarni kiritamiz:

C = ( c₁, c₂, …, c_n ), X = ( x₁, x₂, …, x_n ) bo`lib, CX = c<sub>1</sub>x<sub>1</sub> + c<sub>2</sub>x<sub>2</sub> + …… + c<sub>n</sub>x<sub>n</sub> skalar ko`paytma bo`lsin. Bu holda chiziqli programmalash masalasini vector ko`rinishda quyidagicha ifodalash mumkin:
F=CX
chiziqli funksiya minimumga ega bo`ladigan X vektorning
P₁x₁ + P₂x₂ + … + P_nx_n = P₀, X≥0 (6)
shartlarni qanoatlantiruvchi qiymatni toping.


2. Matritsa shaklida yozilishi. PX = P₀ X≥0 shartlarni qanoatlantiruvchi F = CX chiziqli funksiya minimum qiymatga ega bo`ladigan X vektorning qiymatini toping, bunda C = ( c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub> ) satr matritsa,
ustun matritsa va P = ( a<sub>ij</sub> ) sistema matritsa hamda ustun matritsa bo`ladi.


3. Yig`indi belgisi orqali yozilishi.

Shartlarni qanoatlantiruvchi chiziqli funksiya minimumga ega bo`ladigan x<sub>j</sub> o`zgaruvchilarning qiymatini toping.
1 – ta`rif. (2) va (3) shartlarni qanoatlantiruvchi X = ( x<sub>1</sub> , x<sub>2</sub> , …. , x<sub>n</sub> ) vektor chiziqli programmalash masalasining mumkin bo`lgan yechimi yoki qisqacha rejasi deyiladi.
2 – ta`rif. (6) yoyilmaga kiruvchi x<sub>i</sub> larning musbat hadli P<sub>i</sub> = ( i = 1, 2, …, m) vektorlari chiziqli bog`lanmagan bo`lsa, X = ( x<sub>1</sub> , x<sub>2</sub> , …. , x<sub>n</sub>) reja tayanch reja deyiladi.
3 – ta`rif. Tayanch reja m ta musbat komponentlarga ega bo`lsa, unga maxsusmas, aks holda maxsus reja deyiladi.
4 – ta`rif. Chiziqli funksiya minimum (maksimum) qiymatga ega bo`ladigan rejaga chiziqli programmalash masalasining optimal rejasi deyiladi.

Simpleks usuli birinchi bo`lib amerikalik olim D.Dansig tomonidan 1949 – yili taklif etilib, keyinchalik 1956 – yilda Dansig, Ford, Fulkeron va boshqalar tomonidan to`la rivojlantirildi. Lekin 1939 – yilda rus matematigi L.V.Kantorovich va uning shogirdlari asos slogan yechuvchi ko`paytuvchilar usuli simpleks usulidan k`op farq qilmaydi. “ Simpleks “ so`zi n o`lchovli fazodagi n + 1 ta uchga ega bo`lgan oddiy qavariq ko`pyoqni ifodalaydi. Simpleks bu

ko`rinishdagi tengsizliklarning yechimlari sohasidir.
Simpleks usuli yordamida chiziqli programmalashning ko`pgina masalalarini yechish mumkin. Bu usul yordamida chekli qadamlarda optimal yechimlarni topish mumkin. Har bir qadamda shuday mumkin bo`lgan yechimlarni topish kerakki, maqsad funksiyasining qiymati oldingi qadamdagi qiymatidan kata bo`lsin. Bu jarayon maqsad funksiyasi optimal ( maksimum yoki minimum ) yechimga ega bo`lguncha davom ettiriladi.

Simpleks usulini ishlatganda jadvallarni ketma – ket almashtirish ancha qulay bo`ladi. Jadvalni tuzishga o`tamiz:

1. Eng yuqoridagi m+1 satrga maqsad funksiyaning koeffitsiyentlarini joylashtiramiz;
2. Jadvaldagi yuqoridagi ikkinchi satriga x₁, x₂, …., x_n , y₁, y₂, …., y_m o`zgaruvchilarni yozamiz;
3. x₁, x₂, …., x_n larning koeffitsiyentlari jadvalning asosiy qismini tashkil qiladi (asosiy matritsa) y₁, y₂, …., y_m o`zgaruvchilarning koeffitsiyentlari esa bosh diagonal bo`yicha yozilib, birlik matritsani tashkil etadi;
4. Jadvalning oxirgi satri indekslar satri deyiladi va bu satr maqsad funksiyasida qatnashuvchi o`zgaruvchilarning koeffitsiyentlari teskari ishora bilan olingan koeffitsiyentlari orqali to`ldiriladi.
Natijada quyidagi jadval hosil bo`ladi:

Bu jadvalga asoslanib 1 – simpleks jadvalni tuzamiz. Dastlabki berilganlarning asosiy jadvalini tahlil qlamiz. Indekslar satrini tahlil qilganda satr elementlarining musbat va manfiyligiga e`tabor beramiz. Agar indeks satri elementlarining hammasi musbat bo`lsa, u holda mumkin bo`lgan yechimni o`zgartirib bo`lmaydi va bu yechim optimal yechim bo`ladi. Faraz qilaylik, indeks satri elementlarining ichida bir nechta manfiy sonlar mavjud va bu manfiy son –c₁ ga teng bo`lsin. –c<sub>1</sub> ni qora chiziqli to`rtburchak ichiga olamiz. Bu ustun yechuvchi ustun deyiladi. –c₁ joylashgan ustun elementlarini ham qora chiziq bilan chizilgan to`rtburchak ichiga olamiz. Bu yerda shuni ham aytish kerakki, agar bordi – yu indeks satrida bir –biriga teng bir necha kichik manfiy sonlar bo`lsa, u holda chap tomondan boshlab 1 – katakdagi manfiy sonni tanlaymiz. Yechuvchi satrni topish uchun o`zgaruvchilar ustundagi sonlarni kalitli ustundagi mos musbat sonlarga bo`lib, ular ichidan eng kichik musbat sonni tanlab olamiz.
Faraz qilaylik, bu son b₁/a₁₁ bo`lsin, ya`ni

Birinchi simpleks jadvalda S₁, S₂, … , S_m+1 ning qiymatlari quyidagicha topiladi: