本文共 3520 字，大约阅读时间需要 11 分钟。

线性规划问题

（1） 确定决策变量

（2） 确定目标函数 （3） 找出约束条件 （4） 求最优解

简单问题

例: 图片来源:《趣学算法》陈小玉-人民邮电出版社

 变量满足约束条件的一组值称为线性规划的一个可行解  所有可行解构成集合称为线性规划问题的可行区域  使得目标函数取得极值得可行解称为最优解  在最优解处目标函数的值称为最优值

线性规划问题解的情况

有唯一最优解 有无数个最优解 没有最优解

线性规划标准型

线性规划标准型转化方法

单纯性算法

基本变量：

每个约束条件中的系数为正且只出现在一个约束中的变量。 非基本变量: 除基本变量外的变量全部为非基本变量。 基本可行解： 满足标准形式约束条件的可行解称为基本可行解。 检验数: 目标函数中非基本变量的系数。

线性规划基本定理：

定理1：最优解判别定理 若目标函数中关于非基本变量的所有系数(检验数Cj )小于等于0，则当前基本可行解就是最优解。 定理2：无穷多最优解判别定理 若目标函数中关于非基本变量的所有检验数小于等于0，同时存在某个非基本变量的检验数等于0，则线性规划问题有无穷多个最优解。 定理3：无界解定理 如果某个检验数Cj大于0，而Cj所对应的列向量的各分量a1j,a2j,…,amj都小于等于0，则线性规划问题有无界解。 算法步骤 （1） 建立初始单纯形表 （2） 判断是否得到最优解 （3） 选入基变量 （4） 选离基变量 （5） 换基变换 （6） 计算新的单纯形表

（7） 判断是否得到最优解

实例

/*问题引入 *工厂最大收益--单纯形算法 *某工厂共有3个加工车间、第1个车间用1个单位的原料N可以加工出5个单位的A或2个单位的产品B *产品A直接出售、售价为10元。 *产品B直接出售、售价为16元。 *如果在第2车间继续加工产品A,要额外加工费5元、加工后售价为19元。 *如果在第3车间继续加工产品B,要额外加工费4元、加工后售价为24元。 *原料N的单位购入价为5元。 *每工时工资为15元。 *第1车间加工一个单位N需要0.05个工时。 *第2车间加工一个单位需要0.1个工时。 *第3车间加工一个单位需要0.08工时。 *每个月最多可以得到12000单位的原料N。 *工时最多为1000工时。 *如何安排生产，才能使得工厂的收益最大呢？ * *//*问题分析 * x1:卖出A x2:卖出二次加工的A x3:卖出的B x4:卖出二次加工的B x5:第1车间共使用原料N的总单位 *目标函数:max z=10*x1+12.5*x2+16*x3+18.8*x4-5.75*x5 *约束条件: *x1+x2-5*x5=0 *x3+x4-2*x5=0 *x5<=12000 *0.1*x2+0.08*x4+0.05*x5<=1000 *xi>=0(i=0,1,2,3,4,5) * * *转化为标准型 *max z=10*x1+12.5*x2+16*x3+18.8*x4-5.75*x5 * * *x1+x2-5*x5=0 *x3+x4-2*x5=0 *x5+x6=12000 *0.1*x2+0.08*x4+0.05*x5+x7=1000 *xi>=0(i=1,2,3,4,5,6,7) * *基本变量：x1\x3\x6\x7 *非基本变量:x2\x4\x5 * *目标函数由非基本变量表示 *x1=5*x5-x2  x3=2*x5-x4 *目标函数:max z=2.5*x2+2.8*x4+76.25*x5 * */

代码实现

#include
   
    #include
    
     using namespace std;float kernel[100][100];//存储非单纯形表char FJL[100]={
   };//非基本变量char JL[100]={
   };//基本变量int m,n;//m:非基本变量的个数 n:基本变量的个数void print();//打印表void DCXA();//单纯形算法int main(void){
       cout<<"请输入非基本变量的个数与非基本变量的下标\n";    cin>>m;    for(int i=1;i<=m;i++){
           cin>>FJL[i];    }    cout<<"请输入基本变量个数与非基本变量的下标\n";    cin>>n;    for(int i=1;i<=n;i++){
           cin>>JL[i];    }    cout<<"请输入约束标准型初始单纯形表参数\n";    for(int i=0;i<=n;i++){
           for(int j=0;j<=m;j++){
               cin>>kernel[i][j];        }    }    print();    DCXA();    return 0;}//打印表void print(){
       cout<<"单纯形表\n";    cout<<"       b ";    for(int i=1;i<=n;i++){
           cout<<"      x"<
     
      =1){
               cout<<"x"<
      
       0){
   //检验数为正                for(int i=1;i<=n;i++){
                       if(max2
       
        0&&temp
       
      
     
    
   

测试实例

请输入非基本变量的个数与非基本变量的下标32 4 5请输入基本变量个数与非基本变量的下标41 3 6 7请输入约束标准型初始单纯形表参数0 2.5 2.8 76.250 1 0 -50 0 1 -212000 0 0 11000 0.1 0.08 0.05单纯形表       b       x2      x4      x5      xc       0       2.5       2.8       76.25x1      0       1       0       -5x3      0       0       1       -2x6      12000       0       0       1x7      1000       0.1       0.08       0.05单纯形表       b       x2      x4      x6      xc       915000       2.5       2.8       -76.25x1      60000       1       0       5x3      24000       0       1       2x5      12000       0       0       1x7      400       0.1       0.08       -0.05单纯形表       b       x2      x7      x6      xc       929000       -1       -35       -74.5x1      60000       1       -0       5x3      19000       -1.25       -12.5       2.625x5      12000       0       -0       1x4      5000       1.25       12.5       -0.625获得最优解: 929000单纯形表       b       x2      x7      x6      xc       929000       -1       -35       -74.5x1      60000       1       -0       5x3      19000       -1.25       -12.5       2.625x5      12000       0       -0       1x4      5000       1.25       12.5       -0.625

转载地址：http://xucki.baihongyu.com/