2 laboratoriya. Chizily dasturlash masalalari (chpm) larni echishda



Download 142,17 Kb.
Sana16.06.2022
Hajmi142,17 Kb.
#676367
Bog'liq
24 var 2 lab


2 - laboratoriya . Chizily dasturlash masalalari (CHPM) larni echishda
simplex usul hikoya wa shijoatli dasturlash masalalar bo'yicha
topshiriq variantlarini narsa buyicha xizmatlar ku tufayli


Simpleks usuli yordamida chiziqli dasturlash masalasining optimal rejasini topish:

Biz manfiy bo'lmagan o'zgaruvchilarni qo'shish orqali tengsizliklarni tenglikka aylantiramiz:

Koeffitsient matritsasi A a ij ǁ tenglamalar tizimi quyidagi shaklga ega:

Tenglamalar sistemasi cheklovlarining o'ng tomoni B kabi ko'rinadi:

maqsad funktsiyasi C kabi ko'rinadi:

Biz simpleks jadvalini tuzamiz. ustun uchun x0 _ cheklovlarning o'ng tomoni yoziladi. Koeffitsientlar matritsasi o'ng tomonda yozilgan A. _ Oxirgi qator -1 ga ko'paytirilgan maqsad funksiyasi:

Asosiy vektorlar x 4 , x 5 , x 6 dir , shuning uchun gorizontal chiziq ostidagi x 4 , x 5 , x 6 ustunlardagi barcha yozuvlar nolga teng bo'lishi kerak.
Simpleks stol qabul qiladi turdagi :

1-qadam
Keling, joriy asosiy chiziqni yozamiz:

Maqsad funktsiyasining ma'lum bir nuqtadagi qiymati:

Ushbu mos yozuvlar rejasi optimal emas, chunki 4-qator va ustunlar kesishmasida x 1 x2 , _ x 3 x 4 x 5 x6 _ salbiy elementlar mavjud. Eng katta modulli salbiy element (-30), shuning uchun asos vektorni o'z ichiga oladi x 1 . Qaysi vektor asosni qoldirishini aniqlaymiz. Buning uchun biz hisoblaymiz min ( a i ,0 / a i ,1 ), qachon a i ,1 >0, i = 1,...3. min (236:8, 186:6, 164:5)=59/2 1-qatorga mos keladi. Vektor asosni tark etadi x 4 . Etakchi element 1-qatorga mos kelishini hisobga olib, x 1 ustun uchun Gauss istisnosini qilaylik . Buning uchun 1-qator mos ravishda -3/4, -5/8, 15/4 ga ko'paytirilgan 2, 3, 4 qatorlarni qo'shing. Keyinchalik, biz etakchi element bilan qatorni etakchi elementga ajratamiz.
Simpleks jadvali quyidagicha ko'rinadi:


2-qadam
Keling, joriy asosiy chiziqni yozamiz:

Maqsad funktsiyasining ma'lum bir nuqtadagi qiymati:

Ushbu mos yozuvlar rejasi optimal emas, chunki 4-qator va ustunlar kesishmasida x 1 x2 , _ x 3 x 4 x 5 x6 _ salbiy elementlar mavjud. Eng katta modulli salbiy element (-5), shuning uchun asos vektorni o'z ichiga oladi x 2 . Qaysi vektor asosni qoldirishini aniqlaymiz. Buning uchun biz hisoblaymiz min ( a i ,0 / a i ,2 ), qachon a i ,2 >0, i = 1,...3. min (59/2:1/2, 9:2)=9/2 2-qatorga mos keladi. Vektor asosni tark etadi x 5 . Etakchi element 2-qatorga mos kelishini hisobga olib, x 2 ustuni uchun Gauss istisnosini qilaylik . Ushbu ustunning barcha elementlarini nolga o'rnating, yetakchi elementdan tashqari. Buning uchun 2-qator mos ravishda -1/4, 1/4, 5/2 ga ko'paytirilgan 1, 3, 4 qatorlarni qo'shing. Keyinchalik, biz etakchi element bilan qatorni etakchi elementga ajratamiz.
Simpleks jadvali quyidagicha ko'rinadi:

