Режа11. Масаланинг берилиши Масалананинг ечимлари

• Название: Масаланинг берилиши Масалананинг ечимлари
• Дата: 08.12.2022
• Размер: 169.12 Kb.
• Имя файла: Режа11.docx
• Тип: Программа; #834704

Режа.

1. 
   Симплекс усулнинг асосий гояси.
   
2. 
   Симплекс усулининг аналитик берилиши.
   
3. 
   Симплекс жадвал.
   
4. 
   Чизиқли программалаштириш масаласи.
   
5. 
   Чизиқли программалаштириш масаласининг асосий тушунчалари.
   

Масаланинг берилиши



Масалананинг ечимлари

Агар , яъни номаълумлар сони тенгламалар сонидан катта бўлса, юқоридаги чизиқли тенгламалар системаси одатда чексиз кўп ечимга эга бўлади. Иқтисодий масалаларнинг математик моделини ечишда қидирилаётган номаълум катталиклар номанфий бўлганлиги учун берилган чизиқли тенгламалар системасининг номанфий ечимларини топиш муҳим.

Номанфий ечимларни топиш

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

Озод ҳадларни мусбат қилиш

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

Аниқловчи коэффициент

Сўнгра ажратилиши зарур бўлган ўзгарувчини танлаш учун, унинг аниқловчи коэффициентларини хисоблаймиз.

Масалан: ўзгарувчини ажратиб олиш керак бўлса, у ҳолда ўзгарувчининг аниқловчи коэффициентлари қуйидагича топилади. .

Аниқловчи коэффициент бўлганда қаралади. ўзгарувчининг аниқловчи коэффициентлари ичидан аниқловчи коэффициенти энг кичик бўлган қатордаги ўзгарувчи ажратиб (белгилаб) олинади.

Номанфий ечимлар

Агар аниқловчи коэффициентларнинг энг кичигини танлаш қоидасига риоя қилинса, шакл алмаштиришлардан ҳосил бўлган янги чизиқли тенгламалар системаси манфий озод ҳадга эга бўлмайди. Шу жараён кетма-кет бажарилгандан кейин ҳосил бўлган ечимлар номанфий ечимлар бўлади.

Базис ечим

Ажратиб олинмаган ўзгарувчилар нолга тенглаб олинганда ҳосил бўладиган ечим берилган чизиқли тенгламалар системасининг базис ечими дейилади.

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

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

Берилган масала бошланғич таянч ечимга эга бўлсин.

1. 
   Масаланинг шартларидан фойдаланиб бошланғич симплекс жадвал тўлдирилади.
   

Масаланинг берилганларини қуйидаги жадвалга жойлаштирамиз:

Б.В

СБ

Р0

c1

c2

…

cm

cm+1

…

ck

…

cn

АК

Р1

P2

…

Pm

Pm+1

…

Pk

…

Pn

P1 P2 … Pl … Pm

в1 в2 … вk … вm

а11 х21 … хk1 … хm1

х12 х22 … хk2 … хm2

… … … … … …

х1m х2m … хkm … хmm

x1m+1 x2m+1 … xkm+1 … xmm+1

... … … … … …

x1k x2k … xlk … xmk

… … … … … …

x1n x2n … xkn … xmn

j

(АК – аниқловчи коэффициент) C_Б – б.в, Р₀ – озод ҳад, Б.в. – б.в,

2. 
   Ҳар бир j учун y_j-c_j=D_j лар текширилади, бунда агар барча j лар учун
   

D_jЈ0 бўлса, топилган план оптимал план бўлади.

3. 
   Агар лар орасида бирортаси, масалан, ∆ _к бўлиб, к-нчи устундаги барча бўлса, функция қуйидан чегараланмаган бўлади, масала ечимга эга бўлмайди. Масалани ечиш тўхтатилади.
   
4. 
   Агар ∆ мавжуд бўлиб, камида битта бўлса, масалани ечиш давом эттирилиб, топилган ечимдан кўра оптималроқ ечимга ўтилади; бунинг учун аниқланади, бунга мос келган устун йўналтирувчи устун дейилади, бу устунга мос келган Р_к вектор базисга киритилади, кейинги 5га ўтилади.
   
5. 
   Базисдан чиқариладиган вектор аниқланади. шу шартга мос - қатордаги - вектор базисдан чиқарилади. 6 пунктга ўтилади.
   
