Chiziqli programmalash masalasini simpleks usulida yechish

tengsizlik o‘rinli bo‘ladi.
Isbot. (19) va (20) ni ga ko‘paytirib, mos ravishda (17) va (18) dan ayiramiz. Natijada quyidagilarga ega bo‘lamiz:
(21)
(22)
Agar (21) dagi , vektorlar oldidagi koeffitsentlar manfiy bo‘lmasa, ga mos keluvchi yangi planga ega bo‘lamiz. Ma’lumki noma’lumlar musbat hamda shunday uchun (21) dagi , vektorlarning har biri oldidagi koeffitsiyentlarni manfiy bo‘lmasligiga erishish mumkin. Teoremaning shartiga ko‘ra . Shuning uchun

shu bilan teorema isbot qilindi.
2-teorema. Agar tayanch plan uchun o‘rinli bo‘lsa, u plan optimal plan bo‘ladi.
Isbot. Ixtiyoriy plan olamiz bu plan uchun quyidagilar o‘rinli bo‘ladi:
(23)
(24)
bu yerda - chiziqli funksiyaning plandagi qiymati. Endi ekanligini ko‘rsatamiz. Teoremaning shartiga ko‘ra

yoki

(24) da har bir ni bilan almashtirib quyidagi tengsizlikka ega bo‘lamiz:
(25)
Endi (23) dagi har bir ning o‘rniga uning qiymatini (19) dan keltirib qo‘yamiz:

yoki
(26)
xudi shuningdek, (25) dagi har bir ning o‘rniga uning qiymatini (20) dan qo‘yib quyidagini hosil qilamiz:
(27)
vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi uchun vektorning bu vektorlar orqali faqat bitta yoyilmasini topish mumkin. Demak (26) va (27) dagi vektorlar oldidagi koeffitsiyentlar o‘zaro teng bo‘lishi kerak, ya’ni
(28)
Endi (28) dagi larning qiymatlarini (27) ga qo‘yamiz, natijada
(29)
tengsizlikni hosil qilamiz.
Bundan (18) ga asosan:
Teorema isbot bo‘ldi.
shart tayanch planining optimal bo‘lish sharti (optimallik kriteriysi) bo‘ladi.
3. Simpleks usul algoritmi. Yuqoridagi 1- va 2- teoremalarga asosan berilgan boshlang‘ich plandan boshlab tayanch planlar ketma-ketligini hosil qilib borib, jarayonni optimal yechim topulguncha davom ettirish mumkin. Faraz qilaylik,

masalaning boshlang‘iya tayanch plani, shu planga mos keluvchi o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar sistemasi bo‘lsin. Bu vektorlardan tashkil topgan ( ) matritsani V bilan belgilaymiz. U holda Bundan

va

kelib chiqadi. Bu yerda vektor ustunlar. Simpleks jarayoni boshlashdan avval masalaning vektorlarini quyidagidek gruppalaymiz:

yoki
(30)
Elementlari ayrim qismlardan iborat bo‘lgan (30) matritsani ga ko‘paytiramiz va quyidagiga ega bo‘lamiz:

yoki

So‘ngra har bir uchun ni hisoblaymiz. Agar barcha lar uchun bo‘lsa, 2-teoremaga asosan topilgan tayanch plan optimal plan bo‘ladi. Agar ayirma ba’zi lar uchun musbat bo‘lsa, 1-teoremaga asosan topilgan tayanch plan optimal plan bo‘lmaydi, bu planni optimal planga yaqin bo‘lgan boshqa plan bilan almashtirish kerak bo‘ladi.
Berilgan masalada dastlabki vektorlar - o‘lchovli vektor fazodagi bazisini tashkil qilsin, ya’ni

bo‘lsin, bu yerda - o‘lchovli birlik matritsa. Bu holda bo‘lganligi sababli

va

bo‘ladi. Masalaning berilganlarini quyidagi ko‘rinishdagi jadvalga joylashtiramiz. Chiziqli sistemasi ko‘rinishda berilgan masala uchun deb qabul qilamiz.

1-jadval. Hisoblarning birinchi iteratsiyasi.

B. v

S

…

…

…

…

…

…

…

…

…

…

1

1

0

…

0

…

0

…

…

…

2

0

1

…

0

…

0

…

…

…

0

0

…

1

…

0

…

…

…

0

0

…

0

…

0

…

…

…

0

0

…

0

…

1

…

…

…

m+1

0

0

0

0

…

0

ym+1-sm+1

yk-ck

yj-cj

yn-cn

vektor – ustunni vektor – ustunga skalyar ko‘paytmasidan iborat, ya’ni

va larni jadvalning qatoridagi tegishli ustunlarga joylashtiramiz. Bazis vektorlar uchun har doim bo‘ladi. Agar bo‘lsa, optimal plan bo‘ladi. Bu plandagi chiziqli funksiyaning qiymati ga teng.
Endi kamida bitta uchun bo‘lsin deb faraz qilaylik. Bu holda topilgan tayanch planni optimal planga yaqinroq plan bilan almashtirish kerak, buning uchun

