Чизиқли программалаш масалалари (чпм) ларни ечишда Симплекс усули алгоритми ва унинг моҳияти

ij
A
a





A n
n m
 

тўғри тўртбурчак шаклидаги матрица.


1
2
, ,...,
n m
С
с с
с



сатр матрица,
1
2
n m
х
х
Х
х















устун матрица,
1
2
m
b
b
B
b
 
 
 


 
 
 
устун 
матрица.
Энди симплекс усулинингалгоритмига ўтамиз. Бунинг учун биз олдин 
базис ўзгарувчиларни танлаб олишимиз керак бўлади, улар сони 
m
захиралар(ресурслар) сонига тенг бўлиши керак. Базис ўзгарувчиларга мос 
келувчи шартлар матрицаси 
А
нингустунлари бирлик қийматга эга бўлиши 
керак. Базис ўзгарувчиларнинг қийматлари тенгламанинг ўнг томонидаги 

---

3 
қийматларига тенг қилиб олинади. Агар шартлар системаси бу талабларга 
мос келмаса, у холда уни аввал шу кўринишга келтириб олиш керак бўлади. 
Шундан сўнг биринчи симплекс жадвалини тузишга ўтамиз, у қуйидаги 
кўринишда бўлади:
1-жадвал. 
I
𝐶
𝑗
 
 
𝐶
𝑘𝑖
 
𝐶
1
 
𝐶
2
 
𝐶
3
 
 
𝐶
𝑛+𝑚−1
 
𝐶
𝑛+𝑚
 
 
 
 
 
базис 
А
1
 
А
2
 
А
3
 
 
А
𝑛+𝑚−1
 
А
𝑛+𝑚
 
В 
𝛿
𝑖
 
1 
𝐶
𝑘1
 
𝑋
𝑘1
 
𝑎
11
 
𝑎
12
 
𝑎
13
 
 
𝑎
1 𝑛+𝑚−1
 
𝑎
1 𝑛+𝑚
 
𝑏
1
 
 
2 
𝐶
𝑘2
 
𝑋
𝑘2
 
𝑎
21
 
𝑎
22
 
𝑎
23
 
 
𝑎
2 𝑛+𝑚−1
 
𝑎
2 𝑛+𝑚
 
𝑏
2
 
 
 
 
 
 
 
 
 
 
 
 
 
m-1 
𝐶
𝑘
𝑚−1
 
𝑋
𝑘
𝑚−1
 
𝑎
𝑚−1 1
 
𝑎
𝑚−1 2

 
𝑎
𝑚−1 𝑛+𝑚
 
𝑎
𝑚−1 𝑛+𝑚
 
𝑏
𝑚−1

m 
𝐶
𝑘
𝑚
 
𝑋
𝑘𝑚
 
𝑎
𝑚 1
 
𝑎
𝑚 2
 
 
 
𝑎
𝑚 𝑛+𝑚−1
 
𝑎
𝑚 𝑛+𝑚
 
𝑏
𝑚
 
 
 
 
j
 
 
 
 
 
 
 
 
1- жадвалда базис ўзгарувчилар 
1
2
,
,...,
m
k
k
k
x
x
x
деб,уларнингқийматлари 
эса 
мос 
равишда 
тенгламанингўнгтомонидаги
1
2
, ,...,
.
m
b b
b
қийматларгатенгдебқабул қилинган. Базис ўзгарувчиларга мос келувчи1-
жадвал устунлари бирга тенг бўлиши керак (биттаси бирга қолганлари нолга 
тенг бўлиши керак). Қолган барча базис бўлмаган ўзгарувчилар нолга тенг 
деб олинади. 
Жадвалга мос келувчи ечимнинг оптималлик меъзонини қуйидагича 
талқин қилишимиз мумкин. Жадвалнинг хар бир 
А
1
дан 
А
n+m
гача устуни учун
∆
𝑗
лар ҳисобланади: 
1
,
1, 2,..., ,
1,
.
i
m
j
ij
k
j
i
a
c
c
j
n n
n
m

 






