Симплекс усули. Бошланғич таянч режани топиш чдмнинг максимумини топиш

• Chiziqli dasturlash masalasini echishning simpleks usuli. Boshlang’ich tayanch rejani topish

СИМПЛЕКС УСУЛИ. БОШЛАНҒИЧ ТАЯНЧ РЕЖАНИ ТОПИШ ЧДМнинг максимумини топиш

(1)
(2)

Юкоридаги (1-4) кадамлар Zj-Cj индекс қаторидаги ҳамма нома’лумларнинг коэффициентлари мусбат бўлгунча давом эттирилади. Хар кадамда янги симплекс жадвал тузилади.

• Юкоридаги (1-4) кадамлар Zj-Cj индекс қаторидаги ҳамма нома’лумларнинг коэффициентлари мусбат бўлгунча давом эттирилади. Хар кадамда янги симплекс жадвал тузилади.
• Zj - Cj индекс қаторидаги ҳамма сонлар мусбат бўлса, берилган ЧДМ оптимал ечимга эга бўлади.

•  4.1- Вазифа. Берилган ЧДМни симплекс усули билан ечинг ва оптимал ечимини аниқланг.
• Zmax= х1+2х2+3х3
• х1 + 2х2 + 3х3  14,
• 2х1 + 2х2 + 5х3  21,
• х1 + х2 - 3х3  10.
• х1 0, х2 0, х3 0

I. Қўшимча но’малумларни киритамиз

• I. Қўшимча но’малумларни киритамиз

ЧДМдаги тенгсизликларни тенгликка айлантириш учун y1 0, y2 0, y3 0 қўшимча нома’лумларни мусбат ишора билан қўшамиз. Мақсад функциясига қўшимча нома’лумлар 0 коэффициент билан киритилади. Натижада берилган ЧДМ қуйидаги кўринишни олади:

• Zmax= х1+2х2+3х3+ 0y1+ 0y2+ 0y3
• х1 + 2х2+ 3х3 + y1 = 14,
• 2х1 + 2х2+ 5х3 + y2 = 21 ,
• х1 + х2- 3х3 + y3 = 10.
• х1 0, х2 0, х3 0 , y1 0, y2 0, y3 0 .

 Берилган тенгламалар системасидан y1 0, y2 0, y3 0 қўшимча нома’лумларни базис нома’лумлар сифатида қабул қиламиз ва бошланғич таянч режани топамиз.

•  Берилган тенгламалар системасидан y1 0, y2 0, y3 0 қўшимча нома’лумларни базис нома’лумлар сифатида қабул қиламиз ва бошланғич таянч режани топамиз.
• Zmax= 0 - ( - х 1-2х2-3х3 + 0y1+ 0y2+ 0y3).
• y1 = 14 - (х1 + 2х2+ 3х3),
• y2 = 21 - (2х 1 + 2х2+ 5х3),
• y3 = 10 - (х1 + х2- 3х3).
• Бу ерда
• х1= х2= х 3 = 0 деб олсак,
• берилган ЧД масаласи бошланғич таянч режа эга бўлади: y 1 = 14, y2 = 21, y 3 = 10, Zmax= 0 .

Базис	Cj	Bi	х1	х2	х3	y1	y2	y3
			c1=1	c2=2	c3=3	c4=0	c5=0	c6=0
y1	c4=0	b1=14	1	2	3	1	0	0
y2	c5=0	b2=21	2	2	5	0	1	0
y3	c6=0	b3=10	1	1	-3	0	0	1
Zj -Cj		0	-1	-2	-3	0	0	0

II. Бошлағич симплекс жадвалини тузиш
Бошланғич симплекс жадвали

III. Оптимал режани топиш

