#3_运筹学讲义[影子价格-灵敏度分析-运输问题]ppt课件

1、影子价格,1,对偶最优解的经济含义影子价格,代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。 其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率； 其经济含义是为约束条件所付出的代价。 当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,2,影子价格举例,3,y*1=5/3, y*2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。,分析： 1. y1=5/3说明在现有的资源限量的条件下， 增加一个单位第一种资源可以给企业带来5/3元 的利润；如果要出售该资源，其价格至少在成本 价上加5/3元。 如果y1为0，则表示增加第一种资源不会增加利润，因为第

2、一种资源还 没有用完。,4,影子价格是根据资源在生产中作出的贡献而作出的估价，这种估价不是资源的市场价格。 它反映了在最优经济结构中，在资源得到最优配置前提下，资源的边际使用价值。 单纯形表中松弛变量所对应的检验数的相反数是在该经济结构中的影子价格，也可以说对偶问题的最优解向量是结构中的影子价格。,5,定理1：在某项经济活动中，在资源得到最优配置条件下， 此定理的经济意义： （1）若生产一个单位第j种产品按消耗资源的影子价格计算的支出等于销售一个单位该产品所得收入，则可生产此产品。 （2）如果生产一个单位的第j种产品按所消耗资源的影子价格计算的支出大于销售一个单位该产品得到的收入，则不宜生产此

3、产品。,6,定理2：在某项经济活动中，在资源得到最优配置条件下， （1）若第种资源供大于求，即 则该项资源的影子价格为0 （2）若第种资源供求平衡，即 则该项资源的影子价格大于等于0。 影子价格越大，说明这种资源越是相对紧缺（根据影子价格确定资源采购,当市场价格低于影子价格，就买进资源，当市场价格高于影子价格，就卖出资源） 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,7,例,y*1=5/3, y*2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉

4、部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,8,和市场价格的比较,9,继续比较,10,例(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)：,求：(1)若目前市场上原料A的实际价格为0.5万元/t，工厂应如何决策？ (2)若目前市场上原料B的实际价格为0.8万元/t，工厂应如何决策？,解：建立模型，设x1,x2,x3分别表示I，II，III的生产量，则模型如下：,对偶问题,11,模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2

5、万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y22,也就是一定比生产产品I赚得多。产品II，III同理。 亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。,如果把资源A的量由7增加到8，会导致什么结果呢？,影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。,12,影子价格的经济意义

6、：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。,影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。,程序编写：,执行结果如下：,13,说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。,影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。,通过对右端项的灵敏性分析：,14,在最优基不变时，

7、A,B的右端项变化范围分别为(4.67,22)和(3.5,21) 对问题(1)0.50.6，应该售出部分原料将使利润更大，最大售出量为3.33t,利润将会增加(0.8-0.6)*3.33=0.66万元,15,例(奶制品的加工问题),50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,(1)35元可买到1桶牛奶，买吗？若买，每天最多买多少?,(2)可聘用临时工人，付出的工资最多是每小时几元?,(3)A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,16,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能

8、力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,17,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000

9、4) 40.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2，利润3360元。,模型求解,18,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.0000

10、00 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,也可理解为： 为了使该非基变量变成基变量，目标函数中对应系数应增加的量,19,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000

11、 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,20,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.0

12、00000 4) 40.000000 0.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,时间加1单位, 利润增2,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,21,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.00

13、0000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由243

14、= 72 增加为303= 90，在允许范围内,不变！,(约束条件不变),结果解释,22,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREA

15、SE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶？,(目标函数不变),注意: 充分但可能不必要,23,灵敏度分析,24,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。

16、在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。,25,更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,26,设线性规划问题： maxZ=CX s.t. AX=b A代表企业技术状况 b 代表企业资源状况 C代表企业产品市场状况（利润) 这些因素不 变的情况下，企业最优生产计划和最大利润由线性规划的最优解和最优值决定。,27,最优

17、化后分析，可归为以下两类问题： 1）当系数A，b，C发生改变时，目前 最优基是否还最优？ 2） 为保持目前最优基还是最优，系 数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 灵敏度分析包括以下五种： 目标系数C变化 基变量系数发生变化； 非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,28,若B是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,29,例2 线性规划,30,灵敏度分析,31,3-2*（-1）-3*2=-1,32,价值系数CN发生改变,C3,C3-4,如果C34,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变

18、。即对于C3而言,使最优解不变的条件是C34。,33,价值系数CN发生改变,34,价值系数CB发生改变,C1-3,1-4/3C1,1/3C1-1,C1-3 0, 1-4/3C10, 1/3C1-10 C13 若C13/4 则x4进基，x1出基 若3 C1 则x3或x5进基，x2出基,35,价值系数CB发生改变,36,价值系数CB发生改变,37,右端常数b发生改变,b1,4b1/3-3,3-b1/3,9/4b1 9,-3-5b1/3,38,右端常数b发生改变,39,右端常数b发生改变,b2,4-b2/3,b2/3-1,3b2 12,-b2/3-5,40,增加一个变量 若企业在计划期内，有新的产品

19、可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,41,灵敏度分析,例2,42,增加一个约束 在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响， 所以需要增加约束条件。 1）若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。

20、 2)若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,43,灵敏度分析,例 增加约束,44,灵敏度分析,增加约束,45,灵敏度分析,A中元素改变 如果N中数据改变，可以用增加一个变量来处理 如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解,46,运输问题,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,47,例 某公司从两个产地A1、A2将物品运往三个销地B1,

21、B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,48,解：产销平衡问题：总产量 = 总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）,49,运输规划问题的数学模型,运输

22、问题的一般形式：产销平衡,A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：,50,变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,定理: 设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,

