單純形法求解線性規(guī)劃的步驟(已修改)
2025-08-02 00:19 本頁(yè)面
【正文】 單純形法求解線性規(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,int col=0)。2:直接在主程序中初始化一個(gè)二維數(shù)組,然后利用構(gòu)造函數(shù) SimpleMatrix(introw,int col,double **M) 來(lái)初始化和處理(本程序所用的實(shí)例用的是這種方法)程序中主要的函數(shù)以及說(shuō)明~SimpleMatrix()。,bool Is_objectLine_All_Positive()。//判斷目標(biāo)行是否全部為非負(fù)數(shù),最后一列不作考慮這個(gè)函數(shù)用來(lái)判斷是否已經(jīng)存在最優(yōu)解bool Is_MainCol_All_Negative(int col)。//判斷主元列是否全部為負(fù)數(shù)或零這個(gè)函數(shù)用來(lái)判斷線性規(guī)劃是否是無(wú)解的bool Is_column_all_Positive(int col)。 //判斷col列中是否全部為正(不包括目標(biāo)行)用來(lái)判斷線性規(guī)劃是否存在最優(yōu)解,因?yàn)槿绻詈笠涣腥绻胸?fù)數(shù)的化,就無(wú)解了,算法終止int InColumn()。//確定輸入變量用來(lái)判斷主元所在的列int DepartRow(int col)。//確定分離變量(尋找主元)用來(lái)確定主元所在的行void MainItem_To_1(int row,int col)。//將主元所在的行做處理,使主元變?yōu)?void SubMatrixLine(int row1,int row2,intcol)。//將矩陣的其他行做處理,矩陣的兩行相減這個(gè)函數(shù)是在主元行已經(jīng)做處理以后調(diào)用,目的是是矩陣的其他行主元列的元素變成0.其中row2為主元所在的行,col為主元所在的列,row1為要處理的行void PrintAnswer()。//輸出矩陣的最優(yōu)解int GetRows()。//返回矩陣的行數(shù)int GetCols()。//返回矩陣的列數(shù)double GetItem(int row,int col)。//返回矩陣第row行,第col列的元素源代碼//ifndef SIMPLEMATRIX_H_define SIMPLEMATRIX_H_class SimpleMatrix{public:SimpleMatrix(int row=0,int col=0)。SimpleMatrix(int row,int col,double **M)。~SimpleMatrix()。 bool Is_objectLine_All_Positive()。//判斷目標(biāo)行是否全部為非負(fù)數(shù),最后一列不作考慮 bool Is_MainCol_All_Negative(int col)。//判斷主元列是否全部為負(fù)數(shù)或零 bool Is_column_all_Positive(int col)。//判斷col列中是否全部為正(不包括目標(biāo)行) int InColumn()。//確定輸入變量 int DepartRow(int col)。//確定分離變量(尋找主元) void MainItem_To_1(int row,int col)。//將主元所在的行做處理,使主元變?yōu)? vo
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1