六章数学规划方法建模.ppt

第六章 数学规划方法建模,6.1 线性规划模型,6.2 非线性规划模型,6.3 整数规划模型,第六章 数学规划方法建模,6.1 线性规划模型,6.1.1 引例及线性规划模型,某工厂制造甲,乙 两种产品，资料如下：,问：甲，乙 两种各应生产多少吨，才能获利最大？,例6.1生产计划问题,且,6.1 线性规划模型,6.1.1 引例及线性规划模型,表示利润，则,解,写成线性规划的数学模型为：,目标函数,约束条件,解,6.1.1 引例及线性规划模型,的线性函数,的线性不等式,线性规划模型，简写成LP,问：如何调用，才能使运费最省？,例6.2 运输问题,6.1.1 引例及线性规划模型,6.1.1 引例及线性规划模型,解,可得线性规划的数学模型,6.1.1 引例及线性规划模型,线性规划模型的一般形式为(以最小目标为例),解,写成矩阵形式为,线性规划模型的标准形为,非标准形的线性规划都可以化为标准形,6.1.2 线性规划模型的解法,6.1.2.1 两个变量的线性规划模型的图解法,用图解法求下面的线性规划模型的最优解,例6.3,1) 求可行域,6.1.2 线性规划模型的解法,解,同一条直线的点,函数值相同 称为等值线。,越往上移动，,值越大。,最大值为：,2）求目标函数的最优值。,解,6.1.2 线性规划模型的解法,A(1 , 0),在点 A（1 , 0）处达到最优。,用图解法求下面的线性规划模型的最优解,例6.4,6.1.2 线性规划模型的解法,由上面两个例子可知： 1）线性规划模型的可行域是凸集； 2）当线性规划模型的可行域有界时， 其最优解可在其可行域的顶点上达到。,6.1.2 线性规划模型的解法,求解线性规划模型的一种常用的方法就是单纯形法，单纯形法是通过迭代来求问题的最优解:最优解一定能在可行域的顶点上达到。 目前，求解线性规划模型有不少现成的数学软件，比如LINDO软件、LINGO软件及MATLAB等。,6.1.2.2 用数学软件包求解线性规划模型,6.1.2 线性规划模型的解法,例6.6 某厂用甲、乙、丙三种原料生产A、B、C三种产品，每种产品消耗原料定额如表6.2所示。问如何组织生产，才能使利润最大？,表6.2 三种产品的额定消耗与利润,并进一步回答下列问题： 1）若产品A的价格降低了2（万元/万件），是否改变生产计划？ 2）若产品C的价格上涨了3（万元/万件），是否改变生产计划？ 3）若市场上还可以买到原料甲，其价格为1（万元/千克），是否购 买，最多可以买多少千克？,打开LINDO执行文件， 编程如下： max 2x1+2x2 st 2) x14 3) x23 4) x1+2x28 end,例6.5 用LINDO软件求线性规划模型例6.3的最优解,解：,LINDO中已规定所有决策变量均为非 负，因此模型中的第四个约束条件不 必输入； 式中不能有括号，右端不能有数学符 号； 不等号 写成 （二者与 等价）； 程序中第1行为目标函数，标号 2）, 3）,4）是标示各约束条件，以便从输 出结果中查找相应信息（标号可以 省略）； 程序以“end”结束。,6.1.2 线性规划模型的解法,输入程序后，选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“否（N）”，则可得到如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 12.00000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.000000 3) 1.000000 0.000000 4) 0.000000 1.000000 NO. ITERATIONS= 2,从上面输出我们得到：模型的最优解为 最优值,例6.5 用LINDO软件求线性规划模型例6.3的最优解,6.1.2.3 线性规划模型的灵敏性分析,灵敏度分析是指由于系统环境发生变化， 而引起系统目标变化的敏感程度。 对于线性规划模型(3)，我们总假设A ， b ，c 都是常数向量，但实际上这些数值往 往是通过测量和预测得到的，实际中多种原 因都能引起它们的变化。 现在的问题是：这些参数在多大的范围内 变化时，使线性规划模型的最优解不变。,6.1.2.3 线性规划模型的灵敏性分析,1）市场条件变化。 目标函数的系数 变化，即第 j 种产品的价格变动。 2）资源条件变化。 约束条件右端常数项 变化, 即第i种原料数量变动。 3）工艺技术条件变化。 系数矩阵中 变化，即单位产品所需耗材变动。 我们要研究的是上述三种变化引起生产计划的改变及利润的变化情况。在什么条件下，要改变生产计划。,6.1.2.3 线性规划模型的灵敏性分析,灵敏度分析主要研究下面几个问题：,1. 建立数学模型,设A、B、C三种产品计划生产量分别为万件，利润为z万元，则可得如下线性规划模型,应用LINDO软件来求解模型. 打开LINDO执行文件，编程如下： max 12x1+8x2+35x3 st 2) 3x1+2x2+12x330 3) x1+x2+2x37 4) 2x1+x2+x314 end,2. 模型求解,例6.6 求解,选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 100.5000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.000000 2.166667 X3 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.833333 3) 0.000000 6.500000 4) 4.500000 0.000000 NO. ITERATIONS= 2,例6.6 求解,即A、B、C三种产品的生产量分别为4, 0和1.5万件，利润为100.5万元。,3. 结果分析。一般将三个约束条件的右端看作三种“资源”，上面输出的第811行“SLACK OR SURPLUS”给出了三种资源在最优解下是否有剩余： 2）原料甲，3)原料乙的剩余均为零，4）原料丙剩余4.5千克。 我们称“资源”剩余为零的约束为紧约束（或称为有效约束）,选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 100.5000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.000000 2.166667 X3 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.833333 3) 0.000000 6.500000 4) 4.500000 0.000000 NO. ITERATIONS= 2,例6.6 求解,在经济学上，把在最优解下某种“资源”增加1个单位时的“效益”增量，称为该种“资源”的影子价格。在本问题中，原料甲的影子价格为1.833333万元，原料乙的影子价格为6.5万元，原料丙的影子价格为0。,目标函数可以看作“效益”,成为紧约束的“资源”一旦增加,就必然会引起“效益”增长.,第811行“DUAL PRICES”给出3种原料在最优解下“资源”增加1个单位时“效益”的增量：,2）原料甲增加1千克时，利润增长1.833333万元；,3）原料乙增加1千克时，利润增长6.5万元；,4）增加原料丙(非紧约束)不会使利润增长。,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINITY X3 35.000000 13.000000 11.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000,例6.6 求解,目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。,输出的第1419行“CURRENT COEF” 的“ALLOWABLE INCREASE”与“ALLOWABLE DECREASE”给出了最优解不变条件下目标函数系数的允许变化范围：,注意： 的系数的允许变化范围是指在 和 的系数不变的条件下的,其余相同.,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINITY X3 35.000000 13.000000 11.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000,例6.6 求解,目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。,对“资源”的影子价格做进一步分析，影子价格的作用是有限制的。,输出的第2025行“CURRENT RHS”的 “ALLOWABLE INCREASE”与 “ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的限制范围。,1）若产品A的价格降低了2（万元/万件），则产品A利润变成了10万元/万件，在允许范围(12-1.625, 12+5.5)之外，应该改变生产计划。 2）若产品C的价格上涨了3（万元/万件），则产品C利润变成了38万元/万件，在允许范围(35-11, 35+13)内，因此，不应改变生产计划。 3）由于原料甲的影子价格为1.833333万元，因此，应该在市场上以1（万元/千克）的价格购买原料甲，但最多只可以买12千克。,通过以上的灵敏性分析我们可以对问题 1),2),3)给出解答.,例6.6 求解,6.1.3 线性规划模型实例,例6.7 投资方案的确定,某部门要进行投资，现有四个投资项目： 项目A： 从第一年到第四年的每年年初需要投资，并于次年年末回收本利115；项目B：从第三年年初需要投资，到第五年末回收本利125，但规定最大投资额不超过40万元；项目C：第二年初需要投资，到第五年末才能回收本利140，但规定最大投资额不超过30万元；项目D：五年内每年的年初可买公债，于当年年末归还，并可获得6的利息。,已知该部门现有资金100万元，试为该部门确定投资方案，使得第五年末它拥有的资金本利总额最大？,1）决策变量 决策变量为每年年初向四个项目的投资额， 设第 i,年年初向A、B、C、D,四个项目的投资额为 (万元),2）目标函数 设第五年年末拥有的资金本利总额为z，将 所有可能的投资列于表6.3 。,求解例6.7,6.1.3 线性规划模型实例,1. 模型建立,表6.3 可能的投资方案,目标函数应该是四项投资在第五年年末回收的本利之和， 于是，目标函数为,6.1.3 线性规划模型实例,3）约束条件 (a)为了获得最大的投资收益，每年的年初应将手头的全部资金投出去，因此第一年的投资总额应是100万元，,(b)第二年的投资总额应是第一年年底回收的各项投资的本利，即,同理，第三、四、五年的投资总额应是上一年年底回收的各项投资本利，即,6.1.3 线性规划模型实例,（c）由于投资限制，因此还有,由此得投资问题的数学模型为,6.1.3 线性规划模型实例,用LINDO软件求解，为了能应用LINDO软件，编制程序时应将各约束条件的右端的决策变量移到左端。求得投资方案的最优解为,其余决策变量均为零。,最优值,2. 模型求解,6.1.3 线性规划模型实例,一饲养场饲养供实验用的动物，已知动物生长对饲料中的三种营养成分蛋白质、矿物质和维生素特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该场能搞到五种饲料，每种饲料10kg的成本如表6.4。每一千克饲料中所含的营养成分如表6.5。,表6.4,表6.5,试确定既能满足需要,又使总成本为最低的饲料配方,建立数学模型.,6.1.3 线性规划模型实例,例6.8 配料问题,1）决策变量。设动物每天食用的混合饲料中所含的第j 种饲料Aj的数量为 kg,2）目标函数。设混合饲料的总成本为z，则,3）约束条件。,（a）蛋白质的限制； （b）矿物质的限制； （c）维生素的限制。,6.1.3 线性规划模型实例,例6.8 配料问题,模型建立,由此的上述问题的数学模型为,2. 模型求解 用LINDO软件求解，得到最优解为：,最优值,6.1.3 线性规划模型实例,例6.8 配料问题,如何装运,使本次飞行获利最大？,三个货舱最大载重(吨),最大容积(米3),三个货舱中实际载重必须与其最大载重成比例,飞机平衡,6.1.3 线性规划模型实例,例6.9 货机装运,决策变量,xij-第i 种货物装入第j 个货舱的重量(吨） i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓),模型假设,每种货物可以分割到任意小；,每种货物可以在一个或多个货舱中任意分布；,多种货物可以混装，并保证不留空隙；,模型建立,6.1.3 线性规划模型实例,例6.9 货机装运,货舱容积,目标函数(利润),约束条件,模型建立,货舱重量,xij-第i 种货物装入第j 个货舱的重量,6.1.3 线性规划模型实例,例6.9 货机装运,约束条件,平衡要求,货物供应,xij-第i 种货物装入第j 个货舱的重量,模型建立,6.1.3 线性规划模型实例,例6.9 货机装运,OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000,货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3；货物4: 中仓3。,模型求解,最大利润约121516元,货物供应点 货舱需求点,平衡要求,6.1.3 线性规划模型实例,例6.9 货机装运,