Mavzu: Algoritmlarning qiymat qabul qilish va o‘zgarish sohalarini loyihalashtirish va tahlil

Mavzu: Algoritmlarning qiymat qabul qilish va o‘zgarish sohalarini loyihalashtirish va tahlil

Bizga chiziqli dasturlash masalasi berilgan bo’lsin.

Chiziqli dasturlash masalasi(CH.D.M)ning optimal yechimi uning bazis yechimlaridan birortasi bo’lib, unda maqsad funksiya minimal qiymatga erishadi.
(CH.D.M) ni yechishning simpleks usulini ko’rib chiqamiz.
Topilgan bazis yechimning optimal yechim bo’lishini tekshirish hamda, agar bu bazis yechim optimal yechim bo’lmasa, boshqa bazis yechimga o’tish qoidasi bilan tanishish uchun sistemani quyidagi ko’rinishga joylashtiramiz.

Bazis o’zgaruvchilar	B	Erkli o’zgaruvchilar
		Xm+1	Xm+2	..	Xn
X1	b1	a11	a12	…	a1n
X2	b2	a11	a12	…	a1n
…	….	…	…	..	..
Xm	b3	a11	a12	…	a1n
F	c0	C1	C2	…	Cn

Bunday jadval simpleks jadval deb ataladi.

C_1i i=1..n shart o’rinli bo’lsa, u holda topilgan X₀ bazis reja optimal reja deyiladi
Simpleks usuli algoritmi quyidagi bosqichlarni o'z ichiga oladi.

1. 
   Birinchi boshlang’ich bazis rejani tuzish . manfiy bo'lmagan qo'shimcha parametrlarini kiritish orqali chiziqli dasturlash masalasining kanonik shakliga o'tish.
   
2. 
   Rejani optimoptimallikka tekshirish . Agar kamida noldan kichik bo'lgan bitta ko'rsatkich qatori koeffitsienti bo'lsa, unda reja maqbul emas va uni takomillashtirish kerak.
   
3. 
   Asosiy ustun va qatorni aniqlang . Indeks qatorining manfiy koeffitsientlaridan mutlaq qiymat bo'yicha eng kattasi tanlangan. Keyin soddalashtirilgan jadvalning ustun elementlari yetakchi ustunning bir xil belgisining elementlariga bo'linadi.
   
4. 
   Yangi basis reja tuzish. Yangi rejaga o'tish Gauss usuli bo'yicha soddalashtirilgan jadvalni qayta hisoblash natijasida amalga oshiriladi .
   

Misol 1. Kichik korxona meva sharbatlarini chiqaradigan bo'lsin. Korxonada 30kg olcha, 45kg olma, 12kg shakar bor. Korxona ikki xil turdagi meva sharbatlarini chiqaradi. 1 – tur meva sharbatining bir bankasiga 0,1kg olcha, 0,5kg olma, 0,1 kg shakar solinsin. 2 – tur meva sharbatining bir bankasiga 0,3kg olcha, 0,2kg olma, 0,1kg shakar solinsin. Agar 1 banka 1 – tur sharbat narxi 1000so'm, 2 – tur meva sharbati 1400so'm tursa, korxona har bir tur meva sharbatidan qanchadan ishlab chiqarganda korxonaning meva sharbatlarini sotishdan tushgan daromadi eng katta bo'ladi?
Yechim
Masalaning matematik ifodasini tuzish uchun masala shartlariga ko'ra kelib chiqadigan munosabatlarni hosil qilishimiz kerak. Avvalo masala shartiga ko'ra topilishi kerak bo'lgan 1 – va 2 – tur meva sharbatlarining noma'lum sonini x₁ , x₂ deb belgilaymiz. Bu holda 1 – , 2 – va 3 – tur xomashyo (olcha, olma, shakar) sarflarini hisoblab bu sarflar korxonadagi bor bo'lgan xomashyo zaxiralaridan ortmasligini talab qilamiz. Xususan olcha sarfi bo'yicha har bir banka 1 – tur meva sharbatiga 0,1kg olcha , 2 – tur meva sharbatiga esa 0,3kg olcha 4 solinadigan bo'lsa mos ravishda 1 x banka 1 – tur , 2 x banka 2 – tur meva sharbatlariga jami 1x × 0,1 + 2x × 0,3 kg olcha sarflanadi. Bu esa korxonada bor bo'lgan 30kg olchadan ortmasligi kerak. Demak olchalar bo'yicha qo'yiladigan shart 0,1x₁ + 0,3x₂ ≤ 30 ko'rinishini oladi. Xuddi shunday mulohazalarga ko'ra olma va shakar sarfi bo'yicha korxona imkoniyatlaridan kelib chiqqan holda
0,1x₁ + 0,3x₂ ≤ 30
0,5 x₁ + 0,2 x₂ ≤ 45
0,1 x₁ + 0,1 x₂ ≤ 12
ko'rinishdagi shartlarni hosil qilamiz. Meva sharbatlarini sotishdan tushadigan daromad esa keltirilgan narxlarga ko'ra jami L(x₁ , x₂) = 1000 x₁ + 1200 x₂ bo'lar ekan. Bu yerda L(x₁ , x₂) maqsad funksiyasi bo'lib, shunday ishlab chiqarish rejasini tanlash kerakki , bu reja avvalo resurslar bo'yicha shartlarga mos kelsin va maqsad funksiyasining eng katta qiymatini keltirib chiqarsin. Shunday qilib keltirilgan iqtisodiy masala quyidagicha ifodalanar ekan (1.1)
L(x₁ , x₂ ) = 1000 x₁ + 1200 x₂ + 0x₃+ 0x₄+ 0x₅→ max
0,1x₁ + 0,3x₂ + x₃= 30
0,5 x₁ + 0,2 x₂ + x₄= 45
0,1 x₁ + 0,1 x₂ + x₅=12

