应用运筹学 第三章 线性规划模型 浙江大学管理学院 杜红 博士 副教授.

Presentation on theme: "应用运筹学 第三章 线性规划模型 浙江大学管理学院 杜红 博士 副教授."— Presentation transcript:

1 应用运筹学 第三章 线性规划模型 浙江大学管理学院 杜红 博士 副教授

2 第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型 线性规划的图解方法 敏感分析与影子价格
第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型 线性规划的图解方法 敏感分析与影子价格 线性规划模型的应用

3 第三章 线性规划模型 线性规划问题的提出 解决有限资源的最佳分配问题。即如何对有限的资源作出最佳方式的调配和最有利的使用，以使最充分地发挥资源的效能去获取最佳的经济效益。 线性规划（Linear Programming, LP) 康托洛维奇 《生产组织与计划中 的数学方法》 丹捷格（美） 单纯形方法

4 第三章 线性规划模型 线性规划问题的提出 线性规划（LP)问题包含下列要素： 变量：决策要控制的因素 目标：决策目标（最优）的数学描述
第三章 线性规划模型 线性规划问题的提出 线性规划（LP)问题包含下列要素： 变量：决策要控制的因素 目标：决策目标（最优）的数学描述 约束条件：实现目标的一组限制条件 求LP问题：在约束条件下使目标最优的一组 变量的取值 解决环节：确定问题、建立模型、问题求解、 经济分析、敏感性分析

5 第三章 线性规划模型 建立线性规划问题模型 线性规划问题举例：教材 P40 LP模型： 决策变量：每周的生产批次 G、T
第三章 线性规划模型 建立线性规划问题模型 线性规划问题举例：教材 P40 LP模型： 决策变量：每周的生产批次 G、T 目标函数： max Z＝ 30×G+20×T （获利最大） 约束条件： 1×G + 2×T≤40 （配料工序约束） (s.t.) ×G + 1×T≤40 （整流工序约束） 1×G + 1×T≤ （包装工序约束） G≥0; T≥0 （生产批次的非负约束）

6 第三章 线性规划模型 建立线性规划问题模型 确定该LP问题的目标是什么？ 实现目标取决于什么因素和条件？ 确定哪几个因素为决策变量？
第三章 线性规划模型 建立线性规划问题模型 总结模型构建的一般思路： 确定该LP问题的目标是什么？ 实现目标取决于什么因素和条件？ 确定哪几个因素为决策变量？ 目标如何用决策变量来加以描述？ 约束条件如何表达？ 决策变量本身是否有限制条件？

7 第三章 线性规划模型 例3-1:请你构建以下问题的LP模型：
第三章 线性规划模型 例3-1:请你构建以下问题的LP模型： 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 用线性规划制订使总利润最大的生产计划。

8 第三章 线性规划模型 建立的模型如下： 设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数Z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型： max Z = 5.24x1 +7.30x2 +8.34x3 +4.18x4 s.t. 1.5x1 +1.0x2 +2.4x3 +1.0x4 ≤2000 1.0x1 +5.0x2 +1.0x3 +3.5x4 ≤8000 +3.0x2 +3.5x3 ≤5000 x1, x2, x3, x4 ≥0

9 第三章 线性规划模型 求解这个线性规划，可以得到最优解为： x1=294.12 x2=1500 x3=0 x4=58.82 最大利润为：
第三章 线性规划模型 求解这个线性规划，可以得到最优解为： x1= x2= x3= x4=58.82 最大利润为： z= （元） 请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。另外，变量是否需要取整也是需要考虑的问题。

10 第三章 线性规划模型 总结：线性规划问题的典型特征 可用一些变量表示这类问题的待定方案，这些变量 （决策变量）的一组值代表一个具体方案；
第三章 线性规划模型 总结：线性规划问题的典型特征 可用一些变量表示这类问题的待定方案，这些变量 （决策变量）的一组值代表一个具体方案； 存在一定的约束条件，这些约束条件都能用关于 决策变量的线性不等式或等式来表示； 有一个期望达到的目标，这个目标能以某种确定的数量指标刻划出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑的问题的不同，要求该函数值最大化或最小值。

