Mavzu: Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini yechishning simpleks usulini C++ da bajarish

nomlari	sillyuloza	yog‘och massasi	Kaolin
daromad
Tipografiya qog‘ozi	306	829	20	10
Muqova qog‘ozi	424	627	18	12
YOzuv qog‘ozi	510	518	12	16

Qolgan xom ashyolardan qog‘ozlarni xar bir turidan kancha miqdorda ishlab chiqarilsa kombinat eng yuqori daromad oladi va qaysi turdagi xom ashyolardan qancha miqdorda ortib qoladi.

Echish x₁ -tipografiya qog‘ozi, x₂-muqova qog‘ozi, x₃-yozuv qog‘ozi bo‘lsin, u holda bu masalani matematik modeli kuyidagicha bo‘ladi:

306x₁+424x₂ +510x₃ ≤50 000

829x₁+627x₂ +518x₃ ≤80 000

20x₁+18x₂ +12x₃ ≤2 000

F=10x₁+12x₂+16x_{3 →} max

Bu masalada qo‘shimcha x₄, x₅, x₆ – o‘zgaruvchilar kiritib kuyidagi simpleks jadvalni xosil kilamiz:

Bazis o‘zgaruvchilar	Ozod had	Erkin o‘zgaruvchilar
		-x1	-x2	-x3
x4	50 000	306	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.

Bazis o‘zgaruvchilar	Ozod had	Erkin o‘zgaruvchilar
		-x1	-x2	-x3	s.n
x4	50 000	306	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

Demak xal qiluvchi element bu 510, ya’ni x₄ bazis o‘zgaruvchi va x₃ erkin o‘zgaruvchilar o‘rin almashadi, jadval esa kuyidagi tarzda o‘zgaradi:

Bazis o‘zgaruvchilar	Ozod had	Erkin o‘zgaruvchilar
		-x1	-x2	-x4
x3	50 000/510	306/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

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 erda x₁, x₂, x₄ – erkin o‘zgaruvchilar nol qiymat qabul qiladi va bu holatda x₃=50 000/510 (98.03)x₅=14 900 000/510 (29 215,7) vax₆=420/510 (0.82)– qiymatlarni qabul qilib maqsad funksiya F=900 000/510 (1 764.7) maksimal qiymatga erishadi. Nolga teng bo‘lmagan yangi qo‘shilgan o‘zgaruvchilarx₅ va x₆ –larni qiymatlari shu o‘zgaruvchilarga mos keluvchi xom ashyolarni ortib qolgan mikdorini bildiradi.

JavobFakat yozuv qog‘ozidan 98.03 miqdorda ishlab chiqarganda korxona 1 764.7 pul birligidagi maksimal daromad oladi.



#include

#include

#include

using namespace std;

class Simplex{

bool isUnbounded;

public:

Simplex(std::vector > matrix,std::vector bvector 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++ ){

C[i] = c[i] ;

}

for(int i=0; i< b.size();i++ ){

B[i] = b[i];

}

}

bool simplexAlgorithmCalculataion(){

if(checkOptimality()==true){

return true;

}

int pivotColumn = findPivotColumn();

if(isUnbounded == true){

cout<<"Error unbounded"<

return true;

}

int pivotRow = findPivotRow(pivotColumn);

doPivotting(pivotRow,pivotColumn);

return false;

}

bool checkOptimality(){

bool isOptimal = false;

int positveValueCount = 0;

for(int i=0; i

float value = C[i];

if(value >= 0){

positveValueCount++;

}

}

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

isOptimal = true;

print();

}

return isOptimal;

}

void doPivotting(int pivotRow, int pivotColumn){

float pivetValue = A[pivotRow][pivotColumn];

float pivotRowVals[cols];

float pivotColVals[rows];

float rowNew[cols];

maximum = maximum - (C[pivotColumn]*(B[pivotRow]/pivetValue));

for(int i=0;i

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

}

for(int j=0;j

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

}

for(int k=0;k

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

}

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

for(int m=0;m

if(m !=pivotRow){

for(int p=0;p

float multiplyValue = pivotColVals[m];

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

}

}

}

for(int i=0;i

if(i != pivotRow){

float multiplyValue = pivotColVals[i];

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

}

}

float multiplyValue = C[pivotColumn];

for(int i=0;i

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

}

for(int i=0;i

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

}

}

void print(){

for(int i=0; i

for(int j=0;j

cout<

}

cout<<""<

}

cout<<""<

}

int findPivotColumn(){

int location = 0;

float minm = C[0];

for(int i=1;i

if(C[i]

minm = C[i];

location = i;

}

}

return location;

}

int findPivotRow(int pivotColumn){

float positiveValues[rows];

std::vector result(rows,0);

int negativeValueCount = 0;

for(int i=0;i

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

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

}

else{

positiveValues[i]=0;

negativeValueCount+=1;

}

}

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;

}

}

}

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++){

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=6;

int rowSizeA = 3;

float C[]= {-6,-5,-4,0,0,0};

float B[]={180,300,240};

float a[3][6] = {

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

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

{ 2, 1, 2, 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];

}

Simplex simplex(vec2D,b,c);

simplex.CalculateSimplex();

return 0;

}