数据、模型与决策 汕头大学商学院 林佳丽

围猫游戏 2019/1/14 运营规划与决策优化

围猫策略分析 更大范围内围点 最短路径分析猫行动的方向 隔点围法，在猫跑出包 围圈之前围堵薄弱环节 2019/1/14 运营规划与决策优化

灵敏度分析与最优解的解释

线性规划模型的构建 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 (定性-定量、权重、可行域的设置） 一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 2019/1/14 数据、模型与决策

AB公司 AB公司在这一周内只生产两种产品：产品A和产品B。管理部门必须决定每种产品各生产多少吨。产品A的售价为每吨25美元，产品B的售价为每吨10美元。生产出的全部产品都将被出售。 产品A和产品B由多种材料混合而成，这些材料都从仓库中提取。可供这一周使用的三种原材料数量如下： 原料1 ：12 000吨 原料2： 4 000吨 原料3： 6 000吨 产品A由60%的原料1和40%的原料2制成 产品B由50%的原料1，10%的原料2和40%的原料3制成 2019/1/14 数据、模型与决策

如何决策？ 有人以1美元/吨的价格提供500吨的原料1，我们是否接受？ 有人以50美元/吨的价格提供原料2，是否接受？ 一个公司彻底用完了原料3，而以15美元/吨的价格向我们求购原料3（有多少要多少），我们是否应该卖给他们一些？ 如何决策？ 2019/1/14 数据、模型与决策

例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？ 线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 2019/1/14 数据、模型与决策

图 解 法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。 x2 x1 X1≥0 X1=0 x2 x1 X2≥0 X2=0 2019/1/14 数据、模型与决策

图 解 法 （2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。 100 200 2x1+x2≤400 300 400 100 200 300 x1+x2≤300 x1+x2=300 2019/1/14 数据、模型与决策

图 解 法 （3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。 x1 x2 x2=0 x1=0 x2=250 100 x2≤250 x2=250 200 300 2019/1/14 数据、模型与决策

图 解 法 （4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。 x2 B A C z=27500=50x1+100x2 z=10000=50x1+100x2 z=20000=50x1+100x2 D x1 z=0=50x1+100x2 E 2019/1/14 数据、模型与决策

灵敏度分析 建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。 2019/1/14 数据、模型与决策

例1.目标函数：max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 2019/1/14 数据、模型与决策

图 解 法 x2 B A C z=27500=50x1+100x2 z=10000=50x1+100x2 z=20000=50x1+100x2 D x1 z=0=50x1+100x2 E

改变目标向量 目标函数中的系数 ci 的灵敏度分析 考虑例1的情况， ci 的变化只影响目标函数等值线的斜率， 目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜 率为 -1 )之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。 一般情况 z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ， 当 -1  - (c1 / c2 )  0 （*） 时，原最优解仍是最优解。 2019/1/14 数据、模型与决策

假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0  c1  100 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则 - 2  - (60 / 55)  - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。 2019/1/14 数据、模型与决策

改变右端向量 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。 考虑例1的情况： 假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。 变化后的总利润 - 变化前的总利润 = 增加的利润 (50×60+ 100×250) - (50 × 50+100 × 250) = 500 ，500 /10 = 50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。

假设原料 A 增加10 千克时，即 b2变化为410，这时可行域 扩大，但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶 价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余， 因此增加10千克值增加了库存，而不会增加利润。 在一定范围内，当约束条件右边常数增加1个单位时 （1）若约束条件的对偶价格大于0，则其最优目标函数值得 到改善（变好）； （2）若约束条件的对偶价格小于0，则其最优目标函数值受 到影响（变坏）； （3）若约束条件的对偶价格等于0，则最优目标函数值不变。 2019/1/14 数据、模型与决策

百分百法则 当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（约束条 件右边常数值），当其所有允许增加的百分比与允许减少的百分比 之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原 来几个线性方程的解）。 * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 2019/1/14 数据、模型与决策

例： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最优解不变。 b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。 在使用百分之一百法则进行灵敏度分析时，要注意： 1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0； 2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不一定变化； 3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。

“管理运筹学”软件的输出信息分析 相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。 　“管理运筹学”软件的输出信息分析 相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。 松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。 对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。 目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。 常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。 以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！ 2019/1/14 数据、模型与决策

　“管理运筹学”软件的输出信息分析 注意： 当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。 “管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的Lindo计算机软件包的微型计算机版本Lindo/PC。 2019/1/14 数据、模型与决策

AB公司 AB公司在这一周内只生产两种产品：产品A和产品B。管理部门必须决定每种产品各生产多少吨。产品A的售价为每吨25美元，产品B的售价为每吨10美元。生产出的全部产品都将被出售。 产品A和产品B由多种材料混合而成，这些材料都从仓库中提取。可供这一周使用的三种原材料数量如下： 原料1 ：12 000吨 原料2： 4 000吨 原料3： 6 000吨 产品A由60%的原料1和40%的原料2制成 产品B由50%的原料1，10%的原料2和40%的原料3制成 2019/1/14 数据、模型与决策

目标函数：max 25A+10B 2019/1/14 数据、模型与决策