6. 
   Янги базисга мос келувчи симплекс – жадвал Жордан-Гаусс усулида тўлдирилади, қайта 2 – пунктга ўтилади ва қайтадан - ҳисобланади. Бу жараён оптимал ечим топилгунча қадар ёки ечимни мавжуд эмаслик шарти бажарилганча қадар давом этади.
   

1-масала. Қуйидаги ЧПМ ни симплекс усулда ечамиз:



Чегаравий шартлардаги тенгсизликларни қўшимча ўзгарувчи киритиб, тенгкучли тенгламалар системасига алмаштирамиз, яъни



Белгилаш киритамиз:


Масала шартларини симплекс жадвалга жойлаштирамиз.

Баз.век.	Сбаз	P0	С1 =2	С2 =1	С3 =0	С4 =0	А.К.
			Р1	Р2	Р3	Р4
Р3	0	7	3	1	1	0	7/3
Р4	0	1		-1	0	1	1:1к1
		y0к0			0	0

I қадамда, қаторда бўлганлиги сабабли, топилган таянч ечим - оптимал ечим эмас, масалани ечиш давом этади - кейинги иккинчи қадамга ўтилади. Р₁ – вектор базисга киритилади. Сўнгра -аниқловчи коэффициент (А.К.) аниқланади, бу шарт бажарилган вектор базисдан чиқарилади.

, демак вектор базисдан чиқарилади. 6 пунктдаги формуладан фойдаланиб янги 2 жадвалда тўлдирилган алмаштириш Гаусс усули ёрдамида бажарилади.

i	Баз.вектор	Сбаз	Р0	-2	-1	0	0	А.К.
				Р1	Р2	Р3	Р4
1	Р3	0	4	0		1	-3	4:4к1
2	Р1	-2	1	1	-1	0	1	-

Жадвалда , топилган таянч ечим оптимал эмас, кейинги ечим аниқланади. га мос вектор - Р₂ базисга киритилади. - бунга мос Р₃ - вектор эса базисдан чиқарилади. Базис алмаштириш бажарилиб, янги 3 жадвалда тўлдирилган.

i	Баз.вектор	Сбаз	Р0	-2	-1	0	0	А.К.
				Р1	Р2	Р3	Р4
1	Р2	-1	1	0	1	¼	-3/4
2	Р1	-2	2	1	0	¼	¼
				0	0	-3/4	-1/4

. - масаланинг оптимал ечими.

2-масала. ЧПМ ни симплекс усулда ечамиз:

i	Баз. вектор	Сбаз	Р0	-2	5	0	0	А.К.
				Р1	Р2	Р3	Р4
1	Р3	0	12		3	1	0	12:4к3
2	Р4	0	12	3	4	0	1	12:3к4
						0	1
1	Р1	-2	3	1	¾	¼	0
2	Р4	0	3	0	7/4	-3/4	1

ечим оптимал.

Масалаларни ечишдан аввал қуйидаги маълумотларга аҳамият бериш керак.

Агар ЧПМ да чегаравий шартлар ( ) белги билан, ёки ( =) белги билан боғланган бўлиб, бошлангич ечим маълум бўлмаса, бу хилдаги масалалар сунъий базис ўзгарувчилар киритиш ёрдамида ечилади. ЧПМни чегаравий шартларидаги базис ўзгарувчиси бўлмаган ҳар бир тенгламага сунъий равишда базис ўзгарувчилар қўшамиз, бу ўзгарувчилар мақсад функцияга (min-формадаги) етарлича катта бўлган мусбат М коэффициент билан қўшамиз, бундай ўзгарувчилар «сунъий базис ўзгарувчилар» деб аталади. Ҳосил бўлган масала берилган масалага нисбатан кенгайтирилган нормал кўринишдаги масала деб аталади. Масалани ечиш жараёни симплекс жадвалда симплекс усул билан бажарилади.
Оптималлик критерийси. Оптимал ечимни топиш.

(1)

x₁0, x₂0,..., x_m0, x_m+10,...., x_n0 (2)

y_min=c₁x₁+ c₂x₂+.... +c_nx_n

чизиқли дастурлаш масаласининг режалари мавжуд ва улар хосмас деб фараз қиламиз, яъни барча b_i>0, i=1,m. Масаланинг X=(x₁, x₂,...,x_m) таянч режаси ва унга мос келувчи узаро чизиқли боғлиқ бўлмаган P₁, P₂,..., P_m векторлар системаси маълум бўлсин. У ҳолда

