matlab语言(整数规划模型).doc

9.2.2 线性规划9.2.2.1 基本数学原理线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面线性规划问题的标准形式是：或写成矩阵形式为：其中，0 为 n 维列向量线性规划的标准形式要求目标函数最小化，约束条件取等式，变量非负不符合这几个条件的线性模型要首先转化成标准形线性规划的求解方法主要是单纯形法（Simple Method） ，该法由 Dantzig 于1947 年提出，以后经过多次改进单纯形法是一种迭代算法，它从所有基本可行解的一个较小部分中通过迭代过程选出最优解其迭代过程的一般描述为：1． 将线性规划化为典范形式，从而可以得到一个初始基本可行解 x(0)(初始顶点)，将它作为迭代过程的出发点，其目标值为 z(x(0))2． 寻找一个基本可行解 x(1)，使 z(x(1))≤z(x(0))方法是通过消去法将产生x(0)的典范形式化为产生 x(1)的典范形式3． 继续寻找较好的基本可行解 x(2)，x(3)，…，使目标函数值不断改进，即z(x(1))≥z(x(2)) ≥z(x(3)) ≥…当某个基本可行解再也不能被其它基本可行解改进时，它就是所求的最优解。

Matlab 优化工具箱中采用的是投影法，它是单纯形法的一种变种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)求解问题 min f'*x，约束条件为 A*x <= bx = 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 处的拉格朗日乘子它有以下一些属性：l lambda.lower –lambda 的下界。

l lambda.upper –lambda 的上界l lambda.ineqlin –lambda 的线性不等式l lambda.eqlin –lambda 的线性等式其它参数意义同前算法：大型优化算法 大型优化算法采用的是 LIPSOL 法，该法在进行迭代计算之前首先要进行一系列的预处理中型优化算法 linprog 函数使用的是投影法，就象 quadprog 函数的算法一样linprog 函数使用的是一种活动集方法，是线性规划中单纯形法的变种它通过求解另一个线性规划问题来找到初始可行解诊断：大型优化问题 算法的第一步涉及到一些约束条件的预处理问题有些问题可能导致 linprog 函数退出，并显示不可行的信息在本例中，exitflag 参数将被设为负值以表示优化失败若 Aeq 参数中某行的所有元素都为零，但 Beq 参数中对应的元素不为零，则显示以下退出信息： Exiting due to infeasibility: an all zero row in the constraint matrix does not have a zero in corresponding right hand size entry.若 x 的某一个元素没在界内，则给出以下退出信息：Exiting due to infeasibility: objective f'*x is unbounded below.若 Aeq 参数的某一行中只有一个非零值，则 x 中的相关值称为奇异变量。

这里，x 中该成分的值可以用 Aeq 和 Beq 算得若算得的值与另一个约束条件相矛盾，则给出以下退出信息：Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.若奇异变量可以求解但其解超出上界或下界，则给出以下退出信息： Exiting due to infeasibility: singleton variables in the equality constraints are not within bounds.9.2.2.3 应用实例[ [例二] 生产决策问题某厂生产甲乙两种产品，已知制成一吨产品甲需用资源 A 3 吨，资源 B 4m3；制成一吨产品乙需用资源 A 2 吨，资源 B 6m3，资源 C 7 个单位若一吨产品甲和乙的经济价值分别为 7 万元和 5 万元，三种资源的限制量分别为 90 吨、200m3 和 210 个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？令生产产品甲的数量为 x1，生产产品乙的数量为 x2由题意可以建立下面的模型：该模型中要求目标函数最大化，需要按照 Matlab 的要求进行转换，即目标函数为首先输入下列系数：f = [-7;-5];A = [3 2 4 60 7];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: [3x1 double]eqlin: [0x1 double]upper: [2x1 double]lower: [2x1 double]由上可知，生产甲种产品 14 吨、乙种产品 24 吨可使创建的总经济价值最高。

最高经济价值为 218 万元exitflag=1 表示过程正常收敛于解 x 处磁盘中本问题的 M 文件为 opt22_2.m[例三] 投资问题某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得到得净收益（投入资金的百分比）如下表所示：表 9-11 工程项目收益表工 程 项 目A B CD收益（%） 15108 12由于某种原因，决定用于项目 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 -1 1];b = [0; 0];Aeq=[1 1 1 1];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.4 1.1 1 0 0 00 0 0 0.5 1.2 1.3];b = [700; 800];Aeq=[1 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1];beq=[300 500 400];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 材料方案表裁 料 方 案 编 号 i下料长。