使用C语言实现单纯形法求解线性规划问题

#include<stdio.h>#define M 5#define N 7float Max(float a[],int n);int k,l;void main(){ float a[M][N];//{{0,2,3,0,0,0,0},{12,2,2,1,0,0,0},{8,1,2,0,1,0,0},{16,4,0,0,0,1, 0},{12,0,4,0,0,0,1}};//初始化单纯形表float cb[M],X[N],z[N],cj[N];//z[M]为检验数准备,jj[M],cj[N]是检验数int jj[M],i,j;int s,p,t=0;float maxcj,Z=0.0;printf("请输入一个%d行%d列的初始单纯形表用于求解%d个约束条件%d个变量的线性规划的原问题！",M,N,M-1,N-1);printf("\n"); printf("请输入初始单纯形表的第1行元素即变量的价值系数（第一个元素应默认为0.0）！");printf("\n");for(j=0;j<N;j++)scanf("%f",&a[0][j]);for(i=1;i<M;i++){printf("请输入初始单纯形表的第%d行元素即限定条件与系数矩阵！",i+1);printf("\n");for(j=0;j<N;j++)scanf("%f",&a[i][j]);}//初始化单纯形表*/for(i=1;i<N;i++) //最优解矩阵的初始化X[i]=0.0;for(j=1;j<N;j++){ s=0;p=0;for(i=1;i<M;i++){if(a[i][j]==1){s++;p=i;}}if(s==1)jj[p]=j;} //确定初始基变量，并标识基变量位置//jj[1]=3;jj[2]=4;jj[3]=5;jj[4]=6;//确定初始基变量，并标识基变量位置for(i=1;i<M;i++) cb[i]=a[0][jj[i]]; //基变量的价值系数for(j=0;j<N;j++)X[j]=0.0;for(i=1;i<M;i++)X[jj[i]]=a[i][0];for(j=1;j<N;j++){ z[j]=0.0;for(i=1;i<M;i++)z[j]+=cb[i]*a[i][j]; }//为寻找出基变量的检验数做准备for(j=1;j<N;j++){ cj[j]=0.0;cj[j]=a[0][j]-z[j];}// 检验数maxcj=Max(cj,N);printf("*********************************\n"); printf("输入的单纯形表如下：\n");for(i=0;i<M;i++){ for(j=0;j<N;j++)printf("%6.2f",a[i][j]);printf("\n");} //输出初始化单纯形表//for(i=1;i<M;i++)//printf("%6.2f",cb[i]);printf("\n");//输出基变量的价值系数//for(i=1;i<N;i++)//printf("%6.2f",X[i]);printf("\n");//输出一个基本可行解矩阵//for(j=1;j<N;j++)//printf("%6.2f",cj[j]);printf("\n");// 输出检验数printf("*********************************\n");while(maxcj>0){float R,alk;R=1000.0;for(i=1;i<M;i++)if(a[i][k]>0){ if(R>a[i][0]/a[i][k]){ R=a[i][0]/a[i][k];l=i;}else if(R==a[i][0]/a[i][k])if(jj[l]<jj[i])l=i;else;}if(R==1000.0){ printf("此问题无解!");t=1;break;}jj[l]=k;alk=a[l][k];for(j=0;j<N;j++)a[l][j]=a[l][j]/alk;for(i=1;i<M;i++)if(i!=l)for(j=0;j<N;j++)if(j!=k)a[i][j]=a[i][j]-a[l][j]/a[l][k]*a[i][k]; for(i=1;i<M;i++)if(i!=l)a[i][k]=0.0;for(i=1;i<M;i++)cb[i]=a[0][jj[i]]; //基变量的价值系数for(j=0;j<N;j++)X[j]=0.0;for(i=1;i<M;i++)X[jj[i]]=a[i][0];for(j=1;j<N;j++){ z[j]=0.0;for(i=1;i<M;i++)z[j]+=cb[i]*a[i][j]; }//为寻找出基变量的检验数做准备for(j=1;j<N;j++){ cj[j]=0.0;cj[j]=a[0][j]-z[j];} // 检验数maxcj=Max(cj,N);}if(t!=1){for(j=0;j<N;j++)Z+=a[0][j]*X[j];for(i=0;i<M;i++){ for(j=0;j<N;j++)printf("%6.2f",a[i][j]);printf("\n");}//输出初始化单纯形表//for(i=1;i<M;i++)//printf("%6.2f",cb[i]);printf("\n");//输出基变量的价值系数printf("满足最优解时，X的取值如下：");printf("\n");for(i=1;i<N;i++)printf("X[%d]=%6.2f,",i,X[i]);printf("\n");//输出一个基本可行解矩阵//for(j=1;j<N;j++)//printf("%6.1f",z[j]);printf("\n");//for(j=1;j<N;j++)//printf("%6.2f",cj[j]);printf("\n");// 输出检验数printf("最优解为Z=%6.2f",Z);printf("\n");}}float Max(float a[],int n){int i,maxjj;float maxaj;maxaj=a[1];maxjj=1;for(i=2;i<n;i++)if(maxaj<a[i]){ maxaj=a[i]; maxjj=i;} k=maxjj;return (maxaj);}。

单纯形法C语言程序实验:编制《线性规划》计算程序一、实验目的:(1)使学生在程序设计方面得到进一步的训练;，掌握Matlab (C或VB)语言进行程序设计中一些常用方法。

