没有对偶单纯形法课件

1、解:1)决策变量：设y1, y2分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金 3)约束条件:工厂决策者考虑： （1）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有2）目标函数：此时工厂的总收入为W=24y1+26y2,这也是租赁方需要付出的成本.而在这个问题中,是企业不生产,将自己的资源出售或出租,因此,此时,起决定作用的是租赁方,所以此时的目标函数为 Min W=24y1+26y2（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）租赁者考虑：希望价格越低越好，否则另找他人。 于是，能够使双方共同接受的是 ： 上述两个LP问题的

2、数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。 一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为： 原问题（P） 对偶问题（D）相应的矩阵形式为：4对称形式的对偶问题为：（P）（D）二、对偶理论(Dual Theory)1. 原问题与对偶问题的关系由以上两式可知，原问题与对偶问题之间具有如下关系(1)一个问题中的约束条件个数等于它的对偶问题中的变量数;(2)一个问题中目标函数的系数是其对偶问题中约束条件的右端项(3)约束条

3、件在一个问题中为“ ”,则在其对偶问题中为“ ”;(4)目标函数在一个问题中为求最大值,在其对偶问题中则为求最小值5非对称形式的对偶问题为：（LP）（DP）推导过程如下：原模型变化为根据对称对偶关系，写出其相应的对偶问题令6原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m 变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=” 第i个变量0 第i个变量0 第i个变量无限制变量个数=n 约束条件个数=n第i个变量0第i个变量0第i个变量无限制 第i个约束条件为“” 第i个约束条件为“” 第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数

4、第i个变量的系数 第i个约束条件的右端顶 归纳对称形式与非对称形式的对偶,原问题与对偶问题之间的关系如下表所示解:例1、写出下列线性规划问题的对偶问题解:定理1 如果线性规划中第k个约束条件是等式,则它的对偶规划中的第k个变量无非负限制,反之亦然.例2、写出下列线性规划问题的对偶问题例3 写出下面原规划的对偶规划解:10 2、对偶问题的基本定理 MaxZ=CXMinW=Yb（1）（对称性）对偶问题的对偶是原问题；（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解, 则有（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；（4）（最优性定理），若

5、X(0) 、 Y(0)分别是互为对偶问题的可行解，且C X(0) = Y(0) b，则X(0) 、 Y(0)分别是它们的最优解（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。 1112思考题：已知如下线性规划问题的对偶问题的最优解为y1*=4/5,y2*=3/5,z*=5，试用对偶理论找出原问题的最优解解：其对偶问题为：应用互补松驰性定理，将y1*=4/5, y2*=3/5代入对偶问题的约束条件得：解得：x1=1, x5=1, x2=x3=x4=0又由于y1*,y2* 0 ，原问题的两个 约束为紧约束，所以x10 x2=0 x3=0 x4=0 x5

6、 0作业已知如下线性规划问题的对偶问题的最优解为y1*=4,y2*=1，试用对偶理论找出原问题的最优解和最优值13三、对偶单纯形法1.单纯形法的重新解释X*是最大化LP问题最优解的充要条件是同时满足： （称为原始可行条件） （称为对偶可行条件） 因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。 ，然后从到 根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解.对偶单纯形法就是根据这种思想所设计的。因此，对偶单纯形法是先保证现行解对对偶问题可行，即，然后从到例14 用对偶单纯形法求解下列线性规划问题：解：化为标准形后，用对偶单

7、纯形法求解过程如下表所示 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y600y5y6-2-3 -2 -1 -4 0 1 0 -2 -2 0 -4 0 1 w0 12 8 16 12 0 02、对偶单纯形法的计算步骤： cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y60-12y5y4-23/4 -2 -1 -4 0 1 0 1/2 1/2 0 1 0 -1/4 w-9 6 2 16 0 0 3 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y6-8-12y2y42-1/4 2