11 第三章 线性规划模型 线性规划问题的基本要求 目标函数和约束条件必须是线性函数； 线性表达：相加性、比例性 决策变量的连续分布；
第三章 线性规划模型 线性规划问题的基本要求 目标函数和约束条件必须是线性函数； 线性表达：相加性、比例性 决策变量的连续分布； 不限于整数，可以是小数，但不能四舍五入 目标函数的单一性； 多目标是要设法简化成单目标 模型必须是确定型的； 所有参数(a、b、c)都应是确定值 决策变量的非负性

12 第三章 线性规划模型 线性规划问题模型的一般形式： 目标函数： 约束条件：

13 第三章 线性规划模型 线性规划问题一般模型的简化形式： 目标函数： max Z = ∑Cj Xj
第三章 线性规划模型 线性规划问题一般模型的简化形式： 目标函数： max Z = ∑Cj Xj 约束条件： ∑ai j Xj ≥(=, ≤) bi Xj ≥ 0 i = 1,2,3, …… ,m j = 1,2,3, …… ,n n Xj 的单位贡献 j=1 Xj 的技术性系数： 表示第 j 种活动消耗资源 i 的数量 第i 资源的约束量

14 第三章 线性规划模型 线性规划问题的标准形式 s.t. a11X1+a12X2+…+a1nXn=b1
第三章 线性规划模型 线性规划问题的标准形式 目标函数为最大化； 约束条件（非负条件除外）全为等式； 约束条件右端项为大于等于零； max Z = C1X1+C2X2+…+CnXn s.t. a11X1+a12X2+…+a1nXn=b1 a21X1+a22X2+…+a2nXn=b2 …………… am1X1+am2X2+…+amnXn=bm X1,X2,...,Xn≥0

15 第三章 线性规划模型 将非标准形式转化为标准形式 目标函数为最小化： 若约束条件是小于等于型： 在不等式左边加上一个新变量（松弛变量），
第三章 线性规划模型 将非标准形式转化为标准形式 目标函数为最小化： 令 Z’ = - Z , Z’ 为最大化问题。 若约束条件是小于等于型： 在不等式左边加上一个新变量（松弛变量）， 不等式改为等式，目标函数中新变量系数为零。 若约束条件是大于等于型： 在不等式左边减去一个新变量（剩余变量），

16 第三章 线性规划模型 将非标准形式转化为标准形式 在约束方程两端乘以（－1），不等号改变方向，然后再转化成等式。
第三章 线性规划模型 将非标准形式转化为标准形式 若约束方程右端项 bi < 0 : 在约束方程两端乘以（－1），不等号改变方向，然后再转化成等式。 若决策变量Xk没有非负要求： 作两个新变量Xk’≥0, Xk” ≥0,令Xk＝ Xk’ - Xk” ，在原有模型中用（ Xk’ － Xk” ）代替所有的Xk，在非负约束中增加Xk’≥0和Xk” ≥0 。

17 第三章 线性规划模型 例3-2: 将下列LP问题转化为标准形式 x1,x3≥0, x2 无符号限制 min Z = 2x1 -3x2 +x3
第三章 线性规划模型 例3-2: 将下列LP问题转化为标准形式 x1,x3≥0, x2 无符号限制 min Z = 2x1 -3x2 +x3 s.t. x1 -x2 +2x3 ≤3 +3x2 -x3 ≥5 +x2 =4

18 第三章 线性规划模型 令Z’=-Z， 引进松弛变量x4≥0,和剩余变量 x5≥0，
第三章 线性规划模型 令Z’=-Z， 引进松弛变量x4≥0,和剩余变量 x5≥0， 令 x2=x2'-x2'‘ 其中x2'≥0，x2''≥0, 得到以下等价的标准形式 : MAX z’= -2x1 +3x2' -3x2'' -x3 s.t. x1 -x2' +x2'' +2x3 +x4 =3 2x1 -x5 =5 +x2' -x2'' +x3 =4 x1, x2', x2'', x3, x4, x5 ≥0

19 第三章 线性规划模型 两个变量的线性规划问题的几何解释 例3-3:
第三章 线性规划模型 两个变量的线性规划问题的几何解释 例3-3: 目标函数等值线 Z = X1+3X2 x2 Max z = X1+3X2 s.t. X1+ X2≤6 -X1+2X2≤8 X1 , X2≥0 6 5 4 3 2 1 (4/3,14/3) z=15.3 可行域 z=12 z=9 z=6 z=3 z=0 x1

