第六章 运筹与优化模型.ppt

线性规划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下： （2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。 （3）绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。 结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。 Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 ≤ 65 (A) 2x1+ x2 ≤ 40 (B) 3x2 ≤ 75 (C) x1 , x2 ≥ 0 (D, E) 例题作图（1） 按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系； （2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示。 例题作图（2） 第2步图示(1) 分别作出各约束半平面 例题作图（3） 第2步图示(2) 各约束半平面的交－可行域 （3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点 (5,25)T ，即最优解。此目标函数的值为70000。 例题作图（4） 2.线性规划的图解法 例题作图（5） 第3步图示(2) 求出最优解 线性规划问题可以用单纯形方法求解，但是比较复杂，可以用常用的数学软件如MATLAB，MATHEMATICA,LINGO等求解，这里只介绍用LINGO求解的方法。 * 例：分配问题 假设某工厂用m台机床加工n种零件。在一个生产周期内，第i(i=1,2,…,m)台机床只能工作 个机时，而第j(j=1,2,…,n)种零件必须完成 个，又第i台机床加工第j种零件所需机时和成本分别为 （机时／个）和 （元／个）。问在这个生产周期内怎样安排各机床的生产任务，才能使得既完成加工任务，又使总的加工成本最少？ 解：在一个生产周期内，假设第i台机床加工第j种零件的个数为 。 由于 是零件个数，因此 必须是非负整数， * 本问题的数学模型为： * 问题（2）的求解 问题（2）：零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下料最节省。 问题分析 按照（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。 下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 * 同（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4 m），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3 m。 此外，这里我们仅选择总根数最小为目标进行求解。 模型建立 决策变量 由于不同切割模式不能超过3种， 可以用 表示按照第i种模式（ ）切割的原料钢管的根数，显然它们应当是非负整数。 * 设所使用