Чизиқли программалаш масаласини ечишнинг Симплекс усули

Мавзу: Чизиқли программалаш масаласини

ечишнинг Симплекс усули.

Режа

1. 
   Симплекс усул хакида кискача умумий маълумот
   
2. 
   Симплекс усулнинг алгоритми
   
3. 
   Баъзи иктисодий масалаларни симплекс усул ёрдамида ечиш
   
4. 
   Мустакил ечиш учун тавсия килинган мисоллар
   

1.Чизиқли программалаш соҳасини илк принциплари Л.В. Конторовични “Математические методы организации и планирования производства” номли ишларида учрайди(1939й), 1947 йлда эса америка олими Данциг томонидан чизиқли программалаш масаласини умумий қўйилган.

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

Симплекс усул чизиқли программалаш масаласини мумкин бўлган режалар тўплами бўлган кўпёқни учлари орасидан оптимал ечимни топиш усулидир. Агар масалани ўзгарувчилар сони n-та чекловлар сони m-та бўлса у ҳолда кўпёқнинг учлари сони С_n^m –га тенг бўлади, бу еса катта сон бўлиб, бурчакларни бирма-бир текшириб чиқиш мақсадга муофиқ эмас.

2. Умумий ҳолда берилган куйидаги чизиқли программалаш масаласини кўрайлик:

a₁₁x₁+a₁₂x₂+…+a_1nx_n≤b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n≤b₂

. . . . . . . . . . . . . (1)

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m,

x_1, x_{2, . . . ,} x_n≥0 шартларни қаноатлантирган ҳолда F=c₁x₁+c₂x₂+…+c_nx_n (2) мақсад функцияга максимал қиймат берувчи x_1, x_{2, . . . ,} x_n ларни топиш керак.

1-қадам. Берилган (1) тенгсизликлар системасида янги x_n+1, x_{n+2, . . . ,} x_n+m, мусбат ўзгарувчилар киритиб барча тенгсизликларни тенгликларга айлантириб оламиз. Бу ерда янги киритилган ўзгарувчиларни иктисодий маъноси: шу ўзгарувчи катнашган тенгсизликга мос келувчи хом ашёни ортиб қолган миқдоридир. Демак n+m- ўзгарувчили m-та чизиқли тенгламалар системасини хосил қилдик ва бу системада x_n+1, x_{n+2, . . . ,} x_n+m – ўзгарувчилар фақат биттадан тенгламада бир коэффициет билан иштирок этади.

2-қадам. Хосил бўлган тенгламалар системада x_n+1, x_{n+2, . . . ,} x_n+m – ўзгарувчиларни базис ўзгарувчилар, x_1, x_{2, . . . ,} x_n –ўзгарувчиларни эса эркин ўзгарувчилар деб оламиз ва базис ўзгарувчиларни эркин ўзгарувчилар орқали ифодалаймиз.

x_n+1 = b₁ -a₁₁x₁-a₁₂x₂-…-a_1nx_n

x_n+2 = b₂ -a₂₁x₁-a₂₂x₂-…-a_2nx_n

. . . . . . . . . . . . . (3)

x_n+m = b_m-a_m1x₁-a_m2x₂-…-a_mnx_n,

бу ерда x_1, x_{2, . . . ,} x_n –ўзгарувчиларни барчасига 0 қиймат берсак

x_n+1, x_{n+2, . . . ,} x_n+m – ўзгарувчилар мос равишда b₁, b₂, ..., b_m –қийматларни қабул қилади ва (0,0,...,0, b₁, b₂, ..., b_m,) биринчи таянч режа бўлади.

3-қадам. Тузилган (3) системани ва (2) мақсад функцияни

қуйидаги симплекс жадвалга киритамиз.

Базис ўзгарувчилар	Озод ҳад	Эркин ўзгарувчилар
		-x1	-x2	...	-xn
xn+1	b1	a11	a12	...	a1n
xn+2	b2	a21	a22	...	a2n
....	....	...	...	...	...
xn+m	bm	am1	am2	...	amn
F	0	-c1	-c2	...	-cn

Агар бу жадвлда F сатрдаги барча эркин ўзгарувчиларга мос келувчи элементлар, яъни -c₁, -c₂, ...,-c_n лар мусбат бўлса бу жадвалга мос келувчи режа (0,0,...,0, b₁, b₂, ..., b_m,) оптимал режа бўлади.

4-қадам. Агар F сатрда манфий элементлар мавжуд бўлса, у ҳолда бу режа оптимал бўлмайди ва биз бошка таянч режага ўтамиз, яъни мумкин бўлган режалар кўпёқиниг бошқа учига.бу ишни куйидагича амалга оширамиз: F сатрдаги энг кичик манфий сон жойлашган устун хал қилувчи устун бўлади ва бу устун элементлари учун ( F сатрдаги элементдан ташкари) симплекс нисбатларни ҳисоблаймиз (хар бир озод ҳадни унга мос келувчи ҳал килувчи устун элементига нисбати). Ҳосил бўлган нисбатлардан энг кичигига мос келувчи элемент ҳал қилувчи элемент бўлади.

