数学软件第十一章讲课件

第十一章MATLAB线性规化应用11.1 线性规划11.1.1、线性规划实例：实例1：生产计划问题假设某厂计划生产甲、乙两种产品，现库存主要材料有A类3600公斤，B类2000公斤，C类3000公斤。

每件甲产品需用材料A类9公斤，B类4公斤，C类3公斤。

每件乙产品，需用材料A类4公斤，B类5公斤，C类10公斤。

甲单位产品的利润70元，乙单位产品的利润120元。

问如何安排生产，才能使该厂所获的利润最大。

建立数学模型：设x1、x2分别为生产甲、乙产品的件数。

f为该厂所获总润。

max f=70x1+120x2s.t 9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0实例2：投资问题某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益(投入资金百分比)如下表：工程项目收益表投资之和而用于项目B和C的投资要大于项目D的投资。

试确定该公司收益最大的投资分配方案。

建立数学模型：设x 1、 x 2 、x 3 、x 4分别代表用于项目A 、B 、C 、D 的投资百分数。

max f=0.15x 1+0.1x 2+0.08 x 3+0.12 x 4 s.t x 1-x 2- x 3- x 4≤0 x 2+ x 3- x 4≥0 x 1+x 2+x 3+ x 4=1 x j ≥0 j=1,2,3,4 实例3：运输问题有A 、B 、C 三个食品加工厂，负责供给甲、乙、丙、小。

建立数学模型：设a i j 为由工厂i 运到市场j 的费用，x i j 是由工厂i 运到市场j 的箱数。

b i 是工厂i 的产量，d j 是市场j 的需求量。

⎪⎪⎪⎭⎫ ⎝⎛=114312312312A⎪⎪⎪⎭⎫ ⎝⎛=343332312423222114131211x x x x x x x x x x x x Xb= ( 60 40 50 ) d= ( 20 35 33 34 )∑∑===3141min i j ijij x a fs.t3,2,141=≤∑=i b xij ij4,3,2,131==∑=j d xi jijx i j ≥0从上述实例可以看出，规划问题研究的对象大体可以分为两大类：一类是在现有的人、财、物等资源的条件下，研究如何合理的计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使成本、费用最小等。

这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小）。

线性规划研究的问题要求目标与约束条件函数都是线性的，而目标函数只能是一个。

在经济管理问题中，大量问题是线性的，有的也可以转化为线性的，从而使线性规划有极大的应用价值。

线性规划模型包含3个要素：（1）决策变量. 问题中需要求解的那些未知量，一般用n 维向量T n x x x x ),,,(21 =表示。

（2）目标函数. 通常是问题需要优化的那个目标的数学表达式，它是决策变量x 的线性函数。

（3）约束条件. 对决策变量的限制条件，即x 的允许取值范围，它通常是x 的一组线性不等式或线性等式。

线性规划问题的数学模型一般可表示为： min （max ） f T X s.t A X≤bAe q X =beq lb ≤X≤ub其中X 为n 维未知向量，f T =[f 1,f 2,…f n ]为目标函数系数向量，小于等于约束系数矩阵A 为m ×n 矩阵，b 为其右端m 维列向量，Aeq 为等式约束系数矩阵，beq 为等式约束右端常数列向量。

lb,ub 为自变量取值上界与下界约束的n 维常数向量。

特别注意：当我们用MATLAB软件作优化问题时，所有求maxf 的问题化为求min(-f )来作。

约束g i (x)≥0，化为–g i≤0来做。

11.1.2．线性规划问题求最优解函数：调用格式： 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,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval]=linprog(…)[x, fval, exitflag]=linprog(…)[x, fval, exitflag, output]=linprog(…)[x, fval, exitflag, output, lambda]=linprog(…) 说明：x=linprog(f,A,b)返回值x为最优解向量。

x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。

若没有不等式约束，则令A=[ ]、b=[ ] 。

x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。

[x,fval]=linprog(…) 左端fval 返回解x处的目标函数值。

[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0) 的输出部分：exitflag 描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。

Output 为关于优化的一些信息。

Lambda为解x的Lagrange乘子。

