單純形法求解線性規(guī)劃的步驟

單純形法求解線性規(guī)劃的步驟單純形法求解線性規(guī)劃的步驟單純形法求解線性規(guī)劃的步驟V:1.0精細(xì)整理，僅供參考單純形法求解線性規(guī)劃的步驟日期：20xx年X月單純形法求解線性規(guī)劃的步驟

1>

初始化將給定的線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式,并建立一個(gè)初始表格,它最右邊的單元格都是非負(fù)的(否則無(wú)解),接下來(lái)的m列組成一個(gè)m*m的單元矩陣(目標(biāo)行的單元格則不必滿足這一條件),這m列確定了初始的基本可行解的基本變量,而表格中行用基本變量來(lái)表示2>

最優(yōu)化測(cè)試如果目標(biāo)行的所有單元格都是非負(fù)的(除了最右列中代表目標(biāo)函數(shù)值的那個(gè)單元格),就可以停止了,該表格代表了一個(gè)最優(yōu)解,它的基本變量的值在最右列中,而剩下的非基本變量都為03>

確定輸入變量從目標(biāo)行的前n個(gè)單元格中選擇一個(gè)負(fù)的單元格(選擇絕對(duì)值最大的那個(gè))該單元格所在的列確定的輸入變量及主元列4>

確定分離變量對(duì)于主元列的每個(gè)正單元格,求出θ比率(如果主元格的單元格為負(fù)或?yàn)?,說(shuō)明該問(wèn)題是無(wú)解的,算法終止),找出θ比率最小的列,改行確定了分離變量和主元行5>

建立下一張表格將主元行的所有單元格除以主元得到新的主元行,包括主元行在內(nèi)的每一行,要減去改行主元列單元格和新主元行的成績(jī)(除主元行為1外,這一步將主元列的所有單元格變成0).把主元列的變量名進(jìn)行代換,得到新的單純形表,返回第一步

為求簡(jiǎn)單在本程序中,需要自己建立標(biāo)準(zhǔn)矩陣(比如加入松弛變量等工作需要用戶自己完成),程序的輸入有兩種方式:1:指定行和列,由用戶自行輸入每一個(gè)元素

SimpleMatrix(introw=0,intcol=0);2:直接在主程序中初始化一個(gè)二維數(shù)組,然后利用構(gòu)造函數(shù)

SimpleMatrix(introw,intcol,double**M)

來(lái)初始化和處理(本程序所用的實(shí)例用的是這種方法)

程序中主要的函數(shù)以及說(shuō)明~SimpleMatrix();

銷毀動(dòng)態(tài)分配的數(shù)組.用于很難預(yù)先估計(jì)矩陣的行和列,所以在程序中才了動(dòng)態(tài)的內(nèi)存分配.需要重載析構(gòu)函數(shù)boolIs_objectLine_All_Positive();

其中row2為主元所在的行,col為主元所在的列,row1為要處理的行voidPrintAnswer();

數(shù)不合法"<<endl;

}

SimpleMatrix::SimpleMatrix(introw,intcol)

{

init(row,col);

for(inti=0;i<rowLen;i++)

{

cout<<"請(qǐng)輸入矩陣中第"<<i+1<<"行的系數(shù)"<<endl;

for(intj=0;j<colLen;j++)

cin>>data[i][j];

}

}

SimpleMatrix::SimpleMatrix(introw,intcol,double**M)

{

rowLen=row;

colLen=col;

init(row,col);

for(inti=0;i<row;i++)

for(intj=0;j<col;j++)

{

data[i][j]=*((double*)M+col*i+j);

;

}

}

SimpleMatrix::~SimpleMatrix()

{

if(colLen*rowLen!=0)

{

for(inti=rowLen-1;i>=0;i--)

{

if(data[i]!=NULL)

delete[]data[i];

}

if(data!=NULL)

delete[]data;

}

}

boolSimpleMatrix::Is_objectLine_All_Positive()

{

for(inti=0;i<colLen-1;i++)

if(data[rowLen-1][i]<0)

returnfalse;

returntrue;

}

boolSimpleMatrix::Is_MainCol_All_Negative(intcol)

{

for(inti=0;i<rowLen;i++)

if(data[i][col]>0)

returnfalse;

returntrue;

}

boolSimpleMatrix::Is_column_all_Positive(intcol)

{

for(inti=0;i<rowLen-1;i++)

{

if(data[i][col-1]<0)

returnfalse;

}

returntrue;

}

intSimpleMatrix::InColumn()

{

intcount=0;

for(inti=0;i<colLen-1;i++)

{

inttemp=GetItem(rowLen-1,i);

if(temp>=0)

{

count++;

}

else

break;

}

doublemaxItem=fabs(GetItem(rowLen-1,count));

intindex_col;

for(i=0;i<colLen-1;i++)

{

doubletemp=GetItem(rowLen-1,i);

if(temp<0)

{

if(maxItem<=fabs(temp))

{

maxItem=fabs(temp);

index_col=i;

}

}

}

returnindex_col;

}

intSimpleMatrix::DepartRow(intcol)

{

intindex_row;

intcount=0;

for(inti=0;i<rowLen;i++)

{

if(data[i][col]<0)

count++;

else

break;

}

doubleminItem=data[count][colLen-1]/data[count][col];

index_row=count;

doubletemp;

for(i=0;i<rowLen-1;i++)

{

temp=data[i][col];

if(temp>0)

{

temp=data[i][colLen-1]/temp;

if(temp<minItem)

{

minItem=temp;

index_row=i;

}

}

}

returnindex_row;

}

voidSimpleMatrix::MainItem_To_1(introw,intcol)

{

doubletemp=GetItem(row,col);

pp

#include<iostream>

#include""

usingnamespacestd;

intmain()

{

doubleM[4][7]={{5,3,1,1,0,0,9},{-5,6,15,0,1,0,15},{2,-1,1,0,0,-1,5},{-10,-15,-12,0,0,0,}};

SimpleMatrixMatrix(4,7,(double**)M);

if(5))

//判斷是否存在最優(yōu)解

{

boolp=();

//判斷主元列是否全部為正,確定是否已經(jīng)取得最優(yōu)解

while(!p)

{

intcol=();

//確定主元所在的行

if(col))

//確定線性規(guī)劃的解是否為無(wú)解的

{

cout<<"線性規(guī)劃問(wèn)題是無(wú)界的,沒(méi)有最優(yōu)解"<<endl;

exit(EXIT_FAILURE);

}

else

{

intmainRow=(col);

//確定主元所在的行

(mainRow,col);

//將主元所在的行做變換,使主元變成1

inti=0;

while(i<())

{

if(i!=mainRow)

{

(i,mainRow,col);

//處理矩陣中其他的行,使主元列的元素為0

i++;

}

else

{

i++;

}

}

}

for(inti=0;i<();i++)

//輸出變換以后的矩陣,判斷是否正確處理