20 第三章 线性规划模型 线性规划的可行域及最优解的性质 若线性规划的可行域非空，则可行域必为凸集 若线性规划有最优解，则最优解至少在一个极点上
第三章 线性规划模型 线性规划的可行域及最优解的性质 若线性规划的可行域非空，则可行域必为凸集 若线性规划有最优解，则最优解至少在一个极点上 (a)凸集 (b)凸集 (c)凸集 (a)非凸集 (b)非凸集 (c)非凸集

21 第三章 线性规划模型 线性规划的可行域及最优解的可能结果 可行域为封闭的有界区域：唯一、多个最优解
第三章 线性规划模型 线性规划的可行域及最优解的可能结果 可行域为封闭的有界区域：唯一、多个最优解 可行域为非封闭的无界区域：唯一、多个最优解、 目标函数无界，无最优解 可行域为空集：没有可行解，更无最优解

22 第三章 线性规划模型 (a)可行域封闭，唯一最优解 (a)可行域封闭，多个最优解 (c)可行域开放，唯一最优解 (d)可行域开放，多个最优解
第三章 线性规划模型 线性规划的可行域及最优解的可能结果图示： (a)可行域封闭，唯一最优解 (a)可行域封闭，多个最优解 (c)可行域开放，唯一最优解 (d)可行域开放，多个最优解 (e)可行域开放，目标函数无界 (f) 可行域为空集

23 第三章 线性规划模型 线性规划的EXCEL求解：
第三章 线性规划模型 线性规划的EXCEL求解： 例3-1: 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 用线性规划制订使总利润最大的生产计划。

24 第三章 线性规划模型 第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型
第三章 线性规划模型 第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型 线性规划的图解方法 影子价格与敏感分析 线性规划模型的应用

25 第三章 线性规划模型 对偶问题的提出 某厂生产甲、乙两种产品，消耗A、B两种原材料 。生产一件甲产品可获利2元，生产乙产品获利3元。问在 以 下条件下如何安排生产？ 建立线性规划模型： 目标函数： MAX Z = 2X1+3X2 约束条件： X1+2X2≤ 8 4X ≤16 4X2≤12 X1, X2≥0 甲 乙 总量 设备台时 原材料A 原材料B 1 4 2 8 16 12

26 第三章 线性规划模型 对偶问题的提出 从另一角度考虑：
第三章 线性规划模型 对偶问题的提出 从另一角度考虑： 如果该厂决定不生产甲、乙两种产品，而将其资源出租或出售，这时工厂的决策者就要考虑给每种资源如何定价的问题。设用Y1,Y2,Y3分别表示出租单位设备台时的租金和出让原材料 A、B 的附加值。作如下比较，用一个单位设备台时和四个单位的原材料可以生产甲产品一件，获利2元，那么出租和出让的收益不应低于自己生产时的收益。因此有 Y1+4Y2≥2 ; 同样地乙产品也有：2Y1+4Y3≥3

27 第三章 线性规划模型 全部出让或出租的总收入为 W = 8Y1+16Y2+12Y3 从决策者来看，当然希望W值越大越好。但从接受者来讲，支付越少越好。为提高竞争力，因此工厂只能在满足≥所有产品的利润条件，使其总收入具有竞争力的，因此，W需要求解最小值。 因此有线性规划模型： 目标函数： min W = 8Y1+16Y2+12Y3 s.t Y1+4Y2≥2 2Y1+4Y3≥3 Y1,Y2,Y3≥0

28 第三章 线性规划模型 线性规划模型： 目标函数： MAX Z = 2X1+3X2 s.t. X1+2X2≤ 8 4X1 ≤16 4X2≤12
第三章 线性规划模型 线性规划模型： 目标函数： MAX Z = 2X1+3X2 s.t X1+2X2≤ 8 4X ≤16 4X2≤12 X1, X2≥0 线性规划模型： 目标函数： MIN W = 8Y1+16Y2+12Y3 s.t Y1+4Y2≥ 2 2Y1 +4Y3≥ 3 Y1, Y2,Y3≥0 最优解：X1=4, X2=2, Z=14 最优解：Y1=1.5,Y2=0.125, Y3=0,W=14 原问题 对偶问题

