Chiziqli programmalash masalasini yechishning Simpleks usuli

bazis oʻzgaruvchilar	Ozod had	erkin oʻzgaruvchilar
		-x1	-x2	-x3
x4	50 000	206	424	510
x5	80 000	829	627	518
x6	2 000	20	18	12
F	0	-10	-12	-18

Jadvaldan koʻrinib turibdiki xal qiluvchi ustun 3-chi ustun

chunki bu ustunda F- satrni eng kichik manfiy elementi -18 joylashgan. Hal kiluvchi ustun elementlariga o’ziga mos simpleks nisbatni (xar bir ozod hadni unga mos keluvchi hal qiluvchi ustun elementiga nisbati) hisoblaymiz va jadvalga kiritamiz

bazis oʻzgaruvchilar	Ozod had	erkin oʻzgaruvchilar
		-x1	-x2	-x3	с.н
x4	50 000	206	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

Jadvaldan ko’rinib turbidiki xal qiluvchi element bu 510, yaʼni x4 bazis oʻzgaruvchi va x3 erkin oʻzgaruvchilar oʻrin almashadi, jadval esa quyidagi tarzda oʻzgaradi:

a) hal qiluvchi element oʼzining teskarisiga almashadi (1/510)

b) hal qiluvchi element joylashgan satrdagi barcha elementlar hal qiluvchi elementga boʼlinadi

c) hal qiluvchi element joylashgan ustundagi barcha elementlar hal qiluvchi elementga boʼlinadi va qarama-qarshi ishora bilan olinadi

bazis oʻzgaruvchilar	Ozod had	erkin oʻzgaruvchilar
		-x1	-x2	-x4
x3	50 000/510	206/510	424/510	1/510
x5				-518/510
x6				-12/510
F				18/510

d) qolgan elementlar quydagi tartibda hisolanadi: masalan

1-chi ustun 3-chi strda turgan elementni (2000) olaylik

bazis oʻzgaruvchilar	Ozod had	erkin oʻzgaruvchilar
		-x1	-x2	-x3
x4	50 000	206	424	510
x5	80 000	829	627	518
x6	2 000	20	18	12
F	0	-10	-12	-18

hal qiluvchi element (510) 1-chi satr 3-chi ustunda joylashgan boʼlib bu ikkala elementlarni satrlari va ustunlari kesishmasida yana ikkita element 1-chi ustun 1-chi satrda (50 000) va 3-chi ustun 3-chi satrda (12) joylashgan elemntlar bor. Yaʼni uchlarida sonlar joylashgan toʼgʼri toʼtrburchak hosil boʼldi. Hal qiluvchi element turgan dioganaldagi sonlar koʼpaytmasidan (yaʼni sariq kataklarda joylashgan sonlar) ikkinchi dioganaldagi sonlar qoʼpaytmasini (yaʼni yashil kataklarda joylashgan sonlar) ayrimiz va natijani hal qiluvchi elementga boʼlamiz: (510*2000 – 50 000*12)/510 = =420/510

bazis oʻzgaruvchilar	Ozod had	erkin oʻzgaruvchilar
		-x1	-x2	-x4
x3	50 000/510	206/510	424/510	1/510
x5	80 000	829	627	-518/510
x6	420/510	20	18	-12/518
F	0	-10	-12	18/510

Xuddi shu tartibda qolgan barcha (boʼyalmagan katakdagi) elementlarni xam oʼzgartiramiz, natijada quyidagi jadval hosil boʼladi:

Bu jadvaldan koʻrinib turibdiki F satrdagi barcha erkin oʻzgaruvchilarga mos keluvchi elementlar musbat,demak bu jadvalga mos keluvchi tayanch reja optimal boʻladi. Yaʼni bu yerda x1, x2, x4 – erkin oʻzgaruvchilar nol qiymat qabul qiladi va bu holatda x3=50 000/510 (98.03)

x5=14 900 000/510 (29 215,7) va x6=420/510 (0.82) – qiymatlarni qabul qilib maqsad funktsiya F=900 000/510 (1 764.7) maksimal qiymatga erishadi. Nolga teng boʻlmagan yangi qoʻshilgan oʻzgaruvchilar x5 va x6 –larni qiymatlari shu oʻzgaruvchilarga mos keluvchi xom ashyolarni ortib qolgan miqdorini bildiradi.

bazis oʻzgaruvchilar	Ozod had
		-x1	-x2	-x4
X3	50 000/510	206/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

Hozirgi kunda simpleks usulda masalalarni yechish uchun juda koʼp dasturlar mavjud boʼlib, bulardan halq hoʼjaligini ayrim masalalarini yechishda keng qoʼllanilmoqda. Bunday dasturiy taʼminotlardan ayrimlarini misol qilishimiz mumkin:

Пакеты, использующие симплекс-метод:

1. LP_solve. Написан на C++. Решает задачи ЛП с количеством переменных до 30000 и ограничений а€” до 50000. Текущая версия 3.0. Условия использования а€” Lesser GNU Public License. Существует конвертер из формата MPS в формат Lp_solve. Может решать задачи с целочисленными переменными.

LP-Optimizer. Решает задачи ЛП и ЦП. Доступны бесплатно исходные тексты на Borland Pascal 7.0, исполняемые файлы для DOS http://www.netcologne.de/~nc- weidenma/lp_dos.zip и OS/2.

SoPlex. Объектно-ориентированная реализация прямого и двойственного симплекс- метода. Доступны исходные тексты.

SPLP. Составная часть библиотеки программ SLATEC. Написан на Фортране. Решает задачи ЛП с несколькими тысячами переменных и ограничений.

4. Quyidagi masalaning iqtisodiy matematik modeli tuzilsin va simpleks usuli bilan yechilsin.

Korxona n -xil mahsulot ishlab chiqaradi. Bu mahsulotlarni ishlab chiqarish uchun korxona oʻz ixtiyoridagi m -ta resurslardan (xomashyo, ishchi kuchi, elektr energiyasi va hakozo) foydalanadi. Har bir resursning zahirasi (zapasi) ; har bir mahsulot birligini ishlab chiqarish uchun sarf qilinadigan har bir resursning miqdori (sarf normalari) ; har bir mahsulot birligini sotishdan olinadigan daromad сi -lar (i=1,2,…,m; j=1,2,…,n) maʼlum boʻlsin.

Ishlab chiqarish rejasini shunday tuzish kerakki, unda sarf qilingan resurslar miqdori, berilgan zaxiralar miqdorlaridan ortmasin va hamma ishlab chiqarilgan mahsulotlarni sotishdan olinadigan daromad eng koʻp boʻlsin.

Masaladagi sarf normalari; matritsa (A) , zahiralar bi vektor (B), olinadigan daromadlar cj vektor (C) orqali berilgan.

 

4)

5) .

•  

 

1) .

2)

3) .

 

6) .

7).

 

8) .

9).

10).

11) .

 

12.

13).

14)

15).

16)

17)

 

18)

19)

20)

 

E’tiboringiz uchun rahmat…