Чизиқли программалаш масалалари (чпм) ларни ечишда Симплекс усул моҳияти ва чизиқли программалаш масалалар бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар



Download 0,97 Mb.
Sana31.12.2021
Hajmi0,97 Mb.
#209982
TuriПрограмма
Bog'liq
al2


218-19-guruh: Mirzayev Azamat

Mavzu: Чизиқли программалаш масалалари (ЧПМ) ларни ечишда Симплекс усул моҳияти ва чизиқли программалаш масалалар бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар

17-variant.

Berilgan:

3x1 + 4x2 + 2x3 → max
x1 + 2x2 + x3 ≤ 18
2x1 + x2 + x3 ≤ 16
x1 + x2  ≤ 8

X2 + x3 ≤6

Tengsizlikkaegabo’lganharbircheklovalruchunqo’shimcha  x4..x6 lar qo’shiladi. x1gax4, x2 ga x5 , x3 ga x6 .

Boshlang’ishsimpleksjadval:



So’ngradeltalarnianiqlaymiz:

Deltalarbilansimpleksjadval:

Hozirgi X: [0,0,0,18,16,8,6]

Delta 1 inkorbo’lganligiuchun plan optimal emas.

Iteratsiya 1

Engkam Delta joylashganruxsatberuvchiustunnianiqlang: 3, D3: -23

bkoeffitsientlarini 3 ustuniningtegishliqiymatlarigabo'lishorqalioddiy Qmunosabatlarinitopamiz.

Topilganustundaengkamqiymatbilanqatorniqidiramiz Q: Qmin = 16/1, 2-qator.

Topilgansatrvaustunningkesishmasidaruxsatberuvchi element mavjud: 1.

X5 ningasosiyo'zgaruvchisisifatida x3ni olamiz.

2-satrini 1 gabo'lamiz. 1, 3 -satrlaridan 2 - satrini 3- ustunidagitegishli element bilanko'paytiramiz.

Yangideltalarnihisoblaymiz:

Δi = C4·a1i + C3·a2i + C6·a3i - Ci

HozirgiX:

Delta 1 inkorbo’lganligiuchun plan optimal emas.

Iteratsiya 2.

Engkam Delta joylashganruxsatberuvchiustunnianiqlang: 2, D2: - 55/7.

b koeffitsientlarini 2-ustunining tegishliqiymatlarigabo'lishorqalioddiy Q munosabatlarinitopamiz.

Topilganustundaengkamqiymatbilanqatorniqidiramiz Q: Qmin = 6 ,3-qator.

Topilgansatrvaustunningkesishmasidaruxsatberuvchi element mavjud: 2.

X6 ningasosiyo'zgaruvchisisifatida biz x2 niolamiz.

3-satrni 2/1 gabo’lamiz.

1, 2-satrlaridan 3-satrini 2-ustunidagi tegishli element bilanko'paytiramiz.

Yangideltalarnihisoblaymiz:



Δi = C4·a1i + C3·a2i + C2·a3i - Ci

Hozirgi X; [2,6,0,4,6,0,0,0]

Funksiya F: 19*0+21*347/25+23*916/25+0*2992/25+0*0+0*0=5621/5

Delta 1 inkorbo’lganligiuchun plan optimal emas.

Iteratsiya 3

Minimal Delta joylashganruxsatberuvchiustunnianiqlang: 1, D1: -27/5.

b koeffitsientlarini 1-ustunining tegishliqiymatlarigabo'lishorqalioddiy Qmunosabatlarinitopamiz.

Topilganustunda biz engkamqiymatbilanqatorniqidiramiz Q: Qmin = 17, 1-qator.

Topilgansatrvaustunningkesishmasidaruxsatberuvchi element mavjud: 176/25

X4 asosiyo'zgaruvchisisifatida biz x1ni olamiz.



1-satrini 6/2 gabo’lamiz.

2, 3 - satrlaridan 1-ustunidagi tegishli element bilanko'paytiriladigan 1-satrini chiqaring.

Yangideltalarnihisoblang:Δi = C1·a1i + C3·a2i + C2·a3i - Ci



Hozirgi X: [17,20,21,0,0,0,]

Funksiya F: 3*5+4*3+2*3+0*4+0*0+0*0+0*0=33

Inkordeltalarbo’lmaganligiuchun plan optimal.

Javob: x1 = 5, x2 = 3, x3 = 3, x4 = 4 F = 33

Kodi:

#include

#include

#include

using namespace std;