8、1 4 0 -1 0 -1/2 0 -2 1 1/2 -1/4 w-13 2 0 8 0 2 3 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y6-8-16y2y33/21/8 1 1 0 2 0 -1/2 1/4 0 1 -1/2 -1/4 1/8 w-14 0 0 0 4 4 2 上表中常数列b所对应的系数均为非负，已求得问题的最优解，最优解为y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最优值为z*=14注意：对偶单纯形法仍是求解原问题，它是适用于当原问题无可行基解，且所有检验数均大于0的情况。若原问题既无可行基解，而检验数中又有小

9、于0的情况，只能用人工变量法求解。在计算机求解时，只有人工变量法，没有对偶单纯形法。19练习：用对偶单纯形法求解下列线性规划问题解：迭代结果如下 cj -4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 00y4y5-3-5 -1 0 -1 1 0 0 -2 -2 0 1 Z0 4 12 18 0 0 20 cj -4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 0-12y4y2-35/2 -1 0 -3 1 0 0 1 1 0 -1/2 Z-30 4 0 6 0 6 cj -4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 18-

10、12y3y213/2 1/3 0 1 -1/3 0-1/3 1 0 1/3 -1/2 Z-36 2 0 0 2 6 因此，最优解为：y2=3/2,y3=1，最优值为： maxZ=-3621四、影子价格一、影子价格问题的提出影子价格的定义影子价格在经济管理中的应用二、边际贡献本 节 要 点资源的合理利用问题：影子价格1、问题的提出资源单位消费产品资源限制单位利润还有现金，如何投资决策依据：比较第i种资源增加一个单位，其余资源不增加时利润的增加值决策依据：在取得最优方案的前提下比较第i种资源增加一个单位，其余资源不增加时利润的增加值设B是最优基，Z*是最优值设Y*是（D）的最优解则Z*=Y*b25

11、Lagrange乘子边际价格2、影子价格的定义27 其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是yi*。换句话说，yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。 CCBCNCSbXBXNXSXBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1最优基变量为 时，单纯形表29 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5用单纯

12、形法求得最优表为：由此，它们的最优解分别是X*=(6,4)T和Y*=(1/5,6/5) 最优值为：Z*=W*=36=24y1*+26y2* 其中y1*=1/5表示单独对材料增加1个单位，可使Z值增加1/5个单位的利润；y2*=6/5表示单独对工时增加1个单位，可使Z值增加6/5个单位的利润。302.影子价格的定义 把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。 影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。 资源的影子价格定量的反映了单位资源在最优生产方案中为总收益所做出的贡献。3

13、13、影子价格的求法资源的影子价格Y*=CBB-1，即为最优单纯形表中松驰变量对应的检验数。例如：在生产计划问题中，最优表如下 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5两种资源：材料的影子价格为y1=1/5 工时的影子价格为y2=6/5资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位利润（万元）1018x1x2x3x4x5x3001-23/711/7540/7x11005/7-3/750/7x2010-1/72/7200/7000-32/7-6/7Z-

14、4100/7最优解X*=(50/7，200/7)最优值Z*=4100/7Y*=(0，32/7,6/7)对偶问题的最优解对偶问题最优解Y*=(0，32/7,6/7)钢材煤炭设备台时即再增加1吨钢材，利润不会增加即再增加1吨煤炭，利润增加32/7万元即再增加1个台时，利润增加6/7万元利润原问题最优解X*=(50/7，200/7)对偶问题最优解Y*=(0，32/7,6/7)钢材煤炭设备台时由互补松弛定理：现有资源中的煤炭和设备台时已经全部用完而没有剩余，因此若增加这两种资源，必然会给工厂带来新的效益。现有资源中的钢材有剩余，因此若增加这种资源，只能造成积压，不会给工厂增加效益。利润*影子价格的大小

