Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

Симплекс жадвал устида тартиб билан қуйидаги ишларни бажариш керак:

.

• Дастлабки симплекс жадвал

	C CБ		С1	с2	...	cm	cm+1	...	cn
b,ai Aб		b	a1	a2	...	am	am+1	...	an
a1	c1	x1	1	0	...	0	x1 m+1	...	x1n
a2	c2	x2	0	1	...	0	x2 m+1	...	x2n
...	...	...	...	...	...	...	...	...	...
am	cm	xm	0	0	...	1	xm m+1	...	xmn
Z			c1	c2	...	cm		...
Z-C			0	0	...	0		...

мисол

• Корхонада тўрт хил маҳсулот тайёрланади. Бирлик маҳсулотларнинг сотув нархлари мос равишда 2,1,3 ва 5 минг сўмдан бўлсин. Маҳсулотларни тайёрлаш учун энергия, хомашё ва меҳнат сарфланади. Бирлик маҳсулот учун сафланадиган ресурслар миқдори қуйидаги жадвалда келтирилган.

	1 хил маҳсулот	2 хил маҳсулот	3 хил маҳсулот	4 хил маҳсулот	ресурслар
Энергия	2	3	1	2	30
Хомашё	4	2	1	2	40
Меҳнат	1	2	3	1	25

• Маҳсулотларни ишлаб чиқаришнинг шундай режасини тузиш керакки, маҳсулотларнинг сотув нархлари йиғиндиси максимал бўлсин.

• Бу иқтисодиёт масаласини ечиш учун унинг математик моделини тузамиз. Шу мақсадда х1, х2, х3, х4 лар орқали режалаштирилган маҳсулотлар миқдорларини белгилаймиз. Уларнинг нархи

• бўлади.
• Маҳсулотларга сарфланадиган энергия миқдори

• хомашё миқдори

• меҳнат миқдори

• Масала шартига кўра, қуйидаги чизиқли программалаштириш масаласига эга бўламиз:

• Бу масалани симплекс метод ёрдамида ечиш учун уни каноник кўринишга келтирамиз. Шу мақсадда юқоридаги тенгсизликларга мувозанатловчи, ёрдамчи, х5, х6 ва х7 миқдорларни қўшамиз. Бу миқдорларни иқтисодий талқин этсак, улар қаралаётган режа учун эркин ресурсларни англатади. Натижада қуйидаги каноник масалага эга бўламиз:

• Бу масала учун (0,0,0,0,30,40,25) базис режа бўлади ва унга

• баъзис мос келади.

• Юқорида баён этилган алгоритм асосида биринчи симплекс жадвални тўлдирамиз

	Сi СБ		2	1	3	5	0	0	0
b,ai aБ		b,x	a1	a2	a3	A4	a5	a6	a7
a5	0	30	2	3	1	2	1	0	0	15
a6	0	40	4	2	1	2	0	1	0	20
a7	0	25	1	2	3	1	0	0	1	25
Z		0	0	0	0	0	0	0	0
Z-C			-2	-1	-3	-5	0	0	0
a4	5	15	1	3/2	1/2	1	1/2	0	0	30
a6	0	10	2	-1	0	0	-1	1	0
a7	0	10	0	1/2	5/2	0	-1/2	0	1	4
Z		75	5	15/2	5/2	5	5/2	0	0
Z-C			3	13/2	-1/2	0	5/2	0	0
a4	5	13	1	7/5	0	1	3/5	0	-1/5
a6	0	10	2	-1	0	0	-1	1	0
a3	3	4	0	1/5	1	0	-1/5	0	2/5
Z		77	5	38/5	3	5	12/5	0	1/5
Z-C			3	33/5	0	0	12/5	0	1/5

• Демак иккинчи итерация натижасида учинчи қадамда оптималлик шарти бажарилди. Оптимал режа хопт=(0,0,4,13,0,10,0) бўлиб, мақсад функциянинг жоиз максимал қиймати