X	x1	x2	x3	x4	x5	Xn
x3	0.1	0.3	1	0	0	30
x4	0.5	0.2	0	1	0	45
x5	0.1	0.1	0	0	1	12
L	-1000	-1200	0	0	0	0

X	x1	x2	x3	x4	x5	Xn
x2	1/3	1	10/3	0	0	100
x4	13/30	0	-2/3	1	0	25
x5	1/15	0	-1/3	0	1	2
L	-600	0	4000	0	0	120000

X	x1	x2	x3	x4	x5	Xn
x2	0	1	7/3	0	-5	90
x4	0	0	19/20	1	-13/2	12
x1	1	0	-3	0	15	30
L	0	0	5800	0	9000	138000

Misol 2

L(x)=10x₁+12x₂+8x₃→max
3x₁+4x₂+2x₃≤1020
4x₁+3x₂+3x₃≤940
5x₁+3x₂+5x₃≤1010
x₁, x₂, x₃≥0


G(x)=10x₁+12x₂+8x₃+0x₄+0x₅+0x₆
3x₁+4x₂+2x₃+x₄≤1020 3x₁+4x₂+2x₃+1x₄+0x₅+0x₆=1020
4x₁+3x₂+3x₃+x₅≤940 => 4x₁+3x₂+3x₃+0x₄+1x₅+0x₆=940
5x₁+3x₂+5x₃+x₆≤1010 5x₁+3x₂+5x₃+0x₄+0x₅+1x₆=1010
x₁, x₂, x₃, x₄, x₅,x₆ ≥0 x₁, x₂, x₃, x₄, x₅,x₆ ≥0

X	x1	x2	x3	x4	x5	x6	X^n
	1	4	2	1	0	0	1020
	4	3	3	0	1	0	940
	5	3	5	0	0	1	1010
L	-10	-12	-8	0	0	0	0

1024/4=255-min

940/3 313,33
1010/3 336,67


Masalaning dasturi:
/* Ch.D. simpleks usul */
#include
#include
#define ND 2
#define NS 3
#define N (ND+NS)
#define N1 (NS*(N+1))
using namespace std;
void init(float x[],int n) {
int i=0;
for (;i
x[i] = 0; }
int main() {
int i,j,k,kj,ki,bas[NS];
float a[NS][N+1], c[N], cb[NS], th[NS], x[ND], cj, z, t, b, min, max;
/* massiv */
init(c,N);
init(cb,NS);
init(th,NS);
init(x,ND);
for (i=0;i
init(a[i],N+1);
/* o'zgaruvchan parametrlar koeffisiyentlari */
for (i=0;i
a[i][i+ND] = 1.0;
/* bazis */
for (i=0;i
/*chegaraviy shartlar va maqsad funksiyasi */
cout<<"Cheklovlar (shart)ni kiriting "<
for (i=0;i
for (j=0;j
cin >> a[i][j];
cin >> a[i][N]; }
cout << "Maqsad funksiyasini kiriting "<< endl;
for (j=0;j
cin >> c[j];
cout << fixed;
/*cj larni hisoblash va kiruvchi ma'lumotlarni tavsiflash */
while (1) {
max = 0;
kj = 0;
for (j=0;j
z = 0;
for (i=0;i
z += cb[i]*a[i][j];
cj = c[j]-z;
if(cj > max) {
max = cj; kj = j; } }
/* Optimallik testini qo'llash */
if(max <= 0) break;
/* Hisoblash */
max = 0;
for (i=0;i
if(a[i][kj]!= 0) {
th[i] = a[i][N]/a[i][kj];
if(th[i] > max) max=th[i]; }
/* Yechimlarni tekshirish*/
if(max <= 0) {
cout << "Cheklanmagan yechimlar ";
return 1; }
/*Chiquvchi o'zgaruvchilarni izlash */
min = max; ki = 0;
for (i=0;i
if ((th[i] < min)&&(th[i]!= 0)) {
min = th[i]; ki = i; }
/* hal qiluvchi element*/
t = a[ki][kj];
/*Hal qiluvchi kalit satrni hal qiluvchi elementga bo'lish */
for (j=0;j
a[ki][j] /= t;
/*kalit ustunning qolgan barcha elementlarini nolga tenglashtirish */
for (i=0;i
if(i!= ki) {
b = a[i][kj];
for (k=0;k
a[i][k]-=a[ki][k]*b; }
cb[ki] = c[kj];
bas[ki] = kj; }
/* Optimal qiymatni hisoblash */
for (i=0;i
if ((bas[i] >= 0) && (bas[i]
x[bas[i]] = a[i][N]; z = 0;
for (i=0;i
z += c[i]*x[i];
for (i=0;i
cout << "x[" << setw(3) << i+1 << "] = "<< setw(7) << setprecision(2)<<
x[i] << endl;
cout << "Optimal yechim = " << setw(7) << setprecision(2)<< z << endl;
return 0; }