15、客观地反映了资源 在系统内部的稀缺程度364.影子价格的参谋作用 （1）指出企业挖潜革新的途径影价0，说明该资源已耗尽，成为短线资源。影价=0，说明该资源有剩余， 成为长线资源。影子价格能指示企业内部挖潜的方向影子价格越大的资源，表明：这种资源对目标增益的影响越大这种资源在该企业越稀缺、贵重管理措施：重视对该种资源的管理，通过挖潜革新、降低消耗或及时补充该种资源影价0，说明该资源已耗尽，成为短线资源。影价=0，这种资源对该企业来说相对富裕管理措施：向别的企业转让或以市场价出售 通过对企业内部的改造、挖潜和增加对影子价格大于零的资源的投入，使原有剩余资源得到充分利用39（3）可以预测产品的价格产

16、品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。 （4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。 （2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给EX: 某化工厂有三种资源A、B、C，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为x1,x2,x3,其数学模型为： 已解得最优单纯形表如下 已解得最优单纯形表如下 CBXBb x1 x2 x3 x4 x5 x6250 x2x3x610023020-1/4 1 0 1/2 -1/4 03/2 0 1 0 1/

17、2 0 2 0 0 -2 1 1 Z 4 0 0 1 2 0(1)求三种资源的影子价格,并解释其经济含义;(2)市场看好，决定增加一种资源的供应量，问应增加哪种资源？ 2、影子价格是在系统达到最优时对系统资源的一 种最优估价，并假设第i种资源增加一个单位时 最优基没改变。关于影子价格的说明：1、影子价格的取值与系统的状态有关，系统中任 一状态的改变都会引起影子价格的变化3、影子价格是一种资源的虚拟价格资源的市场价格影子价格是一种机会成本，在纯市场经济条件下，当市场价格低于影子价格，可以买进这种资源；相反，当市场价格高于影子价格，可以卖出这种资源。二、边际贡献生产策略问题：资源单位消费产品资源限

18、制单位价格问题：市场上正在热卖第j种产品，是否增加该产品的产量策略：若在最优方案中，第j种产品的产量xj为非基变量，不能生产该产品检验数别人热卖的产品我该不该生产？隐含成本第j种产品的价格新产品开发决策分析资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位价格（万元）1018x1x2x3x4x5000-32/7-6/7Z-4100/7x3001-23/711/7540/7x11005/7-3/750/7x2010-1/72/7200/7现有两种新产品A和B，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他们是否值得投产。资源单位消费产品AB钢材12煤炭21

19、设备台时34单位价格（万元）109资源单位消费产品AB钢材12煤炭21设备台时34价格（万元）109现有两种新产品A和B，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他们是否值得投产。产品A的隐含成本=不生产产品B的隐含成本=可以生产优化后分析（灵敏度分析）面对市场变化，灵敏度分析的任务是须解决以下两类问题一、当系数A、b、C中的某个发生变化时,目前的最优基是否仍最优（即目前的最优生产方案是否要变化）?(称为模型参数的灵敏度分析)二、增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化） (称为模型结构的灵敏度分析) 灵敏度分析的方法是在目前最优

20、基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？ bXXBB-1b0对原问题可行B-1AZC BB-1bC BB-1A-C0对对偶问题可行矩阵形式的单纯形表为优化后分析按如下方式进行原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量,编制新的单纯形表重新计算1、对于参数b的灵敏度分析从矩阵形式的单纯形表中可以看出，b的变化只影响最优解的变化和最优值的变化。XXBB-1bB-1AZC BB-1bC BB-1A-C因此，当 时，

21、最优基不变（即生产产品的品种不变，但数量及最优值会变化）。是一个不等式组，从中可以解得b的变化范围若B-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。53P137 例题4-12 对于生产计划问题，为使最优方案不变，试讨论第二个约束条件b2的变化范围。 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5 解：生产计划问题的数学模型和最优单纯形表为：54 从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性B-1b0,因此，为使最优解不变，只需变化以后的 B-1b0即可

22、。由解得：55若b2变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x112-6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z12 0 0 1/5 6/5 将上述数字替换最优单纯形表中相应位置的数据得：56 cj 4 3 0 0 CBXBb x1 x2 x3 x4 30 x2x3315 3/2 1 0 1/2 -5/2 0 1 -3/2 Z9 1/2 0 0 3/2 用对偶单纯形法迭代，求出的最优单纯形表如下：得到新的最优解为：x1=0,x2=3; maxz=9572、对价值系数Cj变化的分析（1）当CN（非