29 第三章 线性规划模型 第三章 线性规划模型 对偶问题与影子价格 MAX Z = CTX s.t. AX≤b X≤0 为原始问题，则称以下问题
第三章 线性规划模型 第三章 线性规划模型 对偶问题与影子价格 定义： 设以下线性规划问题 MAX Z = CTX s.t AX≤b X≤0 为原始问题，则称以下问题 MIN W = bTY s.t ATY≤C Y≥0 为原始问题的对偶问题，最优值Y为影子价格

30 第三章 线性规划模型 原问题与对偶问题转换： 对 偶 问 题 对 偶 问 题

31 第三章 线性规划模型 对偶问题与原始问题的关系 目标 变 量 n xj≥0 aTijyi≥cj 约 束 xj无约束 aTijyi=cj
第三章 线性规划模型 对偶问题与原始问题的关系 目标 极大化问题 Cj（max Z） 极小化问题bi（min W） 变 量 n xj≥0 —— aTijyi≥cj 约 束 xj无约束 aTijyi=cj xj≤0 aTijyi≤cj m aijxj≥bi yi≤0 aijxj=bi yi无约束 aijxj≤bi yi≥0

32 第三章 线性规划模型 对偶问题的性质 对偶问题的对偶是原问题。
第三章 线性规划模型 对偶问题的性质 对偶问题的对偶是原问题。 若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。 若X*,Y*分别是原问题和对偶问题的可行解，则 X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。 原问题标准型： Max Z= CX AX + XL= b X,XL≥0 对偶问题标准型： Min W= Yb YA - YS= C Y,YS≥0

33 第三章 线性规划模型 对偶问题的性质（续） 原问题和对偶问题的互补松松弛关系

34 第三章 线性规划模型 例3-4: 根据对偶原理求解以下线性规划问题：

35 第三章 线性规划模型 作业： 目标函数：MIN Z = 2X1+3X2+X3 s.t ： 3X1 - X2+ X3≥1
第三章 线性规划模型 作业： 运用对偶原理求以下原问题的最优解： 目标函数：MIN Z = 2X1+3X2+X3 s.t ： X1 - X2+ X3≥1 X1+2X2-3X3≥2 X1,X2,X3≥0

36 第三章 线性规划模型 第三章 线性规划模型 对偶问题解的经济解释－－影子价格 根据对偶问题的性质有： Z* = W* = ∑bi yi*
第三章 线性规划模型 第三章 线性规划模型 对偶问题解的经济解释－－影子价格 根据对偶问题的性质有： Z* = W* = ∑bi yi* 两边对bi求偏导数得到： ∂ Z* = yi* (i= 1,2, …,m) ∂ bi 即 yi* 表示每增加一个单位 bi 后 Z* 的增量 m i=1

37 第三章 线性规划模型 对偶问题解的经济解释－－影子价格 bi 在原问题中是约束条件的右端项，表明了第 i 种资源的可用量。因此，
第三章 线性规划模型 对偶问题解的经济解释－－影子价格 bi 在原问题中是约束条件的右端项，表明了第 i 种资源的可用量。因此， 对偶解的经济含义就是资源的单位改变引起目标函数值的增加量。定量表达了在最优生产方案下对单位第 i 种资源的一种估价，这种估价不是该种资源的市场价格，而是在最优生产方案下的一种虚拟价格，故称其为影子价格（shadow price)。

38 第三章 线性规划模型 影子价格的作用：决定企业的经营策略
第三章 线性规划模型 影子价格的作用：决定企业的经营策略 影子价格真实地反映了资源在经济结构中最优决策下对总收益的影响和贡献大小。影子价格越高，表明该种资源的贡献越大。影子价格为正数（非零），该资源约束的松弛变量取值为零（没有松弛变量），因此表明了该资源在最优决策下已充分利用耗尽，并成为进一步增加总收益的紧缺资源。影子价格越高，表明该种资源越紧缺。影子价格为零，表明该资源在最优决策下尚有剩余。

39 第三章 线性规划模型 影子价格的作用：决定企业的经营策略
第三章 线性规划模型 影子价格的作用：决定企业的经营策略 影子价格也是机会成本。当第 i 种资源的市场价格低于影子价格时，企业应适量购进这种资源，组织和增加生产；相反，当市场价格高于影子价格时，可以卖出资源而不安排生产或提高产品的价格。在完全的市场条件下，随着资源的买进和卖出，影子价格随之变化，直到影子价格与市场价格 保持同等水平。