(5.9) 

---

4 
Агар 
j

қийматлари орасида манфий қийматлар бўлмаса у холда бу 
жадвалга мос режа оптимал деб хулоса қилинади ва ҳисоблаш тўхтатилади. 
Агар 
j

қийматлари орасида манфий қийматлар бўлса, бу режа оптимал 
бўлмайди ва уни яхшилаш керак бўлади. Режани яхшилаш босқичма-босқич 
давом эттирилади. Манфий 
j

орасидан энг кичиги танланади ва танланган
j

устун хал қилувчи деб эълон қилинади, уни жадвалда(→) билан белгилаш 
мумкин.Шундан сўнг қуйидаги қийматлар аниқланади: 
,
1, 2,..., ,
i
i
il
b
i
m
a



(5.10) 
бу ерда 
l

хал қилувчи устун номери.Агар қаторда
0
il
a

бўлса, бундай 
қатор ўтказиб юборилади. 
i

нинг қийматларидан минимали аниқланади ва 
берилган 
S

га мос 
S
хал қилувчи деб эълон қилинади.Хал қилувчи устун ва 
хал қилувчи сатр кесишмасида жойлашган
a
Sl
элемент хал қилувчи элемент 
деб эълон қилинади. Шундан сўнг кейинги симплекс жадвални тўлдиришга 
ўтамиз. Бу жараён чизиқли алгебраик тенгламалар ечишнинг номаълумларни 
кетма кет йўқотиш усулига ўхшаш олиб борилади.Аввало хал қилувчи 
элемент қаторидаги элементларни хал қилувчи элементга бўламиз. Бунда ҳал 
қилувчи элемент ўрнида бирнихосил қиламиз.Кейин хал қилувчи элемент 
қаторидаги сонларни қолган қатор элементларидан, мос сонга кўпайтириб 
айирамиз, натижада хал қилувчи устунимизда қолган сонлар нолга айланади. 
Биз кўраётган холда мос кўпайтувчилар 
,
1, 2,...,
1,
1,..., .
il
a i
s
s
m



га тенг 
бўлади Шундан сўнг иккинчи симплекс жадвалига ўтамиз, бу жадвалда ҳам 
юқорида бажарилган амалларни такрорлаймиз. Бу жараён оптимал режага 
эришгунимизча давом эттирилади. 
Энди олдинги мавзуда ўтилган (4.1)-(4.3) масалани симплекс усулида 
ечилишини кўриб чиқамиз. 

---

5 


1
2
1
2
1
2
1
2
1
2
1
2
0,1
0,3
30
0,5
0, 2
45
0,1
0,1
12
0;
0
,
1000
1400
max.
x
x
x
x
x
x
x
x
L x x
x
x


















Сунъий 
3
4
5
,
,
.
x x x
ўзгарувчиларни тенгсизликнинг чап томонига киритиб 
масаланиканоник кўринишга келтириб оламиз 


1
2
3
1
2
4
1
2
5
1
2
1
2
3
4
5
0,1
0,3
30
0,5
0, 2
45
0,1
0,1
12
,
1000
1400
0
0
0
max.
x
x
x
x
x
x
x
x
x
L x x
x
x
x
x
x

















      

Бу тенглама учун биринчи симплекс жадвалини тузиб оламиз: 
1-жадвал 
i
𝐶
𝑗
 
 
𝐶
𝑘𝑖
 
1000 
1400 
0 
0 
0 
 
 
 
 
Базис
 
А
1
 
А
2
 
А
3
 
А
4
 
А
5
 
В 
𝛿
𝑖
 
1 
0 
𝑋
3
 
0.1 
0.3 
1 
0 
0 
30 
100 
2 
0 
𝑋
4
 
0.5 
0.2 
0 
1 
0 
45 
225 
3 
0 
𝑋
5
 
0.1 
0.1 
0 
0 
1 
12 
120 
 
 
J 
-1000 -1400 
→
 
0 
0 
0 
 
 
 