x₁P₁+x₂P₂+...+x_mP_m=P₀ (3) ва x₁c₁+ x₂c_2+...+ x_mc_m=y₀ (4)

Бу ерда y₀ - чизиқли функциянинг X таянч режадаги қиймати, x_i ва c_j (j=1,n) - чизиқли функциянинг коэффициентлари. P₁, P₂, ..., P_m векторлар ўзаро чизиқли боғлиқ бўлмаган векторлар бўлганлиги сабабли ихтиёрий базис бўлмаган P_j векторнинг бу векторлар орқали фақат битта ёйилмасини топиш мумкин: x_1jP₁+x_2jP₂+...+x_mjP_m=P_j, (j=1,n) (5) Бу векторга чизиқли функциянинг x_1jc₁+ x_2jc_2+...+ x_mjc_m=y_j, (j=1,n) (6)

қиймати мос келади, P_j векторга мос келувчи чизиқли функциянинг коэффициентини c_j билан белгилаймиз

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

Берилган бошланғич режадан бошлаб таянч режалар кетма-кетлигини ҳосил қилиб бориб, жараённи оптимал ечим топилгунча давом эттириш мумкин. Фараз қилайлик, X= (x₁,x₂,...,x_m) масаланинг бошланғич таянч режаси, P₁, P₂,...,P_m шу режага мос келувчи ўзаро чизиқли боғлиқ бўлмаган векторлар системаси бўлсин. Бу векторлардан ташкил топган (P₁, P₂,...,P_m) матрицани B билан белгилаймиз. У ҳолда BX=P₀ . Бундан X=B^-1P₀ ва X_j=B^-1P_j келиб чикади. Бу ерда Х=(х₁, х₂,...,х_m) (х_i0), x_j=(х_1j, х_2j,...,х_mj)-вектор устунлар.

Симплекс жараён

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

(Р₀| P₁, P₂,...,P_m | P_m+1,...,P_n) ёки (Р₀|В| P_m+1,...,P_n) (7)

Элементлари айрим қисмлардан иборат бўлган (7) матрицани В^-1 га кўпайтирамиз ва қуйидагига эга бўламиз: (В^-1 Р₀| В^-1 В| В^-1 P_m+1,..., В^-1 P_n) ёки (X|J_m|X_m+1,...,X_n). Сўнгра ҳар бир j=1,n учун y_j-c_j ни ҳисоблаймиз. Агар барча j лар учун y_j-c_j0 бўлса, топилган таянч режа оптимал режа бўлади. Агар y_j-c_j айирма баъзи j лар учун мусбат бўлса, топилган таянч режа оптимал режа бўлмайди, бу режани оптимал режага яқин бўлган бошқа режа билан алмаштириш керак бўлади. Берилган масалада дастлабки P₁, P₂,...,P_m векторлар m ўлчовли вектор фазодаги базисни ташкил қилсин, яъни В=( P₁, P₂,...,P_m)= I _m бўлсин, бу ерда I _m- m ўлчовли бирлик матрица. Бу ҳолда В^-1В=I _m бўлганлиги сабабли Х=Р₀ва Х_j=Р_j бўлади. Чизиқли системаси АХ=В кўринишда берилган масала учун х_i=в_i, x_ij=a_ij деб қабул қиламиз. У_j -j вектор- устунни С вектор -устунга скаляр кўпайтмасидан иборат, яъни у₀= .Y_i= , j=1,n. у₀ ва y_j-c_j ларни жадвалнинг m+1 қаторидаги тегишли устунларга жойлаштирамиз. Базис векторлар учун ҳар доим y_j=c_j=0 бўлади.

Оптимал режа

Агар y_j-c_j0 (j=1,n) бўлса, Х=(х₁, х₂,...,х_m)=(b₁, b₂,...,b_m) оптимал режа бўлади. Бу режадаги чизиқли функциянинг қиймати у₀ га тенг. Энди камида битта j учун y_j-c_j0 бўлсин деб фараз қилайлик. Бу ҳолда топилган таянч режани оптимал режага яқинрок режа билан алмаштириш керак, бунинг учун шартни қаноатлантирувчи Р_l векторни базисга киритиб, базисдан шартни қаноатлантирувчи Р_l векторни чиқариш керак. Янги режа учун P₁, P₂,..., P_l1, P_l1,...,P_lm ,P_k векторлар базис векторлар бўлади.

Оптималликка текшириш

