16. Чизикли дастурлаш масалаларини ечишда симплекс усул алгоритми ва унинг тахлили

16. Чизикли дастурлаш масалаларини ечишда симплекс усул алгоритми ва унинг тахлили

Dastlab berilgan chiziqli programmalashtirish masalasining chegaraviy shartlarida m ta o‘zaro chiziqli bog‘liq bo‘lmagan birlik vektorlar mavjud deb faraz qilinadi. Umumiylikni buzmagan holda bu vektorlar birinchi m ta vektordan iborat bo‘lsin. U holda masala quyidagi ko‘rinishda bo‘ladi:

1. 
   sistemani vektor formada yozamiz:
   

(4)

vektorlar n o‘lchovli vektor fazodagi o‘zaro chiziqli bog‘liq bo‘lmagan birlik vektorlardan iborat bo‘lib, bu fazoning bazisini tashkil qiladi. (1) da o‘zgaruvchilarni bazis o‘zgaruvchilar, o‘zgaruvchilarni esa bazis bo‘lmagan (ozod) o‘zgaruvchilar deb qabul qilib, bazis bo‘lmagan o‘zgaruvchilarni nolga tenglaymiz. Natijada:

(5)

boshlang‘ich yechimni hosil kilamiz. (5) yechimga quyidagi

(6)

yoyilma mos keladi. Bu yoyilmadagi vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi sababli, topilgan boshlang‘ich (5) yechim tayanch yechim bo‘ladi. Berilgan boshlang‘ich rejadan boshlab tayanch rejalar ketma-ketligini hosil qilib borib, jarayonni optimal yechim topilguncha davom ettirish mumkin va bu tayanch yechimlar simpleks jadval va simpleks usul algoritmi asosida optimallikka tekshiriladi.

2. (1) - (4) masalaning berilganlari simpleks jadvalda quyidagi ko‘rinishda bo‘ladi:

Bazis vekt.	Cbaz	P0	c1	c2	…	cm	cm+1	…	ck	…	cn
			P1	P2	…	Pm	Pm+1	…	Pk	…	Pn
P1	c1	b1	1	0	…	0	a1m+1	…	a1k	…	a1n
P2	c2	b2	0	1	…	0	a2m+1	…	a2k	…	a2n
…	…	…	…	…	…	…	…	…	…	…	…
Pl	cl	bl	0	0	…	0	alm+1	…	alk	…	aln
…	…	…	…	…	…	…	…	…	…	…	…
Pm	cm	bm	0	0	…	1	amm+1	…	amk	…	amn
j=Zj-cj	…	m Y0=cibi+c0 ^i=0	1=0	2=0	…	m=0	m m+1 =aim+1ci-cm+1 ^i=0	…	m k =aikci-ck ^i=0	…	m n =ainci-cn ^i=0

Simpleks jadval ustida tartib bilan quyidagi ishlarni bajarish kerak:

1.Har bir j uchun y_j-c_j=D_j lar tekshiriladi. Agar barcha j lar uchun D_jЈ0 bo‘lsa, topilgan yechim optimal yechim bo‘ladi.

2.Agar birorta j uchun y_j-c_j>0 bo‘lsa, bazisga kiritiladigan vektor tanlanadi. Bazisga shartni qanoatlantiruvchi R_k vektor kiritiladi.

3.Bazisdan chiqarilishi kerak bo‘lgan vektor aniqlanadi. Bazisdan

ga mos keluvchi P_l vektor chiqariladi.Agar R_k vektorga mos keluvchi barcha x_ikЈ0 bo‘lsa, chiziqli funksiya quyidan chegaralanmagan bo‘ladi;

4.Aniqlovchi element x_ik>0 tanlangandan so‘ng simpleks jadval almashtiriladi.

Shunday yul bilan har bir iteratsiyada yangi tayanch yechim topiladi. Simpleks usul yoki optimal yechimni beradi, yoki masaladagi chiziqli funksiyaning chekli minimum ga ega emasligini aniqlaydi.

20. Статистик моделлаштиришда энг кичик квадратлар усули.