运筹学综合复习题

1、1已知原问题为V37V6maxZx-i4x23x32%3x25x323x1X26X31花X2X34人0,X2OX无符号限制要求：（a）写出其对偶问题；（b）已知原问题最优解为X0,0,4，试根据对偶理论，直接求出对偶问题的最优解。2、分配甲、乙、丙、丁四个人去完成ABCDE五项任务。每个人完成各项任务的时间如下表所示。任务人ABCDE甲2529314237乙3938262033丙3427284032丁2442362345任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。3、用标号法求下图中v1到v7的最短距离V2V5v4810*33E%8620664420丄

2、B4、用标号算法求下图从S到t的最大流量及最小割。弧旁数字为Cjfjxx%64A5、某公司拟将五台设备分配给下属的甲、乙、丙三个工厂，各工厂获得这种设备后,可以为公司带来的盈利如下表所示：盈利工厂设备数甲乙丙000013542710639111141211125131113问分配各工厂多少台这种设备，可以为公司带来盈利总和为最大。用动态规划方法求解。6、一自动化工厂的组装车间从本厂的配件车间订购各种零件。估计下一年度的某种零件的需求量为20000单位，单位产品的年存储费为其价值的20%，该零件每单位价值为20元，所有订货均可及时送货。一次订货的费用是100元，车间每年工作日为250天。(1)

3、计算经济订货批量；(2) 每年订货多少次；(3) 如从订货到交货的时间为10个工作日，产出是一致连续的，求订货点。7、某企业要确定下一计划内产品产量。根据以往经验及市场调查，已知产品销路较好、一般和较差的概率分别为0.3、0.5和0.2,采用大批量生产时可能获得的利润分别为20万元、12万元和8万元；采用中批量生产时可能获得的利润分别为16万元、16万元和10万元；采用小批量生产时可能获得的利润分别为12万元、12万元和12万元。试用期望损失准则作出最优决策。minW2y1y24y32y13y2y313y1y2y345y16y2y33yi0,y20,y3无符号限制1解：对偶问题为将X0,0,4

4、代入原问题的三个约束条件知，2x13x25x32023x1x26x3241x1x2x340，代入对E必须完0，建立的即对X而言，前两个约束为松约束，由互补松弛条件知，必有y1y2偶问题的第3个约束得y33，故对偶问题的最优解为Y0,0,3。2解：由于任务数多于人数，所以需要有一名假想的人，设为戊。因为工作成，故设戊完成E的时间为M（M为非常大的数），其余的假想时间为效率表矩阵如下：八任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M用指派方法求解过程如下：每行减25293142372504617123938262033201918

5、6013342728403227701135244236234523119130220000M00000M44040(a)(b)每列减0000501010000100021831813103110118001480124005M故最优解为X12X24X35X41X531，其余Xij0，即甲一B,乙一D,丙一E,丁A,C放弃。最少的时间为105个小时3.解:V2V5bl9v1V37V4833X.V710V610l0|ViV291V5卞、34J。V627V483V37(c)V2V70|Vi4.解:v2_91V57K27V4830V37V611112127、327V44>V7V15V4>

6、Z8/冋、3/108、8”冋、3V37V6V37(d)9548f)10Vi8103|1310(e)找到一条从s到t的增广链，在图中由粗线标出3V710ABCDEt，D55*33增广链最大的调整量为EA871,调整后如下图所示33-k324433”20sc20C6521>55再用标号法找增广链，点A标号后，增广链中断，表明已找不出增广链，此时网络中的可行流即为最大流，其流量为5+3+5=13。最小割为V,Vs,D,s,C，代B5解：将五台设备分配给三个工厂看成依次分三个阶段（用k表示，k1,2,3）。决策变量xk表示第k阶段向工厂分配的设备数；状态变量Sk表示第k阶段到第3阶段可供分配的设

7、备数允许决策集合为：DkskxkXk为不大于5的非负整数，且XkSk状态转移方程为：sk1skxk用PkXk表示第k阶段分配设备数为Xk时，该厂的盈利额。基本方程为fkskmaxpkxkfk1sk1k1,2,3xkDksk用逆序算法，当k3时，faS3maxpaX3X3D3S3x3S3P3x3f3s3X3012345000010441204662304611113404611121245046111213135当k2时，f2S2maxp2x2f3s3X2D2S2X2sP2X2f3s3f2s2X201234500+0001045051206541001023011561041101424012511106114110161或250135121011116114110212当k1时，f1s1maxp1x1f2s2XiD1S1乙厂26、解：(1)CP2020%4元/件.年；CD100元/次；D20000件2CDDCp21002000041000件每年订货次数=2000020次Q100010个工作日的需求量二1020000800件，故订货点为800件。2507、解：设Ei,E2,E3分别表示销路较好、一般和较差，Si,S2,S3分别表示大批、中批和小批，贝U该冋题的收益矩阵为：E1E2ESi20128AS2161610S3121212其对应