Биринчи жадвални ҳисоб-китобларсиз тўғридан тўғри масалани шарти 
бўйича тўлдирамиз. Бу ерда 
3
4
5
,
,
x x x
базис ўзгарувчилар ҳам масала 
берилишидан олинади.Жадвалда бу ўзгарувчиларнинг мос қийматлари 
устунида бир турибди. Базис ўзгарувчилари нархлари кўрситилган устунида 
ҳам нол турибди, яъни
с
3
=с
4
=с
5
=
0. Энди 
j
k
j
j
c
A
c
  

ни ҳисоблаймиз.
j
k
j
j
c
A
c
  


---

6 
1
0 0,1 0 0,5 0 0,1 1000
1000
  
 
 

 
2
0 0,3 0 0, 2
0 0,1 1400
1400.
  
 
 

 
Буерда хал қилувчи элемент иккинчи устунда бўлади. Жадвалда у 
стрелка билан белгиланди. Жадвалда 
j

қиторда манфий қийматлар бўлгани 
учун,бу қатордаги 


1
2
3
4
5
0;
0;
30;
45;
12
x
x
x
x
x





ечимлар режаси 
оптимал бўлмайди.
2
,
1, 2,3.
i
i
i
b
i
a



формула бўйича1 чи жадвалдаги 
i

устунни тўлдирамиз.Топилган натижалар ичидан 
i

нинг энг кичик қиймати 
100 тенг экан, шунинг учун биринчи қатор хал қилувчи бўлади. Жадвалда бу 
қатор стрелка билан белгиланган.Хал қилувчи элемент0,3ини белгилаб 
оламиз. Иккинчи симплекс жадвални тўлдиришни бошлаймиз. Бу жадвални 
ўлчами аввалгиси билан бир хил бўлади. Жадвални тўлдиришни хал қилувчи 
қатордан бошлаймиз. Қатордаги ҳамма сонларни 0,3 га бўламиз. 
3-жадвал. 
i
𝐶
𝑗
 
 
𝐶
𝑘𝑖
 
1000 
1400 
0 
0 
0 
 
 
 
 
баз
 
А
1
 
А
2
 
А
3
 
А
4
 
А
5
 
В 
𝛿
𝑖
 
1 
1400 
𝑋
2
 
1/3 
1 
10/3 
0 
0 
100 300 
2 
0 
𝑋
4
 
13/30 0 
-2/3 
1 
0 
25 
16000/13 
3 
0 
𝑋
5
 
2/30 
0 
-1/3 
0 
1 
2 
30 
 
 
j 
-
1600/3
0 
14000/3 0 
0 
 
 
 
Жадвалда қолган қатор катакларини юқорида айтилган ҳисоблашлар 
орқали тўлдирилади. Янги хосил бўлган хал қилувчи қатор элементларини
0,2 га кўпайтириб иккинчи қатор элементларидан айириб, шу қаторга ёзамиз, 
худди шундай учинчи қаторни0,1 га кўпайтириб юқоридаги амални 
бажарамиз. Бу жадвалга мос режа 
2
4
5
1
3
100;
25;
2;
0;
0.
x
x
x
x
x






---

7 
тенг бўлади. Топилган режани оптималикка текширамиз. 
j

ҳисоблаймиз: 
1
2
1
1600
1400
1000
;
1400 1 1400
0;
3
3
 
 
 
 
 

3
10
1400
1400
0
.
3
3
 

 
Бу 
j

қаторда манфий қийматлар борлиги учун тўртинчи симплекс 
жадвалига ўтамиз. Худди аввалгидек хал қилувчи қатор элементларини хал 
қилувчи элементга бўлиб ёзиб оламиз. 
4 -жадвал. 
i
𝐶
𝑗
 
 
𝐶
𝑘𝑖
 
1000 
1400 
0 
0 
0 
 
 
 
баз
 
А
1
 
А
2
 
А
3
 
А
4
 
А
5
 
𝑏
𝑖
 
1 
1400 
𝑋
2
 
0 
1 
5