《运筹学综合复习题》由会员分享，可在线阅读，更多相关《运筹学综合复习题（7页珍藏版）》请在金锄头文库上搜索。
1、1、已知原问题为max Z x1 4x23x3 2x13x25x3 23x x 6x 1123x x x 4123x1 0, x2 0,x3无符号限制要求：(a) 写出其对偶问题； (b) 已知原问题最优解为X0, 0, 4，试根据对偶理论，直接求出对偶问题的最优解。2、分配甲、乙、丙、丁四个人去完成 A、B、C、D、E 五项任务。每个人完成各项任务的时间如下表所示。人人甲甲乙乙丙丙丁丁任务任务A A25393424B BC CD DE E29383126283642373332452040232742任务 E E 必须完成，其他 4 项中可任选 3 项完成。试确定最优分配方案，使完成任务的总
2、时间最少。3、用标号法求下图中v1到v7的最短距离v212v4v59v173743v71058v38v64、用标号算法求下图从s到t的最大流量及最小割。弧旁数字为cijfijD5532E4486s64333320C2022t66BA545、某公司拟将五台设备分配给下属的甲、乙、丙三个工厂，各工厂获得这种设备后，可以为公司带来的盈利如下表所示：盈利盈利设备数设备数工厂工厂甲甲乙乙丙丙00379120510012346111111111245问分配各工厂多少台这种设备，可以为公司带来盈利总和为最大。用动态规划方法求解。6、一自动化工厂的组装车间从本厂的配件车间订购各种零件。估计下一年度的某种零件的
3、需求量为 20000 单位，单位产品的年存储费为其价值的 20，该零件每单位价值为 20 元，所有订货均可及时送货。一次订货的费用是 100 元，车间每年工作日为 250 天。(1)计算经济订货批量；(2)每年订货多少次；(3)如从订货到交货的时间为 10 个工作日，产出是一致连续的，求订货点。7、某企业要确定下一计划内产品产量。根据以往经验及市场调查，已知产品销路较好、一般和较差的概率分别为 0.3、0.5 和 0.2，采用大批量生产时可能获得的利润分别为 20 万元、12 万元和 8 万元；采用中批量生产时可能获得的利润分别为 16 万元、16 万元和 10 万元；采用小批量生产时可能获得
4、的利润分别为 12 万元、12 万元和 12 万元。试用期望损失准则作出最优决策。13131解：对偶问题为min W 2y1 y2 4y3 2y13y2 y313y y y 41235y16y2 y3 3y1 0, y2 0, y3无符号限制将X0, 0, 4代入原问题的三个约束条件知，2x13x25x3 20 23x1 x2 6x3 24 1x x x 4231 0，代入对即对X而言，前两个约束为松约束，由互补松弛条件知，必有y1 y2 3，故对偶问题的最优解为Y0, 0, 3。偶问题的第 3 个约束得y32 解：由于任务数多于人数，所以需要有一名假想的人，设为戊。因为工作E E 必须完成，
5、故设戊完成 E E 的时间为 MM（MM 为非常大的数），其余的假想时间为 0，建立的效率表矩阵如下：人人甲甲乙乙丙丙丁丁戊戊任务任务A A25393424B BC CD DE E2938312628364237333245M20402327420000用指派方法求解过程如下：每行减252931423725 0461712046177 439382620332019186013191860843427284032277011357011300244236234523 119130174 119130220000M00000M00000M每列减0021180018005 400 40001914
6、110 115400221903 0 0041181317001100131014404M01703 31800125M00 10故最优解为x12 x24 x35 x41 x531，其余xij 0，即甲B，乙D，丙E，丁A，C 放弃。最少的时间为 105 个小时。3.解：v212v4v5v212v4v50v1958v373743v7100v1958v73743v7108883 (a) (b)v6v6v2912v4v5v23912v4v5100v19588 v387374v7100v195887343v71078 v3 (c) (d)v29v6v61012v411v510v2912v411v50
7、v19588 v387343v7100v1958v734310v7138836 (e) (f)4.解：找到一条从s到t的增广链，在图中由粗线标出7v67vD5532E442086s64333320Ct6622A54B即s A B C D E t，增广链最大的调整量为 1，调整后如下图所示E33D553244s65338720C20t6621再用标号法找增广链，点A标号后，增广链中断，表明已找不出增广链，此时网络中的可行流即为最大流， 其流量为 53513。 最小割为V,Vs, D,s,C,A, B5解：将五台设备分配给三个工厂看成依次分三个阶段(用k表示，k 1, 2,3)。决策变量xk表示第
8、k阶段向工厂分配的设备数； 状态变量sk表示第k阶段到第 3 阶段可供分配的设备数。允许决策集合为：Dksk xkxk为不大于5的非负整数，且xk skA55B状态转移方程为：sk1 sk xk用pkxk表示第k阶段分配设备数为xk时，该厂的盈利额。基本方程为fksk maxxkDkskpkxk fk1sk1k 1, 2, 3x3D3s3用逆序算法，当k 3时，f3s3 maxx3s300000000p3x33p3x3144444245f3s3x3001234666661231111111212111245451313当k 2时，f2s2 maxx2s2x2D2s2p2x2 f3s3p2x2
9、f3s300012345f2s2x20051001230 450065 41001221或20 115610 411001251110611 41100 13512101111611 4110141645212当k 1时，f1s1 maxx1D1s1p1x1 f2s2p1x1 f2s2x1s1012345f1s1x15021316714 910125 130210或2最优分配方案是：分配甲厂 0 台、乙厂 2 台、丙厂 3 台；或分配甲厂 2 台、乙厂 2台、丙厂 1 台。总盈利最大为 21。6、解：(1)CP 2020% 4元/件年；CD100元/次；D 20000件Q2CDDCP21002
10、00001000件4(2) 每年订货次数D20000 20次1000Q(3) 10 个工作日的需求量1020000 800件，故订货点为 800 件。2507、解：设E1, E2, E3分别表示销路较好、一般和较差，S1, S2, S3分别表示大批、中批和小批，则该问题的收益矩阵为：E1E2S120128 A S1610216S1231212其对应机会损失矩阵为：E1E2E3S1044L S202S43840三个待选方案的期望机会损失分别为：S1:00.3 40.5 40.2 2.8万元S2:40.3 00.5 20.2 1.6万元S3:80.3 40.5 00.2 4.4万元故最优方案为方案S2，即中批量生产。E3
