运筹学——解对偶单纯形法

《运筹学——解对偶单纯形法》由会员分享，可在线阅读，更多相关《运筹学——解对偶单纯形法（13页珍藏版）》请在装配图网上搜索。

1、对偶单纯形法解线性规划问题题目：对偶单纯形法解线性规划问题 小组成员： 摘要： 运筹学是辅助人们进行科学管理的一种数学方法.而对偶单纯形法是线性规划中重要的数学方法，在简化运算，解决实际问题中具有重要的应用。它是解决研究线性约束条件下线性目标函数的极值问题的数学理论和方法，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求。关键词：对偶单纯形法 线性规划 最优解 正文：单纯形法和对偶单纯形法的基本思想： 给出一个线性规划问题:Max z =

2、 CXAXbX0其对偶问题是:Min w = YbYACY0单纯形法解决线性规划问题的思想是:从问题(1)的一个基解X0开始迭代到另一个基解,在迭代过程中保持基解的可行性,同时它对应的对偶问题(2)的基解Y0= CBB-1的不可行性逐步消失,直到Y0是问题(2)的可行解时,X0就是问题(1)的最优解了。对偶单纯形法正是基于对称的想法,从一个基解X0开始,X0不是基可行解,但它的检验数全部非正,对应的对偶问题的基解Y0= CBB-1是基可行解;从X0迭代到另一个基解X1,在迭代过程中保持它对应的对偶问题的基解是基可行解,逐步消除原问题基解的不可行性,最终达到两者同时为可行解，也就同时是最优解了。

3、这就是对偶单纯形法的基本思想。算法：用对偶单纯形法解决生产资料分配问题的步骤:Step1找出一组以定基元素x0i和人工变量为基变量的正则解X0,若X0是可行的,则X0是最优解,停止,否则转向STEP2;Step2确定换出变量x0l,其中x0l=minx0r;x0r0;Step3如果对所有非基变量x0j,lj0,则该问题无可行解,运算停止,否则转向STEP4;Step4确定换入变量x0k,其中klk=mintlt;lt0;1tn+m ;Step5取x0l为换出变量,x0k为换入变量进行迭代,然后重复上过程直到得到最优解。程序：#include#includeint m,n;float M=100

4、0000.0;float A100100; float C100; float b100; float seta100; int num100; float z=0; void input();void print();int duioudanchunxing1();int duioudanchunxing2(int a);void duioudanchunxing3(int a,int b);void input()printf(请输入方程组的系数矩阵维数,m行n列：n);scanf(%d%d,&m,&n);int i,j;printf(请输入方程组的系数矩阵A(%d行%d列):n,m,n)

5、;for(i=0;im;i+)for(j=0;jn;j+)scanf(%f,&Aij);printf(n请输入初始基变量的数字代码num矩阵:n);for(i=0;im;i+)scanf(%d,&numi);printf(n请输入方程组右边的值矩阵b:n);for(i=0;im;i+)scanf(%f,&bi);printf(n请输入目标函数各个变量的系数所构成的系数阵C:n);for(i=0;in;i+)scanf(%f,&Ci);int duioudanchunxing1()int i,k;int flag;float min=0;for(i=0;i=0)flag=1;else flag=

6、0;break;if(flag=1)return -1;for(i=0;ibi) min=bi;k=i;return k;int duioudanchunxing2(int a)int i,j;int flag=0;float min;for(j=0;j=0)flag=1;else flag=0;break;if(flag=1)printf(n该线性规划无最优解!n); return -1;for(j=0;jn;j+) if(Aaj0) setaj=-Cj/Aaj; else setaj=M;min=M;for(j=0;j=setaj) min=setaj;i=j;numa=i+1;retur

7、n i;void duioudanchunxing3(int p,int q)int i,j,c,l;float temp1,temp2,temp3;c=q;l=p;temp1=Acl;bc=bc/temp1;for(j=0;jn;j+)Acj=Acj/temp1;for(i=0;im;i+) if(i!=c) if(Acl!=0) temp2=Ail; bi=bi-bc*temp2; for(j=0;jn;j+) Aij=Aij-Acj*temp2; temp3=Cl;for(i=0;in;i+)Ci=Ci-Aci*temp3;z=z+bc*temp3; void print()int i,

8、j;printf(n-n);printf(t);for(i=0;in;i+) printf(%.3ft,-Ci);printf(%.3f,z);printf(n-n);for(i=0;im;i+) printf(x(%d)t,numi); for(j=0;jn;j+) printf(%.3ft,Aij); printf(%.3fn,bi);printf(n-n); main()int i,j=0;int p,q;input();for(i=0;im;i+) if(Ainumi-1=0) bi=-bi; for(j=0;jn;j+) Aij=-Aij; printf(n-n);printf(t)

9、;for(i=0;in;i+)printf(X(%d)t,i+1);printf(RHSn);while(1) q=duioudanchunxing1(); if(q=-1) printf(n所得解已经是最优解!n); print(); for(i=0;im;i+)printf(x(%d)=%.3ft,numi,bi); printf(z=%.3f,z); break; print(); p=duioudanchunxing2(q); if(q=-1) break; duioudanchunxing3(p,q);流程图：duioudanchunxing1();duioudanchunxing2(int a); duioudanchunxing3(int a,int b);参考文献：1胡运权,甘应爱 .运筹学教程M.北京：清华大学出版社，2009. 2王周宏.运筹学基础M.北京：清华大学出版社，北京交通大学出版社，2010.3何钦铭,颜晖.C语言程序设计M.浙江：浙江科学技术出版社，2003.4吕凤煮.C+语言程序设计教程M.北京：人民邮电出版社.2009. 12