1、2023-5-5主要内容主要内容 案例背景案例背景 线性规划的标准型线性规划的标准型 线性规划问题的线性规划问题的MATLAB求解求解 线性规划案例分析线性规划案例分析 案例扩展案例扩展含参数线性规划含参数线性规划2023-5-5第一节第一节 案例背景案例背景2023-5-5一、线性规划应用一、线性规划应用【例例13.1-1】某厂生产某厂生产 三种产品,每种产品生产需经过三道工序:三种产品,每种产品生产需经过三道工序:选料、提纯和调配。根据现有的生产条件,可确定各工序有效选料、提纯和调配。根据现有的生产条件,可确定各工序有效工时、单位产品耗用工时及利润如表工时、单位产品耗用工时及利润如表13.
2、1-1所列。试问应如何安所列。试问应如何安排各种产品的周产量,才能获得最大利润?排各种产品的周产量,才能获得最大利润?工工 序序单位产品耗用工时(单位产品耗用工时(h/kg)每周有效工时(每周有效工时(h)选料选料1.11.21.44600提纯提纯0.50.60.62100调配调配0.70.80.62500利润(元利润(元/kg)121413 ABC2023-5-5【例例13.1-1续续】该例数学模型如下:该例数学模型如下:123123123123123max 1214131.11.21.446000.50.60.62100.0.70.80.625000,0,0zxxxxxxxxxstxxxx
3、xx2023-5-5二、线性规划的求解方法二、线性规划的求解方法1.Matlab求解线性规划用到的算法求解线性规划用到的算法 大规模内点法(大规模内点法(Large-scale interior-Point)中等规模作用集算法(中等规模作用集算法(Medium-scale active set)中等规模单纯形算法(中等规模单纯形算法(Medium-scale Simplex)2023-5-5第二节第二节 线性规划的标准型线性规划的标准型2023-5-5一、线性规划的标准型一、线性规划的标准型min .Tzf xA xbst Aeq xbeqlbxup其中其中f 为目标函数中决策变量的系数值向量
4、,为目标函数中决策变量的系数值向量,A为线性不为线性不等式约束的系数矩阵,等式约束的系数矩阵,b为线性不等式约束的右端常数向为线性不等式约束的右端常数向量,量,Aeq为线性等式约束的系数矩阵,为线性等式约束的系数矩阵,beq为线性等式约束为线性等式约束的右端常数向量,的右端常数向量,lb为决策变量为决策变量 x 的下界值向量,的下界值向量,up为决为决策变量策变量x的上界值向量。的上界值向量。2023-5-5第三节第三节 线性规划问题的线性规划问题的MATLAB求解求解2023-5-5一、一、linprog函数的调用格式函数的调用格式 x,fval=linprog(f,A,b,Aeq,beq,
5、lb,ub,x0,options)最优解最优解最优值最优值目标函数中决策变量的系数值向量目标函数中决策变量的系数值向量不等式约束系数矩阵不等式约束系数矩阵不等式约束常数向量不等式约束常数向量等式约束系数矩阵等式约束系数矩阵等式约束常数向量等式约束常数向量可行域下界可行域下界可行域上界可行域上界初始迭代点初始迭代点优化参数设置优化参数设置2023-5-5二、二、options参数的字段及说明参数的字段及说明字字 段段说说 明明Diagnostics显示目标函数的诊断信息,可选字段值如下:on 显示诊断信息off 不显示诊断信息(默认)Display结果显示方式,可选字段值如下:off 不显示输出
6、结果iter 显示每一步迭代结果,只适用于大规模内点法和中等规模单纯形算法final 只显示最终结果(默认)LargeScale设置迭代算法,可选字段值如下:on 使用大规模内点法(默认)off 使用中等规模算法MaxIter设置迭代步数,字段值为正整数TolFun设置目标函数的终止容限,对于大规模内点法,默认值为1e-8,对于单纯形法,默认值为1e-6Simplex设置中等规模算法,可选字段值如下:on 使用单纯形算法,此时不需要用户指定初始迭代点x0off 使用中等规模作用集算法(默认)2023-5-5第四节第四节 线性规划案例分析线性规划案例分析2023-5-5【例例13.1-1续续】该
7、例数学模型如下:该例数学模型如下:123123123123123max 1214131.11.21.446000.50.60.62100.0.70.80.625000,0,0zxxxxxxxxxstxxxxxx2023-5-5一、大规模内点法求解一、大规模内点法求解 f=-12,-14,-13;A=1.1,1.2,1.4;0.5,0.6,0.6;0.7,0.8,0.6;b=4600;2100;2500;Aeq=;beq=;lb=0;0;0;ub=;x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub)2023-5-5二、单纯形法求解
8、二、单纯形法求解 options=optimset(LargeScale,off,Simplex,on,Display,iter);x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,options)%最优解最优解x=1.0e+003*0.7500 1.2500 1.6250%最优值最优值fval=-476252023-5-5第五节第五节 案例扩展案例扩展含参数线性规划含参数线性规划2023-5-5一、目标函数含参数一、目标函数含参数【例例13.5-1】求解含参数线性规划问题求解含参数线性规划问题1 122331231231231
9、23min739185416951,0fa xa xa xxxxxxxstxxxx x x其中其中a1=-1,a2=-2,a3=-3 为参数。为参数。2023-5-5 f0=1,1,1;a=-1,-2,-3;f=a.*f0;A=7,3,9;8,5,4;6,9,5;b=1;1;1;Aeq=;beq=;lb=0,0,0;ub=;x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub)2023-5-5二、约束函数含参数二、约束函数含参数【例例13.5-2】求解含参数线性规划问题求解含参数线性规划问题1231 12312231233123min391841691,0fxxxa xxxxa xxstxxa xx x x 其中其中a1=7,a2=5,a3=3 为参数。为参数。2023-5-5 f=-1,-1,-1;a=7,5,5;A=a(1),3,9;8,a(2),4;6,9,a(3);b=1;1;1;Aeq=;beq=;lb=0,0,0;ub=;x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub)