1、華北水利水電學院 算法分析與設計 實驗報告200102011學年 第 二 學期 2008級 計算機科學與技術專業班級：2008109 學號：200810906 姓名：劉景超實驗四 單純形算法的設計與實現一、 實驗目的：1、 了解單純形算法的設計思路與設計技巧，理解單純形算法的概念，掌握設計有效的單純形算法的策略。2、 通過實際案例，領會算法的執行效率二、 試驗內容：單純形算法三、核心程序源代碼：#include <fstream>#include <iostream>#include <cmath>#include <iomanip>#inclu

2、de <cfloat>using namespace std;class LinearProgrampublic:LinearProgram(char *filename);/LinearProgram();void solve();private:int enter(int objrow);int leave(int col);int simplex(int objrow);int phase1();int phase2();int compute();void swapbasic(int row, int col);void pivot(int row, int col);/v

3、oid stats();void setbasic(int *basicp);void output();int m,/ 約束總數n,/ 變量數m1,/ 不等式約束數（<=）m2,/ 等式約束數m3,/ 不等式約束數（>=）n1,n2,/ n1 = n + m3; n2 = n1 + m1;error,/ 記錄錯誤類型*basic,/ 基本變量下標*nonbasic;/ 非基本變量下標double *a, minmax;void Make2DArray(double * &x,int rows,int cols)x=new double*rows; for(int i=0;

4、i<rows;i+) xi=new doublecols; LinearProgram:LinearProgram(char *filename)ifstream inFile;int i,j;double value;cout<<"按照下列格式數據："<<endl;cout<<"1: +1(max)或-1(min); m; n"<<endl;cout<<"2: m1; m2; m3"<<endl;cout<<"約束系數和右端項&quo

5、t;<<endl;cout<<"目標函數系數"<<endl<<endl;error=0;inFile.open(filename);inFile>>minmax;inFile>>m;inFile>>n;/輸入各類約束數inFile>>m1;inFile>>m2;inFile>>m3;if(m!=m1+m3+m2)error=1;n1=n+m3;n2=n+m1+m3;Make2DArray(a,m+2,n1+1);basic = new int m+2;no

6、nbasic = new int n1+1;/初始化基本變量和非基本變量for(i=0; i<=m+1; i+)for(j=0; j<=n1; j+)aij = 0.0;for(j=0; j<=n1; j+)nonbasicj = j;/引入松弛變量和人工變量for(i=1, j=n1+1; i<=m; i+,j+)basici = j;for(i = m-m3+1, j=n+1; i<=m; i+,j+)aij = -1.0;am+1j = -1.0;/輸入約束系數和右端項for(i=1; i<=m; i+)for(j=1; j<=n; j+)inF

7、ile>>value;aij = value;inFile>>value;if(value<0) error = 1;ai0 = value;/輸入目標函數系數for(j=1; j<=n; j+)inFile>>value;a0j = value*minmax;/引入人工變量，構造第一階段的輔助目標函數for(j=1; j<=n; j+)for(i=m1+1, value=0.0; i<=m; i+)value += aij;am+1j = value;inFile.close();int LinearProgram:simplex(

8、int objrow)for(int row=0;)int col = enter(objrow);if(col>0) row = leave(col);else return 0;if(row>0)pivot(row,col);else return 2;int LinearProgram:enter(int objrow)double temp = DBL_EPSILON;for(int j=1, col=0; j<=n1; j+)if(nonbasicj<=n2 && aobjrowj>temp)col=j; temp = aobjrowj;

9、break; /Bland 避免循環法則return col;int LinearProgram:leave(int col)double temp = DBL_MAX;for(int i=1, row=0; i<=m; i+)double val = aicol;if(val>DBL_EPSILON)val = ai0/val;if(val<temp)row = i;temp = val;return row;void LinearProgram:pivot(int row, int col)for(int j=0; j<=n1; j+)if(j!=col)arowj

10、 = arowj/arowcol;arowcol = 1.0/arowcol;for(int i=0; i<=m+1; i+)if(i!=row)for(int j=0; j<=n1; j+)if(j!=col)aij = aij - aicol * arowj;if(fabs(aij)<DBL_EPSILON)aij = 0.0;aicol = -aicol*arowcol;swapbasic(row,col);void LinearProgram:swapbasic(int row, int col)int temp = basicrow;basicrow = nonba

11、siccol;nonbasiccol = temp;int LinearProgram:compute()if(error>0)return error;if(m != m1)error = phase1();if(error>0)return error;return phase2();int LinearProgram:phase1()error = simplex(m+1);if(error>0)return error;for(int i=1; i<=m; i+)if(basici>n2)if(ai0 > DBL_EPSILON)return 3;f

12、or(int j=1; j<=n1; j+)if(fabs(aij)>=DBL_EPSILON)pivot(i,j);break;return 0;int LinearProgram:phase2()return simplex(0);void LinearProgram:solve()/cout<<endl<<"*線性規劃單純形算法*"<<endl<<endl;error = compute();switch(error)case 0:output();break;case 1:cout<<"

13、;-輸入數據錯誤"<<endl;break;case 2:cout<<"-無界解"<<endl;break;case 3:cout<<"-無可行解"<<endl;break;cout<<"計算結束"<<endl;void LinearProgram:setbasic(int *basicp)int i;for(i=0; i<=n+m; i+)basicpi = 0;for(i=1; i<=m; i+)basicpbasici =

14、i;void LinearProgram:output()int width = 8, *basicp;double zero = 0.0;/ofstream fout("output.txt");basicp = new intn+m+1;setbasic(basicp);cout.setf(ios:fixed|ios:showpoint|ios:right);cout.precision(4);/stats();cout<<endl<<"*線性規劃單純形算法*"<<endl<<endl;cout<<endl<<"最優值："<<-minmax*a00<<endl<<endl;cout<<"最優解："<<endl<<endl;for(int j=1; j<=n+m; j+)cout<<"x"<<j<<" = "if(basicpj!=0)cout<<setw(width)<<abasicpj0<<'t'else cou