23、基变量的目标函数系数）中某个Cj发生变化时，只影响到非基变量xj的检验数由于所以,当即当时,最优解不变反之,当 时,最优解改变,需要用单纯形法重新进行迭代,以求得新的最优解.P133例4-10： 对于下列线性规划模型,为使最优解不变，讨论非基变量y1的目标函数系数c3的变化范围。用单纯形法求得其最优表为： cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 59解：因为y1为非基变量，其目标函数系数c3的变化只会影响到y1的检验数，因此为使最优解不变，

24、只需即若C3=3,则代入最优单纯形表中相应位置继续迭代以求出新的最优解。 cj 4 3 3 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 -2/5 1/5 6/5 （2）当CB(即基变量的目标函数系数)中某个Cj发生变化时则会影响到所有变量的检验数=CBB-1AC解不等式组P135例4-11 设基变量x1的系数C1变化为 ，在最优性不变的条件下，试确定 的范围解：将上述数字替换单纯形表中相应位置的数字得： cj 5 3 0 0 CBXBb x1 x2 x3 x4 35x2x146 0 1

25、 3/5 -2/5 1 0 -2/5 3/5 Z42 0 0 -1/5 8/5 62用单纯形法迭代得最优解表如下： cj 5 3 0 0 CBXBb x1 x2 x3 x4 05x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3 Z130/3 0 1/3 0 16/15 63（3）技术系数aij变化的分析 第一种情况（当jJN）：即aij为非基变量xj的技术系数时，它的变化只影响xj的系数列B-1Pj和检验数 ，为使最优方案不变，只需 例4-13： 对于下列规划问题的最优解，若由于工艺改进，y1的技术系数改为p3=(1,1)T，试讨论最优解的变化。65 cj 4 3 2

26、 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 解：最优解改变。此时其系数列改为：66 第二种情况（当jJB）：由于B中元素的改变影响到B-1的变化，因此也影响到整个单纯形表T(B)的变化。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解 将上述数据替换最优表中相应位置的数据，然后再用单纯形法求得新的最优解。 cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 1/5 3/5 -2/5 1 0 1/

27、5 -2/5 3/5 Z36 0 0 -3/5 1/5 6/5 67例题： 对于生产计划问题，分析原计划生产产品的工艺结构发生变化。若生产产品甲的工艺有了改进，其技术系数向量改为p1=(1,2)T，相应甲产品的每件利润为6元。试分析对计划有什么影响？解：此问题是关于参数的一个综合优化后分析问题，因为在这个问题中既有基变量系数的改变，又有基变量目标函数系数的改变。现只计算改变了的部分：（即X1的目标函数系数和其系数列）将这些改变了的数据填入单纯形表中，有：68 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146-1/5 1 3/5 -2/5 4/5 0 -2/5 3/5

28、Z36-17/5 0 1/5 6/5 在此表中X1是基变量，其对应的系数列应为单位向量，其检验数应为0。因此，进行行变换，将其化为正常的单纯形表的形式。 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x111/215/20 1 1/2 -1/4 1 0 -1/2 3/4 Z123/21 0 -3/2 15/4 69 cj 6 3 0 0 CBXBb x1 x2 x3 x4 06x3x11113 0 2 1 -1/2 1 1 0 1/2 Z78 0 3 0 3 新的最优解为X1=13，X2=0，最优值Z=7870注意：对于参数的灵敏度分析,在计算机软件中只有对C、b的分析，没

29、有对A的分析。以下是计算机软件的灵敏度分析。 Summarized Report for liu Page 1NumberVariableSolutionOpportunity CostObjective CoefficientMinimum Obj.CoeffMaximum Obj.Coeff12X1X2+6.0000+4.000000+4.0000+3.0000+2.0000+2.6666+4.5000+6.0000Maximized OBJ=36 Iteration=2 Elapsed CPU second=01、关于参数C的灵敏度分析712、关于参数b的灵敏度分析 Summarized

