线性规划问题

9.2.2.2相关函数介绍linprog函数功能：求解线性规划问题。数学模型：其中f,x,b,beq,lb和ub为向量，A和Aeq为矩阵。语法：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)求解问题minf'*x，约束条件为A*x=b。x=linprog(f,A,b,Aeq,beq)求解上面的问题，但增加等式约束，即Aeq*x=beq。若没有不等式存在，则令A=[]、b=[]。x=linprog(f,A,b,Aeq,beq,lb,ub)定义设计变量x的下界lb和上界ub，使得x始终在该范围内。若没有等式约束，令Aeq=[]、beq=[]。x=linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为x0。该选项只适用于中型问题，缺省时大型算法将忽略初值。x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用options指定的优化参数进行最小化。[x,fval]=linprog(...)返回解x处的目标函数值fval。[x,lambda,exitflag]=linprog(...)返回exitflag值，描述函数计算的退出条件。[x,lambda,exitflag,output]=linprog(...)返回包含优化信息的输出变量output。[x,fval,exitflag,output,lambda]=linprog(...)将解x处的拉格朗日乘子返回到lambda参数中。变量：lambda参数lambda参数是解x处的拉格朗日乘子。它有以下一些属性：lambda.lower–lambda的下界。lambda.upper–lambda的上界。lambda.ineqlin–lambda的线性不等式。lambda.eqlin–lambda的线性等式。其它参数意义同前。算法：大型优化算法大型优化算法采用的是LIPSOL法，该法在进行迭代计算之前首先要进行一系列的预处理。中型优化算法linprog函数使用的是投影法，就象quadprog函数的算法一样。linprog函数使用的是一种活动集方法，是线性规划中单纯形法的变种。它通过求解另一个线性规划问题来找到初始可行解。诊断：大型优化问题算法的第一步涉及到一些约束条件的预处理问题。有些问题可能导致linprog函数退出，并显示不可行的信息。在本例中，exitflag参数将被设为负值以表示优化失败。若Aeq参数中某行的所有元素都为零，但Beq参数中对应的元素不为零，则显示以下退出信息：Exitingduetoinfeasibility:anallzerorowintheconstraintmatrixdoesnothaveazeroincorrespondingrighthandsizeentry.若x的某一个元素没在界内，则给出以下退出信息：Exitingduetoinfeasibility:objectivef'*xisunboundedbelow.若Aeq参数的某一行中只有一个非零值，则x中的相关值称为奇异变量。这里，x中该成分的值可以用Aeq和Beq算得。若算得的值与另一个约束条件相矛盾，则给出以下退出信息：Exitingduetoinfeasibility:Singletonvariablesinequalityconstraintsarenotfeasible.若奇异变量可以求解但其解超出上界或下界，则给出以下退出信息：Exitingduetoinfeasibility:singletonvariablesintheequalityconstraintsarenotwithinbounds.9.2.2.3应用实例[[例二]生产决策问题某厂生产甲乙两种产品，已知制成一吨产品甲需用资源A3吨，资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源C7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？令生产产品甲的数量为x1，生产产品乙的数量为x2。由题意可以建立下面的模型：该模型中要求目标函数最大化，需要按照Matlab的要求进行转换，即目标函数为首先输入下列系数：f=[-7;-5];A=[324607];b=[90;200;210];lb=zeros(2,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb)x=14.000024.0000fval=-218.0000exitflag=1output=iterations:5cgiterations:0algorithm:'lipsol'lambda=ineqlin:[3x1double]eqlin:[0x1double]upper:[2x1double]lower:[2x1double]由上可知，生产甲种产品14吨、乙种产品24吨可使创建的总经济价值最高。最高经济价值为218万元。exitflag=1表示过程正常收敛于解x处。磁盘中本问题的M文件为opt22_2.m。[例三]投资问题某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得到得净收益（投入资金的百分比）如下表所示：表9-11工程项目收益表工程项目ABCD收益（%）1510812由于某种原因，决定用于项目A的投资不大于其它各项投资之和；而用于项目B和C的投资要大于项目D的投资。试确定使该单位收益最大的投资分配方案。用x1、x2、x3和x4分别代表用于项目A、B、C和D的投资百分数，由于各项目的投资百分数之和必须等于100%，所以x1+x2+x3+x4=1据题意，可以建立下面的数学模型：将它转换为标准形式：然后进行求解：首先输入下列系数：f=[-0.15;-0.1;-0.08;-0.12];A=[1-1-1-10-1-11];b=[0;0];Aeq=[1111];beq=[1];lb=zeros(4,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb)；x=0.50000.25000.00000.2500fval=-0.1300exitflag=1可见，四个项目的投资百分数分别为0.50、0.25、0.00和0.25时可使该单位获得最大的收益。最大收益为13%。过程正常收敛。磁盘中本问题的M文件为opt22_3.m。[例四]工件加工任务分配问题某车间有两台机床甲和乙，可用于加工三种工件。假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300、500和400，且已知用三种不同机床加工单位数量的不同工件所需的台时数和加工费用（如表所示），问怎样分配机床的加工任务，才能既满足加工工件的要求，又使总加工费用最低？表9-12机床加工情况表机床类型单位工作所需加工台时数单位工件的加工费用可用台时数工件1工件2工件3工件1工件2工件3甲0.41.11.013910700乙0.51.21.311128800设在甲机床上加工工件1、2和3的数量分别为x1、x2和x3，在乙机床上加工工件1、2和3的数量分别为x4、x5和x6。根据三种工种的数量限制，有x1+x4=300(对工件1)x2+x5=500(对工件2)x3+x6=400(对工件3)再根据机床甲和乙的可用总台时限制，可以得到其它约束条件。以总加工费用最少为目标函数，组合约束条件，可以得到下面的数学模型：首先输入下列系数：f=[13;9;10;11;12;8];A=[0.41.110000000.51.21.3];b=[700;800];Aeq=[100100010010001001];beq=[300500400];lb=zeros(6,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb);x=0.0000500.00000.0000300.00000.0000400.0000fval=1.1000e+004exitflag=1可见，在甲机床上加工500个工件2，在乙机床上加工300个工件1、加工400个工件3可在满足条件的情况下使总加工费最小。最小费用为11000元。收敛正常。磁盘中本问题的M文件为opt22_4.m。[例五]裁料问题在某建筑工程施工中需要制作10000套钢筋，每套钢筋由2.9m、2.1m和1.5m三种不同长度的钢筋各一根组成，它们的直径和材质不同。目前在市场上采购到的同类钢筋的长度每根均为7.4m，问应购进多少根7.4m长的钢筋才能满足工程的需要？首先分析共有多少种不同的套裁方法，该问题的可能材料方案如表9-13所示。表9-13材料方案表下料长度(m)裁料方案编号i123456782.9211100002.1021032101.510130234料头长度(m)0.10.30.901.10.20.81.4设以xi(i=1,2,…,8)表示按第i种裁料方案下料的原材料数量，则可得该问题的数学模型为：首先输入下列系数：f=[1;1;1;1;1;1;1;1];Aeq=[200000000210321010130234];beq=[100001000010000];lb=zeros(8,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,[],[],Aeq,beq,lb);x=1.0e+003*5.00000.00000.00000.00001.66672.50000.00000.0000fval=9.1667e+003所以最节省的情况需要9167根7.4m长的钢筋，其中第一种方案使用5000根，第五种方案使用1667根，第六种方案使用2500根。磁盘中本问题的M文件为opt22_5.m。[例六]工作人员计划安排问题某昼夜服务的公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人数如表所示，这些值班人员在某一时段开始上班后要连续工作8个小时（包括轮流用膳时间），问该公交系统至少需要多少名工作人员才能满足值班的需要？表9-14各时段所需值班人数表班次时间段所需人数16:00—10:0060210:00—14:0070314:00—18:0060418:00—22:0050522:00—2:002062:00—6:0030设xi为第i个时段开始上班的人员数，据题意建立下面的数学模型：需要对前面六个约束条件进行形式变换，是不等式为非正不等式。只需要在不等式两侧取负即可。首先输入下列系数：f=[1;1;1;1;1;1];A=[-10000-1-1-100000-1-100000-1-100000-1-100000-1-1];b=[-60;-70;-60;-50;-20;-30];lb=zeros(6,1);然后调用linprog函数：[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb);x=41.917628.082435.049414.95069.860620.1394fval=150.0000exitflag=1可见，只要六个时段分别安排42人、28人、35人、15人、10人和20人就可以满足值