运筹学作业题参考答案.doc

运筹学第五章作业题参考答案51 解：设在A处建幢住宅. 则数学模型为Max z = 5.2 解：设每种毛坯截取根则数学模型为Max z = 5.4 解：设X =数学模型为：Max Z =( 1.92X+1.92X+1.78X)/5 5.6 用割平面法解下列整数规划 （1） Max Z = X + X s.t 解：将其化为标准型为 Max Z = X + X s.t 基XXXXbX21106X450120-Z1100X11/21/203X03-218-Z01/2-1/20X105/6-1/65/3X01-2/31/38/3-Z00-1/6-1/6从表中第二行产生割平面的约束条件： -1/3 X - 1/3 X引入松弛变量X为： -1/3 X 1/3 X + X=-2/3基XXXXXbX105/6-1/605/3X01-2/31/308/3X00-1/3-1/31-2/3-Z00-1/6-1/60X100-15/20X0101-24X0011-32-Z0000-1/2X101 0-1/22X01-1012X0011-32-Z0000-1/2X=(0, 4) 或 ( 2, 2)， Z=4(2) MinZ=5+X解: 化为标准型为 max z=-5-X C-5-1000C 基bXXXXX0X-9-3-11000X-5-1-10100X-8-1-8001 C-Z-5-1000-1X9 31-1000X420-1100X64230-801 C-Z-20-100因此，原问题的最优解为X=( 0, 9 ) ，最优值Z = 95.7用分支定界法解下列整数规划（1） Max Z=2X+X 解：用图解法求得该整数规划的松弛问题的最优解为 X=X=21/8 选择X=21/8进行分支B1: B2:Max Z =2X+X Max Z =2X+X 最优解为X=2 X=3 Z=7； 最优解X=3 X= 3/2 Z=15/2 7选择X= 3/2进行分支B3 B4 Max Z =2X+X Max Z =2X+X 最优解为X=19/6 X=1 Z=22/3 7； 无可行解选择X=19/6 进行分支B5 B6Max Z =2X+X 最优解为X=3 X=1 Z= 7； B6无可行解综上：原整数规划最优解为 X= ( 2 , 3)或 ( 3 , 1) Z=75.8 解下列01型 整数规划：(2) Max Z =2X+X- X 解：（X1，X2, X3 ）Z值约束条件a b c d过滤条件（0， 0 ， 0 ）0 Z0（0， 0 ， 1 ）-1（0， 1 ， 0 ）1（0， 1 ， 1 ）0（1， 0 ， 0 ）2 Z2（1， 0 ， 1 ）1（1， 1 ， 0 ）3（1， 1 ， 1 ）2最优解为X=(1 , 0 , 0 ) Z= 25.11（1） 解：引入一个虚拟人A,使之成为标准的指派问题，则系数矩阵为 C = 将各行元素减去本行的最小元素得C = C由于只有4个独立零元素，小于系数矩阵阶数n=5，所以将第二行，第三行，第四行都减去1，第一列和第五列加上1得C= CC中有5个独立零元素，则可确定指派问题的最优指派方案。 最优解为X= Z= 22 (2) 解：增加虚拟事件B，B,使之成为标准的指派问题，则系数矩阵为C = 将各列元素减去本列的最小元素得C = CC中有6个独立零元素，则可确定指派问题的最优指派方案，最优解为X = Z= 85.12解：原指派问题的系数矩阵为 C = 由于原问题为最大化指派问题，所以转化为最小化指派问题得 1.4EC = = B将B的各行（列）元素减去本行（列）的最小元素得B = B由于B中只有4个独立零元素，小于系数矩阵阶数n=5，所以将第一行，第四行，第五行都减去0.1，第一列，第五列加上0.1得B=DD中有5个独立零元素，则可确定指派问题的最优指派方案.最优解为 X = 即最优指派方案为A去做B工作，A去做B， A去做B，A去做B，A去做B，最大评分为Z= 1.3 + 0.9 + 1.3 + 1.2 + 1.2 + 1.4 =6.1运筹学第七章作业题参考答案7.2 解：虚拟一个港口G为目的港口 K = 5 . = 0 = 0 =0 X= G K = 4 . = min=min=20 X=F = min=min=30 X=F K=3 . = min=min=70 X=D = min=min=60 X=D = min=min=45 X=DK=2 = min=min=90 X=C=C = min=min=75 X=CK=1 = min=min=120 X=B 最短路线为A B C D F，最短为 1207.4 解：将投资A,B,C 三个项目分为三个阶段 K = 1 , 2 , 3 S表示第K阶段初可供支配的投资额 X表示第K阶段的投资额，则状态转移方程为 S = S- X递推方程为 K=3 0 S 4. =0 X= 0 =64 X=1 =68 X=2 =78 X=3=76 X=4 K=2 0 S 4. =0 X=0 =max=64 X=0=max=106 X=1=max=114 X=2=max=124 X=3 K=1 S=4=max=155 X=1最优解为X= , 最大收益为155万元.7.5解；由题意得对A A A的选择可以分为3个阶段，K=1, 2, 3S表示第K 阶段初可供支配的资金额 S=8 ， 5S7 ， 2 S 4X表示第K阶段的投资额 这状态转移方程为X= S- X 递推方程为 K=3时=0.1 X=2 = 0.2 X=3=0.7 X= 4 K=2时=0.2*0.1=0.02 X=3=0.2*0.2=0.04 X=3 = max=0.14 X=3 K=1时= max=0.042 X=1最优解为X= ,即A A A分别备用一 、三、 四件， 设备的可靠性最高 为0.042 。7.6 解: S表示第K阶段可投入的高负荷下生产，低负荷生产机器的数量，X表示第K阶段可投入高负荷下生产的机器数量，则 S-X表示在低负荷下生产的机器数量。 则状态转移方程为递推方程为K=5时 0 K=4 0 K=3 0 K=2时0 K=1 时0 综上可得S=0.9 S= 0.81 810 S= 0.567 567 S= 0.3969 3