30、 Report for liu Page 2Constr.StatusRHSShadow PriceSlack or SurplusMinimum RHSMaximum RHS12TightTight+24.000+26.000+0.2000+1.200000+17.333+16.000+39.0000+36.0000Maximized OBJ=36 Iteration=2 Elapsed CPU second=072（4）对增加新产品的分析设某企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,am,n+1)T，此时

31、应如何分析才能确定该新产品是否值得投产？增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最优基B出发考虑：若n+1=CBB-1Pn+1Cn+10，则不应投入。 即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。73例题4-14： 现有一新产品丙，经预测其单位利润为3，技术消耗系数为P5=（2，2）T，问该产品是否值得投产？解：所以，值得投产。其系数列为： cj 4 3 0 0 3CBXBb x1 x2 x3 x4 y5 34x2x146 0 1 3/5 -2/5 2/5 1 0 -2/5 3/5 2/5 Z36 0 0 1/5 6/5 -1/5将此变量加入最优

32、单纯形表中得：用单纯形法迭代求得最优解为： cj 4 3 0 0 3CBXBb x1 x2 x3 x4 y5 34y5x1102 0 5/2 3/2 -1 1 1 -1 -1 1 0 Z38 0 1/2 1/2 1 075 在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。 对增加新约束条件的分析方法步骤是：（5）对增加新约束条件的分析第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束

33、条件。否则转下一步；第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。P142例4-15： 对于生产计划问题，设增加电力约束，生产1单位甲产品需耗电3个单位，生产1单位乙产品需耗电4个单位，且每天供电量不超过30单位。试分析此时最优解的变化情况。 解：将最优解x1=6,x2=4代入约束条件 ， 不满足，说明约束条件起作用。将约束条件加入松驰变量，化为等式 ，加入最优单纯形表中。 cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x54630 0 1 3/5 -2/5 0 1 0 2/5 3/5

34、0 3 4 0 0 1 Z36 0 0 1/5 6/5 077 cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x54630 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 3 4 0 0 1 Z36 0 0 1/5 6/5 0在这个表中，由于x1,x2是基变量，必须为单位向量，因此将x1,x2化为单位向量得 cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x546-4 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 0 0 -6/5 -1/5 1 Z36 0 0 1/5 6/5 0再用对偶单纯形法求得新的

35、最优表如下： cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x3222/310/3 0 1 0 -1/2 1/2 1 0 0 2/3 -1/3 0 0 1 1/6 -5/6 Z106/3 0 0 0 6/7 1/6案例1：综合生产问题某工厂加工A、B、C三种元件,三种元件在粗加工、精加工和包装检验三个车间所需的单位工时，单位价格和各车间总工时限额如下表，问如何安排生产，可获得最大总产值.ABC各车间工时粗加工121430精加工302460检查包装140420单位价格(元)30205080解:设生产A、B、C元件分别为x1,x2,x3件，其数学模型为求出其最优

36、表如下： cj 30 20 50 0 0 0CBXBb x1 x2 x3 x4 x5 x620500 x2x3x610023020 -1/4 1 0 1/2 -1/4 0 3/2 0 1 0 1/2 0 2 0 0 -2 1 1 Z13500 40 0 0 10 20 081因此，最优生产方案是：A元件不生产，B元件生产100件，C元件生产230件，可获得最大产值13500元。现继续对该问题进行优化后分析（1）该厂附近有甲、乙两个小厂愿意承接粗加工和精加工任务，但受各种因素的限制，该厂只能与一个厂签订一种加工合同。为增加收益，该厂应如何分别与两厂签订合同？已知甲、乙两厂分别提出的条件如下表：粗

