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

《單純形法求解線性規(guī)劃的步驟》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、單純形法求解線性規(guī)劃的步驟?1>????初始化將給定的線性規(guī)劃問題化成標(biāo)準(zhǔn)形式,并建立一個(gè)初始表格,它最右邊的單元格都是非負(fù)的(否則無解),接下來的m列組成一個(gè)m*m的單元矩陣(目標(biāo)行的單元格則不必滿足這一條件),這m列確定了初始的基本可行解的基本變量,而表格中行用基本變量來表示2>????最優(yōu)化測(cè)試如果目標(biāo)行的所有單元格都是非負(fù)的(除了最右列中代表目標(biāo)函數(shù)值的那個(gè)單元格),就可以停止了,該表格代表了一個(gè)最優(yōu)解,它的基本變量的值在最右列中,而剩下的非基本變量都為03>????確定輸入變量從目標(biāo)行的前n個(gè)單元格中選

2、擇一個(gè)負(fù)的單元格(選擇絕對(duì)值最大的那個(gè))該單元格所在的列確定的輸入變量及主元列4>????確定分離變量對(duì)于主元列的每個(gè)正單元格,求出θ比率(如果主元格的單元格為負(fù)或?yàn)?,說明該問題是無解的,算法終止),找出θ比率最小的列,改行確定了分離變量和主元行5>????建立下一張表格將主元行的所有單元格除以主元得到新的主元行,包括主元行在內(nèi)的每一行,要減去改行主元列單元格和新主元行的成績(jī)(除主元行為1外,這一步將主元列的所有單元格變成0).把主元列的變量名進(jìn)行代換,得到新的單純形表,返回第一步??為求簡(jiǎn)單在本程序中,需要自

3、己建立標(biāo)準(zhǔn)矩陣(比如加入松弛變量等工作需要用戶自己完成),程序的輸入有兩種方式:1:指定行和列,由用戶自行輸入每一個(gè)元素??SimpleMatrix(introw=0,intcol=0);2:直接在主程序中初始化一個(gè)二維數(shù)組,然后利用構(gòu)造函數(shù)??SimpleMatrix(introw,intcol,double**M)?來初始化和處理(本程序所用的實(shí)例用的是這種方法)?程序中主要的函數(shù)以及說明~SimpleMatrix();???銷毀動(dòng)態(tài)分配的數(shù)組.用于很難預(yù)先估計(jì)矩陣的行和列,所以在程序中才了動(dòng)態(tài)的內(nèi)存分配.需

4、要重載析構(gòu)函數(shù)boolIs_objectLine_All_Positive();???//判斷目標(biāo)行是否全部為非負(fù)數(shù),最后一列不作考慮這個(gè)函數(shù)用來判斷是否已經(jīng)存在最優(yōu)解boolIs_MainCol_All_Negative(intcol);//判斷主元列是否全部為負(fù)數(shù)或零這個(gè)函數(shù)用來判斷線性規(guī)劃是否是無解的boolIs_column_all_Positive(intcol);?//判斷col列中是否全部為正(不包括目標(biāo)行)用來判斷線性規(guī)劃是否存在最優(yōu)解,因?yàn)槿绻詈笠涣腥绻胸?fù)數(shù)的化,就無解了,算法終止intIn

5、Column();????//確定輸入變量用來判斷主元所在的列intDepartRow(intcol);??//確定分離變量(尋找主元)用來確定主元所在的行voidMainItem_To_1(introw,intcol);??//將主元所在的行做處理,使主元變?yōu)?voidSubMatrixLine(introw1,introw2,intcol);//將矩陣的其他行做處理,矩陣的兩行相減這個(gè)函數(shù)是在主元行已經(jīng)做處理以后調(diào)用,目的是是矩陣的其他行主元列的元素變成0.其中row2為主元所在的行,col為主元所在的列,r

6、ow1為要處理的行voidPrintAnswer();??//輸出矩陣的最優(yōu)解intGetRows();????//返回矩陣的行數(shù)intGetCols();????//返回矩陣的列數(shù)doubleGetItem(introw,intcol);??//返回矩陣第row行,第col列的元素源代碼//SimpleMatrix.h#ifndefSIMPLEMATRIX_H_#defineSIMPLEMATRIX_H_classSimpleMatrix{public:???SimpleMatrix(introw=0,intc

7、ol=0);???SimpleMatrix(introw,intcol,double**M);???~SimpleMatrix();???boolIs_objectLine_All_Positive();???//判斷目標(biāo)行是否全部為非負(fù)數(shù),最后一列不作考慮???boolIs_MainCol_All_Negative(intcol);//判斷主元列是否全部為負(fù)數(shù)或零???boolIs_column_all_Positive(intcol);?//判斷col列中是否全部為正(不包括目標(biāo)行)???intInColum

8、n();????//確定輸入變量???intDepartRow(intcol);??//確定分離變量(尋找主元)???voidMainItem_To_1(introw,intcol);??//將主元所在的行做處理,使主元變?yōu)????voidSubMatrixLine(introw1,introw2,intcol);//將矩陣的其他行做處理,矩陣的兩行相減???voidPr