5-қадам. Ҳал қилувчи элемент ёрдамида симплекс жадвални ўзгартирамиз. Бу ишдан мақсад ҳал элементга мос келувчи сатрдаги базис ўзгарувчи ва устунда турган эркин ўзгарувчилар алмашади. (жадвални алмаштириш алгоритми мисолда тушунтирилади).

3. Ҳалқ хўжалигининг кўп сохаларини айрим масалалари (ишлаб чикаришни режалаштириш, чорва моллари учун оптимал озуқа тайёрлаш, екин ерлага минерал ўғитлар солиш масалалари ва ҳ.қ.,) айнан чизиқли программалаш масаласига келтирилиб шу симплекс усул билан ечилади. Қуйидаги масалани кўрайлик.

Масала Қоғоз ишлаб чиқарувчи комбинат ишлаб чикариш режасини бажариш билан бирга хом ашёларни барча туридан тежаб қолди. Яъни 50 тонна циллюлоза, 80 тонна ёғоч массаси ва 2 тонна каолин хом ашёлари ортиб қолди. Қуйидаги жадвалда барча турдаги қоғозларни 1тоннасини ишлаб чикариш учун сарф қилинадигон хом ашёларни нормалари (кг) ва буқоғозларни сотишдан қоладиган фойда миқдорлари келтирилган.

номлари	циллюлоза	ёғоч массаси	Каолин	даромад
Типография қоғози	306	829	20	10
Муқова қоғози	424	627	18	12
Ёзув қоғози	510	518	12	16

Қолган хом ашёлардан қоғозларни хар бир туридан канча миқдорда ишлаб чиқарилса комбинат энг юқори даромад олади ва қайси турдаги хом ашёлардан қанча миқдорда ортиб қолади.

Ечиш x₁ -типография қоғози, x₂ -муқова қоғози, x₃ -ёзув қоғози бўлсин, у ҳолда бу масалани математик модели куйидагича бўлади:

306x₁ +424x₂ +510x₃ ≤50 000

829x₁ +627x₂ +518x₃ ≤80 000

20x₁ +18x₂ +12x₃ ≤2 000

F=10x₁+12x₂+16x_{3 →} max

Бу масалада қўшимча x₄, x₅, x₆ – ўзгарувчилар киритиб куйидаги симплекс жадвални хосил киламиз:

Базис ўзгарувчилар	Озод ҳад	Эркин ўзгарувчилар
		-x1	-x2	-x3
x4	50 000	306	424	510
x5	80 000	829	627	518
x6	2 000	20	18	12
F	0	-10	-12	-18

Жадвалдан кўриниб турибдики хал қилувчи устун 3-чи устун.

Базис ўзгарувчилар	Озод ҳад	Эркин ўзгарувчилар
		-x1	-x2	-x3	с.н
x4	50 000	306	424	510	50000/510=98,03
x5	80 000	829	627	518	80000/518=154.44
x6	2 000	20	18	12	2000/12=166,67
F	0	-10	-12	-18

Демак хал қилувчи элемент бу 510, яъни x₄ базис ўзгарувчи ва x₃ эркин ўзгарувчилар ўрин алмашади, жадвал эса куйидаги тарзда ўзгаради:

Базис ўзгарувчилар	Озод ҳад	Эркин ўзгарувчилар
		-x1	-x2	-x4
x3	50 000/510	306/510	424/510	1/510
x5	14 900 000/510	316 086/510	100 138/510	-518/510
x6	420/510	7 728/510	4 092/510	-12/518
F	900 000/510	408/510	1512/510	18/510

Бу жадвалдан кўриниб турибдики F сатрдаги барча эркин ўзгарувчиларга мос келувчи элементлар мусбат,демак бу жадвалга мос келувчи таянч режа оптимал бўлади. Яъни бу ерда x₁, x₂, x₄ – эркин ўзгарувчилар нол қиймат қабул қилади ва бу ҳолатда x₃=50 000/510 (98.03) x₅=14 900 000/510 (29 215,7) ва x₆=420/510 (0.82) – қийматларни қабул қилиб мақсад функция F=900 000/510 (1 764.7) максимал қийматга эришади. Нолга тенг бўлмаган янги қўшилган ўзгарувчилар x₅ ва x₆ –ларни қийматлари шу ўзгарувчиларга мос келувчи хом ашёларни ортиб қолган микдорини билдиради.

Жавоб Факат ёзув қоғозидан 98.03 миқдорда ишлаб чиқарганда корхона 1 764.7 пул бирлигидаги максимал даромад олади.

4 Қуйидаги масаланинг иқтисодий математик модели тузилсин ва симплекс усули билан ечилсин.

Корхона -хил маҳсулот ишлаб чиқаради. Бу маҳсулотларни ишлаб чиқариш учун корхона ўз ихтиёридаги -та ресурслардан (хомашё, ишчи кучи, электр энергияси ва ҳакозо) фойдаланади. Ҳар бир ресурснинг захираси (запаси) ; ҳар бир маҳсулот бирлигини ишлаб чиқариш учун сарф қилинадиган ҳар бир ресурснинг миқдори (сарф нормалари) ; ҳар бир маҳсулот бирлигини сотишдан олинадиган даромад-лар маълум бўлсин.

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

Масаладаги сарф нормалари матрица , захиралар вектор , олинадиган даромадлар вектор орқали берилган.