class Simplex{

private:

int rows, cols;

//stores coefficients of all the variables

std::vector > A;

//stores constants of constraints

std::vector B;

//stores the coefficients of the objective function

std::vector C;

float maximum;

bool isUnbounded;

public:

Simplex(std::vector > matrix,std::vector b ,std::vector c){

maximum = 0;

isUnbounded = false;

rows = matrix.size();

cols = matrix[0].size();

A.resize( rows , vector( cols , 0 ) );

B.resize(b.size());

C.resize(c.size());

for(int i= 0;i

for(int j= 0; j< cols;j++ ){

A[i][j] = matrix[i][j];

}

}

for(int i=0; i< c.size() ;i++ ){ //pass c[] values to the B vector



C[i] = c[i] ;

}

for(int i=0; i< b.size();i++ ){ //pass b[] values to the B vector



B[i] = b[i];

}

}



bool simplexAlgorithmCalculataion(){

//check whether the table is optimal,if optimal no need to process further

if(checkOptimality()==true){

return true;

}

//find the column which has the pivot.The least coefficient of the objective function(C array).



int pivotColumn = findPivotColumn();

if(isUnbounded == true){

cout<<"Error unbounded"<

return true;

}

//find the row with the pivot value.The least value item's row in the B array



int pivotRow = findPivotRow(pivotColumn);

//form the next table according to the pivot value

doPivotting(pivotRow,pivotColumn);

return false;

}

bool checkOptimality(){



//if the table has further negative constraints,then it is not optimal

bool isOptimal = false;

int positveValueCount = 0;

//check if the coefficients of the objective function are negative

for(int i=0; i

float value = C[i];

if(value >= 0){

positveValueCount++;

}

}

//if all the constraints are positive now,the table is optimal



if(positveValueCount == C.size()){

isOptimal = true;

print();

}

return isOptimal;



}

void doPivotting(int pivotRow, int pivotColumn){

float pivetValue = A[pivotRow][pivotColumn];//gets the pivot value

float pivotRowVals[cols];//the column with the pivot

float pivotColVals[rows];//the row with the pivot

float rowNew[cols];//the row after processing the pivot value

maximum = maximum - (C[pivotColumn]*(B[pivotRow]/pivetValue)); //set the maximum step by step

//get the row that has the pivot value

for(int i=0;i

pivotRowVals[i] = A[pivotRow][i];

}

//get the column that has the pivot value



for(int j=0;j

pivotColVals[j] = A[j][pivotColumn];

}

//set the row values that has the pivot value divided by the pivot value and put into new row



for(int k=0;k

rowNew[k] = pivotRowVals[k]/pivetValue;

}

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



//process the other coefficients in the A array by subtracting

for(int m=0;m

//ignore the pivot row as we already calculated that

if(m !=pivotRow){

for(int p=0;p

float multiplyValue = pivotColVals[m];

A[m][p] = A[m][p] - (multiplyValue*rowNew[p]);

//C[p] = C[p] - (multiplyValue*C[pivotRow]);

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

}

}



}

//process the values of the B array

for(int i=0;i

if(i != pivotRow){

float multiplyValue = pivotColVals[i];

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

}

}

//the least coefficient of the constraints of the objective function



float multiplyValue = C[pivotColumn];

//process the C array

for(int i=0;i

C[i] = C[i] - (multiplyValue*rowNew[i]);

}

//replacing the pivot row in the new calculated A array



for(int i=0;i

A[pivotRow][i] = rowNew[i];

}

}

//print the current A array



void print(){

for(int i=0; i

for(int j=0;j

cout<

}

cout<<""<

}

cout<<""<

}

//find the least coefficients of constraints in the objective function's position



int findPivotColumn(){

int location = 0;

float minm = C[0];

for(int i=1;i

if(C[i]

minm = C[i];

location = i;

}

}



return location;

}

//find the row with the pivot value.The least value item's row in the B array



int findPivotRow(int pivotColumn){

float positiveValues[rows];

std::vector result(rows,0);

//float result[rows];

int negativeValueCount = 0;

for(int i=0;i

if(A[i][pivotColumn]>0){

positiveValues[i] = A[i][pivotColumn];

}

else{


positiveValues[i]=0;

negativeValueCount+=1;

}

}

//checking the unbound condition if all the values are negative ones



if(negativeValueCount==rows){

isUnbounded = true;

}

else{


for(int i=0;i

float value = positiveValues[i];

if(value>0){

result[i] = B[i]/value;

}

else{


result[i] = 0;

}

}



}

//find the minimum's location of the smallest item of the B array

float minimum = 99999999;

int location = 0;

for(int i=0;i

if(result[i]>0){

if(result[i]

minimum = result[i];

location = i;

}

}



}

return location;

}

void CalculateSimplex(){



bool end = false;

cout<<"initial array(Not optimal)"<

print();

cout<<" "<

cout<<"final array(Optimal solution)"<

while(!end){

bool result = simplexAlgorithmCalculataion();

if(result==true){

end = true;

}

}



cout<<"Answers for the Constraints of variables"<

for(int i=0;i< A.size(); i++){ //every basic column has the values, get it form B array

int count0 = 0;

int index = 0;

for(int j=0; j< rows; j++){

if(A[j][i]==0.0){

count0 += 1;

}

else if(A[j][i]==1){



index = j;

}

}



if(count0 == rows -1 ){

cout<<"variable"<

}

else{


cout<<"variable"<

}

}



cout<<""<

cout<<"maximum value: "<

}

};

int main()



{

int colSizeA=7; //should initialise columns size in A

int rowSizeA = 4; //should initialise columns row in A[][] vector

float C[]= {-3,-4,-2,0,0,0,0}; //should initialis the c arry here

float B[]={18,16,8,6}; // should initialis the b array here

float a[4][7] = { //should intialis the A[][] array here

{ 1, 2, 1, 1, 0, 0, 0},

{ 2, 1, 1, 0, 1, 0, 0},

{ 1, 1, 0, 0, 0, 1, 0},

{ 0, 1, 1, 0, 0, 0, 1}

};

std::vector > vec2D(rowSizeA, std::vector(colSizeA, 0));



std::vector b(rowSizeA,0);

std::vector c(colSizeA,0);

for(int i=0;i

for(int j=0; j

vec2D[i][j] = a[i][j];

}

}



for(int i=0;i

b[i] = B[i];

}

for(int i=0;i

c[i] = C[i];

}

// hear the make the class parameters with A[m][n] vector b[] vector and c[] vector



Simplex simplex(vec2D,b,c);

simplex.CalculateSimplex();



return 0;

}


Download 0,97 Mb.

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