北外奥鹏作业运筹学

1、运筹学作业精讲运筹学作业精讲第一单元某企业生产甲、乙两种产品，其单位利润分别为20元和30元。每生产一件甲产品需劳动力3个，原材料2千克，设备4小时；每生产一件乙产品需劳动力7个，原材料4千克，设备3小时。企业现有劳动力240个，原材料150千克，设备可用时间为250小时。问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成标准形式；用图解法进行求解。标准形式；用图解法进行求解。解：设解：设 x x1 1和和x x2 2分别表示产品甲和乙的产量，分别表示产品甲和乙的产量，这样可以建立如下的数学模型。这样可以建立如下

2、的数学模型。目标函数：目标函数：Max20Max20 x x1 1 +30 +30 x x2 2约束条件：约束条件：s.t.3 s.t.3 x x1 1 +7 +7 x x2 2 240 240（劳动力限制）（劳动力限制） 2 2 x x1 1 + 4 + 4 x x2 2 150 150（原材料限制）（原材料限制） 4 4 x x1 1 + 3 + 3 x x2 2 250 250（设备限制）（设备限制） x x1 1，x x2 2 0 0（非负约束）（非负约束）化为标准型：化为标准型：目标函数：目标函数：Max20Max20 x x1 1 +30 +30 x x2 2约束条件：约束条件：s

3、.t.3 s.t.3 x x1 1 + 7 + 7 x x2 2 + +x x3 3= 240= 240 2 2 x x1 1 + 4 + 4x x2 2+x x4 4=150=150 4 4 x x1 1 + 3 + 3 x x2 2 + +x x5 5= 250= 250 x x1 1，x x2 2，x x3 3，x x4 4，x x5 5 0 0阴影部分为可行域，阴影部分为可行域，虚线为目标函数线。虚线为目标函数线。由图可知最优解为由图可知最优解为约束约束2 2和约束和约束3 3的的交点，解得坐标为交点，解得坐标为（55,1055,10），故最），故最优生产计划为生产优生产计划为生产甲产

4、品甲产品5555件，乙件，乙产品产品1010件，最大件，最大利润为利润为202055+3055+301010 =1400 =1400元。元。第二单元某厂生产三种型号的铝锅，已知单耗数据如下。试制定最优生产计划使总收入最大。 解：设解：设 x x1 1、x x2 2、x x3 3分别表示大号、中号、小号铝锅的产量，分别表示大号、中号、小号铝锅的产量， 这样可以建立如下的数学模型。这样可以建立如下的数学模型。目标函数：目标函数：Max50Max50 x x1 1 +40 +40 x x2 2+30 +30 x x3 3约束条件：约束条件：s.t.6s.t.6x x1 1 +2 +2 x x2 2+

5、 4 + 4 x x3 3 400 400（铝板限制）（铝板限制） 4 4x x1 1 +8 +8 x x2 2+ 6 + 6 x x3 3 360 360（劳力限制）（劳力限制） 8 8x x1 1 +4 +4 x x2 2+10 +10 x x3 3 420 420 （机器限制）（机器限制） x x1 1，x x2 2，x x3 3 0 0（非负约束）（非负约束） 化为标准型：化为标准型：目标函数：目标函数：Max50Max50 x x1 1 +40 +40 x x2 2+30 +30 x x3 3约束条件：约束条件：s.t.6s.t.6x x1 1 + 2+ 2x x2 2+4 +4 x

6、 x3 3 + + x x4 4= 400= 400 4 4x x1 1 +8 +8 x x2 2+6 +6 x x3 3 + + x x5 5 =360 =360 8 8x x1 1 +4 +4 x x2 2+ 10 + 10 x x3 3 + + x x6 6= 420= 420 x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6 0 0 使用单纯形法求解：使用单纯形法求解：得到最优解（得到最优解（40,25,0,110,0,040,25,0,110,0,0），最优值），最优值30003000。即应该生产大号铝锅。即应该生产大号铝锅4040个，中号铝锅个，中