Янги таянч режани ҳосил қилиш ва унинг оптимал режа эканлигини текшириш учун P₀ ва P_j векторларнинг базис векторлар орқали ёйилмасини ҳосил қилиш керак. (P₁, P₂,...,P_m)=I

Шунинг учун

Р₀=х₁ P₁+ х₂ P₂+...+ x_lP_l+...+ х_mP_m (8) Р_k=х_1k P₁+ х_2k P₂+...+ x_lkP_l+...+ х_mkP_m (9)

Р_j=х_1jP₁+х_2jP₂+…+ x _1jP₁ +…+х _mjP_m (10) дан: Р_д = ( Р_л- х_1к Р₁- х_2к Р₂-…-х_mkР_m) (11)

P_l нинг бу қийматини (8) га қўямиз, натижада қуйидагига эга бўламиз:

Р₀=х₁ P₁+х₂P₂+...+[ Р_k- х_1k P₁- х_2k P₂-...-х_mkP_m ]+...+ х_mP_m ёки Р₀=(х₁- х_1k)Р₁+...+ Р_k+...+(х_m- х_mk) P_m

Янги таянч режани ҳисоблаш формулалари

Шундай қилиб, Х₁=(х^’₁, х’₂,...,х’_m) янги таянч режа қуйидаги формулалар орқали ҳисобланади:x^’_i= x_i-- х_ik,(il), x^’_k = , (i=l) (12)

Худди шунингдек, (11) ни (21) га қўйиб Р_j векторнинг янги базис векторлар бўйича ёйилмасини ҳосил қиламиз: Р_j= x^’_1jP₁+ x^’_2jP₂+...+ x^’_kjP_k+...+ x^’_mjP_m, бу ерда x^’_ij= x_ij- х_ik, (il), x^’_kj = , (i=l) (13). (12)ва (13) ни бирлаштириб, j=1,2,...,n лар учун янги таянч режани ва Р_j векторларнинг янги базис векторлар бўйича ёйилмасининг формуласини ҳосил қиламиз:

x^’_ij= x_ij- х_ik, (il), x^’_lj = , (i=l) (14)

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

1.Ҳар бир j учун y_j-c_j=_j лар текширилади. Агар барча j лар учун _j0 бўлса, топилган режа оптимал режа бўлади. 2.Агар бирорта j учун y_j-c_j0 бўлса, базисга киритиладиган вектор танланади. Базисга шартни қаноатлантирувчи Р_k вектор киритилади. 3.Базисдан чиқарилиши керак бўлган вектор аниқланади. Базисдан га мос келувчи P_l вектор чиқарилади. Агар Р_k векторга мос келувчи барча x_ik0 бўлса, чизиқли функция қуйидан чегараланмаган бўлади; 4.Аниқловчи элемент x_ik>0 танлангандан сўнг симплекс жадвал (24) формула орқали алмаштирилади. 5.Шундай йул билан ҳар бир итерацияда янги таянч режа топилади. Симплекс усул ёки оптимал режани беради, ёки масаладаги чизиқли функциянинг чекли минимумига эга эмаслигини аниқлайди.
Математик дастурлаш масаласи

Математик нуқтаи назаридан ўзгарувчиларга маълум (чизиқли ва чизиқсиз) чекламалар қўйилган кўп ўлчовли функциянинг экстремум қийматларини топиш масаласи умумий ном билан математик дастурлаш масаласи деб аталади.

Математик дастурлаш курси олий математика элементлари, чизиқли алгебра ва геометриянинг кўплаб тасдиқ ва натижаларига таянади. Айниқса, чизиқли функция, чизиқли тенглик ва тенгсизликлар ҳамда уларнинг хоссаларидан кенг кўламда фойдаланилади. Шу туфайли уларнинг айрим хосса ва хусусиятларини эслатиб ўтиш ўринлидир.

Иқтисодиётда математик моделлаштиришнинг қўлланилиши. Миқдорларни ҳисоблаш, ўзгарувчиларнинг таъсир кучини аниқлаш орқали объект ҳақида янги маълумотлар олиш;- Иқтисодий назария хулоса ва тушунчаларини аниқ ва ихчам ифодалаш

Турлари

Чизиқли дастурлаш, чизиқсиз дастурлаш, динамик дастурлаш, стохастик дастурлаш.

Чизиқли функция

Ушбу, х₁, х₂, ..., х_n номаълумларга нисбатан чизиқли бўлган, яъни номаълумлар фақат ўзининг биринчи даражаси билан қатнашган z=c₁x₁+c₂x₂+...c_nx_n кўринишдаги функция чизиқли функция деб аталади. бу ерда c₁, c₂,...c_n - берилган ўзгармас, ҳақиқий сонлардир.