• III. Оптимал режани топиш
• Энди ҳал қилувчи устун, ҳал қилувчи сатр ва ҳал қилувчи элементларни аниқлашга ўтамиз. Бунинг учун:
•  жадвалдаги индекс қаторида келтирилган [-1, -2, -3] сонлардан абсолют қиймати бўйича энг каттаси 3 га тенг. Демак, [х3] устун ҳал қилувчи устун бўлади.
•  озод ҳадлар устунида келтирилган [14 ва 21] сонларни х3 ҳал қилувчи устунинг [3 ва 5] мос мусбат сонларига бўлиб, минимал қийматини аниқлаймиз, я’ни:
• min[bi/aij]=min[14/3, 21/5]= 21/5 .
• Демак, y2 сатр ҳал қилувчи сатр бўлади.

 жадвалдаги ҳал қилувчи устун ва ҳал қилувчи сатрларнинг кесишган катакда жойлашган а32 = 5 сон ҳал қилувчи элемент бўлади. Бу сонни жадвалда тўғри тўртбурчак ичига олиб қўямиз. Биринчи симплекс жадвали

Базис	Cj	Bi	х1	х2	х3▼	y1	y2	y3
			1	2	3	0	0	0
y1	0	14	1	2	3	1	0	0	14/3
y2►	0	21	2	2	[5]	0	1	0	21/5
y3	0	10	1	1	-3	0	0	1	inf
Zj -Cj		0	-1	-2	-3	0	0	0

Бошланғич симплекс жадвалидан кўриниб турибдики, х3 устунда битта манфий сон мавжуд (-3) ва у озод ҳад устунидаги мос сон(10) билан бир хил ишорали эмас. Шунинг учун устунда булиш амали бажарилмайди ва inf қўйилади

Энди иккинчи симплекс жадвалини тузишга ўтамиз.

• Энди иккинчи симплекс жадвалини тузишга ўтамиз.
• Бунинг учун y2 қўшимча нома’лум (Базис номли устундан) базисдан чиқарилиб ўрнига х3 асосий нома’лум базисга киритилади. Cj устунга эса y2 қўшимча нома’лумнинг с5=0 коэффициенти ўрнига х3 асосий нома’лумнинг коэффициенти с3 = 3 ни ёзамиз.

Янги тузиладиган иккинчи симплекс жадвалини қолган элементларини ҳисоблаш Жордан чиқариш усули ёрдамида топилади, я’ни: Иккинчи симплекс жадвали

Базис	Cj	Bi	х1	х2▼	y2	y1	y2	y3
			1	2	3	0	0	0
y1►	0	7/5	-1/5	[4/5]	0	1	-3/5	0	7/4
Х3	c3=3	21/5	2/5	2/5	1	0	1/5	0	21/2
y3	0	113/5	11/5	11/5	0	0	3/5	1	113/11
Zj -Cj		63/5	1/5	-4/5	0	0	3/5	0

Zj -Cj индекс қаторида битта (-4/5) манфий сон мавжуд. Демак, х2 устун ҳал қилувчи устун ва y1 сатр ҳал қилувчи сатр бўлади.

Демак, y1 базис нома’лумлар устунидан чиқарилади ва ўрнига х2 асосий нома’лум киритилади. Иккинчи симплекс жадвалида ҳал қилувчи элемент бўйича симплекс ҳисоблашларини бажарамиз ва учинчи симплекс жадвалини ҳосил қиламиз. Учинчи симплекс жадвали

Базис	Cj	Bi	х1	х2	х3	y1	y2	y3
			1	2	3	0	0	0
Х2	2	7/4	-1/4	1	0	5/4	-3/4	0
Х3	3	7/2	½	0	1	-1/2	1/2	0
х6	0	75/4	11/4	0	0	-11/4	9/4	1
Zj -Cj		14	0	0	0	1	0	0

Охирги симплекс жадвалининг индекс қаторидаги барча сонлар мусбат. Демак берилган масала оптимал ечимга эга.
Асосий нома’лумларнинг қийматлари: х 1 = 0, х 2 = 7/4, х 3 = 7/2.