(2)使学生对线性规划的单纯形法有更深的理解.二、实验用仪器设备、器材或软件环境计算机, Matlab R2009a三、算法步骤、计算框图、计算程序等本实验主要编写如下线性规划问题的计算程序:mincxAx,b ,s.t.,x,0,b,0,其中初始可行基为松弛变量对应的列组成.对于一般标准线性规划问题:mincxAx,b ,s.t.,x,0,b,0,,(求解上述一般标准线性规划的单纯形算法(修正)步骤如下:对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。

设初始基为B,然后执行如下步骤:,1Bxb,xBb,令计算目标函数值xfcx,,0,BNBBB(1).解,求得，,1以b(1,2,...,)imBbi,记的第个分量i,1wBC,wCB,BB(2).计算单纯形乘子w, ,得到,对于非基变量，计算判别,1,1,Ac,数,可直接计算令 ,,,,,zccBpciiiBii,cBB,R为非基变量集合 ,,max{}k,,iR,,0k若判别数 ,则得到一个最优基本可行解，运算结束;否则，转到下一步,1yy,0Byp,yBp,kkkkkk(3).解,得到;若,即的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使bbtr,,min,0且y,,x为离基变量,tkyyrktkB:0,tyrtkxp为进基变量,用p替换得到新的基矩阵,B,还回步骤(1)kBkr;12,、计算框图为:开始初始可行基B,1 令x,Bb,x,0,f,cxBNBB1 ,,计算单纯性乘子w,cB,计算判别数,wp,c,j,R(非基变量)Bjjj令,,max{,,j,R}kj是,,0?k否得到最优解,1 解方程By,p,得到y,Bp,kkkk是y,0? k否不存在有限最优解确定下标r,使得,,bbir,min|,0 y,,ikyyrkik,,x为退基变量，x进基变量，以Bkrp代替p,得到新的基矩阵BkBr3: 3(计算程序(Matlab)A=input('A=');b=input('b=');c=input('c=');format rat %可以让结果用分数输出[m,n]=size(A);E=1:m;E=E';F=n-m+1:n;F=F';D=[E,F]; %创建一个一一映射，为了结果能够标准输出 X=zeros(1,n); %初始化Xif(n<m) %判断是否为标准型fprintf('不符合要求需引入松弛变量')flag=0;elseflag=1;B=A(:,n-m+1:n); %找基矩阵cB=c(n-m+1:n); %基矩阵对应目标值的cwhile flagw=cB/B; %计算单纯形乘子，cB/B=cB*inv(B),用cB/B的目的是，为了提高运行速度。

单纯形法C++实现使⽤单纯型法来求解线性规划，输⼊单纯型法的松弛形式，是⼀个⼤矩阵，第⼀⾏为⽬标函数的系数，且最后⼀个数字为当前轴值下的 z 值。

下⾯每⼀⾏代表⼀个约束，数字代表系数每⾏最后⼀个数字代表 b 值。

算法和使⽤单纯性表求解线性规划相同。

对于线性规划问题：Max x1 + 14* x2 + 6*x3s . t . x1 + x2 + x3 <= 4 x1<= 2 x3 <= 3 3*x2 + x3 <= 6 x1,x2,x3 >= 0我们可以得到其松弛形式：Max x1 + 14*x2 + 6*x3s.t. x1 + x2 + x3 + x4 = 4 x1 + x5 = 2 x3 + x6 = 3 3*x2 + x3 + x7 = 6 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0我们可以构造单纯性表，其中最后⼀⾏打星的列为轴值。

单纯性表x1x2x3x4x5x6x7bc1=1c2=14c3=6c4=0c5=0c6=0c7=0-z=011110004100010020010010303100016****在单纯性表中，我们发现⾮轴值的x上的系数⼤于零，因此可以通过增加这些个x的值，来使⽬标函数增加。

我们可以贪⼼的选择最⼤的c，再上⾯的例⼦中我们选择c2作为新的轴，加⼊轴集合中，那么谁该出轴呢？其实我们由于每个x都⼤于零，对于x2它的增加是有所限制的，如果x2过⼤，由于其他的限制条件，就会使得其他的x⼩于零，于是我们应该让x2⼀直增⼤，直到有⼀个其他的x刚好等于0为⽌，那么这个x就被换出轴。

我们可以发现，对于约束⽅程1，即第⼀⾏约束，x2最⼤可以为4（4/1），对于约束⽅程4，x2最⼤可以为3(6/3），因此x2最⼤只能为他们之间最⼩的那个，这样才能保证每个x都⼤于零。

因此使⽤第4⾏，来对各⾏进⾏⾼斯⾏变换，使得⼆列第四⾏中的每个x都变成零，也包括c2。

实验：编制《线性规划》计算程序一、实验目的：(1)使学生在程序设计方面得到进一步的训练，掌握Matlab (C 或VB)语言进行程序设计中一些常用方法。

(2)使学生对线性规划的单纯形法有更深的理解.二、实验用仪器设备、器材或软件环境计算机, Matlab R2009a三、算法步骤、计算框图、计算程序等本实验主要编写如下线性规划问题的计算程序:⎩⎨⎧≥≥≤0,0..min b x b Ax t s cx其中初始可行基为松弛变量对应的列组成.对于一般标准线性规划问题:⎩⎨⎧≥≥=0,0..min b x b Ax t s cx１．求解上述一般标准线性规划的单纯形算法（修正）步骤如下：对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。

设初始基为B,然后执行如下步骤：(1).解B Bx b =,求得1B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量(2).计算单纯形乘子w, B wB C =,得到1B w C B -=,对于非基变量，计算判别数1i i i B i i z c c B p c σ-=-=-,可直接计算σ=1B A c c B --令 max{}k i R σσ∈=,R 为非基变量集合若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步(3).解k k By p =,得到1k k y B p -=；若0k y ≤,即k y 的每个分量均非正数， 则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使 {}:0min ,0t rrk tk tk b b tk y y t y y >=>且r B x 为离基变量,,r k B x p k 为进基变量,用p 替换得到新的基矩阵B,还回步骤(1);２、计算框图为：最优解3．计算程序(Matlab)：A=input('A=');b=input('b=');c=input('c=');format rat%可以让结果用分数输出[m,n]=size(A);E=1:m;E=E';F=n-m+1:n;F=F';D=[E,F]; %创建一个一一映射，为了结果能够标准输出X=zeros(1,n); %初始化Xif(n<m) %判断是否为标准型fprintf('不符合要求需引入松弛变量')flag=0;elseflag=1;B=A(:,n-m+1:n); %找基矩阵cB=c(n-m+1:n); %基矩阵对应目标值的cwhile flagw=cB/B; %计算单纯形乘子，cB/B=cB*inv(B),用cB/B的目的是，为了提高运行速度。

单纯形法例程该程序是用单纯形法求解线性规划的C语言程序。

运行该程序时可根据提示按行输入线性规划的相关系数，程序输出线性规划的最优解所含基变量及其取值和最优解对应的目标函数值。

1. 说明：（1）当线性规划的变量数n大于40或约束方程数m大于20时（例如n=140,m=100），只要修改程序中行：double, q,p1,A[21][41], ,A0[21][41],b[21], b0[21],x[41],c[41] ,c0[41];int n, i,j,k , m, p,J[41], J0[41],s[21];中的41（为141）20(为101)既可。

（2）该程序仅适应于目标函数取最小且已知一个基解的标准形式的线性规划。

（3）程序中所用标识符和算法7.1基本相同。

2. 单纯形法例程源代码#include <stdio.h>#include <math.h>void main(){float q,p1,A[21][41],A0[21][41],b[21],b0[21],x,c[41],c0[41];int n, i,j,k , m, p,J[41], J0[41],s[21];printf("请输入方程组的行数m（<=20）列数n（<=40）");scanf("%d,%d",&m,&n);for(i=1;i<=m;i++){printf("请输入系数矩阵A的第%d行：\n",i);for(j=1;j<=n;j++)scanf("%f",&A[i][j]);}printf("请输入右端向量b：");for(i=1;i<=m;i++)scanf("%f",&b[i]);printf("请输入目标函数中个变量的系数向量c：");for(j=1;j<=n;j++)scanf("%f",&c[j]);printf("请输入初始基变量标志（是基变量输1不是输0）：");for(j=1;j<=n;j++)scanf("%d",&J[j]);for(j=1;j<=n;j++)J0[j]=1-J[j];printf("请输入各行上基变量的下标数：");for(i=1;i<=m;i++)scanf("%d",&s[i]);d1: for(i=1;i<=m;i++)for(j=1;j<=n;j++)A0[i][j]=(-1)*c[s[i]]*A[i][j]*J0[j];for(j=1;j<=n;j++){p1=0;for(i=1;i<=m;i++)p1=p1+A0[i][j];c0[j]=p1+c[j]*J0[j];}d2: q=c0[1];p=1;for(j=2;j<=n;j++)if (c0[j]<q){q=c0[j];p=j;}if (q>=0){q=0;printf("最优解基变量及其取值分别为：\n"); for(i=1;i<=m;i++){printf("x[%d]=%f\n",s[i],b[i]);q=q+c[s[i]]*b[i];}printf("最优解的目标函数值为：%f\n", q); return;}else{for(i=1;i<=m;i++){if (A[i,p]==0)b0[i]=-1;else if ((b[i]==0)&&(A[i,p]<0))b0[i]=-1;else if ((b[i]==0)&&(A[i,p]>0)){c0[p]=1;goto d2;}elseb0[i]=b[i]/A[i][p];}q=b0[1];for(i=2;i<=m;i++)if (b0[i]>q)q=b0[i];if (q<0){printf("线性规划无最优解\n"); return;}else{for(i=1;i<=m;i++)if ((b0[i]>0)&&(b0[i]<=q)) {q=b0[i];k=i;}J[p]=1;J[s[k]]=0;J0[p]=0;J0[s[k]]=1;s[k]=p;x=A[k][p];for(j=1;j<=n;j++)A[k][j]=A[k][j]/x;b[k]=b[k]/x;for(i=k-1;i>=1;i--){x=A[i][p];for(j=1;j<=n;j++)A[i][j]=A[i][j]-A[k][j]*x;b[i]=b[i]-b[k]*x;}for(i=k+1;i<=m;i++){x=A[i][p];for(j=1;j<=n;j++)A[i][j]=A[i][j]-A[k][j]*x;b[i]=b[i]-b[k]*x;}}}goto d1;}。

用c语言实现单纯形法的编程#include "stdio.h"#include "math.h"#include <iostream>int M,N;float c[100],a[100][100],b[100],CZ[100],Dn[100],th[100],x[100];int Fn[100];int K,L,ths;float zy;int shuru();void findmm();void chang();main(){float max_Z,sum=0,s=0;int i,j,r=0;if(!shuru()) { printf("ERROR!!!\n");return 0;}while(r<N){ r=0;for(j=0;j<N;j++){if(Dn[j]>0){findmm();if(ths==M) {goto loop;}else chang();}else r++;}}loop:if(ths==M){printf("\n此线性规划没有有限最优解!!!\n");printf("\n此线性规划最终迭代结果为：");printf("\n Cj ");for(j=0;j<N;j++)printf("%.3f ",c[j]);printf("\n");printf("Cb Xb b ");for(j=0;j<N;j++)printf(" x%d ",j+1);printf(" th ");for(i=0;i<M;i++){ printf("\n%.1f ",CZ[i]);printf("x%d ",Fn[i]+1);printf("%.3f ",b[i]);for(j=0;j<N;j++){ printf(" %.3f ",a[i][j]);}printf(" %.3f ",th[i]);printf("\n");}printf(" Dn ");for(j=0;j<N;j++)printf(" %.3f ",Dn[j]);printf("\n");printf("\n此时的解为:");sum=0;for(i=0;i<M;i++){ sum+=CZ[i]*b[i];printf("\nx%d=%.3f",Fn[i]+1,b[i]);}max_Z=sum;printf("\n此时目标函数的值为：Z= %.3f\n",max_Z);}else{printf("\n此线性规划最终迭代结果为：");printf("\n Cj ");for(j=0;j<N;j++)printf("%.3f ",c[j]);printf("\n");printf("Cb Xb b ");for(j=0;j<N;j++)printf(" x%d ",j+1);printf(" th ");for(i=0;i<M;i++){ printf("\n%.1f ",CZ[i]);printf("x%d ",Fn[i]+1);printf("%.3f ",b[i]);for(j=0;j<N;j++){ printf(" %.3f ",a[i][j]);}printf(" %.3f ",th[i]);printf("\n");}printf(" Dn ");for(j=0;j<N;j++)printf(" %.3f ",Dn[j]);printf("\n");printf("\n故,目标函数的基解为:");sum=0;for(i=0;i<M;i++){ sum+=CZ[i]*b[i];printf("\nx%d=%.3f",Fn[i]+1,b[i]);}max_Z=sum;printf("\n目标函数的值为：max_Z= %.3f\n",max_Z);}system("pause");return 1;}int shuru(){ int i,j;float sum=0;printf("请输入线性规划问题的约束条件个数M：");scanf("%d",&M);printf("请输入线性规划问题的决策变量个数N：");scanf("%d",&N);printf("请输入目标函数的系数：");for(i=0;i<N;i++)scanf("%f",&c[i]);printf("请输入线性规划问题的约束矩阵：\n");for(i=0;i<M;i++){ for(j=0;j<N;j++)scanf("%f",&a[i][j]);scanf("%f",&b[i]);}printf("请输入线性规划问题的初始基：\n");for(j=0;j<N;j++)scanf("%f",&x[j]);for(i=j=0;j<N;j++){if(x[j]!=0){ Fn[i]=j;CZ[i]=c[j];i++;}}for(j=0;j<N;j++){ sum=0;for(i=0;i<M;i++)sum+=CZ[i]*a[i][j];Dn[j]=c[j]-sum;}return 1;}void findmm(){ int i;int max,min;max=0;K=max;for(i=1;i<N;i++)if(Dn[i]>Dn[K]) max=i;K=max;for(i=0;i<M;i++){if(a[i][K]!=0) {th[i]=b[i]/a[i][K];min=i;} else th[i]=-1;}ths=0;for(i=0;i<M;i++)if(th[i]<0) ths=ths+1;for(i=0;i<M;i++)if((th[i]>0)&&(th[i]<th[min])) min=i;L=min;zy=a[L][K];Fn[L]=K;CZ[L]=c[K];}void chang(){ int i,j;float t;for(j=0;j<N;j++)a[L][j]=a[L][j]/zy;b[L]=b[L]/zy;for(i=0;i<M;i++){if(i==L) continue;t=a[i][K];b[i]=b[L]*(-t)+b[i];for(j=0;j<N;j++)a[i][j]=a[L][j]*(-t)+a[i][j];}t=Dn[K];for(j=0;j<N;j++)Dn[j]=(-t)*a[L][j]+Dn[j];K=0;for(i=1;i<N;i++)if(Dn[i]>Dn[K]) K=i;for(i=0;i<M;i++){if(a[i][K]!=0) {th[i]=b[i]/a[i][K];}else th[i]=-1;}}#include "stdio.h"#include "math.h"#include <iostream>int M,N;float c[100],a[100][100],b[100],CZ[100],Dn[100],th[100],x[100]; int Fn[100];int K,L,ths;float zy;int shuru();void findmm();void chang();main(){float max_Z,sum=0,s=0;int i,j,r=0;if(!shuru()) { printf("ERROR!!!\n");return 0;}while(r<N){ r=0;for(j=0;j<N;j++){if(Dn[j]>0){findmm();if(ths==M) {goto loop;} else chang();}else r++;}}loop:if(ths==M){printf("\n此线性规划没有有限最优解!!!\n");printf("\n此线性规划最终迭代结果为：");printf("\n Cj ");for(j=0;j<N;j++)printf("%.3f ",c[j]);printf("\n");printf("Cb Xb b ");for(j=0;j<N;j++)printf(" x%d ",j+1);printf(" th ");for(i=0;i<M;i++){ printf("\n%.1f ",CZ[i]);printf("x%d ",Fn[i]+1);printf("%.3f ",b[i]);for(j=0;j<N;j++){ printf(" %.3f ",a[i][j]);}printf(" %.3f ",th[i]);printf("\n");}printf(" Dn ");for(j=0;j<N;j++)printf(" %.3f ",Dn[j]);printf("\n");printf("\n此时的解为:");sum=0;for(i=0;i<M;i++){ sum+=CZ[i]*b[i];printf("\nx%d=%.3f",Fn[i]+1,b[i]);}max_Z=sum;printf("\n此时目标函数的值为：Z= %.3f\n",max_Z); }else{printf("\n此线性规划最终迭代结果为：");printf("\n Cj ");for(j=0;j<N;j++)printf("%.3f ",c[j]);printf("\n");printf("Cb Xb b ");for(j=0;j<N;j++)printf(" x%d ",j+1);printf(" th ");for(i=0;i<M;i++){ printf("\n%.1f ",CZ[i]);printf("x%d ",Fn[i]+1);printf("%.3f ",b[i]);for(j=0;j<N;j++){ printf(" %.3f ",a[i][j]);}printf(" %.3f ",th[i]);printf("\n");}printf(" Dn ");for(j=0;j<N;j++)printf(" %.3f ",Dn[j]);printf("\n");printf("\n故,目标函数的基解为:");sum=0;for(i=0;i<M;i++){ sum+=CZ[i]*b[i];printf("\nx%d=%.3f",Fn[i]+1,b[i]);}max_Z=sum;printf("\n目标函数的值为：max_Z= %.3f\n",max_Z);}system("pause");return 1;}int shuru(){ int i,j;float sum=0;printf("请输入线性规划问题的约束条件个数M："); scanf("%d",&M);printf("请输入线性规划问题的决策变量个数N："); scanf("%d",&N);printf("请输入目标函数的系数：");for(i=0;i<N;i++)scanf("%f",&c[i]);printf("请输入线性规划问题的约束矩阵：\n");for(i=0;i<M;i++){ for(j=0;j<N;j++)scanf("%f",&a[i][j]);scanf("%f",&b[i]);}printf("请输入线性规划问题的初始基：\n");for(j=0;j<N;j++)scanf("%f",&x[j]);for(i=j=0;j<N;j++){if(x[j]!=0){ Fn[i]=j;CZ[i]=c[j];i++;}}for(j=0;j<N;j++){ sum=0;for(i=0;i<M;i++)sum+=CZ[i]*a[i][j];Dn[j]=c[j]-sum;}return 1;}void findmm(){ int i;int max,min;max=0;K=max;for(i=1;i<N;i++)if(Dn[i]>Dn[K]) max=i;K=max;for(i=0;i<M;i++){if(a[i][K]!=0) {th[i]=b[i]/a[i][K];min=i;} else th[i]=-1;}ths=0;for(i=0;i<M;i++)if(th[i]<0) ths=ths+1;for(i=0;i<M;i++)if((th[i]>0)&&(th[i]<th[min])) min=i; L=min;zy=a[L][K];Fn[L]=K;CZ[L]=c[K];}void chang(){ int i,j;float t;for(j=0;j<N;j++)a[L][j]=a[L][j]/zy;b[L]=b[L]/zy;for(i=0;i<M;i++){if(i==L) continue;t=a[i][K];b[i]=b[L]*(-t)+b[i];for(j=0;j<N;j++)a[i][j]=a[L][j]*(-t)+a[i][j];}t=Dn[K];for(j=0;j<N;j++)Dn[j]=(-t)*a[L][j]+Dn[j];K=0;for(i=1;i<N;i++)if(Dn[i]>Dn[K]) K=i;for(i=0;i<M;i++){if(a[i][K]!=0) {th[i]=b[i]/a[i][K];} else th[i]=-1;}}/view/579bf98b79563c1ec5da71a4.html /view/560260a8647d27284a73510c.html /view/da495b9b76eeaeaad1f330f9.html//在Visual C++控制台程序中编译执行#include<iostream.h>#include<math.h>#define M 10000//全局变量float kernel[11][31];//核心矩阵表int m=0,n=0,t=0;//m:结构向量的个数//n:约束不等式个数//t:目标函数类型：－1代表求求最小值，1代表求最大值//输入接口函数void input(){//读入所求问题的基本条件cout<<"－－－－－－－－－－参数输入－－－－－－－－－－－"<<endl;cout<<"请按提示输入下列参数："<<endl<<endl;cout<<" 结构向量数m: "<<" m= ";cin>>m;cout<<endl<<" 约束不等式数n:"<<" n= ";cin>>n;int i,j;//初始化核心向量for (i=0;i<=n+1;i++)for (j=0;j<=m+n+n;j++)kernel [i][j]=0;//读入约束条件cout<<endl<<" 约束方程矩阵的系数及不等式方向（1代表<=,-1代表>=）:"<<endl<<endl<<" ";for (i=1;i<=m;i++)cout<<" x"<<i;cout<<" 不等式方向 "<<" 常数项"<<endl;for (i=1;i<=n;i++){cout<<" 不等式"<<i<<" ";for (j=1;j<=m+2;j++)cin>>kernel [i][j];}for (i=1;i<=n;i++){kernel [i][0]=kernel [i][m+2];kernel [i][m+2]=0;}//读入目标条件cout<<endl<<endl<<" 目标函数的系数及类型（求最小值:1；求最大值:-1）:"<<endl<<endl<<" ";for(i=1;i<=m;i++)cout<<"x"<<i<<" ";cout<<"类型"<<endl<<" ";cout<<" 目标函数: ";for (i=1;i<=m;i++)cin>>kernel [0][i];cin>>t;//矩阵调整if(t==-1)for(i=1;i<=m;i++)kernel [0][i]=(-1)*kernel [0][i];for(i=1;i<=n;i++){kernel [i][m+i]=kernel [i][m+1];if(i!=1)kernel [i][m+1]=0;}}//算法函数void comput(){int i,j,flag,temp1,temp2,h,k=0,temp3[10];float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c; //初始化for(i=1;i<=n;i++)temp3[i]=0;for(i=0;i<11;i++){ temp4[i]=0;temp5[i]=0;}for(i=1;i<=n;i++){if(kernel [i][m+i]==-1){kernel [i][m+n+i]=1;kernel [0][m+n+i]=M;temp3[i]=m+n+i;}elsetemp3[i]=m+i;}for(i=1;i<=n;i++)temp4[i]=kernel [0][temp3[i]];//循环求解do{for(i=1;i<=m+n+n;i++){a=0;for(j=1;j<=n;j++)a+=kernel [j][i]*temp4[j];kernel [n+1][i]=kernel [0][i]-a; }for(i=1;i<=m+n+n;i++){if(kernel [n+1][i]>=0) flag=1; else{flag=-1;break;}}if(flag==1){ for(i=1;i<=n;i++){if(temp3[i]<=m+n) temp1=1; else{temp1=-1; break;}}//输出结果cout<<endl<<endl;cout<<"－－－－－－－－－－结果输出－－－－－－－－－－－"<<endl<<endl;if(temp1==1){cout<<" 此线性规划的最优解存在!"<<endl<<endl<<" 最优解为："<<endl<<endl<<" ";for(i=1;i<=n;i++)temp5[temp3[i]]=kernel [i][0];for(i=1;i<=m;i++)f+=t*kernel [0][i]*temp5[i];for(i=1;i<=m;i++){cout<<"x"<<i<<" = "<<temp5[i];if(i!=m)cout<<"， ";}cout<<" ;"<<endl<<endl<<" 最优目标函数值f= "<<f<<endl<<endl;return ;}else{cout<<" 此线性规划无解"<<endl<<endl; return ;}}if(flag==-1){temp=100000;for(i=1;i<=m+n+n;i++)if(kernel [n+1][i]<temp){temp=kernel [n+1][i];h=i;}for(i=1;i<=n;i++){if(kernel [i][h]<=0) temp2=1;else {temp2=-1;break;}}}if(temp2==1){cout<<"此线性规划无约束";return ;}if(temp2==-1){c=100000;for(i=1;i<=n;i++){if(kernel [i][h]!=0) b[i]=kernel [i][0]/kernel [i][h]; if(kernel [i][h]==0) b[i]=100000;if(b[i]<0) b[i]=100000;if(b[i]<c){c=b[i];k=i;}}temp3[k]=h;temp4[k]=kernel [0][h];d=kernel [k][h];for(i=0;i<=m+n+n;i++)kernel [k][i]=kernel [k][i]/d;for(i=1;i<=n;i++){ if(i==k)continue;aa=kernel [i][h];for(j=0;j<=m+n+n;j++)kernel [i][j]=kernel [i][j]-aa*kernel [k][j];}}}while(1);return ;}//主函数void main(){ cout<<"-------------------单纯形算法程序----------------------"<<endl<<endl; input();comput();}#include<stdio.h>#include<math.h>#define m 3 /*定义约束条件方程组的个数*/#define n 5 /*定义未知量的个数*/float M=1000000.0;float A[m][n]; /*用于记录方程组的数目和系数;*/float C[n]; /*用于存储目标函数中各个变量的系数*/ float b[m]; /*用于存储常约束条件中的常数*/float CB[m]; /*用于存储基变量的系数*/float seta[m]; /*存放出基与入基的变化情况*/float delta[n]; /*存储检验数矩阵*/float x[n];int num[m]; /*用于存放出基与进基变量的情况*/ float ZB=0; /*记录目标函数值*/void input();void print();int danchunxing1();int danchunxing2(int a);void danchunxing3(int a,int b);int danchunxing1(){int i,k=0;int flag=0;float min=0;for(i=0;i<n;i++)if(delta[i]>=0)flag=1;else {flag=0;break;}if(flag==1)return -1;for(i=0;i<n;i++){if(min>delta[i]){min=delta[i];k=i;}return k;}int danchunxing2(int a){int i,k,j;int flag=0;float min;k=a;for(i=0;i<m;i++)if(A[i][k]<=0)flag=1;else {flag=0;break;}if(flag==1){printf("\n该线性规划无最优解!\n"); return -1;} for(i=0;i<m;i++){if(A[i][k]>0)seta[i]=b[i]/A[i][k];else seta[i]=M;}min=M;for(i=0;i<m;i++){if(min>=seta[i]){min=seta[i];j=i;}}num[j]=k+1;CB[j]=C[k];return j;}void danchunxing3(int p,int q){int i,j,c,l;float temp1,temp2,temp3;c=p;/*行号*/l=q;/*列号*/ temp1=A[c][l];b[c]=b[c]/temp1;for(j=0;j<n;j++)A[c][j]=A[c][j]/temp1;for(i=0;i<m;i++){if(i!=c)if(A[i][l]!=0){temp2=A[i][l];b[i]=b[i]-b[c]*temp2;for(j=0;j<n;j++)A[i][j]=A[i][j]-A[c][j]*temp2;}}temp3=delta[l];for(i=0;i<n;i++)delta[i]=delta[i]-A[c][i]*temp3;}void print(){int i,j=0;printf("\n--------------------------------------------------------------------------\n"); for(i=0;i<m;i++){printf("%8.2f\tX(%d) %8.2f ",CB[i],num[i],b[i]);for(j=0;j<n;j++)printf("%8.2f ",A[i][j]);printf("\n");}printf("\n--------------------------------------------------------------------------\n"); printf("\t\t\t");for(i=0;i<n;i++)printf(" %8.2f",delta[i]);printf("\n--------------------------------------------------------------------------\n"); }void input(){int i,j; /*循环变量*/int k;printf("请输入方程组的系数矩阵A(%d行%d列):\n",m,n);for(i=0;i<m;i++)for(j=0;j<n;j++)scanf("%f",&A[i][j]);printf("\n请输入初始基变量的数字代码num矩阵:\n");for(i=0;i<m;i++)scanf("%d",&num[i]);printf("\n请输入方程组右边的值矩阵b:\n");for(i=0;i<m;i++)scanf("%f",&b[i]);printf("\n请输入目标函数各个变量的系数所构成的系数阵C:\n");for(i=0;i<n;i++)scanf("%f",&C[i]);for(i=0;i<n;i++)delta[i]=C[i];for(i=0;i<m;i++){k=num[i]-1;CB[i]=C[k];}}void main(){int i,j=0;int p,q,temp;input();printf("\n--------------------------------------------------------------------------\n"); printf(" \tCB\tXB\tb\t");for(i=0;i<n;i++)printf(" X(%d)\t",i+1);for(i=0;i<n;i++)x[i]=0;printf("\n");while(1){q=danchunxing1();if(q==-1){print();printf("\n所得解已经是最优解!\n");printf("\n最优解为:\n");for(j=0;j<m;j++){temp=num[j]-1;x[temp]=b[j];}for(i=0;i<n;i++){printf("x%d=%.2f ",i+1,x[i]);ZB=ZB-x[i]*C[i];}printf("ZB=%.2f",ZB);break;}print();p=danchunxing2(q);printf("\np=%d,q=%d",p,q);if(q==-1) break;danchunxing3(p,q);}}。

单纯形法c语言单纯形法（Simplex Algorithm）是一种用于线性规划问题的常用算法。

它的目标是找到线性规划问题的最优解，即满足约束条件下的最大或最小目标函数值。

单纯形法的思想相对简单，但是在实现时需要注意一些细节。

单纯形法的基本原理是通过不断地在可行解空间中移动，逐步逼近最优解。

它通过迭代的方式，每次找到一个更优的可行解，直到找到最优解为止。

这个过程是通过转动问题的一个角点，使其向邻近的角点移动，直到达到最优解。

单纯形法的核心是构造单纯形表（Simplex Tableau）。

单纯形表是一个矩阵，由目标函数和约束条件组成。

表中的每一行代表一个约束条件，而列则代表决策变量。

单纯形表中的元素表示某个变量在约束条件下的系数。

单纯形法的步骤如下：1.将线性规划问题转化为标准形式。

标准形式要求目标函数为最小化形式，约束条件为等式形式，并且决策变量为非负数。

2.构造初始单纯形表。

将约束条件和目标函数转化为单纯形表的形式，并填写初始值。

3.检查单纯形表是否为最优解。

如果表中的目标函数系数均为负数，则可以确定该解为最优解，算法结束。

否则，找到目标函数系数中的最小值所在的列。

4.选择合适的基变量。

在所选列中，找到使约束条件保持满足的最优值所在的行，并将其称为主元行。

将主元行与所选列进行交换，使得目标函数系数中的最小值所在的位置变为主元。

5.进行主元行的消元操作。

通过将主元行除以主元元素，使主元元素变为1，并将其他行的元素都变为0，同时更新单纯形表的其他值。

6.重复第3步到第5步，直到找到最优解或者确定无界问题或者无可行解。

在实现单纯形法的过程中，需要注意以下几点：1.单纯形表的数据结构。

单纯形表可以使用矩阵或数组表示，同时需要记录变量的基变量和非基变量，以及目标函数的最优值。

2.主元行的选取。

可以使用不同的策略选择主元行，例如选取最小比值法或者随机选择法。

3.主元行的消元操作。

消元操作时，需要将主元行的其他元素变为0。

用C语言解决线性规划问题（用单纯形法解）#include<stdio.h>#include<math.h>#include<iostream.h>#define BORDER -0.00001#define M 100int main(){int k; //初始变量的个数int m; //约束条件的个数;cout<<"输入初始变量的个数"<<endl;cin>>k;cout <<"输入约束条件的个数"<<endl;cin>>m;cout<<"输入约束条件的种类"<<endl;cout<<"0 means <="<<endl;cout<<"1 means >="<<endl;cout<<"2 means ="<<endl;int NGET=0;int NLET=0;int NET =0;int I =0;//人工变量；int *code=new int[m]; //the array of the >= <= =;for(int i=0;i<m;i++){cin>>code[i];if(code[i]==0)NGET++;if(code[i]==1)NLET++;I++ ;if(code[i]==2)NET++;I++ ;}int n; //变量总和；n=k+2*NLET+NGET+NET;float *Index=new float[n+1]; //目标函数的系数;float *c=new float[n+1];int NTYPE;for(i=0;i<n+1;i++)Index[i]=0.0;//为语法要求定初值；cout<<"输入目标函数的系数"<<endl;for(i=0;i<k;i++)cin>>Index[i];for(i=k+NGET+NLET;i<n;i++)//人工变量所在的列；Index[i]=-M; //the initionalization of indexes of manul variable;cout<<"输入所求函数的类型是求最大还是最小"<<endl;cout<<"0 means min"<<endl;cout<<"1 means max"<<endl;cin>>NTYPE;if(NTYPE) //the initionalization of the c[i];{for(i=0;i<n+1;i++)c[i]=-Index[i];//一般情况下只要将目标函数系数的相反数输入；}if(!NTYPE){for(i=0;i<n+1;i++)if(i<k+NGET+NLET)c[i]=Index[i];else c[i]=-Index[i];}delete []Index;float **a=new float*[m+1]; //the array of all the variable to compute;for(i=0;i<m+1;i++)a[i]=new float[n+1];int INDEXG=k;int INDEXL=k+NGET;int INDEXE=k+NGET+NLET;int *ARTV=new int[I]; //保存人工变量；for(i=0;i<m;i++) //the analization of the code[](<= >= = );{if(code[i]==0){a[i][INDEXL]=1.0;INDEXL++;}if(code[i]==1){a[i][INDEXE]=1.0;INDEXE++;a[i][INDEXG]=-1.0;INDEXG++;ARTV[I]=i;I++;}if(code[i]==2){a[i][INDEXE]=1.0;INDEXE++;ARTV[I]=i;I++;}}if( (INDEXG!=k+NLET) || (INDEXL!=k+NGET+NLET) || (INDEXE!=n) )//excption {return -1;}cout<<"输入约束表达式左边的系数"<<endl;for(i=0;i<m;i++)for(int j=0;j<k;j++)cin>>a[i][j];float *b=new float[m];cout<<"输入约束表达式右边的值" <<endl;for(i=0;i<m;i++)cin>>b[i];for(i=0;i<m;i++)a[i][n]=b[i];float *temp=new float[n+1];if(I){for(i=0;i<I;i++)for(int j=0;j<n+1;j++){temp[j]=-a[ARTV[i]][j];c[j]+=M*temp[j];}}for(i=0;i<n+1;i++)a[m][i]=c[i];for(i=0;i<m+1;i++){for(int j=0;j<n+1;j++)cout<<a[i][j]<<" ";cout<<endl;}int flag=0;float temp1;float temp2;int K,J;int index;for(i=0;i<n;i++)if(a[m][i]<0)flag=1; //检验系数;while(flag) //Using a[][] to compute the result; {temp1=0;for(i=0;i<n;i++){if(temp1>a[m][i]){temp1=a[m][i];K=i;}}temp2=M;for(i=0;i<m;i++){if(a[i][K]>0&&(a[i][n]/a[i][K])<temp2){temp2=a[i][n]/a[i][K];J=i;}}if(temp2==M){cout<<"无解!"<<endl;return -1;}float temp3=a[J][K];for(i=0;i<n+1;i++){a[J][i]=a[J][i]/temp3;}for(i=0;i<m+1;i++){if(i!=J){float temp4=a[i][K];for(int j=0;j<n+1;j++){a[i][j]=a[i][j]- a[J][j]*temp4;}}cout<<endl;}flag=0;for(i=0;i<n+1;i++){if(a[m][i]<BORDER)flag=1;}cout<<"**************************************"<<endl;for(i=0;i<m+1;i++){for(int j=0;j<n+1;j++)cout<<a[i][j]<<" ";cout<<endl;}cout<<"***************************************"<<endl;getchar();}if(NTYPE)cout<<"The answer is :"<<a[m][n];if(!NTYPE)cout<<"The answer is :"<<-a[m][n];getchar();return 0;}。

单纯形法求解线性规划的步骤1>初始化将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示2>最优化测试如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为03>确定输入变量从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列4>确定分离变量对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行5>建立下一张表格将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步为求简单在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0);2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法)程序中主要的函数以及说明~SimpleMatrix();销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行void PrintAnswer();数不合法"<<endl;}SimpleMatrix::SimpleMatrix(int row,int col){init(row,col);for(int i=0;i<rowLen;i++)cout<<"请输入矩阵中第"<<i+1<<"行的系数"<<endl; for(int j=0;j<colLen;j++)cin>>data[i][j];}？}SimpleMatrix::SimpleMatrix(int row,int col,double **M) {rowLen=row;colLen=col;init(row,col);for (int i=0;i<row;i++)for(int j=0;j<col;j++){data[i][j]=*((double*)M+col*i+j); ;}}SimpleMatrix::~SimpleMatrix(){if(colLen*rowLen != 0 ){for(int i=rowLen-1;i>=0;i--){if (data[i]!=NULL)delete[] data[i];}if (data!=NULL)delete[] data;}？}bool SimpleMatrix::Is_objectLine_All_Positive(){for(int i=0;i<colLen-1;i++)if(data[rowLen-1][i]<0)return false;return true;}bool SimpleMatrix::Is_MainCol_All_Negative(int col) {for(int i=0;i<rowLen;i++)if(data[i][col]>0)return false;return true;}bool SimpleMatrix::Is_column_all_Positive(int col){for(int i=0;i<rowLen-1;i++){return false;}return true;}int SimpleMatrix::InColumn(){int count=0;for(int i=0;i<colLen-1;i++){int temp=GetItem(rowLen-1,i);if(temp>=0){count++;}elsebreak;}double maxItem=fabs(GetItem(rowLen-1,count));int index_col;for(i=0;i<colLen-1;i++){double temp=GetItem(rowLen-1,i);if(temp<0){if(maxItem<=fabs(temp)){maxItem=fabs(temp);index_col=i;}}}return index_col;}int SimpleMatrix::DepartRow(int col){int index_row;int count=0;for(int i=0;i<rowLen;i++){if(data[i][col]<0)count++;elsebreak;}double minItem=data[count][colLen-1]/data[count][col]; index_row=count;double temp;for(i=0;i<rowLen-1;i++)temp=data[i][col];if(temp>0){temp=data[i][colLen-1]/temp;if(temp<minItem){minItem=temp;index_row=i;}}}return index_row;}void SimpleMatrix::MainItem_To_1(int row,int col){double temp=GetItem(row,col);pp#include <iostream>#include ""using namespace std;int main(){double M[4][7]={{5,3,1,1,0,0,9},{-5,6,15,0,1,0,15},{2,-1,1,0,0,-1,5},{-10,-15,-12,0,0,0,}}; SimpleMatrix Matrix(4,7,(double **)M);if(5))//判断是否存在最优解{bool p=();//判断主元列是否全部为正,确定是否已经取得最优解while(!p){int col=();//确定主元所在的行if(col))//确定线性规划的解是否为无解的{cout<<"线性规划问题是无界的,没有最优解"<<endl;exit(EXIT_FAILURE);}else{int mainRow=(col);//确定主元所在的行(mainRow,col);//将主元所在的行做变换,使主元变成1int i=0;while(i<()){if(i!=mainRow){(i,mainRow,col);//处理矩阵中其他的行,使主元列的元素为0i++;}elsei++;}}}for(int i=0;i<();i++)//输出变换以后的矩阵,判断是否正确处理{for (int j=0;j<();j++){cout<<(i,j)<<" ";}cout<<endl;}p=();}();}elsecout<<"线性规划无解"<<endl;return0;}。

c语言实现二阶段单纯形法二阶段单纯形法（Two-Phase Simplex Method）是线性规划的一种求解方法。

它主要分为两个阶段：第一阶段是寻找一个初始解，第二阶段是使用单纯形法进行迭代优化。

以下是一个简单的C语言实现二阶段单纯形法的示例代码：```c#include <stdio.h>#include <stdlib.h>#include <math.h>#define MAX_ITER 1000#define EPSILON 1e-6int main() {int n, m;double a[100][100], b[100], x[100], z, min_x;int phase = 1;int i, j, k;// 输入数据printf("Enter the number of variables (n) and constraints (m): ");scanf("%d %d", &n, &m);printf("Enter the constraint matrix A and the right-hand side vector b:\n");for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {scanf("%lf", &a[i][j]);}scanf("%lf", &b[i]);}printf("Enter the objective function coefficients:\n"); for (j = 0; j < n; j++) {scanf("%lf", &x[j]);}printf("Enter the objective function constant: ");scanf("%lf", &z);// 第一阶段：寻找初始解for (i = 0; i < n; i++) {if (x[i] < 0) { // 如果目标函数的系数小于0，则该变量为基变量min_x = -x[i]; // 计算最小绝对值for (j = 0; j < m; j++) { // 在约束条件中寻找该变量的系数最小值对应的变量if (a[j][i] > EPSILON) { // 如果该变量的系数大于一个很小的值，则该变量为基变量if (fabs(a[j][i]) < min_x) { // 计算最小绝对值min_x = fabs(a[j][i]); // 更新最小绝对值}}}x[i] = -min_x; // 将该变量的值设置为最小绝对值乘以一个很小的正数（使得该变量成为基变量）} else { // 如果目标函数的系数大于等于0，则该变量为非基变量，取值为0x[i] = 0;}}for (i = 0; i < m; i++) { // 判断约束是否满足（无可行解） if (b[i] < z * x[0] + z * x[1] + ... + z * x[n - 1]) { // 如果约束不满足，则无可行解，结束程序printf("No feasible solution.\n");return 0;}}printf("Initial solution: ");for (i = 0; i < n; i++) { // 输出初始解printf("%.2f ", x[i]);}printf("\n");// 第二阶段：使用单纯形法进行迭代优化for (k = 0; k < MAX_ITER; k++) { // 最大迭代次数为1000次，可以根据实际情况进行调整int pivot_index = -1; // 记录pivot变量的下标，初始化为-1表示未找到pivot变量double max_ratio = -1; // 记录最大比值，初始化为-1表示未找到pivot变量对应的比值最大值for (i = 0; i < n; i++) { // 在非基变量中寻找pivot 变量和对应的最大比值if (x[i] > EPSILON) { // 如果该变量的值大于一个很小的正数，则该变量为非基变量，可以作为pivot变量候选者之一 double ratio = b[i] / a[i][n]; // 计算比值（目标函数值/约束条件值）和最大比值比较大小，更新最大比值和对应的pivot变量下标和目标函数值if (ratio > max_ratio) { // 如果当前比值大于最大比值，则更新最大比值和。