40 第三章 线性规划模型 影子价格的作用：决定企业的经营策略
第三章 线性规划模型 影子价格的作用：决定企业的经营策略 从资源最优利用的角度，提出企业挖潜改革，扬长避短的方向。剩余资源也是进一步发展生产的潜在优势。 指导管理部门对紧缺资源进行择优分配。 资源影子价格的高低作为同类企业经济效益的评价指标之一。 帮助预测产品的价格。买方要购入卖方的产品作为资源投入生产，要求其价格必须小于该产品作为自己最优生产的影子价格，卖方要求出售其产品的价格必须大于自己的生产成本，因此，产品的价格应在双方的成本和影子价格之间。

41 第三章 线性规划模型 例3-5: 生产计划问题（例3-1）影子价格 最优解：x1=294.12 x2=1500 x3=0 x4=58.82
第三章 线性规划模型 例3-5: 生产计划问题（例3-1）影子价格 最优解：x1= x2= x3= x4=58.82 Z=

42 第三章 线性规划模型 敏感性分析 分析参数（A，b，C）的改变对最优值的影响，推算出模型的最优解对原有模型系数变化的敏感范围（最优解能够允许其系数变化的范围）。 目标函数的变化 所需资源的变化 资源消耗的变化 决策变量的变化

43 第三章 线性规划模型 敏感性分析－－目标函数的变化 ① Cj的变化影响到目标函数直线斜率K的变化。 要保持E点仍为最优解，K必须介于直线AB
第三章 线性规划模型 敏感性分析－－目标函数的变化 X2 ① Cj的变化影响到目标函数直线斜率K的变化。 要保持E点仍为最优解，K必须介于直线AB 和直线CD的斜率之间，即 KCD < K < KAB D KCD ① K < KCD E → C K > KAB E → B K = KCD E → EC K = KAB E → EB ③ B E KAB K O C A X1 ②

44 第三章 线性规划模型 敏感性分析－－约束方程系数 aij 变化 KAB → KA’B 时： 最优值 E → E2’ ；
第三章 线性规划模型 敏感性分析－－约束方程系数 aij 变化 X2 D aij的变化，使直线AB与CD的斜率发生变化。 当 KCD → KC’D 时： 最优值 E → E1’ ； KAB → KA’B 时： 最优值 E → E2’ ； 同时变化时： 最优值 E → E3’ KC’D KCD B E1’ E 1、最优解的极点不变， 但坐标变化，Z值变。 2、最优解的极点变化？ E3’ E2’ KAB KA’B O C’ C A’ A X1

45 第三章 线性规划模型 敏感性分析－－约束方程常数项 bi 变化 bi 的变化直接导致截距的变化， E有可能变成E1’，E2’，E3’。
第三章 线性规划模型 敏感性分析－－约束方程常数项 bi 变化 X2 D bi 的变化直接导致截距的变化， E有可能变成E1’，E2’，E3’。 最优解的极点变化？ bi 的变化与影子价格的关系？ D’ B E2’ B’ E E3’ E1’ O C’ C A’ A X1

46 第三章 线性规划模型 敏感性分析－－增加一个新产品(教材P56) G T 总量 V 配料 1 2 40 蒸馏 10 包装 25 获利 30
第三章 线性规划模型 敏感性分析－－增加一个新产品(教材P56) G T 总量 影子价格 V 配料 1 2 40 蒸馏 10 包装 25 获利 30 20 50 代价 20 40 新产品V投产带来的收益值 10

47 第三章 线性规划模型 对偶问题与原始问题的关系 目标 变 量 n xj≥0 aTijyi≥cj 约 束 xj无约束 aTijyi=cj
第三章 线性规划模型 对偶问题与原始问题的关系 目标 极大化问题 Cj（max Z） 极小化问题bi（min W） 变 量 n xj≥0 —— aTijyi≥cj 约 束 xj无约束 aTijyi=cj xj≤0 aTijyi≤cj m aijxj≥bi yi≤0 aijxj=bi yi无约束 aijxj≤bi yi≥0

48 作业1: 对偶问题求解 运用对偶原理求以下原问题的最优解： 目标函数：MIN Z = 2X1+3X2+X3
作业1: 对偶问题求解 运用对偶原理求以下原问题的最优解： 目标函数：MIN Z = 2X1+3X2+X3 s.t ： X1 - X2+ X3≥1 X1+2X2-3X3≥2 X1,X2,X3≥0 写出对偶问题： 目标函数：MAX W = Y1+2Y2 s.t : 3Y1+ Y2≤2 - Y1+2Y2≤3 Y1- 3Y2≤1 Y1,Y2≥0

