线性规划应用实例

[大谦MATLAB，dqmatlab点com]

【例2】某厂计划生产甲、乙、丙三种产品，有机器、人工工时和原材料的限制，有关数据如表2-1所示。试建立获得最大产值的生产计划的线性规划模型。

表2-1 各产品机器、人工工时和原材料的限制

产品甲 产品乙 产品丙 资源总量
机器(时) 10 5 2 3000
人工(时) 5 10 4 2000
原材料(公斤) 1 1 2 500
产品售价(元) 10 15 10

设以xi （i=1,2,3）表示三种产品的产量，则可得该问题的数学模型为：

\[\left\{ \begin{matrix} \begin{matrix} \mathrm{\mathrm{max}}{{z=10x}_{1}+15{x}_{2}+10{x}_{3}} \\ 10{x}_{1}+5{x}_{2}+2{x}_{3}\leq3000 \\ 5{x}_{1}+10{x}_{2}+4{x}_{3}\leq2000 \end{matrix} \\ {x}_{1}+{x}_{2}+2{x}_{3}\leq500 \\ {x}_{j}\geq0, j=1,\ldots,3 \end{matrix} \right.\]

该模型要求使目标函数最大化，需要按照MATLAB的要求进行转换，即目标函数为：

\[\mathrm{\mathrm{min}}{{z=-10x}_{1}-{15x}_{2}-10{x}_{3}}\]

首先输入下列系数：

code.matlab 
>> f = [-10; -15;-10];
>> A = [10 5 2
       5 10 4
       1 1 2];
>> b = [3000; 2000; 500];
>> lb = zeros(3,1);

然后调用linprog函数进行计算：

code.matlab 
>> [x,fval,exitflag,output] = linprog(f,A,b,[ ],[ ],lb)

计算结果为：

code.matlab 
Optimal solution found.
x =
  266.6667
   25.0000
  104.1667
fval =
  -4.0833e+03
exitflag =
     1
output =
  包含以下字段的 struct:
         iterations: 3
    constrviolation: 4.5475e-13
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 2.8422e-13

所以，要取得最大产值，需要生产产品甲266.7个单位、产品乙25个单位、产品丙104.2个单位，最大产值为4083.3元。

【例3】一塑料厂利用四种化工原料合成一种塑料产品。这四种原料含A、B、C的成分如表2-2所示。四种原料的价格分别为20、20，30和15元/公斤。合成的塑料产品要求含A为25%，含B、C都不得少于30%。问各种原料投放比例为多少能使成本最低？

表2-2 各原料中A, B和C成分的含量

原料1 原料2 原料3 原料4
含A 30% 40% 20% 15%
含B 30% 30% 60% 40%
含C 40% 25% 15% 30%

设以xi （i=1,2,3,4）表示四种原料的比例，则可得该问题的数学模型为：

\[\left\{ \begin{matrix} \begin{matrix} \begin{matrix} \mathrm{\mathrm{min}}{z=20{x}_{1}+20{x}_{2}+30{x}_{3}+15{x}_{4}} \\ 0.3{x}_{1}+0.4{x}_{2}+0.2{x}_{3}+0.15{x}_{4}=0.25 \end{matrix} \\ 0.3{x}_{1}+0.3{x}_{2}+0.6{x}_{3}+0.4{x}_{4}\geq0.3 \\ 0.4{x}_{1}+0.25{x}_{2}+0.15{x}_{3}+0.3{x}_{4}\geq0.3 \end{matrix} \\ {x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}=1 \\ {x}_{j}\geq0, j=1,\ldots,4 \end{matrix} \right.\]

首先输入下列系数：

code.matlab 
>> f = [20;20;30;15];
>> A = [-0.3 -0.3 -0.6 -0.4
        -0.4 -0.25 -0.15 -0.3];
>> b = [-0.3; -0.3];
>> Aeq=[0.3 0.4 0.2 0.15
        1 1 1 1];
>> beq=[0.25 1];
>> lb = zeros(4,1);

然后调用linprog函数进行计算：

code.matlab 
>> [x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb)

计算结果为：

code.matlab 
Optimal solution found.
x =
    0.1538
    0.3077
         0
    0.5385
fval =
   17.3077
exitflag =
     1
output =
  包含以下字段的 struct:
         iterations: 3
    constrviolation: 1.1102e-16
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 3.5527e-15

所以，要使成本最低，需要投放原料1、原料2和原料4，它们的投放比例为0.1538:0.3077:0.5385，最低成本为每公斤17.3077元。

【例4】在某建筑工程施工过程中需要制作10000套钢筋，每套钢筋由2.9m、2.1m和1.5m 3种不同长度的钢筋各一根组成，它们的直径和材质也不同。目前，在市场上能采购到每根的同类钢筋的长度均为7.4m，问应采购多少根7.4m长的钢筋才能满足工程的需要？

首先分析共有多少种不同的裁料方法，可能的裁料方案如表2-3所示。

表2-3 裁料方案表

下料长度 （m） 裁料方案编号 裁料方案编号 裁料方案编号 裁料方案编号 裁料方案编号 裁料方案编号 裁料方案编号 裁料方案编号
下料长度 （m） 1 2 3 4 5 6 7 8
2.9 2 1 1 1 0 0 0 0
2.1 0 2 1 0 3 2 1 0
1.5 1 0 1 3 0 2 3 4
料头长度（m） 0.1 0.3 0.9 0 1.1 0.2 0.8 1.4

设以xi （i=1,2,…,8）表示按第i种裁料方案下料的原材料数量，则可得该问题的数学模型为

\[\left\{ \begin{matrix} \operatorname{min}{z}={x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}+{x}_{5}+{x}_{6}+{x}_{7}+{x}_{8} \\ 2{x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}=10000 \\ 2{x}_{2}+{x}_{3}+3{x}_{5}+2{x}_{6}+{x}_{7}=10000 \\ {x}_{1}+{x}_{3}+3{x}_{4}+2{x}_{6}+3{x}_{7}+4{x}_{8}=10000 \\ {x}_{j}\geq0,j=1, 2, \cdots, 8 \end{matrix} \right.\]

首先输入下列系数：

code.matlab 
>> f = [1; 1; 1; 1; 1; 1; 1; 1];
>> Aeq=[2  0  0  0  0  0  0  0
        0  2  1  0  3  2  1  0
        1  0  1  3  0  2  3  4];
>> beq=[10000  10000  10000];
>> lb = zeros(8, 1);

然后调用linprog函数进行计算：

code.matlab 
>> [x,fval,exitflag,output] = linprog(f,[],[],Aeq,beq,lb)

计算结果为：

code.matlab 
Optimal solution found.
x =
   1.0e+03 *
    5.0000
         0
         0
         0
    1.6667
    2.5000
         0
         0
fval =
   9.1667e+03
exitflag =
     1
output =
  包含以下字段的 struct:
         iterations: 2
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 1.1102e-16

所以最节省的裁料方案需要9167根7.4m长的钢筋，其中第1种裁料方案使用5000根，第5种方案裁料使用1667根，第6种裁料方案使用2500根。