11.1.3．举例例1：求解线性规划问题：max f=2x1+5x2s.t⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤≤008234212121x x x x x x先将目标函数转化成最小值问题：min(-f)=- 2x 1-5x 2 具体程序如下：f=[-2 -5];A=[1 0;0 1;1 2]; b=[4;3;8]; lb=[0 0];[x,fval]=linprog(f,A,b,[],[],lb) f=fval*(-1)运行结果： x = 2 3fval = -19.0000maxf = 19例2：minf=5x 1-x 2+2x 3+3x 4-8x 5 s.t –2x 1+x 2-x 3+x 4-3x 5≤6 2x 1+x 2-x 3+4x 4+x 5≤70≤x j ≤15 j=1,2,3,4,5 编写以下程序： f=[5 -1 2 3 -8];A=[-2 1 -1 1 -3;2 1 -1 4 1]; b=[6;7];lb=[0 0 0 0 0];ub=[15 15 15 15 15];[x,fval]=linprog(f,A,b,[],[],lb,ub) 运行结果：x = 0.0000 0.0000 8.0000 0.0000 15.0000minf =-104例3：求解线性规划问题：minf=5x1+x2+2x3+3x4+x5s.t –2x1+x2-x3+x4-3x5≤12x1+3x2-x3+2x4+x5≤-20≤x j≤1 j=1,2,3,4,5编写以下程序：f=[5 1 2 3 1];A=[-2 1 -1 1 -3;2 3 -1 2 1];b=[1;-2];lb=[0 0 0 0 0];ub=[1 1 1 1 1];[x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)运行结果：x = 0.00000.00001.19870.00000.0000fval =2.3975exitflag =-2显示的信息表明该问题无可行解。

所给出的是对约束破坏最小的解。

例4：求解实例1的生产计划问题建立数学模型：设x1、x2分别为生产甲、乙产品的件数。

f为该厂所获总润。

max f=70x1+120x2s.t 9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0将其转换为标准形式：min f=-70x1-120x2s.t 9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0编写以下程序：f=[-70 -120];A=[9 4 ;4 5;3 10 ];b=[3600;2000;3000];lb=[0 0];[x,fval,exitflag]=linprog(f,A,b,[],[],lb)maxf=-fval运行结果：x =200.0000240.0000fval =-4.2800e+004exitflag =1maxf =4.2800e+004例5：求解实例2建立数学模型：max f=0.15x1+0.1x2+0.08 x3+0.12 x4s.t x1-x2- x3- x4≤0x2+ x3- x4≥0x1+x2+x3+ x4=1x j≥0 j=1,2,3,4将其转换为标准形式：min z=-0.15x1-0.1x2-0.08 x3-0.12 x4s.t x1-x2- x3- x4≤0-x 2- x 3+ x 4≤0 x 1+x 2+x 3+ x 4=1 x j ≥0 j=1,2,3,4 编写程序：f = [-0.15;-0.1;-0.08;-0.12]; A = [1 -1 -1 -10 -1 -1 1];b = [0; 0]; Aeq=[1 1 1 1]; beq=[1];lb = zeros(4,1);[x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb) fmax=-fval 运行结果：x =0.5000 0.2500 0.0000 0.2500fval =-0.1300exitflag =1fmax = 0.1300即4个项目的投资百分数分别为50%，25%，0, 25%时可使该公司获得最大的收益，其最大收益可到达13%。

过程正常收敛。

例6：求解实例3建立数学模型：设a i j 为由工厂i 运到市场j 的费用，x i j 是由工厂i 运到市场j 的箱数。

b i 是工厂i 的产量，d j 是市场j 的需求量。

⎪⎪⎪⎭⎫ ⎝⎛=114312312312A⎪⎪⎪⎭⎫ ⎝⎛=343332312423222114131211x x x x x x x x x x x x Xb= ( 60 40 50 )Td= ( 20 35 33 34 )T∑∑===3141min i j ijij x a fs.t3,2,141=≤∑=i b xij ij4,3,2,131==∑=j d xi jijx i j ≥0 编写程序：AA=[2 1 3 2;1 3 2 1;3 4 1 1]; f=AA(:);A=[ 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1]; Aeq=[1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1]; b=[60;40;50];beq=[20;35;33;34]; lb=zeros(12,1);[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb) 运行结果：x =0.0000 20.0000 0.0000 35.0000 0.0000 0.0000 0.0000 0.0000 33.0000 0.0000 18.4682 15.5318fval =122.0000exitflag =1即运输方案为：甲市场的货由B厂送20箱；乙市场的货由A厂送35箱；丙商场的货由C厂送33箱；丁市场的货由B厂送18箱，再由C厂送16箱。