49 1 0 1 -1 -1 Y2 (0,3/2) (1/ 7,11/ 7) Y1+2Y2=23/7 -Y1+2Y2=3 3Y1+Y2=1
(2/3,0) Y1 -1 Y1- 3Y2=1

50 求解对偶问题最优解： Y*1=1/7,Y*2=11/7,Y*3=0,Y*4=0,Y*5= 39/7 根据互补松弛定理得到： X*3=0,X*4=0,X*5=0 因此有： 3X1- X2=1 X1+2X2=2 得到：X*1=4/7,X*2=5/7 原问题的解为： X*1=4/7,X*2=5/7,X*3=0 Z*=W*=23/7

51 第三章 线性规划模型 第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型
第三章 线性规划模型 第三章 线性规划模型 线性规划问题的提出 线性规划问题的建模 典型特征和基本条件 一般模型和标准模型 线性规划的图解方法 影子价格与敏感分析 线性规划模型的应用

52 第三章 线性规划模型 线性规划模型的应用 生产计划问题（教材P42,实例3.1,例3-6,7)
第三章 线性规划模型 线性规划模型的应用 生产计划问题（教材P42,实例3.1,例3-6,7) 项目投资问题（教材P43,实例3.2,例3-8) 配料配套问题（教材P44,实例3.3,思考题) 合理下料问题（例3-9) 人力资源问题（例3-10） 运输调运问题（线性规划问题扩展） 任务指派问题（线性规划问题扩展）

53 第三章 线性规划模型 例3-6: 生产计划问题 日期 1 2 3 4 5 刀具数 120 85 160 145 300
第三章 线性规划模型 例3-6: 生产计划问题 某车间在每个生产期5天所需要的每种刀具的统计资料如下： 每一把刀具成本为0.6元，用过的刀具送到机修车间研磨，每把需花费0.2元。刀具用过后送去磨(只一次），两天后可以磨好送回，供当天（第三天）使用。第五天后应全部换新，每期开始时没有任何刀具，问这个车间需要多少刀具才能应付需要，而成本又最低？试建立线性规划模型。 日期 刀具数

54 第三章 线性规划模型 确定变量： 确定目标函数：
第三章 线性规划模型 确定变量： 问题是要确定每期需要新刀具的总数，它等价于要确定每天所需的新刀具，同时考虑到送去研磨的刀具第三天可使用，为此，设决策变量 Xi (i=1,2,3,4,5)为第i天使用的新刀具； Yj (j=1,2,3)为第j天送去研磨的刀具数。 确定目标函数： （新刀具成本＋研磨成本）为最小，即： min Z＝0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3)

55 第三章 线性规划模型 确定约束条件： 由于研磨的刀具第三天才能使用，因此， X1=120 ；X2=85
第三章 线性规划模型 确定约束条件： 由于研磨的刀具第三天才能使用，因此， X1=120 ；X2=85 第三天开始，每天使用新的和研磨送回的刀具： X3+Y1=160, X4+Y2=145, X5+Y3=300 在头三天送去研磨的刀具应满足： Y1≤120, Y2≤85+(120-Y1); Y3≤160+(120-Y1)+(85-Y2) 每天使用的新刀具和送研磨的刀具数为非负整数： X1,X2,X3,X4,X5,Y1,Y2,Y3≥0,且均为整数

56 第三章 线性规划模型 完整的模型为： min Z＝0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3) s.t. X1=120
第三章 线性规划模型 完整的模型为： min Z＝0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3) s.t X1=120 X2=85 X3+Y1=160 X4+Y2=145 X5+Y3=300 Y1≤120 Y2≤85+(120-Y1) Y3≤160+(120-Y1)+(85-Y2) X1,X2,X3,X4,X5,Y1,Y2,Y3≥0,且均为整数

57 第三章 线性规划模型 求解结果 X1= X2= X3=160 X4= X5=80 Y1= Y2=145 Y3=220