7、号铝锅2525个单位，小号铝锅产量为个单位，小号铝锅产量为0 0（不生产），最（不生产），最大利润为大利润为30003000元。元。 . 第三单元线性规划Maxz=5x1+5x2+13x3s.t.x1+x2+3x32012x1+4x2+10 x390 x1,x2,x30的最优表为：分析在下列条件下，最优解分别有什么变化（1）b2由90变为70。（2）c1由-5变为-10。（3）增加一个约束条件 4 x1 + 3 x2 + 6 x3 50。 解：解：（1 1）由最优基不变的条件）由最优基不变的条件 Max - Max -bibi/ /iriririr0D0DbrbrMin-Min-bibi/ /

8、iriririr00 得得-10 = -10/1D-10 = -10/1Db b2 2 b b2 2由由9090变为变为7070，超出了允许变化范围，继续计算，超出了允许变化范围，继续计算或者由或者由B B-1-1( (b b +D +Db b)=(20,-10)=(20,-10)T T可以知道最优基发生变化，继可以知道最优基发生变化，继续迭代。续迭代。最优解变为最优解变为x x1 1 =0 =0，x x2 2 = 5 = 5，x x3 3 = 5 = 5，x x4 4 = 0 = 0，x x5 5 = 0 = 0，最优值，最优值 z z* * = 90 = 90。2 2）c c1 1是非基变

9、量的系数，最优解不变的条件是：是非基变量的系数，最优解不变的条件是：D Dc c1 1 - - s s1 1， c c1 1由由-5-10-5-10，D Dc c1 1 = -5 0 = - = -5 0 = - s s1 1，不影响最优，不影响最优解。解。 （3 3）增加一个约束条件）增加一个约束条件4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 50 50，原最优解不满足这个约束。，原最优解不满足这个约束。引入松弛变量，得到引入松弛变量，得到4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 + + x x6 6 = 50 =

10、 50填入最优单纯形表，进一步求解，得到最优解为填入最优单纯形表，进一步求解，得到最优解为X=(0X=(0，1010，10/3)T10/3)T，最优值，最优值为为280/3280/3。 第四单元对于以下的运输问题，若各个销地少得到对于以下的运输问题，若各个销地少得到1 1个单位的产品，将要求得到赔偿，个单位的产品，将要求得到赔偿，金额分别为金额分别为9 9、1212、6 6、1212，问如何组织运输，才能使总费用最低。（建立运，问如何组织运输，才能使总费用最低。（建立运输模型，用最小元素法求初始解，并求出最优解）输模型，用最小元素法求初始解，并求出最优解）解：总产量为解：总产量为99+55+1

11、10=26499+55+110=264，总销量，总销量44+88+88+77=29744+88+88+77=297，产，产销不平衡且供不应求，增加一个虚拟产地销不平衡且供不应求，增加一个虚拟产地A4A4，其产量为，其产量为297-297-264=33264=33。由虚拟产地运往销地的费用即为赔偿金额。因此可以。由虚拟产地运往销地的费用即为赔偿金额。因此可以建立运输模型如下：建立运输模型如下：使用最小元素法求初始解：使用最小元素法求初始解：说明：每次选择最小元素，因此依次选择说明：每次选择最小元素，因此依次选择3 3（x x3333）、）、6 6（x x2222）、）、9 9（x x4141）、

12、）、1212（x x1111）、）、1515（x x1414）、）、2121（x x3232）、）、3333（x x1212）。）。）得到初始解得到初始解x x1111=11=11，x x1212=11=11，x x1414=77=77，x x2222=55=55，x x3232=22=22，x x3333=88=88，x x4141=33=33，其余运量为，其余运量为0 0，总运费为，总运费为30033003。 使用位势法计算各非基变量检验数，填入括号中：使用位势法计算各非基变量检验数，填入括号中： 令令u u1 1=0=0，由基变量满足，由基变量满足u ui i+ +v vj j= =c

13、cij ij，依次得到各位势，依次得到各位势v v1 1=12=12，v v2 2=33=33，v v4 4=15=15，u u4 4=-3=-3，u u2 2=-27=-27，u u3 3=-12=-12，v v3 3=15=15，再根据公式，再根据公式s sij ij = = c cij ij - - u ui i - - v vj j计算各非基变量检验数。计算各非基变量检验数。进行调整：选负检验数中最小的进行调整：选负检验数中最小的s s4242，那么，那么x x4242为主元，作为进基为主元，作为进基变量。以变量。以x x4242为起点找一条闭回路为起点找一条闭回路x x4242、x

14、x4141、x x1111、x x1212，取偶数标，取偶数标号格的最小运量号格的最小运量1111作为调整量，调整后运量为作为调整量，调整后运量为x x4242=11=11，x x4141=22=22，x x1111=22=22，x x1212=0=0（调整为非基变量），得到新的基本解，并重新（调整为非基变量），得到新的基本解，并重新用位势法计算检验数（令用位势法计算检验数（令v v2 2=0=0），如下表所示。），如下表所示。 所有非基变量检验数均非负，得到最优解为所有非基变量检验数均非负，得到最优解为x x1111=22=22，x x1414=77=77，x x2222=55=55，x x

15、3232=22=22，x x3333=88=88， x x4141=22=22，x x4242=11=11，其余运量为，其余运量为0 0，最，最小的总运费为小的总运费为28052805。 第五单元有一个工厂要确定明年各季度的生产计划，通过订货了解到各季度对产品的需求量dk分别为4000件、3000件、4000件和4000件。又知，工厂生产该产品的季度固定成本为10万元（但如果在某季度中，该种产品1件也不生产，则不需支付固定成本费），单位产品的可变成本为50元，由于设备的能力所限，每季度最多只能生产5000件。若产品销售不出，则每件每季度的存贮费为8元。假设本年底无存货转入下年，明年末也不需要留

16、有存货，问每季度的生产计划应如何安排（假设生产产量以千件为单位），才能使生产的总费用最省？解：首先建立动态规划模型解：首先建立动态规划模型（1 1）阶段）阶段k k：每个季度作为一个阶段，：每个季度作为一个阶段，k k=1,2,3,4=1,2,3,4（2 2）状态变量）状态变量s sk k：第：第k k个季度初的库存量（千件）个季度初的库存量（千件）（3 3）决策变量）决策变量u uk k：第：第k k个季度的生产量（千件）个季度的生产量（千件）（4 4）状态转移方程：）状态转移方程： s sk k+1+1= = s sk k+ + u uk k - - d dk k ( (需求，千件需求，千

17、件) )（即季（即季度末库存量度末库存量= =季度初库存量季度初库存量+ +季度生产量季度生产量 - - 季度销售量或需季度销售量或需求量）求量）（5 5）阶段指标：）阶段指标： g gk k ( (s sk k, , u uk k) =) =生产成本生产成本C(C(u uk k) + ) + 库存成本库存成本E(E(s sk k) )（6 6）最优指标函数）最优指标函数f fk k ( (s sk k) )：第：第k k个季度的状态为个季度的状态为s sk k时从该季时从该季度至计划结束的最低总费用（万元）度至计划结束的最低总费用（万元）（7 7）递推方程：）递推方程： f fk k ( (

18、s sk k)=min)=ming gk k ( (s sk k, , u uk k)+ )+ f fk k+1+1( (s sk k+1+1) )（8 8）终端条件：）终端条件：f f5 5( (s s5 5)=0)=0下面进行求解，采用逆序解法。下面进行求解，采用逆序解法。（1 1）k k=5=5，f f5 5( (s s5 5)=0 )=0 （2 2）k k=4=4，00s s4 444，u u4 4=4-=4-s s4 4，s s5 5= =s s4 4+ +u u4 4- -d d4 4（说明：第（说明：第4 4季度的需求为季度的需求为4 4千件，因此库存量不应超过千件，因此库存量不

19、应超过4 4且显然非负，且显然非负，所以有所以有00s s4 444；年底不需要有库存，所以生产量；年底不需要有库存，所以生产量u u4 4 = 4 - = 4 - s s4 4）（3 3）k k=3=3，00s s3 35+5-4-3=35+5-4-3=3，s s4 4= =s s3 3+ +u u3 3- -d d3 3= =s s3 3+ +u u3 3-4-4，Max(0, 4-Max(0, 4-s s3 3)u u3 3Min(5, 8-Min(5, 8-s s3 3) )（说明：前两季度总产量为（说明：前两季度总产量为5+5=105+5=10千件，需求量为千件，需求量为3+4=73

20、+4=7千件，所以第千件，所以第3 3季度初最大库存量季度初最大库存量=10-7=3=10-7=3千件；千件；在产量需求方面，为了满足需求，至少生产在产量需求方面，为了满足需求，至少生产d d3 3- -u u3 3=4 -=4 - u u3 3，且最大产量为且最大产量为5 5千件，后两个季度总需求为千件，后两个季度总需求为4+4=84+4=8千件，千件，产量不应该超过产量不应该超过8-8-s s3 3。因此有。因此有00s s3 333，Max(0, 4 - Max(0, 4 - s s3 3)u u3 3Min(5, 8-Min(5, 8-s s3 3) )）（4 4）k k=2=2，00

21、s s2 25-4=15-4=1，s s3 3= =s s2 2+ +u u2 2- -d d2 2= =s s2 2+ +u u2 2-3-3，Max(0, 3-Max(0, 3-s s2 2)u u2 2Min(5, Min(5, 11-11-s s2 2)（5 5）k k=1=1，s s1 1=0=0，s s2 2= =s s1 1+ +u u1 1- -d d1 1= =u u1 1-4-4，44u u1 155最优解为最优解为s s1 1=0, =0, u u1 1* *=5, =5, s s2 2=1, =1, u u2 2* *=5, s=5, s3 3=3, =3, u u3

22、3* *=5, =5, s s4 4=4=4，u u4 4* *=0=0即前即前3 3个季度均生产个季度均生产50005000件，第件，第4 4个季度不生产，最低总个季度不生产，最低总费用为费用为111.4111.4万元。万元。 第六单元某企业生产甲、乙两种产品。生产一件甲产品需要使用劳动力4小时，能源2个单位，销售利润为16万元；生产一件乙产品需要使用劳动力2小时，能源4个单位，销售利润为20万元。企业目前拥有劳动力可用时间22小时，能源20个单位。在制定生产计划时，决策者考虑下述4项目标：首先，乙产品的产量不低于甲产品的产量；其次加班费用比较高，尽量不要加班；第三，尽可能充分利用能源，但是

23、又不希望再购买；最后，利润尽量不少于112万元。求决策方案。（建立目标规划模型并用单纯形法求解）解：设 x1、x2分别表示甲产品和乙产品的产，以建立如下的目标规划模型：目标函数：Minf = P1 d1+ + P2 d2+ + P3(d3- + d3+) + P4 d4-约束条件： x1 x2 + d1- - d1+ = 0 4 x1 + 2x2 +d2- d2+ = 22 2 x1 + 4x2 +d3- d3+ = 20 16x1 + 20 x2 + d4-d4+ =112 x1，x2，di-， di+ 0，i = 1, 2, 3, 4（说明：目标1和2是不超过目标值，因此正偏差变量尽量小；

24、目标3是恰好达到目标值，因此要求正、负偏差变量都尽量小；目标4要求不少于目标值，因此是负偏差变量尽量小） 下面用单纯形法进行求解。列出单纯形表，取d1-、d2-、d3-、d4-为初始基变量。把最小化问题转为为最大化问题，所以目标函数系数均乘以-1；基变量的检验数应该为0，处理初始基本可行解对应的各级检验数。由于P1、P2优先级对应目标函数中不含di-，其检验数只需取系数负值，分别为(0，0，0，-1，0，0，0，0，0，0；0)和(0，0，0，0，0，-1，0，0，0，0；0)。 P3优先级对应的目标函数中含d3-，所以其检验数需要把第3个约束行加到取负值的这一行上，得到(2，4，0，0，0，

25、0，0，-2，0，0；20 )。P4优先级对应的目标函数中含d4-，所以其检验数需要把第4个约束行加到取负值的这一行上，得到(16，20，0，0，0，0，0，0，0，-1；112 )。列目标规划的初始单纯形表如下：下面进行计算。（1）k = 1，在初始单纯形表中基变量为（d1-，d2-，d3-，d4-) =（0，22，20，112)； （2）因为P1与P2优先级的检验数均已经为非正，所以这个单纯形表对P1与P2优先级是最优单纯形表；（3）下面考虑P3优先级，第二列的检验数为4最大，此为进基变量，计算相应的比值 bi/aij 写在q列。通过比较，得到d3-对应的比值最小，于是取a32（标*号）为

26、转轴元进行矩阵行变换得到新的单纯形表如下。 （4）下面考虑P4优先级，第一列的检验数为6最大，此为进基变量，计算相应的比值 bi/aij 写在q列。通过比较，得到d4-对应的比值最小，于是取a41（标*号）为转轴元进行矩阵行变换得到新的单纯形表如下。 5 5）当前的单纯形表各优先级的检验数均满足了最优条件，故为当前的单纯形表各优先级的检验数均满足了最优条件，故为最优单纯形表。于是得到最优解最优单纯形表。于是得到最优解x x1 1=2=2，x x2 2=4=4。 第七单元下图为一个交通运输网络图，道路（即弧）旁的权数表示该道路的容量和目前的运输量(cij, fij)，求出该交通运输网络的最大运输

27、能力（即网络最大流）。解：解：第一次标号。第一次标号。（1 1）首先给）首先给v vs s标号标号(0, +)(0, +)； （2 2）看）看v vs s：在弧：在弧( (v vs s, , v v2 2) )上，上，f fs s2 2= =c cs s2 2=2=2，不具备标号条件。在弧，不具备标号条件。在弧( (v vs s, , v v1 1) )上，上，f fs s1 1=5=5c cs s1 1=8=8，故给，故给v v1 1标号标号( (v vs s, , l l( (v v1 1) )，其中，其中l l( (v v1 1) = min) = minl l( (v vs s), (

28、), (c cs s1 1- -f fs s1 1) = ) = min+, 8-5 = 3min+, 8-5 = 3。 （3 3）看）看v v1 1：在弧：在弧( (v v1 1, , v v2 2) )上，上，f f1212 =5 =5c c1212=6=6，给，给v v2 2标号标号( (v v1 1, , l l( (v v2 2) )，其中，其中l l( (v v2 2) ) = min= minl l( (v v1 1), (), (c c1212- -f f1212) = min3, 6-5 = 1) = min3, 6-5 = 1；在弧；在弧( (v v1 1, , v v3

29、3) )上，上，f f1313 =2 =20=20，故给，故给v v4 4标号标号(- (-v v1 1, , l l( (v v4 4) )，其中，其中l l( (v v4 4) = ) = minminl l( (v v1 1),),f f4141 = min3, 2 = 2 = min3, 2 = 2。 （4 4）看）看v v3 3：在弧：在弧( (v v3 3, , v vt t) )上，上，f f3t3t =5 =5c c3t3t=9=9，给，给v vt t标号标号( (v v3 3, , l l( (v vt t) )，其中，其中l l( (v vt t) ) = min= minl l( (v v3 3), (), (c c3t3t- -f f3t3t) = min3, 9-5 = 3) = min3, 9-5 = 3。因为。因为v vt t被标上号，根据标号法，被标上号，根据标号法，转入调整过程