37、加工精加工甲厂3元/工时17元/工时乙厂8元/工时16元/工时82解：由于粗加工和精加工的影子价格（也就是对目标的边际价值）分别为10元/工时，和20元/工时，也说明粗加工和精加工在最优安排时已全部耗尽。参照两小厂提出的价格要求，因此，该企业应该与甲厂签订粗加工的合同，与乙厂签订精加工的合同。签订加工的数量需要以优化后分析确定。即保持现有最优基不变的最大增加量。所以类似有：因此，最终应与甲厂签订粗加工10工时的合同，与乙厂签订精加工400工时的合同83（2）由于市场价格的波动，A元件的价格有上升趋势，问在价格达到多少时，A元件投产才有利。解：A元件投产有利就是指：A元件投产能使企业的收益增加，

38、即选取x1作为进基产品变量，可使收益增加，此时要求x1的检验数为负，即：因此，只有当A元件的单位价格达到70才有利于生产。84（3）由于市场供求关系的限制，现在B元件最多只能生产60件，问应如何调整生产安排？解：这相当于在原问题的基础上增加一个新约束条件：将此约束条件化为等式约束， 加入最优单纯形表中。并用对偶单纯形法迭代求出新的最优解如下。 cj 30 20 50 0 0 0 0CBXBb x1 x2 x3 x4 x5 x6 x7205000 x2x3x6x71002302060 -1/4 1 0 1/2 -1/4 0 0 3/2 0 1 0 1/2 0 0 2 0 0 -2 1 1 0 0

39、 1 0 0 0 0 1 Z13500 40 0 0 10 20 0 0CBXBb x1 x2 x3 x4 x5 x6 x7205000 x2x3x6x46023018080 0 1 0 0 0 0 1 3/2 0 1 0 1/2 0 0 1 0 0 0 0 1 -4-1/2 0 0 1 -1/2 0 -2 Z12700 45 0 0 0 25 0 2086案例2：一家企业制造三种产品，需三种资源，技术服务、劳力、行政管理，下表列出了三种产品每单位数量对每种资源的需要量产品ABC资源限量技术服务111100劳力1045600行政管理226300单位利润106487（1）问如何安排生产，可使利润

40、最大？（2）C产品的单位利润为多少时才值得生产？（3）若劳力资源增加到800小时，问最优计划是否要改变，若要改变，应如何改变？（4）制造部门提出要生产一种产品，需要技术服务1小时、劳力4小时、行政管理3小时，其单位利润为8，问可否投产？（5）若有一种原材料，如今受到限制，限制条件为 ，问最优计划是否受到影响？88 cj 10 6 4 0 0 0 CBXBb x1 x2 x3 x4 x5 x66100 x2x1x6200/3100/3100 0 1 5/6 5/3 -1/6 0 1 0 1/6 -2/3 1/6 0 0 0 4 -2 0 1 Z2200/3 0 0 8/3 10/3 2/3 0解

41、：（1）用单纯形法求得最优表为89（2）（3）最优基不变90（4）设新产品为x7值得投产。（5）将x1=100/3,x2=200/3,x3=0代入约束条件 左边得因此，最优计划不变。练习1、某企业生产甲、乙两种产品，需消耗A、B、C三种资源，产品的单位利润和单位消耗如下表所示： 产品 单位产品消耗资源甲乙丙资源限量A31330B22140C13450产品单位利润436（1）该企业如何安排生产，才能获得最大利润？（2）产品甲、的单位利润在多大范围内变化，可保持最优基解不变？（3）写出资源A、B的影子价格，并解释其经济意义。若资源B、C的限量不变，资源A不够可从市场购买，价格1元/单位，问是否要购

42、进A资源扩大生产？（4）若现有一新产品丁，据市场预测，丁的单位价格5元/单位，对A、B、C三种资源的单位消耗量为2，1，5，问是否值得生产？ 其最优单纯形表如下： cj 4 3 6 0 0 0 CBXBb x1 x2 x3 x4 x5 x6600 x3x5x282068/5 0 1 3/5 0 -1/5 4 0 0 1 1 -1-9/5 1 0 -4/5 0 3/5 Z661/5 0 0 6/5 0 3/593练习2、已知某线性规划的最终单纯形表如下：其中X1，X2，X3表示生产的三种产品。94 cj 3 1 5 0 0 CBXBb x1 x2 x3 x4 x5 05x4x3156 3 -1

