第七章线性优化

1、线性优化模型的应用线性优化模型的应用生产管理交通网络物流配送市场营销项目评价等等7.17.1用线性优化模型定量描述一个管理问题用线性优化模型定量描述一个管理问题通过两个管理问题的实例,介绍线性优化模型的应用。它们分别是:实例7.1 新贝德福德钢铁厂(NBS) 。实例7.2 宝石加工工具公司(GTC) 。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(1)(1)在钢铁生产过程中,炼焦煤是一种必备的生产原料。新贝德福德钢铁厂(NBS)对炼焦煤的年需求量在:100到150万吨之间。为NBS提供炼焦煤的供应商共有8家煤炭公司,分别标记为:A,B,C,D,E,F,G,H 。表7.1给出了8家炼

2、焦煤供应商关于炼焦煤的价格信息。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(2)(2)ABCDEFGH价格(美元/吨)49.5050.0061.0063.5066.5071.0072.5080.00联合/非联合联合联合非联合联合非联合联合非联合非联合卡车/铁路铁路卡车铁路卡车卡车卡车铁路铁路挥发性(%)1516182021222325生产能力(千吨/年)300600510655575680450490表表7.1: 87.1: 8家煤炭公司的价格及相关信息家煤炭公司的价格及相关信息实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(3)(3)根据表7.1,我们以供应商A公司为

3、例来解释相关数据。A公司关于炼焦煤的报价为每吨49.50 。A公司的年供应量为300千吨。A公司是一家联合矿业公司。A公司的运输方式为铁路。A公司煤炭的平均挥发性为15% 。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(4)(4)根据NBS的下一年生产计划,其对炼焦煤的需求量为1,225千吨。从质量上考虑,炼焦煤的挥发性需要至少达到19% 。NBS公司必须从属于联合矿业的公司中的采购量至少为总采购量的50% 。铁路运输量限制在650吨/年,卡车运输量限制在720/吨。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(5)(5)NBS管理层需要解决下述问题。(A) NBS需要

