运筹学-单纯形法解线性规划的计算机模拟.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

dragon1104-2026057-4744300845233867417.doc.pdf-第1页.png

第1页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第2页.png

第2页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第3页.png

第3页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第4页.png

第4页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第5页.png

第5页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第6页.png

第6页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第7页.png

第7页 / 共10页

dragon1104-2026057-4744300845233867417.doc.pdf-第8页.png

第8页 / 共10页

文本预览

运筹学单纯形法解线性规划的模拟实现

一．单纯形法介绍单纯形法是求解线性规划问题的通用方法。它的理论根据是：线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n 的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解； ③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有 106 个决策变量和 104 个约束条件的线性规划问题已能在计算机上解得。二．单纯形法的编程思路单纯形法的一般解题步骤可归纳如下： ①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。 ②若基本可行解不存在，即约束条件有矛盾，则问题无解。 ③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。 ④按步骤 3 进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。 ⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。按此解题步骤可以通过 C++程序进行编程。三．单纯形法的程序代码 #include #include #include float matrix[100][100],x[100]; /* 记录总方程的数组,解的数组 */ int a[100]; /* 记录基础,非基础的解的情况,0:非基础,1:基础 */ int m,n,s,type; /* 方程变量,约束数,求最大最小值的类型,0:最小 1:最大 */ int indexe,indexl,indexg; /* 剩余变量,松弛变量,人工变量 */ void Jckxj() { int i,j; for(i=0;i

x[j]=matrix[i][s]; j=s; } for(i=0;i=0.000001) if(matrix[n][i]<0) return 0; return 1; } int Min() { int i,temp=0; float min=matrix[n][0]; for(i=1;imatrix[n][i]) { min=matrix[n][i]; temp=i; } return temp; } void JustArtificial() { int i; for(i=m+indexe+indexl;i=0.000001) { printf("无解"); return; } } int Check(int in) { int i; float max1=-1;

for(i=0;i=0.000001&&max1=0.000001&&(matrix[i][s]/matrix[i][in]>=0)&&min>matrix[i][s]/matr ix[i][in]) { min=matrix[i][s]/matrix[i][in]; *temp=i; } for(i=0;i

void Achange(int in,int out) { int temp=a[in]; a[in]=a[out]; a[out]=temp; } void Print() { int i,j,k,temp=0; for(i=0;i

printf(" ("); for(i=0;i

for(i=0;i>m; cout<<" 请输入方程的约束条件个数:"; cin>>n; cout<=n )"<>matrix[i][j]; /* 输入方程 */ cin>>b[i]>>code[i]; } cout<<" 请输入目标函数 Z 中的系数:"; /* 输入 z */ for(i=0;i>matrix[n][i]; cout<<" 请选择求解类型( 0:Min 1:Max )"; /* 输入求最大值还是最小值 */ do { cin>>type; if(type!=0&&type!=1) printf("输入错误!"); }while(type!=0&&type!=1); if(type==1) for(i=0;i

for(j=0;j

分享到：

赞收藏

资料库

运筹学-单纯形法解线性规划的计算机模拟.doc

相关推荐

开发技术

热门标签

最新资料