• бўлади.
• Изоҳ. Ҳар бир жадвалнинг Z сатридаги учинчи катакда мақсад функциянинг мос режадаги қиймати ҳосил бўлади ва ҳар бир итерацияда бу қиймат ошиб боради.

Сунъий базис вектор усулининг қўлланилиши

• Бирлик матрица ёрдами билан оптимал ечимга ўтишга ёрдам берадиган ечимни тузиш мумкин. Агар чизиқли программалаштириш масаласининг чегаравий шартлари AX ≤В кўринишда берилган бўлса, қўшимча ўзгарувчилар киритиб, тўғридан тўғри симплекс усул алгоритмидан фойдаланиш мумкин.

• Амалда учрайдиган кўп чизиқли программалаштириш масалалари ечимга эга бўлган ҳолда бирлик матрицани ўз ичига олмайди. Бундай масалаларни ечиш учун “сунъий базис вектор” усул қўлланилади.

Кенгайтирилган чизиқли программалаштириш масаласини тузиш

• Умумий ҳолда берилган чизиқли программалаштириш масаласини кўрамиз:
• (1)
• x10, x20,..., xm0, xm+10,...., xn0 (2)
• ymin=c1x1+ c2x2+.... +cnxn (3)

• Демак, симплекс методни бевосита қўллаб бўлмайди. Бу ҳолда Дж. Данциг масалани ечишнинг икки фазали методини таклиф этган. Биринчи фаза (1)-(3) масала асосида, (2) мувозанатни сунъий равишда бузишга асосланган қуйидаги ёрдамчи масалани тузишдан иборат:

• (4)

• (5)

• (6)

• Бу ерда

• - ўзгарувчилар сунъий ўзгарувчилар бўлиб, х=(0,0,...,0,b1,b2,...,bm) (4)-(6) масаланинг базис режаси бўлади, чунки бу ҳолда ҳам

• деб олиш мумкин.
• Демак, ёрдамчи масалани симплекс метод ёрдамида ечиш мумкин. Асосий масала ва ёрдамчи масалалар орасидаги боғланиш қуйидаги теоремада ўз ифодасини топган.

теорема

• (2)-(3) масаланинг жоиз режага эга бўлиши учун (5)-(6) масала ечимида
• (6) шартнинг бажарилиши зарур ва етарлидир.

мисол

• Қуйидаги каноник масалани сунъий базис усули ёрдамида ечинг

Ечиш

• Бу масалада бўлгани сабабли, асосий
• чеклашлардаги иккинчи тенгламани -1 га кўпайтириб, ҳолатга олиб келамиз:
• Бу масалага мос сунъий масала қуйидагича бўлади.

.

• Бу масаланинг ечимини симплекс усул ёрдамида изласа бўлади, чунки масала каноник кўринишда бўлиб, х0=(0,0,0,0,4,1)
• бузилмаган базис режадир. Ечимни излаш жараёни қуйидаги жадвалда келтирилган

			2	1	3	1
	С СБ		0	0	0	0	-1	-1
А АБ		x0	a1	a2	a3	a4	a5	a6
a5	-1	4	1	2	5	-1	1	0
a6	-1	1	1	-1	-1	2	0	1
Z		-5	-2	-1	-4	-1	-1	-1
Z-C			-2	-1	-4	-1	0	0
a3	0	4/5	1/5	2/5	1	-1/5	1/5	0
a6	-1	9/5	6/5	-3/5	0	9/5	1/5	1
Z		-9/5	-6/5	3/5	0	-9/5	-1/5	-1
Z-C			-6/5	- 3/5	0	-9/5	4/5	0
a3	3	1	1/3	1/3	1	0
a4	1	1	2/3	-1/3	0	1
Z		4	5/3	2/3	3	1
Z-C			-1/3	-1/3	0	0
a2	1	3	1	1	3	0
a4	1	2	1	0	1	1
Z		5	2	1	4	1
Z-C			0	0	1	0