4、确定从每个供应商处的采购量,使总采购成本最小?(B) NBS的总采购成本是多少?(C) NBS的平均采购成本是多少?实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(6)(6)定义炼焦煤的采购量 (以千吨为单位)为 :XA=从A公司采购炼焦煤的数量。XB =从B公司采购炼焦煤的数量。XC=从C公司采购炼焦煤的数量。XD=从D公司采购炼焦煤的数量。XE=从E公司采购炼焦煤的数量。XF=从F公司采购炼焦煤的数量。XG=从G公司采购炼焦煤的数量。XH =从H公司采购炼焦煤的数量。) 1 . 4() 1 . 4(*实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(7)(7)NBS采购炼

5、焦煤的总采购成本。NBS采购炼焦煤的总成本等于:49.50XA+50.00XB+61.00XC+63.50XD +66.50XE+71.00XF+72.50XG+80.00XH目标是确定使上述总采购成本达到最小值的采购方案,即我们需要确定XA, XB, XC, XD,XE, XF, XG, XH的值。但是我们必须考虑约束或限制条件。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(8)(8)NBS在采购炼焦煤时面临的约束条件。对炼焦煤年需求量的约束。需求:XA+XB+XC+XD +XE+XF+XG+XH=1225另外一个必须满足的条件为是,至少50%的炼焦煤必须从联合矿业公司采购:XA

6、+XB+XD+XF XC+XE+XG+XH对上式重新安排后获得联合约束:联合: XA+XB-XC+XD-XE+XF-XG-XH 0类似地,卡车和铁路运输的约束条件分别为:卡车: XB+XD +XE+XF720铁路: XA+XC +XG+XH 650由于要求所采购炼焦煤的平均挥发性必须至少是19%,我们有下述关系式:实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(9)(9)19XXXXXXXX25X23X22X21X20X18X16X15XHGFEDCBAHGFEDCBA实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(10)(10)对上式处理后,获得挥发性约束。挥发性: -4

7、XA-3XB-XC+XD +2XE+3XF+4XG+6XH 0另一类重要的约束是从每家矿业公司的采购量不能够超过其生产能力。A矿的生产能力: XA 300B矿的生产能力: XB 600C矿的生产能力: XC 510D矿的生产能力: XD 655E矿的生产能力: XE 575F矿的生产能力: XF 680G矿的生产能力: XG 450H矿的生产能力: XH 490最后,未知变量XA,XB,XC,XD ,XE,XF,XG,和XH没有一个会出现负数,称为非负性约束条件。非负性:XA,XB,XC,XD ,XE,XF,XG, XH 0 。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(11)(

8、11)NBS的炼焦煤采购问题的数学公式表示。最小化: 49.50XA+50.00XB+61.00XC+63.50XD +66.50XE+71.00XF+72.50XG+80.00XH约束条件为:需求: XA+XB+XC+XD +XE+XF+XG+XH=1225联合: XA+XB-XC+XD-XE+XF-XG-XH 0卡车: XB+XD +XE+XF 720铁路: XA+XC +XG+XH 650挥发性: -4XA-3XB-XC+XD+2XE+3XF+4XG+6XH 0A矿的生产能力: XA 300B矿的生产能力: XB 600C矿的生产能力: XC 510D矿的生产能力: XD 655E矿的生

9、产能力: XE 575F矿的生产能力: XF 680G矿的生产能力: XG 450H矿的生产能力: XH 490非负性: XA,XB,XC,XD ,XE,XF,XG, XH 0对上述模型利用EXCEL的规划求解(将在7.4节介绍),将获得使总采购成本最小的采购方案,参见表7.2 。实例实例7.1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(12)(12)矿业公司变量采购数量(千吨/年)AXA55.0BXB600.0CXC0.0DXD 20.0EXE100.0FXF0.0GXG450.0HXH0.0表表7.2: NBS7.2: NBS使总采购成本最小的采购方案使总采购成本最小的采购方案实例实例7.

10、1 7.1 新贝德福德钢铁厂新贝德福德钢铁厂(13)(13)回答NBS管理者的三个问题。(A)NBS需要确定从每个供应商处的采购量,使的总采购成本最小?答案:参见表7.2的第三列(B)NBS的总采购成本是多少?答案:总成本= 49.50XA+50.00XB+61.00XC+63.50XD+.50XE+71.00XF+72.50XG+80.00XH=49.50X55+50.00X600+61.00X0+63.50X20+66.50X100+71.00X0+72.50X450+80.00X0=73267.50(C)NBS的平均采购成本是多少?答案:平均成本= 73267.50/1225=59.81

11、(美元/吨)实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(1)(1)宝石加工工具公司(GTC)生产扳手和钳子,原料为钢铁,制造过程为先在浇铸机上浇铸工具,然后在装配机上装配工具, GTC公司生产,销售,和利润数据参见表7.3 。表7.3扳手钳子可用资源量钢铁(磅)1.51.027000磅/天浇铸机(小时)1.01.021000小时/天装配机(小时)0.30.59000小时/天需求限制(件/天)1500016000利润(美元/千件)130100实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(2)(2)GTC的目标。GTC管理层希望确定生产使每日利润最大化的扳手和钳子的产量或

12、者说制定每日利润最大化的生产计划。GTC特别关注以下问题:每天应生产扳手和钳子的数量使利润最大化?这个计划产生的利润是多少?在这个计划中,那些资源是最关键的?实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(3)(3)为了确定GTC生产计划问题的目标函数,我们首先给出下述定义:XW=每天生产扳手的数量,以千套为单位。XP=每天生产钳子的数量,以千套为单位。那么目标函数就是利润函数: 利润=130 XW+100 XP变量XW和XP的取值受到可用资源数量和日需求量的限制。实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(4)(4)其中一个约束限制是每天可获得的钢铁的数量是有限的,即

13、:钢铁:1.5 XW+1.0 XP27另一个约束是每天浇铸机的生产能力也是有限的:浇铸: 1.0 XW+1.0 XP 21还有一个约束是装配机的日生产能力限制:装配: 0.3 XW+0.5 XP 9日需求约束扳手: XW 15钳子: XP 16非负性: XW, XP0实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(5)(5)GTC生产计划问题的公式表达如下:最大化: 130 XW+100 XP 约束条件为:钢铁: 1.5 XW+1.0 XP 27浇铸: 1.0 XW+1.0 XP 21装配: 0.3 XW+0.5 XP 9扳手需求: XW 15钳子需求: XP 16非负性: XW,

14、XP 0实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(6)(6)GTC生产计划问题的求解结果。利用EXCEL规划求解(将在7.4节介绍),我们获得GTC生产计划问题的最优解: XW,=12.0, XP=9.0 利润=130 X12.0+100 X9.0 =2460.00美元/天钢铁约束: 1.5 X12.0+1.0 X9.0=27正好等于可用钢铁的上限,或在这个生产方案下,钢铁正好被用完。实例实例7.2 7.2 宝石加工工具公司宝石加工工具公司(7)(7)回答GTC管理者提出的三个问题。每天应生产扳手和钳子的数量使利润最大化?答案:GTC公司应该计划每天生产12000件扳手和900

15、0件钳子。这个计划产生的利润是多少?答案:利润=2460美元/天。在这个计划中,那些资源是最关键的?至少钢铁资源是关键的,多增加一个单位钢铁,利润将会增加。还可计算浇铸机和装配机的时间资源。7.27.2重要概念和定义重要概念和定义(1)(1)根据对前面两个实例的认识,我们定义线性优化模型。目标: 从NBS和GTC这两个实例来看,它们两者都有一个需要优化的目标.在NBS中,目标是使采购炼焦煤的总成本最小化。在GTC中,目标是确定扳手和钳子的每日产量,使日利润最大化。决策变量:在NBS中,决策变量是未知变量XA,XB,XC,XD,XE,XF,XG,和XH,它们分别表示从每家矿业公司的采购量。在GT

16、C中,决策变量是未知变量XW,XP,分别表示每天制造扳手和钳子的数量。7.27.2重要概念和定义重要概念和定义(2)(2)目标函数:每个问题都还有一个表示决策变量目标的目标函数。对于NBS,目标函数为:总成本=49.50XA+50.00XB+61.00XC+63.50XD +66.50XE+71.00XF+72.50XG+80.00XH对于GTC问题,目标函数为:利润=130 XW+100 XP 约束:这两个问题的另一共同特征是,它们的决策变量都受到某种约束或满足某种函数关系。对于NBS问题,约束为:7.27.2重要概念和定义重要概念和定义(3)(3)NBS的约束条件为:需求: XA+XB+X

17、C+XD +XE+XF+XG+XH=1225联合: XA+XB-XC+XD-XE+XF-XG-XH 0卡车: XB+XD +XE+XF720铁路: XA+XC +XG+XH 650挥发性: -4XA-3XB-XC+XD+2XE+3XF+4XG+6XH 0A矿的生产能力: XA 300B矿的生产能力: XB 600C矿的生产能力: XC 510D矿的生产能力: XD 655E矿的生产能力: XE 575F矿的生产能力: XF 680G矿的生产能力: XG 450H矿的生产能力: XH 490非负性: XA,XB,XC,XD ,XE,XF,XG, XH07.27.2重要概念和定义重要概念和定义(4

18、)(4)GTC的约束条件为:钢铁: 1.5 XW+1.0 XP27浇铸: 1.0 XW+1.0 XP 21装配: 0.3 XW+0.5 XP 9扳手需求: XW 15钳子需求: XP 16非负性: XW, XP0我们注意到约束条件可以是等式或者是不等式。7.27.2重要概念和定义重要概念和定义(5)(5)约束函数,左边项与右边项:我们总可以将决策变量放在约束关系式的左边,称为左边项,而关系式的右边放置常数,称为右边项。 约束函数 约束关系 常数其中:约束关系为”=“,” “,和” “比如在NBS例子中,铁路的约束为: XA+XC +XG+XH 650约束函数为XA+XC +XG+XH ,关系式

19、为” “,右边项为650 。7.27.2重要概念和定义重要概念和定义(6)(6)非负性条件:最后,注意到非负条件的存在。比如,GTC的非负条件为:XW 0, XP 0可行解:可行解是满足所有约束条件和非负条件的变量。可行解可以构成可行解的集合。在GTC的问题中, XW,=6, XP=8,是可行解,可以快速验证。7.27.2重要概念和定义重要概念和定义(7)(7)最优解从可行解集合中找出使目标函数达到最优(最大值或最小值)的可行解,也就是说,满足所有约束条件和非负条件。比如,在NBS问题中,最优解是:XA=55,XB=600,XC=0,XD=20,XE=1000,XF=0,XG=450, XH=

20、0,对这个最优解来说,采购成本达到最小,为73267.50线性优化模型7.27.2重要概念和定义重要概念和定义(8)(8)所有约束条件都是线性函数,并且目标函数也是线性函数,则称其为线性优化(或线性规划)模型。线性优化模型的求解是从决策变量的可行解的集合中找到使目标函数达到最优值的过程。7.37.3求解线性优化模型求解线性优化模型(1)(1)图解法,单纯形法,应用计算机求解。图解法以GTC的生产计划问题为例子,介绍图解法的计算步骤。最大化: 130 XW+100 XP 约束条件为:钢铁: 1.5 XW+1.0 XP 27浇铸: 1.0 XW+1.0 XP21装配: 0.3 XW+0.5 XP

21、9扳手需求: XW 15钳子需求: XP 16非负性: XW, XP07.37.3求解线性优化模型求解线性优化模型(2)(2)图解法的五个步骤步骤1:绘制非负性条件的图形步骤2:绘制每个约束条件的图形步骤3:绘制决策变量的可行域步骤4:绘制目标函数的等值线步骤5:确定最优解步骤1:绘制非负性条件GTC问题的非负性条件为:XW0, XP 07.37.3求解线性优化模型求解线性优化模型(3)(3)由图7.1可以看出,只需考虑第一像限图7.1 XPXW7.37.3求解线性优化模型求解线性优化模型(4)(4)步骤2:绘制每个约束条件的图形考虑钢铁约束:钢铁: 1.5 XW+1.0 XP27将直线1.5

22、 XW+1.0 XP=27绘制在平面上,基本方法为缺点两个点,比如让XW=0,则XP=27,获得点(0,27),让XP=0, XW=18,获得点(18,0),将以上两个点相连就可获得一直线,参见图7.2.7.37.3求解线性优化模型求解线性优化模型(5)(5) XPXW 27181.5XW+1.0XP=27区域1区域2图7.27.37.3求解线性优化模型求解线性优化模型(6)(6)图7.2中的区域1是满足钢铁约束的所有点,即满足1.5 XW+1.0 XP27 。图7.2中的区域2是不满足钢铁约束的所有点,即: 1.5 XW+1.0 XP27 绘制GTC问题所有约束条件,即浇铸,装配,扳手需求,

23、和钳子需求,我们将获得下述图形,参见图7.3。7.37.3求解线性优化模型求解线性优化模型(6)(6) XPXW 2718 213015 21 18 16图7.37.37.3求解线性优化模型求解线性优化模型(7)(7)步骤3:确定可行域上图中满足所有约束条件和非负条件的区域构成了可行域步骤4:决定目标函数的等值线GTC问题的目标函数为: 利润=130 XW+100 XP绘制利润等于1300美元的直线,即: 130 XW+100 XP =1300获得两点(0,13)和(10,0),用图形表示,参见图7.47.37.3求解线性优化模型求解线性优化模型(8)(8) XPXW 1310130XW+10

24、0 XP =1300图7.45 6.5 A7.37.3求解线性优化模型求解线性优化模型(8)(8)图7.4中直线上的所有点都等于1300,比如点A出的坐标值为(5,6.5),代入到目标函数中,我们有:130 X5+100X6.5 =650+650=1300同样,我们也可以绘制利润等于1500美元的直线,即: 130 XW+100 XP =1500获得两点(11.54,0)和(0,15),其直线参见图7.57.37.3求解线性优化模型求解线性优化模型(9)(9) XPXW 1310130XW+100X P =1300 1511.54130XW+100X P =1500图7.57.37.3求解线性

25、优化模型求解线性优化模型(10)(10)从图7.5中,我们可以发现这两条直线的斜率是相同的。但是在 XW轴和 XP轴的截距是不同的。步骤5:决定最优解最优解的思路是计算可行域中的那一点有最好的目标函数值。通过添加目标函数的等值线到可行域上,可以确定这个点,如图7.5所示。7.37.3求解线性优化模型求解线性优化模型(11)(11) XPXW1510图7.6 13 16A=(12,9)等值线130X W+130 XP =24607.37.3求解线性优化模型求解线性优化模型(12)(12)从图7.6中我们观察到对应较大目标函数值的等值线位于图中的东北方向。因此,通过向东北方向移动等值线,直到等值线

26、正好接触到可行域的边界,图7.6中的A点。 这个点的坐标值为(XW, XP) =(12,9) 。所以XW =12和XP =9是GTC问题的线性优化模型的最优解。这个最优解的目标函数值等于 130 X12+100X9 =2460(美元)7.37.3求解线性优化模型求解线性优化模型(13)(13)A点的坐标值是如何计算的?它正好是钢铁约束和浇铸约束的等式直线的相交点,可以通过求解下述二元二次联立方程: 1.5XW +1.0 XP =27 1.0XW +1.0 XP =21很容易求出(XW, XP) =(12,9) 关于可行域的讨论:可行域表现为一个多边型,它的边界由不同斜率的直线段所组成。图7.7

27、和图7.8说明了可行域可以呈现的各种形状。7.37.3求解线性优化模型求解线性优化模型(14)(14) XPXW图7.77.37.3求解线性优化模型求解线性优化模型(15)(15) XPXW图7.87.37.3求解线性优化模型求解线性优化模型(16)(16)有效约束和非有效约束如果将最优解代入到约束条件中,其左边函数值正好等于约束值,那么该约束就是有效约束。如果将最优解代入到约束条件中,其左边函数值严格小于约束值,那么该约束就是非有效约束。在GTC问题中,对于铁钢约束,左边函数值为: 1.5XW +1.0 XP=1.5X12+1.0X9=27正好等于铁钢约束的约束值。我们也可以验证浇铸约束也是

28、有效约束。7.37.3求解线性优化模型求解线性优化模型(17)(17)对于装配约束,左边函数值为: 0.3XW +0.5 XP=0.3X12+0.5X9=8.1而装配约束的约束值等于9,由此装配约束是非有效约束。同样我们可以验证扳手需求和钳子需求约束都是非有效约束。多个最优解对于一个线性优化模型来说可以有多于一个的最优解,即有多个最优解,图7.9说明了这种情况。7.37.3求解线性优化模型求解线性优化模型(18)(18)图7.9 多个可行解 XPXW7.37.3求解线性优化模型求解线性优化模型(19)(19)无界线性优化模型对于最大化问题来说,如果存在具有任意大的目标值的可行方案,那么线性优化

29、模型是无界的。对于最下化问题来说,如果存在具有任意小的目标值的可行方案,那么线性优化模型是无界的。图7.10说明了最大化目标函数情况下的一个无界线性优化模型的实例。7.37.3求解线性优化模型求解线性优化模型(20)(20)图7.10 无界线性优化模型 XPXW不断增加的目标值7.37.3求解线性优化模型求解线性优化模型(21)(21)非可行线性优化模型如果没有任何满足所有约束的方案,那么一个线性规划模型是非可行的。图7.11说明了这种情况。出现这种情况意味建立模型过程中存在不合理性。7.37.3求解线性优化模型求解线性优化模型(22)(22)图7.11 XPXW7.37.3求解线性优化模型求

30、解线性优化模型(21)(21)图解法的局限性虽然几何解法只适用于具有两个决策变量的线性规划问题,但它搜索最优解的思路和几何上的直观性对于研究线性规划问题的通用算法提供了参考。随着决策变量和约束条件的增多,搜索最优解的过程也会变的更加复杂,但是几何解法揭示关于线性规划问题最优解的基本结论也适用于复杂的线性规划问题,即其解的情况不外乎以下几种情况:具有唯一最优解或多重最优解,无界解以及无可行解。作业作业(1)(1)P407 练习7.1P408 练习7.27.37.3求解线性优化模型求解线性优化模型(22)(22)求解线性优化模型的单纯形算法单纯形的几何意义是在维空间中,由个点连接起来的几何体。在一

31、维空间中, 单纯形是连接两个点的一条直线;在二维空间中,单纯形是由三个点形成的三角形;在三维空间中,单纯形是由四个顶点构成的四个平面的金字塔。在介绍线性规划问题的几何解法时,我们提到线性规划问题的最优解一定是出现在可行域(二维空间的多边形)的某个顶点,这个结论同样适用于N维空间中的可行域(N维空间的单纯形)。7.37.3求解线性优化模型求解线性优化模型(23)(23)对于N维空间,我们无法通过几何方法直接观察到N维空间的单纯形顶点,但是利用线性代数的知识,我们能够设法计算出单纯形顶点的坐标及对应目标函数值。所以,我们将通过某种方式(线性方程组的基可行解)来记录,描述和分析目标函数和约束函数在单

32、纯形顶点的情况。单纯形法是从一个初始顶点开始, 然后根据一种迭代规则从一个顶点到另一个顶点,直到满足最优顶点的条件。由于寻找线性规划问题最优解的过程是在由约束函数构成的单纯形上进行的,我们称其为单纯形法。7.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优化模型电子表格软件EXCEL有一个称为规划求解的附加功能,这个功能利用单纯形算法求解电子表格中经过相应描述的一个线性优化模型。用电子表格构造一个线性优化模型通过把电子表格组成四个部分完成模型建造,它们是数据,决策变量,目标函数以及约束条件。数据部分提供用于优化模型的数据。决策变量部分确定表示模型中不同决策变量的单元格

33、。目标函数部分包含计算目标函数值所必须的单元格。约束部分定义了计算模型中不同约束的左边项和右边项。7.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优化模型(2)(2)我们讨论如何把NBS构造到电子表格上。NBS线性优化模型为:最小化: 49.50XA+50.00XB+61.00XC+63.50XD +66.50XE+71.00XF+72.50XG+80.00XH约束条件为:需求: XA+XB+XC+XD +XE+XF+XG+XH=1225联合: XA+XB-XC+XD-XE+XF-XG-XH 0卡车: XB+XD +XE+XF 720铁路: XA+XC +XG+XH

34、 650挥发性: -4XA-3XB-XC+XD+2XE+3XF+4XG+6XH0A矿的生产能力: XA 300B矿的生产能力: XB600C矿的生产能力: XC 510D矿的生产能力: XD 655E矿的生产能力: XE 575F矿的生产能力: XF 680G矿的生产能力: XG 450H矿的生产能力: XH 490非负性: XA,XB,XC,XD ,XE,XF,XG, XH 07.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优化模型(3)(3)把NBS线性优化模型的目标函数和约束条件的各项系数转换到标准表格中,参见表7.4 。从表7.4可以看出,标准表格包含了NB

35、S线性优化模型的基本特征。 NBS线性优化模型的标准表格的第一行是决策变量和右边约束值,第二行是决策变量在目标函数中的系数,第三到十五行分别是决策变量在约束条件的系数。由于表格的行是以数字标识,列是以字母标识,所以只要选中了表格中的一行和一列,就唯一确定了一个单元格。表7.5是电子表格的一个截图,其中的相关数据是根据标准表格7.4转换而来,比如说,单元格K5中存放的是需求约束右端项的数据(1225)。 7.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优化模型(4)(4)决策变量XAXBXCXDXEXFXGXH关系符号右端项目标函数49.5050.0061.0063.

36、5066.5071.0072.0080.00=C需求11111111=1225联合11-11-11-1-1=0卡车01011100=720铁路10100011=0A矿产能10000000=300B矿产能01000000=600C矿产能00100000=510D矿产能00010000=655E矿产能00001000=575F矿产能00000100=680G矿产能00000010=450H矿产能00000001=4907.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优化模型(4)(4)表7.57.47.4用电子表格创立和求解一个线性优化模型用电子表格创立和求解一个线性优

37、化模型(6)(6)在电子表格中选择工具规划求解后,获得规划求解参数窗口。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格有关约束的影子价格我们再次考虑GTC问题:目标: 最大化 130 XW+100 XP 约束条件为:钢铁: 1.5 XW+1.0 XP 27浇铸: 1.0 XW+1.0 XP21装配: 0.3 XW+0.5 XP 9扳手需求: XW 15钳子需求: XP 16非负性: XW, XP0最优解为: XW=12,XP=9,目标值(利润)等于2450(美元)7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(2)(2)在这个生产方案下,钢铁正好被用完,并且

38、浇铸机的工时也正好被用完,这两个约束即我们讨论过的有效约束。假设我们获得了额外1000磅的钢铁,那么钢铁的约束值(右端项)将由27变为28,我们重新计算最优解(参见EXCEL7.1),获得:XW=14,XP=7,最优目标值(利润)等于2520(美元)相对于方案XW=12,XP=9,目标函数增加的值为: 2520-2460=60(美元)它是由一个额外的1000磅钢铁所带来的利润,GTC愿意支付60美元/千磅作为额外增加的钢铁数量。这个数值60被称为钢铁约束的影子价格。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(3)(3)影子价格的定义:一个约束的影子价格是当该约束的右端项(

39、通常被理解为可用资源的上限)的值增加一个单位,而所有其他约束保持不变时的优化目标函数值发生变化的数量。影子价格也被称为边际价格,或边际成本。假设我们获得了额外1000小时的浇铸机生产能力,那么浇铸机的约束值(右端项)将由21变为22,我们重新计算最优解(参见EXCEL7.1),获得:XW=10,XP=12,目标值(利润)等于2500(美元)相对于方案XW=12,XP=9,目标函数增加的值为: 2500-2460=40(美元)它是由一个额外的1000小时的浇铸机生产能力所带来的利润,GTC愿意支付40美元/1000小时作为额外增加的的浇铸机生产能力。这个数值40被称为浇铸机约束的影子价格。7.5

40、7.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(4)(4)假设我们获得了额外1000小时的装配机生产能力,那么装配机的约束值(右端项)将由9变为10,由于装配机约束不是有效约束,即在该生产方案(XW=12,XP=9)下,对装配机时实际的消耗为: 0.3 X12+0.5 X9=3.6+4.5=8.1(千小时)本来就剩余900小时,再增加1000小时也不会对利润有任何贡献,因此,装配机生产能力约束的影子价格是0,换言之,GTC将不会愿意为增加的装配机生产能力而支付额外的费用。同样道理,我们可计算扳手需求约束和钳子需求约束的影子,它们都等于0 。表7.6总结了GTC问题的所有影子价格。7

41、.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(5)(5)表7.6:GTC生产问题中的所有影子价格约束影子价格钢铁每千磅60美元浇铸机每千小时40美元装配机每千小时0美元扳手需求每千件0美元钳子需求每千件0美元7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(6)(6)影子价格的基本特点对于一个线性优化模型来说,我们有下述结论:1.每个约束都有一个影子价格。2.影子价格的单位:影子价格的单位是目标函数的单位除以约束的单位。3.影子价格的经济信息: 如果我们考虑一个确定最优生产方案的线性优化模型,我们可以用评估当前资源(约束条件的右端项)的稀缺性。4.影子价格和市

42、场价格的关系:影子价格反映了在当前最优生产方案下对企业利润的贡献度,是属于边际价格,是企业独有的价格。而资源的市场价格是属于交易价格,假如GTC面临钢铁的市场价格是每千磅P美元,影子价格是每千磅60美元。当GTC希望采购钢铁时,钢铁的价格突然上涨, GTC愿意支付钢铁价格的上限为每千磅P+60美元。如果当前钢铁的价格为每千磅P+30美元, GTC还是愿意支付,只不过这时的目标利润仅增加了30美元。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(7)(7)从生产企业拥有资源的角度来分析,企业可以选择生产产品来获取利润,也可以考虑出租出售其拥有的资源来获取利润。以GTC生产问题为

43、例子,其稀缺资源为钢铁和浇铸机的可用工时(因为它们的影子价格等于0),从另外一个角度来看,如果GTC的管理者决定不自己生产扳手和钳子,而将钢铁出售,浇铸机的工时出租,这时管理者就要考虑如何给它们定价的问题。设YG,YJ分别表示钢铁和浇铸机的影子价格,为了生产一把扳手,需要消耗1.5鎊钢铁和消耗浇铸机1个小时的工时,那么如果将生产1把扳手的资源(这里指钢铁和浇铸机的工时)在市场中出售和出租,则GTC的管理者愿意出售和出租的条件是: 1.5YG,1.0YJ0.13其中0.13为生产1把扳手获得的利润。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(8)(8)同样道理,GTC的管理

44、者不愿生产钳子的条件是: 1.0YG,1.0YJ0.1其中0.1为生产1把钳子获得的利润。如果GTC的管理者把所有库存钢铁和浇铸机的工时都出售或出租后,获得的总收益为: S=27000YG,21000YJ我们需要注意S是出售和出租所有钢铁和浇铸机工时的利润,它是经营钢铁和浇铸机工时的利润。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(7)(7)从电子表格的模型中获取影子价格所有求解线性优化模型的商业软件都会计算影子价格,EXCEL的规划求解也计算了影子价格。EXCEL的规划求解的影子价格信息在灵敏度报告中。如何生成线性优化模型的灵敏度分析报告?在完成优化之后, EXCEL的

45、规划求解将提示是否产生相关的报告。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(8)(8)选择输出灵敏度分析报告表7.77.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(8)(8)GTC的线性优化模型的灵敏度报告表7.8:GTC线性优化模型的灵敏度报告7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(9)(9)影子价格的变化范围当右端项(可用资源数量)发生变化时,影子价格在什么范围内还是有效的?比如说,钢铁数量从27000磅变化到35000磅时,GTC的利润是否以60美元/千磅的比例变化?灵敏度分析报告含有有关影子价格是有效的范围信息。GTC

46、的灵敏度报告参见表7.8 。根据表7.8中的数据,钢铁约束的影子价格是60美元/千磅。在表7.8 的下半部分的第六和七列含有有关影子价格是有效的右端值的范围信息。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(10)(10)钢铁约束的允许增加值为1500磅,允许减少的值为2250磅。所以,只要钢铁右端值的变化范围在4500,42000磅之间,当前的影子价格就是有效的。同样道理,浇铸机约束的影子价格的有效范围为当浇铸机的生产能力的变化范围在19500,22000小时之间。7.57.5约束的灵敏度分析和影子价格约束的灵敏度分析和影子价格(10)(10)NBS的线性优化模型的电子表

47、格灵敏度报告表7.9: NBS的电子表格灵敏度报告作业作业(2)(2)P409 练习7.4 P410 练习7.5 P412 练习7.67.67.6构造和利用线性优化模型的要点构造和利用线性优化模型的要点(1)(1)用于构造一个线性优化模型的一般原则确定决策变量确定目标函数,主要有以下两种:(1)使收益与成本之差最大化(2)使成本与收益之差最小化确定约束,主要有以下几类:-资源平衡约束-能力约束-质量约束-政策约束7.67.6构造和利用线性优化模型的要点构造和利用线性优化模型的要点(2)(2)有关利用一个线性优化模型的要点思考与管理相关的问题拥有高质量的数据是前提条件研究数据利用线性优化模型作业

48、作业(3)(3)P418 练习7.12案例分析案例分析DECDEC的短期制造问题的短期制造问题(1)(1)DEC的年收入超过120亿美元。其中,收入的2/3来自硬件销售,而1/3来自软件销售和服务。机构一般来说,制造企业是由下述部门组成的,如下图所示。制造部门对外销售部门芯片制造部门存储器制造部门通信产品制造部门系统集成部门磁盘制造部门销售与服务部门其他市场欧洲市场美国市场案例分析案例分析DECDEC的短期制造问题的短期制造问题(2)(2)背景DEC在1988年第二季度发布了具有高性能价格比的系列计算机系统,参见表7.10。表7.10GP-1高端计算机系统,大内存,磁盘和存储器有扩充功能GP-

49、2中端通用计算机系统,中等内存,磁盘和存储器有扩充功能GP-3使用原先磁盘系统,替换到GP-2的过度产品WS-1基于GP-2计算机系统的高端工作站WS-2使用原先磁盘系统,入门级别工作站,有限存储器和扩充功能案例分析案例分析DECDEC的短期制造问题的短期制造问题(3)(3)相对现有的产品来说,新计算机系列产品具有更好的性价比。国内客户对新产品的接受程度也是非常高的。从1988的第三季度开始,公司进行了新产品系列的装运。然而,从当前季度(第四季度)来看,装运发货的速度比计划的要慢。主要是以下两个问题妨碍了对全国的供货。第一,由于芯片制造部门还在继续对新芯片进行调试,新芯片的供应受到了影响。第二

50、,磁盘驱动器制造部门继续调试磁盘驱动器的生产线,所以磁盘驱动器也受到了影响。案例分析案例分析DECDEC的短期制造问题的短期制造问题(4)(4)在新产品生产的初始阶段,这种现象是不正常的。从现在的情况来看,上述两种调试过程有可能延续到1989年的第一季度。这些问题引起了管理层的重视。公司的销售经理(他的工作是确保产品供应满足市场需求)已经在1988年的第三季度以非常直接的方式对新产品的短缺做出了反应。从产品供应角度来看,生产新型计算机系统所需要的最主要的稀缺资源是CPU芯片,参见表7.11中和表7.12中关于新产品的销售价格和新产品中CPU的套数。案例分析案例分析DECDEC的短期制造问题的短

51、期制造问题(5)(5)表7.11:计算机系统的销售价格计算机系统价格(美元)GP-160,000GP-240,000GP-330,000WS-130,000WS-215,000案例分析案例分析DECDEC的短期制造问题的短期制造问题(5)(5)表7.11 的注释价格是一个基于三个主要地区的价格平均值。内存和新磁盘的容量的变化对价格的影响可以忽略。补贴和折扣的幅度在不同地区中和对不同产品大致相同。价格的上升幅度在不同地区中和对不同产品大致相同。大多数成本在一个季度时间段内可以被认为不变的。案例分析案例分析DECDEC的短期制造问题的短期制造问题(6)(6)表7.12:CPU芯片套数的要求计算机系

52、统CPU芯片套数GP-11GP-21GP-31WS-11WS-21案例分析案例分析DECDEC的短期制造问题的短期制造问题(7)(7)表7.12的注释芯片制造是一种耗时长的生产过程。1989年第一季度芯片供应固定在7000套,没有任何增加的可能性。该数量是基于以前的市场规模的估计。从需求方面来看,通过短期市场促销,客户将被鼓励订购新计算机系统。至少有一种新型磁盘驱动器被用于GP-2系统和WS-1系统(参见表7.13),并且在这两个系统中以及GP-1系统中,这种新型磁盘驱动器在所有增加的计算机附件中是受欢迎的”附件”(参见表7.13) 。比如说,客户对这种新型磁盘驱动器的偏好是每个计算机系统1.

53、7个磁盘驱动器。由于新型磁盘驱动器的稀缺,客户的偏好无法满足,新型磁盘驱动器的实际配置情况参见表7.13的第三列。当新型磁盘驱动器有富余时,将满足那些需要一个以上磁盘驱动器的客户。案例分析案例分析DECDEC的短期制造问题的短期制造问题(8)(8)表7.13:每个系统新型磁盘驱动器的使用量每个系统的平均磁盘数计算机系统客户偏好限制GP-10.30GP-21.71GP-300WS-11.41WS-200案例分析案例分析DECDEC的短期制造问题的短期制造问题(9)(9)表7.13 的注释:GP-3和WS-2使用其他(非限制)磁盘。GP-1是否使用新型磁盘是可选择的。估计结果是全世界范围内的平均值

54、。地区的估计结果误差在正负10%范围内。1989年第一季度可供应的新型磁盘数量减少了50%,为3500个。此外,减少到50%以下或恢复到以前正常水平都是可能的。自从1988年第三季度以来,新型磁盘在新产品中的使用率一直保持在这个限制水平上。客户的不满意程度一直在增加。一些重要客户坚持要求在他们的系统中有多于一个以上的新型磁盘,但涉及这些客户的具体数量是不知的。任何多余的新型磁盘将作为附加附件装运给以前的只有一个新型磁盘的客户。案例分析案例分析DECDEC的短期制造问题的短期制造问题(10)(10)在1988年第三季度的中期,出现了几个新动向,对1989年第一季度的系统供应产生新的影响。公司内部的磁盘驱动器制造部门对1989年第一季度的新型磁盘驱动器的供应量将减少50%,为3500件。公司内部的芯片制造部门认为CPU芯片在1989年第一季度供应量最高达到7000套。256K的DRAM内存的供应在整个行业都处于非常紧张状态。 DRAM内存是生产各种计算机系统和存储产品必不可少的元器件之一,并且生产新产品系列也需要DRAM内存。相对公司的需求量来说, DRAM内存供应量只能满足90%的需求(短缺10%)。此外,通讯模块和模块柄也存在不确定数量的短缺,两种模块在新产品的生产过程中是不可缺少