43、0 1 -1 3/5 4/5 1 0 1/5 Z30 0 3 0 0 1 （1）根据表中数据进行经济分析。（2）若有一新产品X6，其价值系数为C6=4，消耗系数为P6=（1，2）T，问该产品是否值得投产？（3）若增加新约束条件 ，问最优方案是否改变？95 cj 2 -1 1 0 0 0CBXBb x1 x2 x3 x4 x5 x6000 x4x5x6601020 3 1 1 1 0 0 1 -1 2 0 1 0 1 1 -1 0 0 1 Z -2 1 -1 0 0 0练习：3、已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。 cj 0 0 0 0 1 1CBXBb

44、 x1 x2 x3 x4 x5 x602-1x4x1x2 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 Z cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x602-1x4x1x210155 0 0 1 1 -1 -2 1 0 1/2 0 1/2 1/2 0 1 -3/2 0 -1/2 1/2 Z25 0 0 3/2 0 -3/2 -1/296练习4、用单纯形法求解某极大化问题的单纯形表如下，问表中参数a1,a2,a3,d,1, 2为何取值范围时，下列结论成立。 cj 0 0 0 0 1 1CBXBb x1 x2 x3 x4 x5 x6300 x3x4x6d2

45、3 4 a1 1 0 a2 0 -1 -3 0 1 -1 0a3 -5 0 0 -4 1 Z 1 2 0 0 -3 0 （1）表中解为惟一最优解；（2）表中解为多重最优解之一；（3）该问题有无界解；（4）表中解为退化的基解；（5）表中解为不可行解；（6）尚未得到最优解，以x1代换x6 1 0, 2 0,d 0, 12=0 10, 20,d 0 20,a1 0 d=0 d0 13/a3,a3 097练习5、设有线性规划问题：其中b1,b2是常数，且已知此规划的最终表为： cj 5 2 3 0 0CBXBb x1 x2 x3 x4 x5 50 x1x53010 1 b 2 1 0 0 c -8 -

46、1 1 Z150 0 a 7 d e 确定表中所有的参数。e=0,d=5,b=5,c=-10,a=23,b1=30,b2=40应用EXCEL电子表格求解线性规划例： 用EXCEL 规划求解确定伟恩德玻璃制品公司产品组合问题公司有三个工厂： 工厂1：生产铝框和五金件 工厂2：生产木框 工厂3：生产玻璃和组装窗与门公司打算生产的新产品 8 英尺玻璃门；4 英尺6 英尺双层窗基本生产信息如下表：99理论模型为：在EXCEL 电子表格中建立线性规划模型1、选择决策变量单元格，决策变量的初始值一般赋0，并用较醒目的颜色（黄色）表示。2、确定目标单元格，用函数公式表示，并用较醒目的颜色（桔黄色）表示。=S

47、UMPRODUCT(C4:D4,C12:D12)1014、用公式输入每一个约束条件左边项E7： =SUMPRODUCT(C7:D7,C12:D12)E8： =SUMPRODUCT(C8:D8,C12:D12)E9： =SUMPRODUCT(C9:D9,C12:D12)应用EXCEL电子表格求解线性规划5. Excel Solver 的安装: Excel 工具菜单中选择加载宏1. Excel Solver 的安装: Excel 工具菜单中选择加载宏1046、调用规划求解，确定可变单元格和目标单元格1057、求解结果练习：某工厂可分别采用五种生产组合方案生产A, B, C三种产品 ，有关数据如下表。规定每天供应 A产品至少110 个。求收益最大的生产方案。如果第2种生产方法的每批成本提高到21元，问是否会改变最优解?如果产品B的单位售价增加到6元，是否影响最优解?如果加班要另付加班费每小时1.5元,问加班能否使利润增加?如果新购一台机器，购价300000元，每天可增加8个机器时间，机器可使用5年，每年工作250工作日，问是否有利?问增加3台新机器是否有利?第4种