58 第三章 线性规划模型 例3-7：营销策略 一贸易公司专门经营某商品的批发业务，公司有库容5000单位的仓库，某年一月一日，公司有库存1000单位，并有资金20000元，估计第一季度该商品的价格如下表所示。如买进的商品当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000单位，问应采取什么样的买卖策略可使3个月总的获利最大？ 一月 二月 三月 进货价（元） 出货价（元）

59 第三章 线性规划模型 例3-7：营销策略 考虑到资金周转，应该是先卖出再买进，而且最好是月初卖出月底买进。
第三章 线性规划模型 例3-7：营销策略 考虑到资金周转，应该是先卖出再买进，而且最好是月初卖出月底买进。 决策变量：每月买进Xi (i=1,2,3), 每月卖出Yi (i=1,2,3)。 分析库存情况： 库存 卖出 买入 月末库存 一月 Y X Y1+X1 二月 Y1+X Y X Y1+X1-Y2+X2 三月 Y1+X1-Y2+X2 Y X Y1+X1-Y2+X2-Y3+X3 存货限制：Y1≤1000 ;Y2 ≤1000-Y1+X1; Y3≤1000-Y1+X1-Y2+X2 库容限制： 1000-Y1+X1≤5000；1000-Y1+X1-Y2+X2≤5000 1000-Y1+X1-Y2+X2-Y3+X3＝2000

60 第三章 线性规划模型 例3-7：营销策略 分析资金流动情况： 月初资金 卖出 买入 一月 20000 3.10Y1 2.85X1
第三章 线性规划模型 例3-7：营销策略 分析资金流动情况： 月初资金 卖出 买入 一月 Y X1 二月 Y1-2.85X Y X2 三月 Y1-2.85X1+3.25Y2-3.05X Y X3 资金限制：2.85X1≤ Y1 3.05X2≤ Y1-2.85X1+3.25Y2 2.90X3≤ Y1-2.85X1+3.25Y2-3.05X2+2.95Y3 目标函数： MAX Z = 3.10Y1+3.25Y2+2.95Y3-2.85X1-3.05X2-2.90X3

61 第三章 线性规划模型 例3-8 连续投资问题 某部门在五年内考虑给下列项目投资：
第三章 线性规划模型 例3-8 连续投资问题 某部门在五年内考虑给下列项目投资： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115％。 项目B：从第三年初需投资，到第五年末能回收本利125％，但规定最大投资额不超过4万元。 项目C：第二年初需要投资，到第五年末能回收本利140％，但规定最大投资额不超过3万元。 项目D：五年内每年初可购买公债于当年末归还并加利息6％。 该部门现有资金10万元，问应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大。

62 第三章 线性规划模型 确定变量： 以XiA,XiB,XiC,XiD(i=1,2,3,4,5)分别表示第 i 年年初给项目A,B,C,D的投资额。具体列于下表： 第1年 第2年 第3年 第4年 第5年 A B C D X1A X1D X2A X2C X2D X3A X3B X3D X4A X4D X5D

63 第三章 线性规划模型 确定约束条件： 投资额应等于手中拥有的资金，不应有剩余。 确定目标函数：第五年末资金最大
第三章 线性规划模型 确定约束条件： 投资额应等于手中拥有的资金，不应有剩余。 第一年： X1A+X1D=100000 第二年：年初资金仅为D项目第一年的本息。 X2A+X2C+X2D=X1D(1+6%) 第三年：年初资金为A第一次回收本利＋D第二次本息 X3A+X3B+X3D=X1A(1+15%)+X2D(1+6%) 第四年： X4A+X4D= X2A(1+15%)+X3D(1+6%) 第五年： X5D=X3A(1+15%)+X4D(1+6%) B、C投资额限制：X3B≤40000; X2C≤30000 确定目标函数：第五年末资金最大 MAX Z = 1.15X4A+1.40X2C+1.25X3B+1.06X5D

64 第三章 线性规划模型 完整的模型为： MAX Z = 1.15X4A+1.40X2C+1.25X3B+1.06X5D
第三章 线性规划模型 完整的模型为： MAX Z = 1.15X4A+1.40X2C+1.25X3B+1.06X5D s.t. X1A+X1D =100000 -1.06X1D+X2A+X2C+X2D =0 -1.15X1A X2D+X3A+X3B +X3D =0 -1.15X2A X3D+X4A+X4D =0 -1.15X3A X4D +X4D =0 X2C ≤30000 X3B ≤40000 XiA,XiB,XiC,XiD(i=1,2,3,4,5)≥0