3-qadam
Keling, joriy asosiy chiziqni yozamiz:

Maqsad funktsiyasining ma'lum bir nuqtadagi qiymati:

Joriy asosiy chiziq optimaldir, chunki oxirgi qatorda salbiy elementlar yo'q.
Kanonik masala yechimini quyidagicha yozish mumkin:

Qaror original vazifalari :

yoki

Maqsad funksiyasining optimal nuqtadagi qiymati:

qayerda C ref - C ref - asl masalaning maqsad funksiyasi koeffitsientlari.
#include < iostream >
#include < cmath >
#o'z ichiga
std nom maydonidan foydalanish ;
sinf Simpleks {
xususiy :
int qatorlar, qatorlar;
std ::vector < std ::vector > A;
std ::vector B;
std ::vector C;

suzuvchi maksimal;


bool isUnbounded ;


ommaviy :


Simpleks( std ::vector < std ::vector > matritsa, std ::vector b , std ::vector c){
maksimal = 0;
isUnbounded = noto'g'ri;
qatorlar = matrisa.size ();
cols = matritsa[0].size();
A.resize ( satr , vektor( cols , 0 ) );
b.oʻlchamini oʻzgartirish ( b.oʻlcham ());
c.registri ( c.size ());
for( int i = 0;i< satr;i ++){
for( int j= 0; j< cols; j ++ ){
A[ i ][ j] = matritsa[ i ][j];

}
}
for( int i =0; i < c.o'lcham (); men ++ ){


C[ i ] = c [ i ] ;
}
for( int i =0; i < b.hajmi (); men ++ ){
B[ i ] = b[ i ];
}
}
bool simplexAlgoritmCalculation (){
if( chek Optimality ()==true){
haqiqatni qaytarish ;
}
int pivotColumn = findPivotColumn ();
if( isUnbounded == rost){
cout <<"Cheklanmagan xato"<< endl ;
haqiqatni qaytarish ;
}
int pivotRow = findPivotRow ( pivotColumn );
doPivotting ( pivotRow, pivotColumn );
yolg'onni qaytarish ;
}
bool Optimallikni tekshirish (){
bool isOptimal = noto'g'ri;
int ijobiyValueCount = 0;
for( int i =0; i < c.o'lcham (); men ++){
float qiymati = C[ i ];
agar ( qiymat >= 0){
PozitivValueCount ++;
}
}
if( musbatValueCount == C.size ()){
isOptimal = rost;
chop etish ( );
}
qaytish isOptimal ;
}

bekor doPivotting ( int pivotRow , int pivotColumn ){


suzmoq pivetValue = A[ pivotRow ][ pivotColumn ];


suzmoq pivotRowVals [cols];
suzmoq pivotColVals [qatorlar];
suzmoq rowNew [cols];
maksimal = maksimal - (C[ pivotColumn ]*(B[ pivotRow ]/ pivetValue ));
for( int i =0;i< cols;i ++){
pivotRowVals [ i ] = A[ pivotRow ][ i ];
}
for( int j=0;j< rows;j ++){
pivotColVals [ j] = A[j][ pivotColumn ];
}
for( int k=0;k< cols;k ++){
rowNew [ k] = pivotRowVals [k]/ pivetValue ;
}

B[ pivotRow ] = B [ pivotRow ]/ pivetValue ;


for( int m=0;m< rows;m ++){
if( m != pivotRow ){
for( int p=0;p< cols;p ++){
suzmoq multiplyValue = pivotColVals [m];
A[m ][ p] = A[m][p] - ( multiplyValue * rowNew [p]);
}

}
}
for( int i =0;i< B.hajmi (); men ++){


if( i != pivotRow ){

suzmoq multiplyValue = pivotColVals [ i ];


B[ i ] = B[ i ] - ( multiplyValue *B[ pivotRow ]);

}
}
suzmoq multiplyValue = C[ pivotColumn ];


for( int i =0;i< C.hajmi (); men ++){
C[ i ] = C[ i ] - ( multiplyValue * rowNew [ i ]);
}
for( int i =0;i< cols;i ++){
A[ pivotRow ][ i ] = rowNew [ i ];
}
}
bekor chop etish(){
for( int i =0; i < rows;i ++){
for( int j=0;j< cols;j ++){
cout <}
cout <<""<< endl ;
}
cout <<""<< endl ;
}
int Pivot ustunini toping (){
int joylashuvi = 0;
suzmoq minm = C[0];
for( int i =1;i< C.hajmi (); men ++){
if( C[ i ]< minm ){
minm = C[ i ];
joy = i ;
}
}
qaytish joyi;
}
int findPivotRow ( int pivotColumn ){
suzmoq ijobiy qiymatlar [satrlar];
std ::vector natija ( satrlar,0);
int negativValueCount = 0;
for( int i =0;i< satr;i ++){
if( A[ i ][ pivotColumn ]>0){
PozitivValues [ i ] = A[ i ][ pivotColumn ];
}
boshqa{
ijobiy qiymatlar [ i ]=0;
negativValueCount +=1;
}
}
if( negativeValueCount ==satrlar){
isUnbounded = rost;
}
boshqa{
for( int i =0;i< satr;i ++){
float qiymati = musbatValues [ i ];
agar( qiymat>0){
natija [ i ] = B[ i ]/qiymat;
}
boshqa{
natija [ i ] = 0;
}
}
}
float minimal = 99999999;
int joylashuvi = 0;
for( int i =0;i< sizeof (natija)/ sizeof (natija[0]); men ++){
if( natija[ i ]>0){
if( natija[ i ]minimal = natija[ i ];

joy = i ;


}
}

}


qaytish joyi;

}


bekor Simpleksni hisoblash (){
boolend = noto'g'ri;

cout <<" foyda`ich massiv (Optimal emas )"<< endl ;


chop etish ( );

cout <<" "<< endl ;


cout <<" yakuniy massiv (Optimal yechim )"<< endl ;
while( !end){

bool natijasi = simplexAlgoritmCalculation ();


agar( natija==true){


end = rost;


}
}
cout <<" O'zgaruvchilar haqidai uchun javablar "<< endl ;

for( int i =0;i< A.hajmi (); men ++){


int count0 = 0;
int indeksi = 0;
for( int j=0; j< satr; j++ ){
if( A[j][ i ]==0.0){
count0 += 1;
}
Aks holda (A[j][ i ]==1){
indeks = j;
}
}

if( count0 == satrlar -1 ){


cout <<" o`zgaruvchi "<
}
boshqa{
cout <<" o`zgaruvchi "<

}


}
cout <<""<< endl ;
cout <<"maksimal qiymat : "<}
};
int main()
{
int colSizeA =6;
int rowSizeA = 3;
float C[]= {-19,-21,-23,0,0,0};
float B[]={299,312,317};
float a[3][6] = {
{ 8 , 5, 3, 1, 0, 0},
{ 5 , 4, 7, 0, 1, 0},
{3,7,6,0,0,1 }
};
std ::vector < std ::vector > vec2D( rowSizeA , std ::vector( colSizeA , 0));

std ::vector b( rowSizeA,0);


std ::vector c( colSizeA,0);
for( int i =0;i< rowSizeA;i ++){
for( int j=0; j< colSizeA;j ++){
vec2D[ i ][ j] = a[ i ][j];
}
}

for( int i =0;i< rowSizeA;i ++){


b[ i ] = B[ i ];
}

for( int i =0;i< colSizeA;i ++){


c[ i ] = C[ i ];
}
Simpleks simpleks ( vec2D,b,c);
simpleks.CalculateSimplex ( );
qaytish 0;
}­­­­

Download 142,17 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish