单纯形法求解线性规划问题（C++实现代码）

1 单纯形法

（1） 单纯形法是解线性规划问题的一个重要方法。
其原理的基本框架为：
第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。
第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。
第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解。
（2） 用程序进行运算前，要将目标函数及约束方程变成标准形式。

于非标准形式须作如下变换：
a) 目标函数为极小值min z=CX时，转换为max z=-CX形式；
b) 在约束方程中有 “≤”时，在加上一个松弛变量；
c) 在约束方程中有 “≥”时，采用减去一个松弛变量，再加上一个人工变量；
d) 在约束方程中有 “=”时，加上一个人工变量；
e) 所有的人工变量，松弛变量的目标函数系数置为0。
（3） 对于标准形式的线性规划问题。用单纯形法计算步骤的框图。

2 程序测试及结果：

线性规划问题如下:
max z=2*x1-3*x2+3x3;
x1+ x2 -x3<=7;
x1- x2 +x3<=-7;
x1-2*x2 +2*x3<=4;
x1,x2,x3>=0;

3 C++实现代码

// Simplex.cpp : 定义控制台应用程序的入口点。
//
//
/********************************* 
----------------------------------- 
单纯形法求解线性规划问题（C++实现代码）
----------------------------------- 
Author:牧之丶  Date：2014年
Email:bzhou84@163.com 
**********************************/  
#include stdafx.h
#include
   
     #include
    
      using namespace std; #define M 10000 //全局变量大M float juzhen[11][31];//核心矩阵表 int m=0,n=0,t=0;//m:结构向量的个数 //n:约束不等式个数 //t:目标函数类型：－1代表求求最小值，1代表求最大值 void input() //输入接口函数 { int i,j; cout<<－－－－－－－－－－单纯形法的参 数 输 入－－－－－－－－－－－<
     
      >m; cout<
      
       >n; for (i=0;i<=n+1;i++) for (j=0;j<=m+n+n;j++) juzhen [i][j]=0; //初始化矩阵，所有元素均为0 //读入约束条件 cout<
       
        =）:<
        
         >juzhen [i][j]; } for (i=1;i<=n;i++) { juzhen [i][0]=juzhen [i][m+2]; juzhen [i][m+2]=0; } //读入目标条件 cout<
         
          >juzhen [0][i]; cin>>t; //矩阵调整 if(t==-1) for(i=1;i<=m;i++) juzhen [0][i]=(-1)*juzhen [0][i]; for(i=1;i<=n;i++) { juzhen [i][m+i]=juzhen [i][m+1]; if(i!=1) juzhen [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(juzhen [i][m+i]==-1) { juzhen [i][m+n+i]=1; juzhen [0][m+n+i]=M; temp3[i]=m+n+i; } else temp3[i]=m+i; } for(i=1;i<=n;i++) temp4[i]=juzhen [0][temp3[i]]; //循环求解 do{ for(i=1;i<=m+n+n;i++) { a=0; for(j=1;j<=n;j++) a+=juzhen [j][i]*temp4[j]; juzhen [n+1][i]=juzhen [0][i]-a; } for(i=1;i<=m+n+n;i++) { if(juzhen [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<
          
         
        
       
      
     
    
   

?