§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+120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0
归结出规划问题：目标函数和约束条件都是变量x的线性函数。
形如： (1) min f T X
s.t A X≤b
Aeq X =beq
lb≤X≤ub
其中X为n维未知向量，f T=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。
二．线性规划问题求最优解函数：
调用格式： 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为指定优化参数进行最小化。
Options的参数描述：
Display 显示水平。 选择’off’ 不显示输出；选择’iter’显示每一 步迭代过程的输出；选择’final’ 显示最终结果。
MaxFunEvals 函数评价的最大允许次数
Maxiter 最大允许迭代次数
TolX x处的终止容限
[x,fval]=linprog(…) 左端 fval 返回解x处的目标函数值。
[x,fval,exitflag,output,lambda]=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的输出部分：
exitflag 描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。
output 返回优化信息：output.iterations表示迭代次数；output.algorithm表示所采用的算法；outprt.funcCount表示函数评价次数。
lambda 返回x处的拉格朗日乘子。它有以下属性：
lambda.lower-lambda的下界；
matlab难还是c语言难 lambda.upper-lambda的上界；
lambda.ineqlin-lambda的线性不等式；
lambda.eqlin-lambda的线性等式。
三． 举例
例1：求解线性规划问题：
max f=2x1+5x2
s.t x1≤4
x2≤3
x1+x2≤8
x1,x2≥0
先将目标函数转化成最小值问题：min(-f)=- 2x1-5x2
程序：
f=[-2 -5];
A=[1 0;0 1;1 1];
b=[4;3;8];
[x,fval]=linprog(f,A,b)
f=fval*(-1)
结果： x = 2
3
fval = -19.0000
maxf = 19
例2：minf=5x1-x2+2x3+3x4-8x5
s.t –2x1+x2-x3+x4-3x5≤6
2x1+x2-x3+4x4+x5≤7
0≤xj≤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.0000
minf =
-104
例3：求解线性规划问题：
min f=5x1+x2+2x3+3x4+x5
s.t –2x1+x2-x3+x4-3x5≤1
2x1+3x2-x3+2x4+x5≤-2
0≤xj≤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,output,lambda]=linprog(f,A,b,[],[],lb,ub) 运行结果：
Exiting: One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far:
the primal appears to be infeasible (and the dual unbounded).
(The dual residual < TolFun=1.00e-008.)
x = 0.0000
0.0000
1.1987
0.0000
0.0000
fval =
2.3975
exitflag =
-1
output =
iterations: 7
cgiterations: 0
algorithm: 'lipsol'
lambda =
ineqlin: [2x1 double]
eqlin: [0x1 double]
upper: [5x1 double]
lower: [5x1 double]
显示的信息表明该问题无可行解。所给出的是对约束破坏最小的解。
例4：求解实例1的生产计划问题
建立数学模型：
设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。
max f=70x1+120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0
将其转换为标准形式：
min f=-70x1-120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0
程序： f=[-70 -120];
A=[9 4 ;4 5;3 10 ];
b=[3600;2000;3000];
lb=[0 0];
ub=[];
[x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论