23、51,表上作业法,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。,52,表上作业法,例2 某运输资料如下表所示：,问：应如何调运可使总运输费用最小？,53,解：第1步 求初始方案,方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,54,总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元,元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。

24、例如下面两种运输方案。,15,5,10,总运费是z=108+52+151=105,最小元素法：,55,5,15,10,总运费z=105+152+51=85,后一种方案考虑到C11与C21之间的差额是82=6，如果不先调运x21，到后来就有可能x110，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,56,方法2：Vogel法 元素差额法,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,57,2）再从差值最大的行或

25、列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。 重复1)和2)，直到找出初始解为至。,3,11,3,10,1,9,2,7,4,10,5,8,5,58,7,1,1,3,5,2,1,5,59,7,1,3,5,2,7,5,3,60,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费: (13)(46)(35)(210)(18)(35)85元,61,第2步 最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量

26、的检验数都非负，则运输方案最优,求检验数的方法有两种： 闭回路法 位势法（）,62,闭回路的概念,为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表,63,例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表33中的变量x 32及x33不是闭回路的顶点，只是连线的交点。,64,闭回路,例如变量组 不能构成一条闭回路，但A中包含有闭回路,变量组 变量数是奇数，显然不是闭回路，也不含有

27、闭回路；,65,可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。 下表中用虚线画出以非基变量 x22 为起始顶点的闭回路。,66,表 以非基变量 x22 为起始顶点的闭回路,67,可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2 + 3 10 + 5 4 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。 从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。,

28、68,这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路 x24 ，x14 ，x13 ，x23 ，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ，即总的运费减少 1 个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。,69,这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为 24 = -1，22 = 1。闭回路方法原理就是通过寻找闭回路来找到非

29、基变量的检验数。,70,如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有 ij = (闭回路上的奇数次顶点单位运费之和) - (闭回路上的偶数次顶点单位运费之和) 其中 ij 为非基变量的下角指标。,71,按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图所示。,72,显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。 闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。,73,用位势法对初始方案进

30、行最优性检验：,1）由ij=Cij-（Ui+Vj）计算位势Ui ， Vj ，因对基变量而言有ij=0，即Cij-（Ui+Vj） = 0，令U1=0即参照系,2）再由ij=Cij-（Ui+Vj）计算非基变量的检验数ij,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,74,当存在非基变量的检验数kl 0 且kl =minij时，令Xkl 进基。从表中知可选X24进基。,第3步 确定换入基的变量

31、,第4步 确定换出基的变量,以进基变量xik为起点的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示换出作为非基变量。,求 =Minxijxij对应闭回路上的偶数标号格= xpq 那么确定 xpq为出基变量，为调整量；,75,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。,1,2,5,76,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此

32、时最小总运费： Z =(13)(46)(35)(210)(18)(35)85元,3,11,3,10,1,9,2,7,4,10,5,8,5,3,6,3,1,2,0,-2,-5,3,10,3,9,（0）,（2）,（2）,（1）,（12）,（9）,77,表上作业法的计算步骤：,78,表上作业法计算中的问题：,（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取ij0中最小者对应的变量为换入变量。 （2）无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。,79, 退化解： 表格中一

33、般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量，选择任意一个最小运量对应的基变量作为出基变量，并打上“”以示作为非基变量。,80,12,4,11,4,8,3,10,2,9,5,11,6,(0),(2),(9),(2),(1),(12),8,12,4,2,8,14,如下例中11检验数是 0，经过调整，可得到另一个最优解。,81,11,4,4,3,1,3,7,7,8,2,10,6,3

34、,4,1,6,0,6,在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34,例3：用最小元素法求初始可行解,82,运输问题的应用,求极大值问题 目标函数求利润最大或营业额最大等问题。,83,求解方法： 将极大化问题转化为极小化问题。设极大化问题的运价表为C ，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C，其中C=（Mcij）0,将C作为极小化问题的运价表，用表上用业法求出最优解。,84,例3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,85,得到新的最小化运输问题，用表上作业法求解即可。,86,产销不平衡的运输

35、问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,当产大于销时，即：,数学模型为：,87,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,88,当销大于产时，即：,数学模型为：,由于总销量大于总产量,故一定有些

36、需求地不完全满足,这时虚设一个产地Am+1，产量为：,89,销大于产化为平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,90,例4 求下列表中极小化运输问题的最优解。,因为有：,91,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。,92,下表为计算结果。可看出：产地A4还有20个单位没有运出。,93,3. 生产与储存问题,例5 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一

37、规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。,94,解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足： 交货： x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10,把第 i 季度

38、生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度生产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：,95,由于产大于销，加上一个虚拟的销地D，化为平衡问题，即可应用表上作业法求解。,96,该问题的数学模型： Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,97,最优生产决策如下表，最小费用z7

39、73万元。,98,例 (运输问题) 两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大米分别为4t，8t，三个两站至少需要大米分别为2t,4t,5t，两个粮库到三个粮站的距离(km)如下表，求使运费最低。,解： (1)问题分析：总需求量为11t，小于总库存量12t，所以问题可行。 (2)从线性规划的三个要素出发，决策变量：问题是各个粮仓向粮站调运了多少大米，此调运量就是决策变量。 目标函数：运费和运量和距离有关系，即t*km最小，所以要将运量与相应的距离相乘然后使总和最小。 约束条件：两个粮库的库存量限制和三个粮站需求量的限制。,99,(3)建立模型，设A1,A2分别向B1,B2,B3运送大米x11,x12,x13,x21,x22,x23，则有：,min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23,s.t. x11+x12+x13=2 x12+x22=4 x13+x23=5 x11,x12,x13,x21,x22,x23=0,100,101,通过选择Lingo|Generate|Display model将模型展开，方便查看求解报告的第三部分。,相应的添加的剩余变量或者松弛变量。,102,程序改