运筹学试卷A

1石家庄经济学院华信学院2011/2012学年第1学期课程名称：运筹学共8页试卷类型：A考试形式：闭卷一二三四五六七八总分得分阅卷人一、（本题10分）建立线性规划数学模型设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们的砖供应3个工地。其需要量分别为17万块、18万块、和15万块。而自各产地到各工地的运价列表如下：工地砖厂B1B2B3A1506070A260110160-----------------------------------------------装-------------------------------------------订----------------------------------线------------------------------------系专业年级班级学号顺序号姓名-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线-----------------------（密封线内不要答题）索2二、（本题10分）已知线性规划问题12312312313123max321142321,,0zxxxxxxxxxxxxxx写出该问题的大M法数学模型。23三、（本题15分）设线性规划问题为max,,zxxxxxxxxxjj2762401312312123其最优单纯形表为cj2-7100CBXBx1x2x3x4x5B-1b2x11111060x50311110czjj0-9-1-20在下述情况下，进行灵敏度分析并求出最优解。（1）目标函数变为maxzxxx23123；（2）约束条件右端项由(6,4)T变为(3,5)T；-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线--------------------------（密封线内不要答题）索4四、（本题15分）某全整数规划问题的松弛问题的最优单纯性表为XBbX1X2X3X4X5X2X1X523/240101001/2－1/81－1/23/8－2001检验数00－1/4－1/40（1）若用分枝定界法求其整数解，写出在下一步分支问题中要增加的约束条件；（2）用语言描述分枝定界法的求解步骤。5五、（本题10分）某电视机厂生产46厘米和51厘米两种电视机，平均生产能力1台/小时，正常每日两班，每周80小时。下周的最大销售量是46厘米70台，51厘米35台。试建立目标规划模型。经理对重要程度确定以下目标：P1:避免开工不足，保持职工就业稳定；P2:尽量少加班，每周加班不超过10小时；P3:尽量保持预计的销售量。-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线--------------------------（密封线内不要答题）索6六、（本题15分）某种机床，可以在高低不同的负荷下生产，在高负荷下生产时，产品的年产量与年初投入机床数量u1的关系为8u1，年终机床完好台数为0.7u1。在低负荷下生产时，产品的年产量和投入机床数量u2的关系为5u2，年终机床完好台数将为0.9u2。假设某厂开始有1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。7七、（本题10分）有600万元投资5个项目，收益如表，求利润最大的方案？项目投资额项目收益约束条件1210160项目1、2、3中选1项项目3、4中选1项选项目5必先选项目123002103150604130805260180-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线--------------------------（密封线内不要答题）索8八、（15分）工序工时（d）紧前工序工序工时（d）紧前工序ABCDE151010105－－－AA，BFGHI5201015B，CD，EFG，H（1）绘制网络图；并给事项编号；指出关键工序。（2）计算F工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差、单时差。9课程名称运筹学试卷适用班级经管类专业命题负责人田亚明授课教师冯兰刚、武建章、王哲、毕胜男、索贵彬命题日期2011年10月20日教研室主任签字二级学院院长签字10石家庄经济学院华信学院2011/2012学年第一学期《运筹学》试题A卷参考答案及评分标准一、(10分)建立线性规划数学模型解：设xij表示由砖厂Ai运往工地Bj的砖的数量（i=1,2;j=1,2,3)Minz=50x11+60x12+70x13+60x21+110x22+160x23s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15x11、x12、x13、x21、x22、x230二、（10分）三、（15分）（1）X2的价值系数由-7变为3。01310232r最优解发生变化，继续迭代。231001x2x3x4x5xibikiab/21x05x1111003111610610/3jr01-1-2021x32x102/32/3-1/3011/31/31/38/310/30,,123241123max71731653214321763211xxxxxxxxxxxxxxMxMxxxxz11jr00-4/3-7/3-1/346/3此时最优解为346)310,38(),(*21*ZxxXTT（2）11011B0835311011'bBb此时不影响解的最优性，只改变解的值及目标函数值6*)8,3(),(*51ZxxXTT四、（15分）解：1、对X1进行分支，增加的约束条件为X1≤1；X1≥2；2、分支定界法步骤：(1)首先不考虑整数条件，求解整数规划相应的线性规划问题。(2)定界过程。(3)剪枝过程。在下述情况下剪除这些分枝：①若某一子问题相应的线性规划问题无可行解；②在分枝过程中，求解某一线性规划所得到的目标函数值Z不优于现有下界。(4)分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。选取一个不符合整数条件的变量Xi作为分枝变量，若Xi的值是b，构造两个新的约束条件：Xi≤[b]和Xi≥[b]+1，分别并入相应的数学模型中，构成两个子问题。对任一个子问题，转步骤(1)。12五、（10分）六、（15分）解：建立动态规划模型1.划分阶段：设阶段变量k表示年度，因此，阶段总数n=5。2.状态变量：用Sk表示第k年度初拥有的完好机床台数。3.决策变量：用Uk表示第k年度中分配于高负荷下生产的机床台数。于是Sk-Uk便为该年度中分配于低负荷下生产的机床台数。4.状态转移方程：5.动态规划的基本方程及边界条件：6.最优策略：0,,,,,,,,,35709080..)(min4433221121442331222111214332211ddddddddxxddxddxddxxddxxtsddPdPdpz10.70.9()1,2,,5kkkksusuk5,,2,1k0)s(f)]}us(9.0u7.0[f)]us(5u8{[max)s(f66kkk1kkkkUukkkk13七、（10分）个项目投资选中第不个项目投资选中第jjxj01八、（15分）（1）关键工序：A，D，G，I。（2）对于F工序：TES=10,TEF=15,TLS=30,TLF=35,R=5,r=0.be5c10f1a1510d105g20i15h102987654310,,,,116002601301503002101808060210160max5432115433215432154321或xxxxxxxxxxxxxxxxxxxxxxZ14课程名称运筹学试卷适用班级经管类专业命题负责人田亚明授课教师冯兰刚、武建章、王哲、毕胜男、索贵彬命题日期2011年10月20日教研室主任签字二级学院院长签字