使用C語言實現(xiàn)單純形法求解線性規(guī)劃問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上上 機 實 驗 報 告班級：自動化班專業(yè)/方向：自動化姓名：實 驗 成 績(10分制)學(xué)號：上機實驗名稱：使用C語言實現(xiàn)單純形法求解線性規(guī)劃問題上機時間：2015年5月20日上機地點：信自234一、實驗?zāi)康暮鸵?、目的：l 掌握單純形算法的計算步驟，并能熟練使用該方法求解線性規(guī)劃問題。l 了解算法à程序?qū)崿F(xiàn)的過程和方法。2、要求：l 使用熟悉的編程語言編制單純形算法的程序。l 獨立編程，完成實驗，撰寫實驗報告并總結(jié)。二、實驗內(nèi)容和結(jié)果1、單純形算法的步驟及程序流程圖。（1）、算法步驟（1）將線性規(guī)劃化為標準形。（2）用最快的方法確定一個初始基本可行解X（0

2、）。當s·t均為“”形式時，以松馳變量做初始基本變量最快。（3）求X（0）中非基本變量xj的檢驗數(shù)j。若，則停止運算，X（0）=X*（表示最優(yōu)解），否則轉(zhuǎn)下一步。（4）由確定xk進基；由確定xl出基，其中alk稱為主元素；利用初等變換將alk化為1，并利用alk將同列中其它元素化為0，得新解X（1）。（5）返回（3），直至求得最優(yōu)解為止。（2）、程序圖找出初始基可行解列出初始單純形表計算校驗數(shù)所有j<=0?對于某個j>0，是否存在Pj<=0確定為入基變量確定出基變量計算新的單純形表已得最優(yōu)解，結(jié)束無最優(yōu)解，結(jié)束2、單純形算法程序的規(guī)格說明各段代碼功能描述：（1）、定

3、義程序中使用的變量#include<stdio.h>#include<math.h>#define m 3 /*定義約束條件方程組的個數(shù)*/#define n 5 /*定義未知量的個數(shù)*/float M=.0;float Amn; /*用于記錄方程組的數(shù)目和系數(shù);*/float Cn; /*用于存儲目標函數(shù)中各個變量的系數(shù)*/float bm; /*用于存儲常約束條件中的常數(shù)*/float CBm; /*用于存儲基變量的系數(shù)*/float setam; /*存放出基與入基的變化情況*/float deltan; /*存儲檢驗數(shù)矩陣*/float xn; /*存儲決策變量

4、*/int numm; /*用于存放出基與進基變量的情況*/float ZB=0; /*記錄目標函數(shù)值*/（2）、定義程序中使用的函數(shù)void input();void print();int danchunxing1();int danchunxing2(int a);void danchunxing3(int a,int b);(3)、確定入基變量，對于所有校驗數(shù)均小于等于0，則當前解為最優(yōu)解。int danchunxing1()int i,k=0;int flag=0;float max=0;for(i=0;i<n;i+)if(deltai<=0)flag=1;else fl

5、ag=0;break;if(flag=1)return -1;for(i=0;i<n;i+) if(max <deltai) max =deltai;k=i;return k;(4)、確定出基變量，如果某個大于0的校驗數(shù)，對應(yīng)的列向量中所有元素小于等于0，則線性規(guī)劃問題無解。int danchunxing2(int a)int i,k,j;int flag=0;float min;k=a;for(i=0;i<m;i+)if(Aik<=0)flag=1;else flag=0;break;if(flag=1)printf("n該線性規(guī)劃無最優(yōu)解!n")

6、; return -1;for(i=0;i<m;i+) if(Aik>0) setai=bi/Aik; else setai=M;min=M;for(i=0;i<m;i+) if(min>=setai) min=setai;j=i;numj=k+1;CBj=Ck;return j;(5)、迭代運算，計算新的單純形表。void danchunxing3(int p,int q)int i,j,c,l;float temp1,temp2,temp3;c=p;/*行號*/l=q;/*列號*/temp1=Acl;bc=bc/temp1;for(j=0;j<n;j+)Acj

7、=Acj/temp1; for(i=0;i<m;i+) if(i!=c) if(Ail!=0) temp2=Ail; bi=bi-bc*temp2; for(j=0;j<n;j+) Aij=Aij-Acj*temp2; temp3=deltal;for(i=0;i<n;i+)deltai=deltai-Aci*temp3;(6)、輸入函數(shù)，輸入方程組的系數(shù)矩陣、初始基變量的數(shù)字代碼、方程組右邊的值矩陣、目標函數(shù)各個變量的系數(shù)所構(gòu)成的系數(shù)陣。void print()int i,j=0;printf("n-n");for(i=0;i<m;i+) prin

