2-машғулот. Чизикли программалаштириш масаласини ечишининг симплекс–усули

Симплекс-усул алгоритми

Чизиқли программалаштириш масаласини симплекс-усул ёрдамида ечиш учун қуйидаги алгоритм ишлатилади.

1. ни топиш. A матрицани ва b векторни дастлабки базисда ёзиш, яъни , (x – вектор базис план бўлгани учун охирги формула ўринлидир).
2. Ҳар бир j (j=1,2,...,n) учун баҳолаларни ҳисоблаш:
.
Агар барча бўлса, масални ечиш жараёнини тўхтатиш: қаралаётган базис план оптималдир – z_max= . Агар бирорта j учун бўлса, у ҳолда
3. Шундай баҳони излаш керакки, барча k=1,2,...,m лар учун бўлсин. Агар шундай мавжуд бўлса, масалани ечиш жараёнини тўхтатиш. Мақсад функцияси планлар тўпламида юқоридан чегараланмаган. Агар бундай мавжуд бўлмаса, у ҳолда
4. Бирорта ни (одатда ) танлаш. Барча шартни қаноатлантирувчи k учун ни ҳисоблаш ва булар ичидан энг кичигини топиш ( бўлсин).
5. Янги базис планга ўтиш.
2- кадамга ўтиш.
Алгоритм тугади.
Ҳар бир янги базис паланга ўтиш кадам (итерация) деб аталади.

4. 
   Симплекс-усулни жадваллар ёрдамида қўллаш
   

Чизиқли программалаштириш масаласини симплекс усул ёрдамида ечишни жадвал ёрдамида ҳам бажарса бўлади. Бунинг учун ҳар бир итерацияда янги симплекс жадвал тузилади.

c\c			c1	c2	. . .	cs	. . .	cn
	a\а	b	a1	a2	. . .	as	. . .	an	j
		x10	x11	x12	. . .	x1s	. . .	x1n
		x20	x21	x22	. . .	x2s	. . .	x2n
. . .	. . .	. .	. . .	. . .	. . .	. . .	. . .	. . .
		xr0	xr1	xr2	. . .	xrs		xrn
. . .	. . .	. ..	. . .	. . .	. . .	. . .	. . .	. . .
		xm0	xm1	xm2	. . .	xms	. . .	xmn
		z	1	2	. . .	s	. . .	n

Янги симплекс-жадвал тузиш учун тўғри тўртбурчак қоидаси қўлланилади. Бу қоидани -баҳолар қатори учун ҳам қўллаш мумкин.

Мисол.
z=2x₁-x₂+3x₃+2x₄  max, 2x₁+3x₂-x₃+2x₄+x₅=4,
x₁-2x₂+5x₃-3x₄-x₆=1, 4x₁+10x₂+3x₃+x₄+x₇=8,
x_j0, j=1,2,...,7,
масалани қараймиз. Бу чизиқли программалаштириш масаласининг дастлабки базис плани (1;0;0;0;2;0;4) маълум бўлсин. Бу масала учун m=3, n=7,
,
c'=(2;-1;3;2;0;0;0), rankA=3. Дастлабки базис план учун базис матрица , унинг тескариси . матрицани ҳисоблаб дастлабки симплекс –жадвал тузамиз:

c\с			2	-1	3	2	0	0	0
	a\a	b	a1	a2	a3	a4	a5	a6	a7
2	a1	1	1	-2	5	-3	0	-1	0
0	a5	2	0	7	-11	8	1	2	0	1 /4
0	a7	4	0	18	-17	13	0	4	1	4/13
		2	0	-3	7	-8	0	-2	0

Бу жадвалдан дастлабки базис планинг оптимал эмаслиги кўкриниб турибди (баҳолар вектори кординаталари ичида манфийлари бор).

Максад функциясининг чегараланмаганлиги ҳақидаги теорема шартлари бажарилмайди. Шунинг учун min ₄, s=4 эканлигини аниқлаб ; ни топамиз. x_rs=8 – ҳал қилувчи элементдан фойдаланиб янги симплекс жадвал тузамиз.

c\с			2	-1	3	2	0	0	0
	a\a	b	a1	a2	a3	a4	a5	a6	a7
2	a1	7/4	1	5/8	7/8	0	3/8	-1/4	0	2
2	a4	1/4	0	7/8	-11/8	1	1/8	1/4	0
0	a7	3/4	0	53/8	7/8	0	-13/8	3/4	1	6/7
		4	0	4	-4	0	1	0	0

Бу жадвалдан янги базис план (7/4; 0;0;1/4; 0;0;3/4) эканлигини, мақсад функцияси қиймати 4 эканлигини, ҳамда бу базис планнинг оптимал план эмаслигини аниқлаймиз. Яна икки итерациядан сўнг қуйидаги симплекс-жадвал ҳосил қиламиз.

c\с			2	-1	3	2	0	0	0
	a\a	b	a1	a2	a3	a4	a5	a6	a7
0	a5	1/2	1/2	-3	0	0	1	-1/2	-1/2
2	a4	37/14	17/4	4	0	1	0	3/14	5/14
3	a3	25/14	13/14	2	1	0	0	-1/14	3/14
		149/14	45/14	15	0	0	0	3/14	19/14

Охириги симплекс жадвалда баҳолар манфиймас бўлгани учун қаралаётган масаланинг оптимал плани x⁰=(0;0;25/14;37/14;1/2;0;0) бўлиб, мақсад функциясининг оптимал қиймати z_max=149/14 га тенг.

Муаммоли масала ва топшириқлар

Қуйидаги чизиқли программалаштириш масалаларини симплекс усули ёрдамид ҳал қилинг:

1.

2.
3. ;
4.

5. 
   
   
6. 
   )
   

7) 4)

8) 6 )

9)

10)

Мустақил ишлаш учун назорат саволлари

1. 
   Симплекс усулнинг дастлабки қадамида қандай ишлар бажарилади?
   
2. 
   Баҳолар қандай ҳисобланади?
   
3. 
   Қаралаётган базис план оптимал бўлиши учун қандай шартлар бажарилиши керак?
   
4. 
   Қандай шартлар бажарилса мақсад функцияси чегараланмаган деган хулоса қилиш мумкин?
   
5. 
   Янги базис планга ўтиш учун қандай ишлар бажарилади?
   
6. 
   Бошланғич базис план қандай тузилади?