65 第三章 线性规划模型 求解结果（单位元）： 第一年：X1A=34783, X1D=65217
第三章 线性规划模型 求解结果（单位元）： 第一年：X1A=34783, X1D=65217 第二年：X2A=39130, X2C=30000, X2D=0 第三年：X3A=0, X3B=40000, X3D=0 第四年：X4A=45000, X4D=0 第五年：X5D=0 第五年末总资金：Z=143750

66 第三章 线性规划模型 例3-9: 合理下料问题： 某工厂生产某一型号的机床，每台机床上分别需用2.9、2.1、1.5米长的轴1跟、2根和1根，这些轴需用同一种园钢制作，圆钢的长度为7.4米。如需要生产100台机床，问应如何安排下料，才能使用料最省？试建立其线性规划模型。

67 第三章 线性规划模型 问题分析： 对于每一根7.4米长的钢材，可有若干种下料方式把它截取成我们所需要的轴，如可以截取2根2.9米和1根1.5米，合计用料7.3米，余料为0.1米。可以列出全部的下料方式： B1 B2 B3 B4 B5 B6 B7 B8 需要量 2.9m 2.1m 1.5m 余料 2 1 0.1 3 0.3 0.9 0.2 0.8 1.1 4 1.4 100 200 最少

68 第三章 线性规划模型 思考题： 某厂生产一种产品，由两个B1零件和三个B2零件配套组装而成。该厂有A1，A2，A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全部用于加工某一种零部件的最大产量（即生产率：件/日）如下表所示。试求该产品产量最大的生产方案。

69 第三章 线性规划模型 例3-10 人力资源合理调派问题
第三章 线性规划模型 例3-10 人力资源合理调派问题 杭甬高速公路在杭州入口处在24小时内通过的数量是不均匀的，因此，相应地，在入口处收费的人数安排也应按时段不同而有所差异。根据历史资料统计，在各时段至少所需收费的职工人数如下： 每个职工上班后先工作4小时，然后离开1小时（休息、就餐等），再工作4小时。职工可以在任何正点时间上班。试建立雇佣职工最少的线性规划模型（只要求列出目标函数和几个有代表性的约束条件）。

70 第三章 线性规划模型 例3-10 人力资源合理调派问题 定义变量：24小时正点上班的人数作为变量 X0 : 0:00 上班的职工人数
第三章 线性规划模型 例3-10 人力资源合理调派问题 定义变量：24小时正点上班的人数作为变量 X0 : 0:00 上班的职工人数 X1 : 1:00 上班的职工人数 X2 : 2:00 上班的职工人数 …… X22: 22:00 上班的职工人数 X23: 23:00 上班的职工人数 目标函数： 24小时正点上班的人数和为最小 MIN Z = X0+X1+X2+ …… + X22+X23

71 第三章 线性规划模型 例3-10 人力资源合理调派问题
第三章 线性规划模型 例3-10 人力资源合理调派问题 约束条件：每一个时间段（一小时）总会有人在休息，需 要分析哪个时间上班的人不在岗位和在岗位上的是哪些时间上班的人。 0:00-1: :00上班的人（X20）工作四小时后正在休息，0:00、23:00、22:00和21:00上班的人工作还不到四小时，19:00、18:00、17:00和16:00上班的人已休息一小时，这些人都在岗位。此时岗位人数要求是至少2人。因此有： X0+X23+X22+X21+X19+X18+X17+X16≥2 1:00-2:00 X1+X0+X23+X22+X20+X19+X18+X17 ≥2 …… 5:00-6:00 X5+X4+X3+X2+X0+X23+X22+X ≥2 6:00-7:00 X6+X5+X4+X3+X1+X0+X23+X ≥8

72 第三章 线性规划模型 作业：求解以下线性规划问题 要求：1）拟定一个获得利润最大的生产计划； 2）若单价0.8元再购入少量原材料投入生产是
第三章 线性规划模型 作业：求解以下线性规划问题 某企业拟生产A、B两种产品，需利用一种原材料并经过车、铣两台机床加工，加工的工时定额、每天可用工时和原材料以及两种产品可能获得的利润如下表所示： 要求：1）拟定一个获得利润最大的生产计划； 2）若单价0.8元再购入少量原材料投入生产是 否合算？为什么？