有人以1美元/吨的价格提供500吨的原料1，我们是否接受？ 回答：除非我们要为将来使用原料1做储备才接受，因为我们已经有过量的原料1. 有人以50美元/吨的价格提供原料2，是否接受？ 回答：接受。在500吨以内每增加1吨的原料2，就将会有62.5美元的收益。如果以50美元/吨的价格接受，我们还会有12.5美元/吨的纯收入，总共收入6 250美元。 2019/1/14 数据、模型与决策

续 一个公司彻底用完了原料3，而以15美元/吨的价格向我们求购原料3（有多少要多少），我们是否应该卖给他们一些？ 回答：如果他们负责运输，就把6 000吨原料3卖给他们。我们放弃了原料3的9.375美元/吨的收益，从而使得B产品的产量为零。如果我们以15美元/吨的价格卖掉6 000吨的原料3，总贡献将会有33 750美元的增加[（15-9.375）*6 000]。 2019/1/14 数据、模型与决策

线性规划在工商管理中的应用

人力资源分配的问题 例1．某昼夜服务的公交线路每天各时间段内所需司机 和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并 连续工作八小时，问该公交线路怎样安排司机和乘务人员， 既能满足工作需要，又配备最少司机和乘务人员? 2019/1/14 数据、模型与决策

人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数, 这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 2019/1/14 数据、模型与决策

人力资源分配的问题 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？ 2019/1/14 数据、模型与决策

人力资源分配的问题 解：设 xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x4 + x5 + x6 + x7 + x1 ≥ 25 x5 + x6 + x7 + x1 + x2 ≥ 19 x6 + x7 + x1 + x2 + x3 ≥ 31 x7 + x1 + x2 + x3 + x4 ≥ 28 x1,x2,x3,x4,x5,x6,x7 ≥ 0 2019/1/14 数据、模型与决策

往往一些服务行业的企业对人力资源的需求一周内像例2所描述的那样变化，而每天的各时间段的需求又像例1往往描述的那样变化，在保证工作人员每天工作8h，每周休息两天的情况下，如何安排能使人员的编制最小呢？ 2019/1/14 数据、模型与决策

生产计划的问题 例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？ 2019/1/14 数据、模型与决策

生产计划的问题 产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两 种产品的件数。 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种 产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两 种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 产品甲全部自制的利润 =23-(3+2+3)=15 元 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 元 产品乙全部自制的利润 =18-(5+1+2)=10 元 产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 元 产品丙的利润 =16-(4+3+2)=7 元 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15元、10元、7元、13元、9元。 2019/1/14 数据、模型与决策

生产计划的问题 通过以上分析,可建立如下的数学模型: 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 　生产计划的问题 通过以上分析,可建立如下的数学模型: 目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0 2019/1/14 数据、模型与决策

套裁下料问题 例4．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各 　套裁下料问题 例4．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各 一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0

§3 套裁下料问题 用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; §3　套裁下料问题 用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套钢架。 注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。

　投资问题 例5：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元 每次投资的风险指数如右表： 问： a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？

解：1）确定决策变量：连续投资问题 设 xij ( i = 1～5，j = 1～4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24 2019/1/14 数据、模型与决策

投资问题 2）约束条件： 第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11， 于是 x21 + x22+ x24 = 1.1x11； 第三年：年初有资金 1.1x21+ 1.25x12， 于是 x31 + x32+ x33 = 1.1x21+ 1.25x12； 第四年：年初有资金 1.1x31+ 1.25x22， 于是 x41 + x42 = 1.1x31+ 1.25x22； 第五年：年初有资金 1.1x41+ 1.25x32，于是 x51 = 1.1x41+ 1.25x32； B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100

投资问题 3）目标函数及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）

投资问题 b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下： Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330 xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）

个人理财计划 老李的个人理财计划问题：老李是一个做事有条理的人。他计划在退休前为他正在读高中的儿子准备一笔教育资金，以保证儿子四年大学与三年硕士生的学习费用。据估计，四年大学与三年硕士生的学习费用如下所示： 年份 第一年 第二年 第三年 第四年 第五年 第六年 第七年 费用/千元 3.25 2.58 2.60 2.45 3.65 3.20 2019/1/14 数据、模型与决策

个人理财计划（续） 经多方调查，老李发现三种债券值得购买。这三种债券的票面价值均为1000元，但由于它们的回报率不同，所以它们的购买价格不同。它们的购买价格、回报率与到期年限如下表所示： 同时，老李也考虑在每年的年初将经费存入银行，在下一年年初再全部取出，这时可得利息3.5%。老李希望能设计一个理财计划，使得在保证儿子七年学习费用的前提下，所需投入的教育资金最少。 债券 购买价格/千元 回报率 到期年限/年 1 1.15 0.092 4 2 0.055 5 3 1.35 0.122 6

三国的那些事儿 1.刘备的经历告诉我们：集团总裁，完全可以从摆地摊做起。 2.诸葛亮的经历告诉我们：进私企，其实比进国企更有发展空间。 3.吕布的经历告诉我们：频繁的跳槽，直接导致没老板敢录用你。 4.庞统的经历告诉我们：长得太丑，可能会影响你的应聘效果。 5.马谡的经历告诉我们：专业课学得再牛B，工作时基本用不上。 6.杨修的经历告诉我们：在职场上，总搞得比领导高明，你会死得很惨。 2019/1/14 数据、模型与决策

End

Question?