2 laboratoriya. Chizily dasturlash masalalari (chpm) larni echishda

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 ₄ , x ₅ , x _{6 dir , shuning} uchun gorizontal chiziq ostidagi x ₄ , x ₅ , 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 ₁ , x2 , _{_} x ₃ , x ₄ , x ₅ , x6 _{_} salbiy elementlar mavjud. Eng katta modulli salbiy element (-30), shuning uchun asos vektorni o'z ichiga oladi x ₁ . 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 ₄ . Etakchi element 1-qatorga mos kelishini hisobga olib, x ₁ 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 ₁ , x2 , _{_} x ₃ , x ₄ , x ₅ , x6 _{_} salbiy elementlar mavjud. Eng katta modulli salbiy element (-5), shuning uchun asos vektorni o'z ichiga oladi x ₂ . 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 ₅ . Etakchi element 2-qatorga mos kelishini hisobga olib, x ₂ 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;
}­­­­