《运筹学习题.doc》由会员分享，可在线阅读，更多相关《运筹学习题.doc（32页珍藏版）》请在金锄头文库上搜索。
1、习题课1(1) 假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x16x23x32x4(2) 将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 +
2、1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-1.8x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2
3、 ,x3 ,x4 ,x5 0(3)用图解法求解下列线性规划问题本例中目标函数与凸多边形的切点是B(2,5)，则X*=(2,5)为最优解，maxZ=20(4) 找出下列线性规划问题的全部基解，基可行解，并找出最优解基本解：X1=(0,1,4,12,18) X2=(4,0,0,12,6) X3=(6,0,-2,12,0) X4 =(4,3,0,6,0) X5=(0,6,4,0,6) X6=(2,6,2,0,0) X7=(4,6,0,0,-6) X8=(0,9,4,-6,0)其中基本可行解为： X1， X2， X4， X5 ，X6最优解为X*X6 =(2,6,2,0,0) Z*=36习题课2(1)
4、用单纯形表求解LP问题Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余） 最优值 z* = 70000 (2) 用单纯形法解线性规划问题 (唯一解)解：化为标准型列出单纯形表Cj21000CBXBbx1x2x3x4x5000x3x4x51524506152110001000145-Z021000020x3x1x5154101051/3
5、2/310001/6-1/60013123/2-Z-801/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2, X*=(7/2,3/2, 15/2,0,0)习题课3(1) 用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表Cj30100M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201131-111000-10010001-Z10M-2M-34M10-M0000-Mx4x2x73163-260102-141001-13-11-3001
6、-Z6M6M-304M+103M-4M000-3x4x2x103100101001/32/3100-1/201/2-1/20-1/21/21/31/6-Z300303/2-M-3/2-M+1/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/41/21/4-3/4-1/21/41/4-Z-3/2-9/2000-3/4-M+3/4-M-1/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0) Z*=3/2注意：(1)在LP问题的最优解中，人工变量都处在非基变量位置(即取0值)，则原问题有最优解，且去掉人工变量后的解为原问题的最优解。(2)若
7、在最优解中，包含有非零的人工变量，则原问题无可行解。(3)若最优解的基变量中，包含人工变量，但该人工变量的取值为0，这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解。(2) 用单纯形法求解线性规划问题解 化为标准形式有列表计算Cj3200MCBXBbx1x2x3x4x50Mx3x52122314100-10123-Z-12M3M+34M+20-M0-2Mx2x5242-5101-40-101-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4) Z*=4M-4 说明原问题无解(3) 用两阶段法求解例1加入人工变量则为解：第一阶段列单纯形表Cj0000011
8、CBXBbx1x2x3x4x5x6x7011x4x6x74191-201131-111000-10010001-Z-102-400100001x4x2x73163-260102-141001-13-11-3001-Z-6-60-40-340000x4x2x103100101001/32/3100-1/201/21/20-1/21/21/31/6-Z00000011所有的j0(求极小值)，且人工变量已从基变量中换出，因此第一阶段的最优解为X*=(1,3,0,0,0,0,0),将最优表中的人工变量去掉，即可作为第二阶段的初始单纯形表。X0=(1,3,0,0,0),为第2阶段的初始基可行解。第二阶段
9、：将表中的人工变量x6,x7除去，目标函数改为Max z=-3x1+0x2+x3+0x4+0x5 再从第一阶段所得最优表出发，继续用单纯形法计算。Cj30100CBXBbx1x2x3x4x5003x4x2x103100101001/32/3100-1/201/2-Z300303/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/4-Z-3/2-9/2000-3/4X*=(0，5/2，3/2，0，0),Z*=3/2习题课4(1) 人力资源分配的问题 某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：班次i时间至少所需人数xi16:00-10:0
10、060x1210:00-14:0070x2314:00-18:0060x3418:00-22:0050x4522:00-2:0030x562:00-6:0030x6xi： 实际安排司乘人员数 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时问该公交线路怎样安排司机和乘务人员，既能足工作需要，又配备最少司机和乘务员？ 解：设xi表示第i班次时开始上班的司机和乘务人员数，这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数，例如有x1 +x270。又要求这六个班次时开始上班的所有人员最少，既要求x1 +x2 +x3+x4 +x5 +x6最小，这样建立如下的数学模型：目标函数：min z = (x1 +x2 +x3+x4 +x5 +x6)约束条件：(2) 将以下线性规划问题转化
