《运筹学习题解答.doc》由会员分享，可在线阅读，更多相关《运筹学习题解答.doc（72页珍藏版）》请在三一办公上搜索。
1、运筹学习题解答 管理运筹学教程习题参考答案 第一章 线性规划 1、解：设每天应生产A、B、C三种型号的产品分别为x1,x2,x3件。则线性规划模型为： maxZ=405x1+20x2+30x37x1+3x2+6x31200s.t40x1+40x2+50x32000x1,x2,x302、解：设5种债劵的投资额分别为x1,x2,x3,x4,x5件。则线性规划模型为：maxZ=0.065x1+0.09x2+0.045x3+0.055x4+0.05x5x+x12+x3+x4+x5=30x1+x218 s.tx3+x412x20.65(x3+x4)x50.2(x1+x2)x1,x2,x3,x4,x503
2、、（1）解：对原问题标准化，令x1x1，x3=x3-x3 maxZ=-x1+2x2+4x3-4x3-2x1+x2-x3+x3+x4=9s.t3x1+x2+4x3-4x3-x5=254x1-x2+4x3-4x3=30x1,x2,x3,x3,x4,x50（2）解：对原问题标准化，令x1x1，x3=x3-x3 maxZ=x1-2x2-4x3+4x33x+2x2+2x3-2x3+x4=191s.t4x1+3x2+4x3-4x3-x5=14-5x1+2x2+4x3-4x3=26x1,x2,x3,x3,x4,x50（3）解：对原问题标准化，令x2=x2-x2maxZ=x1+x2-x22x1+3(x-x2)
3、62s.tx1+7(x2-x2)42x1-(x2-x2)=3x10,x20,x201 4、（1）解：首先将线性规划模型标准化得：maxz=2x1-x2+x33x1+x2+x3+x4=60s.tx1-x2+2x3+x5=10x1+x2-2x3+x6=20x1,x2,L,x60 最优解为x1 =0，x2 = 110/3 , x3 = 70/3。目标函数值： Z* = 100/3（2）解：首先将线性规划模型标准化得：maxz=-5x1+x2-3x3-2x4 x1+2x2+3x3+4x4+xs.t5=72x1+2x2+x3+2x4+x6=3x1,x2,L,x60 2 最优解为x1 =0，x2 = 1.
4、5, x3 = 0, x4=0。目标函数值： Z* = 1.5 5、(1)利用大M法。解:在上述问题中加入松弛变量和人工变量得：maxz=2x1+3x2-5x3-Mx4-Mx6x1+x2+x3+x4=7s.t2x1-5x2+x3-x5+x6=10 x,x,L,x0612这里M是一个充分大的正数,取基变量为 x4 , x6 ，可得如下表 由于。123利用两阶段法。先在以上问题的约束条件中加入松弛变量、人工变量，给出第一阶段的线性规划问题： 3 maxw=-x4-x6 x1+x2+x3+x4=7s.t2x1-5x2+x3-x5+x6=10 x,x,L,x0612这里取基变量为 x4 , x6 ，可
5、得如下表 由于。这里 x4、x6 是人工变量。第一阶段我们已求得 W = 0,因人工变量 x6 = x4 = 0，所以(45/7, 4/7, 0 ,0)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，所有检验数 j 0，所以 x1 = 45/7，x2 = 4/7 , x3 = 0 是原线性规划问题的最优解。目标函数值： Z* = 102/7。 4 (2)利用大M法。解:在线性规划中加入人工变量得：maxz=-4x1-x2-Mx5-Mx6-Mx73x1+x2+x5=34x1+3x2-x3+
6、x6=6s.tx+2x+x+x=42471x1,x2,L,x70这里由于x5, x6, x7为基变量，因此它们对应的检验数行的检验数应为0，经变换得初始单纯形表。 5 最优解为x1 =0.4，x2 = 1.8, x3 = 1。目标函数值： Z* = 3.4利用两阶段法。先在约束条件中加入人工变量，给出第一阶段的线性规划问题：maxw=-x5-x6-x73x1+x2=34x1+3x2-x3=6 s.tx1+2x2+x4=4x1,x2,x3,x40 由于。6 这里 x5, x6, x7是人工变量。第一阶段我们已求得 W = 0,因人工变量x5 x6 x7 = 0，所以(0.4,1.8 , 1 ,0
7、)T 是原问题的基本可行解。于是可以开始第二阶段的计算。将第一阶段的最终计算表中的人工变量列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，可得如下第二阶段的初始单纯形表最优解为x1 =0.423maxW=20y1+13y2+30y3-4y1-3y2 76、（1）解：将线性规划问题化为对偶问题 2y1-3y2 +5y3=4s.t.6y1-5y2+3y33y0,y0,y无约束231minW=6y1+13y2（2）解：将线性规划问题化为对偶问题2y1+y2 1s.t.-3y1+2y2 2y0,y0217、用对偶单纯形法求解线性规划问题。（1）解：将模型转化为maxZ=-4x1-1
8、2x2-18x3-x1-3x3+x4=-3s.t-2x2-2x3+x5=-5 x,x,L,x01257 可得原问题最优解X*=（2.5，0，0）， Z*=10（2）解：将模型转化为minW=40y1+6y2+25y3y1-2y2+y3 60s.t.2y1+y2 +y350y1,y2,y30进一步可以变为maxW=-40y1-6y2-25y3-y1+2y2-y3+y4=-60s.t.-2y1-y2 -y3+y5=-50y1,y2,y30 可得原问题最优解X*=（25，0）， Z*=15008、已知线性规划问题maxZ=4x1+x2+2x38x1+3xs.t2+x326x1+x2+x38x1,x2
9、,x30x1,x3的目标函数系数的变化范围；8 （3）的变化范围。 （1） 可得原问题最优解X*=（0，0，2），最优值 Z*= 4 对偶问题最优解（2，0），最优值 Z*= 4（2）如果x-1101系数的改变，使s1=c1-CBBP1=c1-(2,0)-1186=c1-160即 c116时，原最优方案不发生改变。如果x3系数的改变，使sA=C-CBB-1A=(4,1,c3,0,0)-(c3,0)31108-2-20-11=(4-8c3,1-3c3,0,-c3,0)04-8c30即 1-3c130解得c3，这时原最优方案不发生改变。-c302（3）如果b改变，则B-1b=10-11b1b029
10、 b10 解得 b10-b1+b20b2b1即b10的范围如果b1改变，则B-1b=103030-4190=-30 10 即第一个约束条件的右端的常数项由20变为30时，则最优方案调整为 X=(0,0,9)T,目标值为117。 （2）如果b2改变，则1B-1b=-4 02020=170-10即第二个约束条件的右端的常数项由90变为70时，则最优方案调整为 X=(0,5,5)T,目标值为90。(3)目标函数中x3的系数由13变为8，由于x3是非基变量，因此c3改变为8时，使s3=c3-CBB-1P3=8-(5,0)这时原最优方案不发生改变。1-403=8-15=-70 110(4) 由于x1是非
11、基变量，它对应的系数矩阵变化时，不会改变B，它只影响单纯形表Pj列，只是对检验数有影响，因此。-1s1=c1-CBB-1P1=-5-(5,0)1-400=-5-0=-50 15这时原最优方案不发生改变。(5) 以x6为基变量，将上式反映到最终单纯形表中得到 11 利用对偶单纯形法计算得增加约束后，最优方案调整为 X=(0,12.5,2.5)T,目标值为95。 则运输量最少为509050801507020080=35000 11、解：初始方案为： 12 则运输量最少为2080140501201104011020908060=32800 12、解：由于已知各面食加工厂制作单位面粉食品的利润及各面粉
12、厂到各面食加工厂之间的 由于要求的是利润最大化，再一点，该问题是产销不平衡问题，增加一个虚拟的面食厂D，他的需求量为10，各面粉厂到面食厂的运价为0。在伏格尔方法中从行差额和列差额中选出则最大利润为15806155105209100=42513、解：设x1为买第一种包装的袋数，x2为买第二种包装的袋数，则数学模型为minz=64x1+48x235x1+24x2107 s.tx1,x20,整数14、解：设xij为第i辆平板车装cj类箱子的数量，i=1,2;j=1,2,L,7。 则箱数的约束为x11+x218x12+x227x13+x239x14+x246 x15+x256x16+x264x17+
13、x27813 重量的约束为2xi1+3xi2+xi3+0.5xi4+4xi5+2xi6+xi740,i=1,2厚度的约束为48.7xi1+52xi2+61.3xi3+72xi4+48.7xi5+52xi6+64xi71020,i=1,2 特殊约束48.7(x15+x25)+52(x16+x26)+64(x17+x27)302.7自然约束xij0,整数,i=1,2;j=1,2,L,7目标函数是使浪费的空间最小，也就是装的越多，空间浪费的越少。maxz=48.7(x11+x12)+52(x12+x22)+61.3(x13+x23)+72(x14+x24)+48.7(x15+x25)+52(x16+
14、x26)+64(x17+x27)15、（1）解：求相应的线性规划（LP）minz=-4x1-3x24x1+x210s.t2x1+3x28x,x012得（LP）的最优解x1=11/5,x2=6/5,z=-62/5首先注意其中一个非整数变量的解，如x2，在松弛问题中的解x2=6/5，于是原问题增加两个约束条件x21，x22将两个约束分别并入原问题的松弛问题（LP）中，形成两个分支，即后继问题（LP1）和(LP2)，这并不影响原问题的可行域。解（LP1），得最优解为x1=9/4,x2=1,z=-12再解（LP2），得最优解为x1=1,x2=2,z=-10继续对（LP1）进行分解。对（LP1）增加两个
15、约束条件x12，x13将两个约束分别并入（LP1）中，形成两个分支，即后继问题（LP11）和(LP12)，这并不影响（LP1）的可行域。解（LP11），得最优解为x1=2,x2=1,z=-1114 再解（LP12），无最优解。因此得原问题的最优解为x1=2,x2=1,z=-11。(2) 解：求相应的线性规划（LP）maxz=2x1+x2x1+x25-x1+x20 s.t6x1+2x221x1,x20得（LP）的最优解x1=2.75,x2=2.25,z=7.75首先注意其中一个非整数变量的解，如x2，在松弛问题中的解x2=2.25，于是原问题增加两个约束条件x22，x23将两个约束分别并入原问题
16、的松弛问题（LP）中，形成两个分支，即后继问题（LP1）和(LP2)，这并不影响原问题的可行域。解（LP1），得最优解为x1=17/6,x2=2,z=23/3再解（LP2），无最优解。继续对（LP1）进行分解。对（LP1）增加两个约束条件x12，x13将两个约束分别并入（LP1）中，形成两个分支，即后继问题（LP11）和(LP12)，这并不影响（LP1）的可行域。解（LP11），得最优解为x1=2,x2=2,z=6再解（LP12），得最优解为。x1=3,x2=1.5,z=7.5继续对（LP12）进行分解。对（LP12）增加两个约束条件x21，x22 将两个约束分别并入（LP12）中，形成两个分
17、支，即后继问题（LP121）和（LP122），这并不影响（LP12）的可行域。解（LP121），得最优解为x1=19/6,x2=1,z=22/7再解（LP122），无最优解。 继续对（LP121）进行分解。对（LP121）增加两个约束条件15 x13，x14将两个约束分别并入（LP121）中，形成两个分支，即后继问题（LP1211）和（LP1212）。 解（LP1211），得最优解为。x1=3,x2=1,z=7再解（LP1212），无最优解为。因此得原问题的最优解为x1=3,x2=1,z=7。16、解：通过观察的方法找一个可行解，易得(x1 , x2 , x3 , x4)=(0 ,0 ,0，1
18、)符合约束条件，计算出其目标函数值Z =4。对于极小化问题，当然希望z4，于是增加一个约束条件，后加的约束条件称为过滤条件。过滤条件为： 2x1+5x2+3x3+4x44 目标函数可以改写成：minz=5x2+4x4+3x3+2x1因为5，、4、3，2是递减的，变量(x2 ,x4 ,x3, x1 )也按下述顺序取值（0，0，0，0），（0，0，0，1），（0，0，1，0），（0，0，1，1）等.5x2+4x4+3x3+2x14 x2+x4+x3-4x104x2+4x4+2x3-2x14x2+x4-x3+x1116 2 4 31（2）maxz=2x1+x2-x3x1+3x2+x324x2+x35
19、s.tx1+2x2-x32 x+4x-x4231x1,x2,x3=0或1解：通过观察的方法找一个可行解，易得(x1 , x2 , x3)=(1 ,0 ,0)符合约束条件，计算出其目标函数值Z =2。对于极大化问题，当然希望z2，于是增加一个约束条件，后加的约束条件称为过滤条件。过滤条件为： 2x1+x2-x32 目标函数可以改写成：maxz=-x3+x2+2x1因为-1，1，2是递增的，变量(x3，x2 , x1)也按下述顺序取值（0，0，0），（0，0，1），（0，1，0），（0，1，1）等。-x3+x2+2x12 x3+3x2+x12x3+4x25-x3+2x2+x12-x3+4x2+x1
20、4改进过滤条件，用 -x3+x2+2x13 17 至此，z值已不能再改进，即得到最优解。 最优解为(x3，x2 , x1)（0，1，1）；最优值为z=3。17、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表2，问如何分配工作可使总的消耗时间为最少？表2解：首先进行行、列变换，使每一行和每一列都出现0元素。在第一列减去15，第二列减去17，第三列减去16，第四列减去17，然后再从第二行中减去1。得首先进行行、列变换，使每一行和每一列都出现0元素。如上表中第一行减去7，第二行减去5，第三行减去4，第四行减去2，然后再从第四列中减去1。得0 1 5 7 3 5 5 0 11
21、0 0 1 4 5 7 0进行试指派，寻找最优解。由有0元素最少的行开始，圈出一个0元素，用 表示，然后划去同行同列的其他0元素，这样依次进行，得1 5 7 3 5 5 11 1 4 5 7 由于独立的0元素个数少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。在没有 的行打；对打的行上的所有0元素的列打号；再对打的列上有 的行上打 号。重复以上步骤，直到得不出新的打 号的行列为止。最后对没有打号的行画横线，将打有号的列画竖线。7 3 5 5 1457 由于覆盖直线个数3少于矩阵阶数4，故进行变换，以增加0元素。在没有被直线覆盖的部分中找出最小元素3；然后对没有覆盖的行中各元素中减去这个最小元
22、素3；被直线覆盖的列中各元素都加上这个最小元素3。这样在没有覆盖的元素中又增加了0元素。 18 0 1 5 10 0 2 2 0 11 0 0 4 1 2 4 0再进行试指派，寻找最优解。1 5 10 2 2 11 4 1 2 4 由于独立的0元素个数仍然少于矩阵的阶数，因此作最少的直线覆盖所有的0元素。1 5 2 2 1 0 0 12 1再进行试指派，寻找最优解。 12 10 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1得到最优解的指派方案为：甲B，乙A，丙C，丁D；最少消耗时间为70。0 1 0 1 1 14 1 0 3 4 1 310 0 5 0 10 5 24 一、思考题
23、第二章 目标规划1，答：因为在经营管理实际中，决策者不仅要考虑资源的最佳配置和有效利用，还要考虑到市场、竞争对手、替代品的政策法律环境等多方面的影响因素和指标要求，此时线性规划模型不能完全解决问题。2，答：一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，并按多个目标的重要性，给定优先等级和权重，顺序求最小值。 按决策者的意愿，对于事先给定的目标值，分为三种情况：19 （1） 当约束要求目标不超过目标值，目标函数求正偏差变量最小。（2） 当约束要求目标不低于目标值，目标函数求负偏差变量最小。（3） 当约束要求目标等于目标值，目标函数求正负偏差变量之和最小。3，答：（一）初始基变
24、量的选择首先选择所有的负偏差变量di为初始基变量；如果负偏差变量数小于约束方程数，则增加选择不同约束条件的松弛变量；如果负偏差变量和松弛变量的总数还小于约束方程数时，则需要加入人工变量，此时引入的M将被视作最高优先级，即0级优先级： M/P1=。（二）满意解的判断当所有非基变量的检验数大于等于零时，目标规划问题获得最优解。非基变量的检验数为：sj-=aiPi+ai+1Pi+1+L+amPm，由于Pj-1Pj=，2jm，所以当非基变量检验数中的首项系数ai0时，获得满意解。（三）入基变量和出基变量的选择入基变量的选择：选择检验数首项系数为负的非基变量入基，若有多个首项系数为负，则取其中检验数首项
25、优先级最高系数最小的非基变量入基。如果首项优先级相同且系数相等，再比较第二个优先级的系数。若有两个及两个以上的非基变量检验数（的所有各项系数）都相等，这些非基变量中有决策变量时，则首先选择决策变量入基；若它们同时是决策变量或偏差变量，则可以选择其中下标最小的变量入基。出基变量的选择：与单纯形法相同。4，答：序列解法不需要使用优先级系数Pi，而是将单纯形法应用于不同目标层次的线性规划问题。单纯形法适用于能给目标确定优先级的场合，序列解法适用于目标层次不需确定优先级的场合。5，答：第一个问题：看最优解是否唯一或是否为最后一个层次。如果是，则不再继续求解，已获得满意解；如果不是，则需要继续下一层次目
26、标的求解。第二个问题：如果z*0，则在加入第二层次目标约束后从约束条件中删去第一层次目标函数含有的偏差变量；如果z*>0，则加入第二层次目标约束后，将第一层次的目标函数（令其等于z*）作为附加约束加入到第二层次约束条件中。6， 判断以下各种说法的正确性1） 正偏差变量大于等于零，负偏差变量小于等于零。答：错，都大于等于零。2） 目标约束一定是等式约束。 答：对。3） 一对正负偏差变量至少一个大于零。 答：错。4） 一对正负偏差变量至少一个等于零。 答：对。20 5） 要求至少达到目标值的目标函数是mind-。 答：对。6） 要求不超过目标值的目标函数是mind。 答：错。要求正偏差变量最
27、小。二、选择题7，答：正确的是C、E。8. 答：应该选择D。9答：应该选择A。三、计算题10， - 图1 图解法第1题（1） 解：对于P1，桔黄色内的部分满足要求，对于P2，蓝色内的部分满足要求，所以满意解是x12，x20，d11，其它偏差变量都等于零。+ 21 图2 图解法第2题（2） 解：对于P1，桔黄色内的部分满足要求，对于P2，蓝色内的部分满足要求，由图2-知P2无法满足，所以满意解在点c取到，满意解是x10，x23，d5，d12-4，d1，其它偏差变量都等于零。3+11，（1）解：初始基变量为三个负偏差变量，得到初始单纯形表如表1。表1 题2(1)的初始单纯形表非基变量x1,x2的检
28、验数分别为s1=8P1P2和s2=4P12P2，因此x1应当入基，用最小比值法确定d1应当出基。换基后，通过计算求得新的基本可行解，见表2。表2 题2(1)的第一次迭代单纯形表-22 -可得，x2入基，d2出基。换基后，通过计算求得新的基本可行解，见表3。表3 题2(1)的第二次迭代单纯形表此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x150/3，x220/3，d3=10，其它偏差变量都等于零。（3） 解：初始基变量为四个负偏差变量，得到初始单纯形表如表4。表4 题2(2)的初始单纯形表-由上表得，x1入基，d1出基。换基后，通过计算求得新的基本可行解，见表5。表5
29、题2(2)的第一次迭代单纯形表23 3+-d由上表得，1入基，d出基。换基后，通过计算求得新的基本可行解，见表6。表6 题2(2)的第二次迭代单纯形表-由上表得，x2入基，d2出基。换基后，通过计算求得新的基本可行解，见表7。表7 题2(2)的第三次迭代单纯形表 +此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x150，x210，d1=20，d4=10，其它偏差变量都等于零。- 12，1）用单纯形法求解；解：初始单纯形表如表8。24 表8 题3的初始单纯形表-由上表得，x2入基，d4出基。换基后，通过计算求得新的基本可行解，见表9。表9 题3的第一次迭代单纯形表 -+由
30、上表得，d4入基，d1出基。换基后，通过计算求得新的基本可行解，见表10。表10 题3的第二次迭代单纯形表25 +-由表10得，d1入基，d2出基。换基后，通过计算求得新的基本可行解，见表11。表11 题3的第三次迭代单纯形表+由表11得，x1入基，d4出基。换基后，通过计算求得新的基本可行解，见表12。表12题3的第四次迭代单纯形表-由表12得，d4入基，d3出基。换基后，通过计算求得新的基本可行解，见表13。表13 题3的第五次迭代单纯形表26 +此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x113/2，x25/4，d1=3，d4-=3/4，其它偏差变量都等于零。
31、由于非基变量d3的检验数为0，所以此题有多个解。由图解法容易得到在（x113/2，x25/4）和（x19，x20）两点间的连线都是满意解。2）目标函数分别变为如下两种情况，请分析解的变化 a)minz=P1d1+P2d2+P3d1+P4(5d3+3d4)b)minz=P1d1+P2d2+P3(w1d3+w2d4)+P4d1（假设w1和w2的按比例变动）。解：对于上面两种情况，在第一、第二目标相继满足的情况下（即d1d20），关+d这时P3和P4优先级的顺序不影响满意解的结果，所1于的目标实际上已经无法有效满足，-+-+-+以a）和b）的解均不变。13.解：设x1，x2分别表示每周生产A,S型号
32、的微型计算机的台数。 第一个目标要求每周总利润不低于10000元，即-minz=Pd11 300x1+450x2+d-d=10000-1+1 第二个目标要求A型机至少每周生产10台，S型机每周至少生产15台，即minz=P2(3d3-+2d2-)x1+d2-d2+=10x2+d3-d3+=15这里在第二目标中对两种产品使用了不同的权重，主要是考虑到A,S型号的微型计算机的利润不同：300/4502/3，所以A和S型号的微型计算机权重为2和3。第三个目标要求工序一每周生产时间最好等于150小时，工序二生产时间可适当超过其能力75小时，即 27 minz=P-+-32(d4+d4)+d54x+1+
33、6x-2+d4-d4=1503x+1+2x-2+d5-d5=75综合以上各指标要求，得到该问题的目标规划模型如下：minz=P-1d1+P2(3d-3+2d2)+P32(d-4+d+4)+d-5300x1+450x2+d-1-d+1=10000x+1+d-2-d2=10x-2+d3-d+3=154x-1+6x2+d4-d+4=1503x1+2x2+d-5-d+5=75x-+1，x20，dm，dm0，m1，2，3，4，5解：设xij是从第Ai产地运往Bj销地的商品数，则对a）minz=Pd-11x-+13+x23+x33+d1-d1=480minz=P-2(d-2+d-3+d4)对b） x-+1
34、1+x2+1x+31d-2d=3220*0.=852x-+ 7212+x2+2x+32d-3d=2340*0.=85204x-+14+x2+4x+34d-4d=3480*0.=85323对c）minz=P-3d5x-+33+d5-d5=200对d） minz=P4d+6x21+d-6-d+6=0minz=P5(d-7+d+7)对e） (x12+x22+x32)x13+x23+x33)-+240-(480+d7-d7=0minz=P+6d8对f） 7x11+3x12+7x13+9x14+2x21+6x22+5x23+11x24+6x31+4x32+2x-+33+5x34+d8-d8=4580 2
35、8 14. 其中4580是由线性规划得到的运费最小值。其它有关供应量和需求量的约束照样成立，得到该问题的目标规划模型如下：-+-+minz=Pd11+P2(d2+d3+d4)+P3d5+P4d6+P5(d7+d7)+P6d8x13+x23+x33+d1-d1+=480x11+x21+x31+d2-d2+=272x12+x22+x32+d3-d3+=204x14+x24+x34+d4-d4+=323x33+d5-d5+=200x21+d6-d6+=0(x12+x22+x32)2404807x11+3x12+7x13+9x14+2x21+6x22+5x23+11x24+6x31+4x32+2x33
36、+5x34+d8-d8+=4580-(x13+x23+x33)+d7-d7+=0 x1x15601x12x134产量约束：x2x24001x22x234x3x37501x32x334+xij0，d-，0，i,j1，23，4 m1，2.，8mdm 15, 解：设xij表示i商标（红、黄、蓝）中j等级的数量（i，j1，2，3），ym表示m商标每天的产量（m1，2，3），则minz=P1(d1+d2-+d3+d4-+d5+d6-)x13-0.1y1+d1-d1+=0x11-0.5y1+d2-d2+=0对于1） x23-0.7y2+d3-d3=0-+ x21-0.2y2+d4-d4+=0x33-0.5
37、y3+d5-d5+=0x31-0.1y3+d6-d6+=0minz=P2d7-对于2） 5.5y1+5.0y2+4.8y3-6(x11+x21+x31) -4.5(x12+x22+x32)-3(x13+x23+x33)+d7-d7+=2500其中2500是由线性规划得到的利润最大值。对于3）minz=P3d8-y1+d-d=2000-8+8 29 x11+x2+1x311500x12+x2+2x322000其它约束：x13+x2+3x331000x11+x1+2x=13y1x21+x2+2x=23y2x31+x3+2x=33y3综合以上各指标要求，得到该问题的目标规划模型如下：minz=P1(
38、d+1+d-+2+d3+d-4+d+-5+d6)+P2d-7+P3d-8x13-0.1y-1+d1-d+1=0x+11-0.5y1+d-2-d2=0x-23-0.7y2+d3-d+3=0x21-0.2y2+d-4-d+4=0x+33-0.5y3+d-5-d5=0x-31-0.1y3+d6-d+6=05.5y1+5.0y2+4.8y3-6(x11+x21+x31)-4.5(x12+x22+x32)-3(x13+x23+x33)+d-7-d+7=2500y1+d-8-d+8=2000x11+x21+x311500x12+x22+x322000x13+x23+x331000x11+x12+x13=y
39、1x21+x22+x23=y2x31+x32+x33=y3xij0,i,j=1,2,3 ym0,m=1,2,3d-+n,dn0,n=1,2.,8 30 第三章 动态规划1.计算图中所示的从A到E的最短路线及其长度。最短路线长度为8。 AB2C1D1E2.解：A.按动态规划要求确定以下参数：（1）将卸货问题按零售店分为四个阶段，顺序1、2、3、4。（2）各阶段的状态参数Sk表示为分配给第k至第4个零售店的总货物箱数。 （3）uk是分配给第k个店的货物箱数。 （4）状态转移方程Sk+1=Sk-uk(Sk)。 （5）最优指标函数fk(Sk)=maxdukk(Sk,uk)+fk+1(Sk+1)f4(S
40、k)=0 B.分阶段计算当k=4,S4=(0,1,2,3,4,5,6)S40 1 2 3 4 5u40 1 2 3 4 5d4(S4,u4)0 4 5 6 6 6f4(S4)0 4 5 6 6 6*u4(S4)0 1 2 3 4 531 6 6 6 6 6当k=3,S3=(0,1,2,3,4,5,6)S30 1u30 0 1 0d3(S3,u3)0 0 8 0 8 5 0 8 5 7 0 8 5 7 8 0 8 5 7 8 8 0 8 5f4(S3-u3)0 4 0 5 4 0 6 5 4 0 6 6 5 4 0 6 6 6 5 4 0 6 6 6d3+f40 4 8 5 12 5 6 13 9 7 6 14 10 11 8 6 14 11 12 12 8 6 14 11*u3(