Чизиқли тенглик

c₁x₁+c₂x₂+...+c_nx_n=k муносабат чизиқли тенглик деб аталади, бу ерда k-тайин ўзгармас сон.

Чизиқли тенгсизлик

c₁x₁+c₂x₂+...+c_nx_n k муносабат чизиқли тенгсизлик деб аталади, бу ерда

k-ўзгармас сон.

Оптимал ечимни топиш босқичлари

1. Масаланинг қўйилиши. 2.Ўрганилаётган объектнинг моделини тузиш. Бунда масаланинг бош мақсади, ундаги чегаравий шартлар системасини бошқаришдаги таъсири ўрганилади. 3.Масаланинг математик моделини тузиш. 4. Масаланинг ечимини аниқлаш. 5. Ечимни таҳлил қилиш. Бу этап моделни сезгирликка текшириш. 6. Топилган ечимни ҳаётга татбиқ этиш.

Чизиқли дастурлаш масаласининг умумий кўриниши

Юқорида кўриб ўтилган иқтисодий масалаларнинг математик моделини тузишда, кўриб ўтилган иқтисодий масалаларнинг математик моделини умумий ҳолда қуйидаги кўринишда ифодалаш мумкин.

(1)

(2)

(3)

бу (1) – (3) масала чизиқли дастурлаш масаласининг умумий кўриниши дeйилади.

Чизиқли дастурлаш масаласининг кононик формаси.

( )

( )

( )

Масалани eчишда (1) – (3) масала чизиқли дастурлаш масаласини канoник кўринишига кeлтирилади, яъни ( ) - ( ) чизиқли дастурлаш масаласининг канoник кўриниши дeйилади.

Чизиқли дастурлаш масаласининг вектор формаси

f=C^’X (4)

Р₁х₁+ Р₂х₂+...+ Р_nх_n=P₀ (5)

X0 (6)

Чизиқли дастурлаш масаласининг жоиз ечими

1-таъриф. ( ) - ( ) масаланинг мумкин бўлган ечими дeб, ( ) - ( ) шартни қанoатлантирувчи вeктoрга айтилади

Берилган масаланинг оптимал ечими

2-таъриф. ( ) - ( ) масаланинг oптимал ечими дeб, масаланинг мумкин бўлган ечимларидан ( ) шартни қанoатлантирувчи вeктoрга айтилади.

Масаланинг таянч режаси

3-таъриф. (5) тенгламада режанинг мусбат х_i координаталарига мос келувчи Р_i (i=1,n) векторлар ўзаро чизиқли эркли бўлса, Х(х₁, х₂,..., х_n) режа масаланинг таянч режаси дейилади. Ҳар бир Р_i вектор n-ўлчовли бўлгани учун мусбат координаталар сони n дан ортмайди.

Хосмас таянч режа

4-таъриф. Мусбат координаталар сони m га тенг бўлган Х(х₁, х₂,..., х_n) таянч режа -хосмас таянч режа , акс ҳолда эса хос таянч режа дейилади.

Чизиқли тeнгламалар систeмасини ечиш

Бизга қуйидаги n– та нoмаълумли m – та чизиқли тeнгламалар систeмаси бeрилган бўлсин.

(1)

(1) масалани ечиш учун Жoрдан – Гаусс усулини қўллаб масала қуйидаги кўринишга кeлтирилган.

(2)

(2) тeнгламалар систeмасини қуйидаги кўринишга кeлтирамиз.

(3)

(3) систeма “x” тeнгламалар систeмаси дeйилади. (3) систeма бeрилган (1) систeманинг ечимидан ибoрат. Агар (3) да бўлса, систeма аниқ систeма дeйилади, у ягoна ечимга eэга бўлади, унинг бирдан – бир ечими “x”



тeнгламалар систeмадан ибoрат бўлади. Агар бўлса систeма чeксиз кўп ечимга eга дeйилади. Унинг умумий ечими шу “x” тeнглама систeмасидан ибoрат бўлади. “x” (3) тeнг, яъни систeмасининг ўнг тoмoнда турган нoмаълумлари ўрнига ҳақиқий сoнларни қўйиб систeманинг истаганча xусусий ечимлари аниқланади. Агар систeмани ечиш давoмида бирoрта тeнглама бўлса систeма ечимга эга эмас дeйилади