线性规划问题

  在一组线性约束条件下的限制下，求一线性目标函数最大或最小的问题。

线性规划标准型

• 数学标准型：

  可行解：满足约束条件的解矩阵x=[x1,x2,x3,..,xn]。

  最优解：是目标函数达到最大值或者最小值的可行解。

  可行域：所有可行解构成的集合称为问题的可行解，记为R。

• matlab标准型：

  • f,x,b,beq,lb,ub为列向量
  • f称为价值向量
  • b称为资源向量
  • A，Aeq为矩阵

Matlab线性规划函数——linprog

>> help linprog
linprog - Solve linear programming problems

    This MATLAB function solves min f'*x such that A*x ≤ b.

    x = linprog(f,A,b)
    x = linprog(f,A,b,Aeq,beq)
    x = linprog(f,A,b,Aeq,beq,lb,ub)
    x = linprog(f,A,b,Aeq,beq,lb,ub,options)
    x = linprog(problem)
    [x,fval] = linprog(___)
    [x,fval,exitflag,output] = linprog(___)
    [x,fval,exitflag,output,lambda] = linprog(___)

    另请参阅 intlinprog, mpsread, optimoptions, quadprog

    linprog 的参考页

• x:返回决策向量的取值
• fval返回目标函数的最优解
• f为价值向量
• A和b对应线性不等式约束
• Aeq和beq对应线性等式约束
• lb和ub分别对应决策向量的下界向量和上界向量
• options是控制参数

例题讲解

1. 题目分析：

     这里求解的最优解是最大值，而matlab里面的标准函数是求最小值为最优解，因此需要对题目进行变形。另外，对最优解的约束同样需要进行整理称为matlab的使用形式。整理结果如下：

   

2. Matlab****程序实现

   f=[-2;-3;5];
   a=[-2,5,-1;1,3,1];
   b=[-10;12];
   aeq=[1,1,1];
   beq=7;
   [x,y]=linprog(f,a,b,aeq,beq,zeros(3,1));
   x,y=-y				%由于之前将求max最优解变形称为了min，这里的y要求相反的值
   

   输出结果：

   x=3x1
   	6.4286
   	0.5714
   		 0
   y=14.5714
   

1. 题目分析

   这个题目里面求的最优解为最小值，因此不需要进行转换，只需要对约束条件进行转换即可。在约束条件中，只有线性不等式约束以及决策向量下界向量，没有线性等式约束。转换结果如下：

2. 程序实现

   f=[2;3;1];    %价值向量是列向量
   a=[1,4,2;3,2,0];
   b=[8;6];
   aeq=[];
   beq=[];
   [x,y]=linprog(f,-a,-b,aeq,beq,zeros(3,1))	%一定要注意这里的符号
   

3. 特别说明：一定要记住matlab的线性规划标准函数的形式，标准形式里面只有小于等于号，如果程序出现大于号一定要进行变换！！！