1、精選優(yōu)質(zhì)文檔-傾情為你奉上單純形法大M法實驗報告目錄一、 實驗目的使用目前熟悉的語言，實現(xiàn)所學的單純形法之大M法，并正確運算測試結(jié)果。本組成員使用C語言實現(xiàn)。 二、 單純形法及大M法1. 單純形法（Simplex Method）（1） 單純形法是解線性規(guī)劃問題的一個重要方法。其原理的基本框架為：第一步：將LP線性規(guī)劃變標準型，確定一個初始可行解（頂點）。第二步：對初始基可行解最優(yōu)性判別，若最優(yōu)，停止；否則轉(zhuǎn)下一步。第三步：從初始基可行解向相鄰的基可行解（頂點）轉(zhuǎn)換，且使目標值有所改善目標函數(shù)值增加，重復第二和第三步直到找到最優(yōu)解。（2） 用程序進行運算前，要將目標函數(shù)及約束方程變成標準形式。對

2、于非標準形式須作如下變換：a) 目標函數(shù)為極小值min z=CX時，轉(zhuǎn)換為max z=-CX形式；b) 在約束方程中有 “”時，在加上一個松弛變量；c) 在約束方程中有 “”時，采用減去一個松弛變量，再加上一個人工變量；d) 在約束方程中有 “=”時，加上一個人工變量；e) 所有的人工變量，松弛變量的目標函數(shù)系數(shù)置為0。（3） 對于標準形式的線性規(guī)劃問題。用單純形法計算步驟的框圖（4） 在程序運算過程中，采用單純形表顯示運算過程。2. 大M法（1） 方法：在約束條件中，加入人工變量后，要求目標函數(shù)不受影響，目標函數(shù)中人工變量的系數(shù)取 M（M為系統(tǒng)所能表示范圍內(nèi)的一個非常大的值本程序取），其運算

3、過程同單純形法。（2） 理由：目標函數(shù)實現(xiàn)最大化，就必須將人工變量從基變量中換出，否則目標函數(shù)就不可能取得最大化。三、 數(shù)據(jù)結(jié)構(gòu)及模塊設計1. 程序中用到的數(shù)據(jù)結(jié)構(gòu)：#define M 20 /最大20個變量#define N 40 /40個約束方程#define Max /大Mdouble DMN;/系數(shù)矩陣double CM;/目標函數(shù)系數(shù)double CbM;/基向量系數(shù)double BM;/約束常數(shù)double ValueN;/檢驗數(shù)int XbM;/基向量double X0M;/可行解int opM;/約束方程符號0-"<"、1-"="、

4、2-">"int m,n;/矩陣行數(shù)、列數(shù)int begin_n;/初始變量數(shù)int In_BaseX=-1;/進基變量int in_n=-1;/進基列標示int out_m=-1;/出基行標示int Out_BaseX=-1;/出基變量int best;/最優(yōu)函數(shù)返回值char name30;/文件名int ManX_num=0;/人工變量數(shù)目int ManX_listM;/人工變量存放數(shù)組2. 模塊設計：void read();/讀取方程子函數(shù)void print();/顯示單純表子函數(shù)void init_change();/初始變換子函數(shù)void compute

5、_value();/計算檢驗數(shù)子函數(shù)int best_Result();/判斷是否得到最優(yōu)解子函數(shù)void in_base();/進基選子函數(shù)void out_base();/出基選擇子函數(shù)void row_change();/行變換子函數(shù)四、 詳細設計1. 文件格式定義格式：（行數(shù)/約束方程數(shù)：列數(shù)/變量數(shù)：） m n （約束矩陣： 符號：0小于，1等于，2大于 B值）D11 D12 D13 Dn1 op1 b1D21 D22 D23 Dn2 op2 b2.Dm1 D2m Dm3 Dnm opm bm（最大值/最小值：1最大，2最小）max/min目標函數(shù)的變量系數(shù)：C1C2 C3 . Cn