shartni qanoatlantiruvchi vektorni bazisga kiritib, bazisdan

shartni qanoatlantiruvchi vektorni chiqarish kerak bo‘ladi.
Yangi plan uchun vektorlar bazis vektorlar bo‘ladi.
Yangi tayanch planni hosil qilish va uning optimal plan ekanligini tekshirish uchun va vektorlarning bazis vektorlar orqali yoyilmasini hosil qilish kerak. Dastlabki bazis vektorlardan tuzilgan matritsa birlik matritsadan iborat edi, ya’ni

Shuning uchun
(31)
(32)
(33)
(32) dan:
. (34)
ning bu qiymatini (31) ga qo‘yamiz, natijada quyidagiga ega bo‘lamiz:

yoki

Shunday qilib, yangi tayanch plan quyidagi formulalar orqali hisoblanadi:
(35)
Xuddi shuningdek, (34) ni (33) ga qo‘yib vektorning yangi bazis vektorlar bo‘yicha yoyilmasini hosil qilamiz:

bu yerda
(36)
(35) va (36) ni birlashtirib, lar uchun yangi tayanch planni va vektorlarning yangi bazis vektorlar bo‘yicha yoyilmasi formulasini hosil qilamiz:
(37)
Bu formula esa Jordan-Gaussning to‘la ajratish formulasidan iboratdir. Haqiqatan ham, da

yangi bazisga kiritilayotgan vektorning ga (bundan keyin bu elementni aniqlovchi element deb ataymiz) mos keluvchi elementi 1 ga teng bo‘lib, qolgan elementlari 0 ga teng bo‘ladi.
yangi plan uchun

bo‘lganligi sababli, (36) dan foydalanib quyidagi ifodani hosil qilamiz:
(38)
xudi shuningdek, ning qiymatini (35) dan

ifodaga qo‘yib,
(39)
ni topamiz.
Yuqoridagilardan xulosa qilib aytganda, simpleks jadval ustida tartib bilan quyidagi ishlarni bajarish kerak:
1. Har bir uchun lar tekshiriladi. Agar barcha lar uchun bo‘lsa, topilgan plan optimal plan bo‘ladi.
2. Agar birorta uchun bo‘lsa, bazisga kiritiladigan vektor tanlanadi. Bazisga

shartni qanoatlantiruvchi vektor kiritiladi;
3. Bazisdan chiqarilishi kerak bo‘lgan vektor aniqlanadi. Bazisdan
ga mos keluvchi vektor chiqariladi. Agar vektorga mos keluvchi barcha bo‘lsa, chiziqli funksiya quyidan chegaralanmagan bo‘ladi;
4. Aniqlovchi element tanlangandan so‘ng simpleks jadval (37) formula orqali almashtiriladi.
Shunday yo‘l bilan har bir iteratsiyada yangi tayanch plan topiladi. 1 va 2 – teoremaga asosan simpleks usul yo optimal planni beradi, yoki masaladagi chiziqli funksiyaning chekli minimumga ega emasligini aniqlaydi.

1-misol.

Yechish. Masalada o‘zaro chiziqli bog‘liq bo‘lmagan

vektorlar berilgan. Ularni bazis vektorlar deb qabul qilamiz. Bu bazis vektorlarga plan mos keladi. Bu planda chiziqli funksiyaning qiymati bo‘ladi.
Simpleks jadval tuzamiz:
1-i t ye r a s i ya

	B. v	S		0	1	-3	0	2	0
1 2 3		0 0 0	7 12 10	1 0 0	3 -2 -4	-1 4 3	0 1 0	2 0 8	0 0 1
4

Jadvalning 4-qatoriga va larning qiymatini yozamiz. bo‘lganligi sababli bazisga vektorni kiritamiz va

bo‘lganligi sababli bazisdan vektor chiqariladi. Shunday qilib aniqlovchi element bo‘ladi. Simpleks jadvalni (37), (38), (39) formulalar yordami bilan almashtiramiz, natijada quyidagi yangi jadvalga ega bo‘lamiz:
2-i t ye r a s i ya

	B. v	S		0	1	-3	0	2	0
1 2 3		0 -3 0	10 3 1	1 0 0		0 1 0		2 0 8	0 0 1
			-9	0		0		-2	0

Yangi simpleks jadvalda

Shuning uchun bazisga vektor kiritiladi.

demak, bazisdan vektor chiqariladi, aniqlovchi element bo‘ladi. Simpleks jadvalni (37), (38), (39) formulalar yordami bilan almashtirib yana keyingi yangi simpleks jadvalni hosil qilamiz.

3-i t ye r a s i ya

	B. v	S		0	1	-3	0	2	0
1		1	4		1	0			0
2		-3	5		0	1			0
3		0	11	1	0	0		10	1
			-11		0	0			0

Bu simpleks jadvaldan ko‘rinib turibdiki, barcha lar uchun . Demak topilgan plan optimal plan bo‘lib, bu plandagi chiziqli funksiyaning qiymati

ga teng.