整数规划例题.doc

运筹学补充例题例题 1.1 某工厂可以生产产品A和产品B两种产品。生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。这两种产品在市场上是畅销产品。该工厂经理要制订季度的生产计划，其目标是使工厂的销售额最大。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 产品售价（元） 800 300 MAX 800X1 +300X2ST6X1 +8X2 = 12010X1 +5X2 =0例题 1.2 该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价格调整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产计划，其目标仍然是使工厂的销售额最大。X 600X1 +400X2ST6X1 +8X2 = 12010X1 +5X2 =0例题 1.3 由于某些原因，该工厂面临产品原料供应的问题。因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。有关信息在下表中给出。 产品A 产品B 资源总量 机器（时） 6 8 120人工（时） 10 5 100 原材料(公斤) 11 8 130 产品售价（元） 600 400MAX 600X1 +400X2ST6X1 +8X2 = 12010X1 +5X2 = 10011X1 +8X2 =0例题 1. 随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出。 产品A 产品B 资源总量 资源价格（元单位） 机器（时） 6 8 120 人工（时） 10 5 100 20原材料(公斤) 11 8 130 1 产品售价（元） 600 400设： J为所用机器资源数量（小时）；R为所用人力资源数量（小时）；L为所用原材料数量（公斤）MAX 600X1 +400X2 -CST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L = 0 J = 120R = 100L =0例题 1.5 学习了管理课程后，该企业的经理明白了产品的成本包括变动成本和固定成本。如果生产产品A，工厂要花费1000元的固定成本，如果生产产品B，工厂要花费800元的固定成本。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。!在例1_4的基础上改进.!设:Y1,Y2是0,1变量。若Y1=1,表示生产A,若Y1=0,表示不生产A;! 若Y2=1,表示生产B,若Y2=0,表示不生产B.!分析:如果X10,应该让Y1=1。为此，选一个充分大的数（此处选1000），! 加约束 X1=1000Y1。! 如果X1=2，Y1必须为1，不能为零。! 若X1=0，Y1既可以为零,又可以等于1；由于目标函数越大越好，! Y1的系数为负数，所以Y1选择等于零。!约束 X1=0；同理，有1000Y2-X2=0。MAX 600X1 +400X2 -C -1000Y1 -800Y2ST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L = 0 J = 120R = 100L =01000Y2-X2=0ENDINT Y1INT Y2见 LINDOIP例1_5.LTX例题 1.6 通过求解例1.4和1.5中的线性规划模型，从结果分析可知原材料已经用尽,是稀缺资源。假设，该原材料在总量100公斤以内，按正常价1元/公斤供应；若超过100公斤，超过部分按1.2元/公斤供应。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。!在例1_5的基础上改进.!将使用的原材料分为两部分L1和L2。L1表示100公斤以内使用的原材料数量，L2表示超过100公斤使用的原材料数量。MAX 600X1 +400X2 -C -1000Y1 -800Y2ST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L1 -L2 = 0 J = 120R = 100L1 =01000Y2-X2=0ENDINT Y1INT Y2见 LINDOIP例1_6.LTX例题 1.7 假设，该原材料在市场上容易买到，是买方市场。原料生产厂家实行如下的销售策略：如果购买100公斤以下，按正常价1元/公斤供应；若超过100公斤，超过部分按0.8元/公斤供应。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。!此题看似与例1.6相同，但是，如果将例1_6中的1.2改为0.8，! 求解后会出现出乎意料的结果：L1=0, L2=120，! 即不使用100公斤以内的，专使用超过100公斤的原材料。!为了解决此问题，增加一个0-1变量Y. ! Y=0，L1没有达到100公斤(L1 = 100)；Y=1, L1已经达到100公斤。!若L1=100Y, ! 只有L1=100时Y才可以等于1。! （变换后为：100Y-L1=0）!若Y=1, L2可以取正数，添约束：L2=10000Y, ! 其中10000是考虑到其它资源，L2不可能超过的数。! （变换后为：L2-10000Y=0）MAX 600X1 +400X2 -C -1000Y1 -800Y2ST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L1 -L2 = 0 J = 120R = 100L1 =01000Y2-X2=0100Y-L1=0L2-10000Y=100？例题 1.8 假设，该原材料是买方市场。原料生产厂家实行如下的销售策略：如果购买100公斤以下，按正常价1元/公斤供应；若超过100公斤，则全部按0.8元/公斤供应。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。!在例1.7的基础上解此题。考虑0-1变量Y. Y=0，L1没有达到100公斤；Y=1, L1已经达到100公斤。! 若L1达到了100公斤（Y=1），L1应该退回100公斤的差价，共计20元；若没有达到100公斤（Y=0），不退。MAX 600X1 +400X2 -C -1000Y1 -800Y2 +20YST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L1 -L2 = 0 J = 120R = 100L1 =01000Y2-X2=0100Y-L1=0L2-10000Y=0ENDINT Y1INT Y2INT Y见 LINDOIP例1_8.LTX!在例1.7的基础上解此题。考虑0-1变量Y. Y=0，L1没有达到100公斤；Y=1, L1已经达到100公斤。!改变IP例1_8.ltx中的模型，只用原始数据，不用人工计算退回的钱。!设C1是机器、人工的费用，C2是100公斤以内的材料费用，100公斤以上的材料费是0.8L2，在目标函数中。!问题的难点是计算C2。!用相互排斥的约束：! 约束1： 1L1 = C2 +MY! 约束2： 0.8L1 = C2 +M(1-Y)! 若Y=1，买够了前100公斤，约束1自然满足，从约束2看，C2至少是 0.8L1!若Y=0，没有买够了前100公斤，约束2自然满足，从约束1看，C2至少是 1L1!达到了约束的目的，又用原始数据。变换后得下列模型。求解后与原来得解相同。MAX 600X1 +400X2 -C1 -C2 -0.8L2-1000Y1 -800Y2ST 6X1 +8X2 - J = 0 10X1 +5X2 - R = 0 11X1 +8X2 - L1 -L2 = 0 J = 120R = 100L1 = 1005J +20R - C1 = 0 L1 - C2 -10000Y= 00.8L1 - C2 +10000Y=01000Y2-X2=0100Y-L1=0L2-10000Y=500X12+X22+X32+X42=800X13+X23+X33+X43=750X14+X24+X34+X44=400!供给的约束!对北京有 X11+X12+X13+X14=1500Y1，变形为X11+X12+X13+X14-1500Y1 = 0X21+X22+X23+X24-1500Y2 = 0X31+X32+X33+X34-1500Y3 = 0X41+X42+X43+X44-1500Y4 = 0! 在北京、上海、广州、武汉四个城市中选择1-2个城市Y1+Y2+Y3+y4=500X12+X22+X32+X42=800X13+X23+X33+X43=750X14+X24+X34+X44=400!供给的约束!若考虑北京建普通库房，有 X11+X12+X13+X14=1500Y1!若考虑北京建大型库房，有 X11+X12+X13+X14=3000Z1!在解题之前不知道是否Y1=1，或Z1=1，上面两个约束不知道哪个起作用。!可以另设一个0-1变量U1，其作用是限制在两个约束中只有一个起作用。为此，选一个充分大的数 M!约束变成：!X11+X12+X13+X14 = 1500Y1 + M U1!X11+X12+X13+X14 =3000,我们取M=10000!得：X11+X12+X13+X14 - 1500Y1 -10000 U1 = 0! X11+X12+X13+X14 - 3000Z1 +10000 U1 = 10000!若U=1，第一个约束自然满足，第二个约束起作用；若U=0，第一个约束起作用，第二个约束自然满足。X11+X12+X13+X14-1500Y1 -10000 U1= 0X21+X22+X23+X24-1500Y2 -10000 U2= 0X31+X32+X33+X34-1500Y3 -10000 U3= 0X41+X42+X43+X44-1500Y4 -10000 U4= 0X11+X12+X13+