6、例：32 0.60.50120000.40.10400000.406000125102. void read()讀取約束矩陣、目標函數(shù)void read()FILE *fp ;/文件int i=0,j=0,k;fp=fopen(name,"r");if(fp!=NULL)/讀變量數(shù)目和約束方程個數(shù)m,nfscanf(fp,"%d",&m);fscanf(fp,"%d",&n); begin_n=n;/初始（未經(jīng)過標準化）變量數(shù)置為n,for(i=0;i<m;i+)/按行讀取約束矩陣，約束方程符號，常數(shù)值for(j

7、=0;j<n;j+)/讀取約束矩陣if(fp!=NULL)fscanf(fp,"%lf",&Dij);elseprintf("error");if(fp!=NULL)/讀約束方程符號fscanf(fp,"%d",&opi);elseprintf("error");if(fp!=NULL)/讀取常數(shù)值fscanf(fp,"%lf",&Bi);elseprintf("error");if(fp!=NULL)/讀取目標函數(shù)類型fscanf(fp,&qu

8、ot;%d",&Type);elseprintf("error");for(k=0;k<n;k+)/讀取目標函數(shù)變量系數(shù)if(fp!=NULL)fscanf(fp,"%lf",&Ck);elseprintf("error");fclose(fp); / void read()3. void print()單純形表顯示函數(shù)void print()int i=0,j=0;void line_V(int);/豎線子函數(shù)void line_R(int);/橫線子函數(shù)void ln();/換行子函數(shù)void sp

9、ace();/空格子函數(shù)ln();/第1條直線line_R(15+n*5);ln(); /顯示第1行 “ C | C1 C2 C3 .” space(6);printf("C");space(7);line_V(1);for(i=0;i<n;i+)if(Ci=-Max)printf(" -M");elseprintf("%5.1lf",Ci);ln();/第2條直線line_R(15+n*5);ln();/顯示第2行“Cb Xb B| X1 X2 X3 .”printf("Cb Xb B ");line_V(

10、1);for(i=0;i<n;i+)printf(" X%-2d",i+1);ln();/第3條直線line_R(15+n*5);ln();/顯示第3部分“Cb1 Xb1 B1| D11 D12 D13 .”/ “Cb2 Xb2 B2| D21 D22 D23 .”/“Cb3 Xb3 B3| D31 D32 D33 .”/“. ”for(i=0;i<m;i+)if(Cbi=-Max)printf("-M ");elseprintf("%-5.0lf",Cbi);printf("X%-2d",Xbi+1)

11、;printf("%5.0lf ",Bi);line_V(1);for(j=0;j<n;j+)printf("%5.1lf",Dij);ln();/第4條直線line_R(15+n*5);ln();/顯示第4行 “ Value | Value1 Value2 Value3 .” space(5);printf("Value");space(4);line_V(1);for(i=0;i<n;i+)if(Valuei>Max/2)/當Value值達到M數(shù)量級時，用aM+b表示int k=(int)(Valuei/Max)

12、;double l=Valuei-k*Max;if(l>Max/2)k+;l-=Max;if(k=0)printf(" ");else if(k=1)printf(" M");elseprintf("%dM",k);if(l=0)printf(" ");else if(l>0)printf("+%-1.0lf",l);elseprintf("%-2.0lf",l);else if(Valuei<-Max/2) /當Value值達到M數(shù)量級時，用aM+b表示i

13、nt k=(int)(Valuei/Max);double l=Valuei-k*Max;if(l<-Max/2)k-;l+=Max;if(k=0)printf(" ");else if(k=-1)printf(" -M");elseprintf("%dM",k);if(l=0)printf(" ");else if(l>0)printf("+%-1.0lf",l);else if(l<0)printf("%-2.0lf",l);else/正常顯示print

14、f(" %4.1lf",Valuei);ln();/第5條直線line_R(15+n*5);ln();/顯示第5行 “ X(0)=( X1， X2， X3.)”space(1);printf("X(0)=(");for(i=0;i<n-1;i+)printf("%.2lf,",X0i);printf("%.1lf",X0i);printf(")");ln();line_R(15+n*5); /第6條直線ln();/*橫線*void line_R(int n)int i;for(i=0;i&

15、lt;n;i+)printf("-");/*豎線*void line_V(int n)int i;for(i=0;i<n;i+)printf("|");/*空格*void space(int n)int i;for(i=0;i<n;i+)printf(" ");/*換行*void ln()printf("n ");4. void init_change()初始矩陣變換，加入松弛變量和人工變量void init_change()int i=0,j;int base_variable(int x);/判斷是

16、否為基變量的子函數(shù)/對 ">=" 約束方程，減去松弛變量，目標系數(shù)為0for(i=0;i<m;i+)if(opi=2)n+;Cn-1=0;for(j=0;j<m;j+)if(j=i)Djn-1=-1;elseDjn-1=0;for(i=0;i<m;i+)/對有 ">="和"=" 約束方程，加上人工變量，目標系數(shù)為Mif(opi=2|opi=1)n+;ManX_listManX_num=n-1;/將人工變量下標存入人工變量表ManX_num+;/人工變量數(shù)目加1Xbi=n-1;Cn-1=-Max;/人工變量

17、的系數(shù)去-MCbi=Cn-1;for(j=0;j<m;j+)if(j=i)Djn-1=1;elseDjn-1=0;/對有 "<=" 約束方程，加上松弛變量，目標系數(shù)為0elsen+;Xbi=n-1;Cn-1=0;Cbi=Cn-1;for(j=0;j<m;j+)if(j=i)Djn-1=1;elseDjn-1=0;/如果是求最小值，則通過將目標函數(shù)各變量系數(shù)去相反數(shù)if(Type=2)for(i=0;i<n;i+)/讀取目標函數(shù)變量系數(shù)Ci=-Ci;/初始可行解for(i=0;i<n;i+)if(j=base_variable(i)!=-1)X0

18、i=Bj;elseX0i=0;/init_change()int base_variable(int x) /*判斷是否為基變量，若是，返回下標，否則返回-1*int j;for(j=0;j<m;j+)if(x=Xbj)return j;return -1;5. void compute_value()計算檢驗數(shù)void compute_value()int i,j,k;int base_variable(int x);/判斷是否為基變量的子函數(shù)for(i=0;i<n;i+)if(j=base_variable(i)!=-1) /基變量的檢驗數(shù)為0Valuei=0;else/非基變

19、量Xi的檢驗數(shù)為Ci-Cb*Dmidouble sum=0;for(k=0;k<m;k+)sum+=Cbk*Dki;Valuei=Ci-sum;/compute_value()6. int best_Result()判斷是否得到最優(yōu)解。int best_Result()/唯一最優(yōu)1，無窮多最優(yōu)2，無界3，無可行5，未得到返回4int i;int less=0,more=0,equal=0;/檢驗數(shù)各種情況的數(shù)目小于0，大于0，等于0；int only_more=-1;/當只有一個檢驗數(shù)大于0時，記錄進基變量的列數(shù)for(i=0;i<n;i+)/統(tǒng)計大于0，等于0，小于0個數(shù)if(V

20、aluei<0)less+;else if(Valuei=0)equal+;else if(Valuei>0)more+;only_more=i; if(more=0) /無檢驗數(shù)大于0/若基解中有人工變量不為0，則無可行解for(i=0;i<ManX_num;i+)if(X0ManX_list1!=0)return 5;/非基變量檢驗數(shù)至少一個等于0，得到無窮多最優(yōu)解for(i=0;i<n;i+)if(Valuei!=0&&base_variable(i)!=-1)return 2;/檢驗數(shù)全部小于0，得到唯一最優(yōu)解else return 1;/檢驗數(shù)

21、只有1個大于0，并且無出基變量，得到無界解else if(more=1)for(i=0;i<m;i+)/是否進基變量所在列的所有D值都小于0if(Dionly_more>0)return 4;/有一個大于0，不能判斷return 3;/全部小于0，無出基變量，得到無界解/檢驗數(shù)至少有2個大于0，不能判斷else return 4;/best_Result()f void in_base();/進基選子函數(shù)void out_base();/出基選擇子函數(shù)void row_change();/行變換子函數(shù)7. void in_base() 進基選子函數(shù)void in_base()dou

22、ble max=0; int i;int max_num=-1;/初始最大的檢驗數(shù)下標為-1for(i=0;i<n;i+)/冒泡算法，求的最大檢驗數(shù)下標if(Valuei>max)max=Valuei;max_num=i;in_n=i;In_BaseX=max_num;/存到全局變量In_BaseX/in_base()8. void out_base()出基選擇子函數(shù)void out_base()double tempM;int i;int in=In_BaseX;double min=Max;int min_num=-1;/初始最小B/Dij下標為-1for(i=0;i<m

23、;i+)/計算B/Dij的值/D值為零，Dif(Diin>0)tempi=Bi/Diin;else tempi=Max;for(i=0;i<m;i+)/冒泡算法，求最小B/Dij下標if(tempi<min)min=tempi;min_num=Xbi;out_m=i;Out_BaseX=min_num;/存到全局變量Out_BaseX/out_base()9. void row_change()行變換子函數(shù)void row_change()int i,j;double temp;Xbout_m=In_BaseX;/進基變量進基/對出基行變換，包括系數(shù)矩陣和B值temp=Dout_min_n;for(j=0;j<n;j+)Dout_mj=Dout_mj/temp;Bout_m=Bout_m/temp;/對其他行變換for(i=0;i<m;i+)/不是出基行，并且其對應進基列值不為0，變換if(i!=out_m&&Diin_n!=0)double m=Diin_n;/倍數(shù)for(j=0;j<n;j+)/系數(shù)矩陣變換Dij=Dij-m*Dout_mj;Bi=Bi-m*Bout_m;/B值