8、tf("%8.2ftX(%d) %8.2f ",CBi,numi,bi); for(j=0;j<n;j+) printf("%8.2f ",Aij); printf("n");printf("n-n");printf("ttt");for(i=0;i<n;i+)printf(" %8.2f",deltai);printf("n-n");void input()int i,j; /*循環(huán)變量*/int k;printf("請輸入方程組的

9、系數(shù)矩陣A(%d行%d列):n",m,n);for(i=0;i<m;i+)for(j=0;j<n;j+)scanf("%f",&Aij);printf("n請輸入初始基變量的數(shù)字代碼num矩陣:n");for(i=0;i<m;i+)scanf("%d",&numi);printf("n請輸入方程組右邊的值矩陣b:n");for(i=0;i<m;i+)scanf("%f",&bi);printf("n請輸入目標函數(shù)各個變量的系數(shù)所

10、構(gòu)成的系數(shù)陣C:n");for(i=0;i<n;i+)scanf("%f",&Ci);for(i=0;i<n;i+)deltai=Ci;for(i=0;i<m;i+) k=numi-1; CBi=Ck;(7)、主函數(shù)，調(diào)用前面定義的函數(shù)。main()int i,j=0;int p,q,temp;input();printf("n-n");printf(" tCBtXBtbt");for(i=0;i<n;i+)printf(" X(%d)t",i+1);for(i=0;i&l

11、t;n;i+)xi=0;printf("n");while(1) q=danchunxing1(); if(q=-1) print(); printf("n所得解已經(jīng)是最優(yōu)解!n"); printf("n最優(yōu)解為:n"); for(j=0;j<m;j+) temp=numj-1; xtemp=bj; for(i=0;i<n;i+) printf("x%d=%.2f ",i+1,xi); ZB=ZB+xi*Ci; printf("ZB=%.2f",ZB); break; print()

12、; p=danchunxing2(q); printf("np=%d,q=%d",p,q); if(q=-1) break; danchunxing3(p,q);輸入:（1）、輸入方程組的系數(shù)矩陣A(3行5列)（2）、輸入初始基變量的數(shù)字代碼num矩陣（3）、輸入方程組右邊的值矩陣b（4）、輸入目標函數(shù)各個變量的系數(shù)所構(gòu)成的系數(shù)陣C輸出：（1）、輸出是否為最優(yōu)解（2）、輸出最優(yōu)解為多少3、使用所編程序求解如下LP問題并給出結(jié)果。請輸入方程組的系數(shù)矩陣A(3行5列):2 2 1 0 04 0 0 1 00 5 0 0 1請輸入初始基變量的數(shù)字代碼num矩陣:3 4 5請輸入方

13、程組右邊的值矩陣b:12 16 15請輸入目標函數(shù)各個變量的系數(shù)所構(gòu)成的系數(shù)陣C:2 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)- 0.00 X(3) 12.00 2.00 2.00 1.00 0.00 0.00 0.00 X(4) 16.00 4.00 0.00 0.00 1.00 0.00 0.00 X(5) 15.00 0.00 5.00 0.00 0.00 1.00- 2.00 3.00 0.00 0.00 0.00-p=2,q=1- 0.00 X(3) 6.00 2.00 0.00 1.00 0.00 -0.40 0.00 X(4) 16.00

14、 4.00 0.00 0.00 1.00 0.00 3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20 2.00 0.00 0.00 0.00 -0.60-p=0,q=0- 2.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20- 0.00 0.00 -1.00 0.00 -0.20-P26 例5 程序運行結(jié)果- 0.00 0.00 -1.00 0.00 -0.20-所得解已經(jīng)是最

15、優(yōu)解!最優(yōu)解為:x1=3.00 x2=3.00 x3=0.00 x4=4.00 x5=0.00 ZB=15.00輸出：請輸入方程組的系數(shù)矩陣A(3行5列):1 0 0.5 0 -0.20 0 -2 1 0.80 1 0 0 0.2請輸入初始基變量的數(shù)字代碼num矩陣:3 4 5請輸入方程組右邊的值矩陣b:3 4 3請輸入目標函數(shù)各個變量的系數(shù)所構(gòu)成的系數(shù)陣C:3 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)0.00 X(3) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00

16、 0.80 0.00 X(5) 3.00 0.00 1.00 0.00 0.00 0.20- 3.00 3.00 0.00 0.00 0.00-p=0,q=0- 3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 - 0.00 3.00 -1.50 0.00 0.60-p=2,q=1- 3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 3.00 X(2) 3.00 0.0

17、0 1.00 0.00 0.00 0.20 P33 例7程序運行結(jié)果所得解已經(jīng)是最優(yōu)解!最優(yōu)解為:x1=4.00 x2=2.00 x3=0.00 x4=0.00 x5=5.00 ZB=18.00輸出：3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20- 0.00 0.00 -1.50 0.00 0.00-p=1,q=4- 3.00 X(1) 4.00 1.00 0.00 -0.00 0.25 0.00 0.00 X(5) 5.00 0.00 0.00 -2.50 1.25 1.00 3.00 X(2) 2.00 0.00 1.00 0.50 -0.25 0.00-

18、0.00 0.00 -1.50 -0.00 0.00-請輸入方程組的系數(shù)矩陣A(3行5列):4 0 1 0 00 0 0 0 00 0 0 0 0請輸入初始基變量的數(shù)字代碼num矩陣:3 4 5請輸入方程組右邊的值矩陣b:16 0 0請輸入目標函數(shù)各個變量的系數(shù)所構(gòu)成的系數(shù)陣C:2 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)P34例8程序運行結(jié)果所得解已經(jīng)是最優(yōu)解!最優(yōu)解為:x1=0.00 x2=0.00 x3=16.00 x4=0.00 x5=0.00 ZB=-1.# 0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00 0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00- 2.00 3.00 0.00 0.00 0.00-該線性規(guī)劃無最優(yōu)解!p=-1,q=1- 0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00 0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00- -1.#J -1.#J -1.#J -1.#J -1.#J-輸出：請輸入方程組的系數(shù)矩陣A(3行5列