Iqtisodiy jarayonlarda optimallashtirish usullarini qo’llash

2.2. Chiziqli programmalashtirish masalasini simpleks usulda yechish.

Endi chiziqli programmalashtirish masalasini yechishning simpleks usuli bilan umumiy holda tanishamiz.

Masala. (2.1)

chiziqli funksiyaning

(2.2)

(2.3)

cheklash shartlarini qanoatlantiruvchi minimum (maksimum) qiymatini toping Ma’lumki, chiziqli programmalashtirishtirishning umumiy masalasi tenglamalar sistemasi orqali ifodalanadi. Shuning uchun (2.2) ni yangi o’zgaruvchilar kiritish yo’li bilan tenglik shaklida ifodalaymiz.

(2.4)

Maqsad funksiyasi esa quyidagi ko’rinishni oladi. (2.5)

(2.4) sistemani vektor shaklida yozsak:

(2.6)

yoyilma hosil bo’ladi, bunda

, ,…, , , ,..,

vektorlar m o’lchovli fazoning chiziqli bog’lanmagan birlik vektorlari bo’lib, bu fazoning bazisini tashkil etadi. Shuning uchun, (2.6) yoyilmada bazis o’zgaruvchilari uchun larni olib, ozod o’zgaruvchilarni 0 ga teng deb, hamda ekanligini hisobga olib, birlik vektorlar bo’lganligi uchun

(2.7)

boshlang’ich yechimni hosil qilamiz. (2.6) yechim yoyilmaga mos kelib, vektorlar chiziqli bog’lanmagan, demak boshlang’ich olingan yechim tayanch yechim ham bo’ladi. Chiziqli funksiyaning bu boshlang’ich yechimga mos qiymatini hisoblaymiz.

(2.8)

Istalgan vektor bazis vektorlari orqali yagona yoyilmaga: (2.9) ega bo’ladi, shuning uchun vektor yoyilmasiga bu bazisda chiziqli funksiyaning yagona (2.10)

qiymati mos keladi. vektorga mos chiziqli funksiyadagi koeffitsiyentlari bo’lsin. Quyidagi teoremani isbotsiz keltiramiz:

Teorema. Biror vektor uchun ( ) baho bajarilsa, yechim optimal bo’lmaydi va shunday yechimni topish mumkinki, ( ) tengsizlik bajariladi.

Natija. Biror yechim va barcha vektorlar bazisdagi yoyilmasi uchun ( ) shart bajarilsa, yechim optimal bo’ladi. Endi simpleks jadvalni umumiy holda keltiramiz.