《运筹学》试题参考答案 一、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。
2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。
3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的标准形式 。
4、在图论中�称 无圈的 连通图为树。
5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。
二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1�m a x z = 6x 1+4x 2�������������0781022122121x x x x x x x � 解�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。
2�m i n z =�3x 1+2x 2 �������������������0,137210422422121212121x x x x x x x x x x解�⑴⑵⑶ ⑷ ⑸⑹、⑺⑴⑵⑶ ⑷ ⑸、⑹可行解域为a b c d a �最优解为b 点。
由方程组������02242221xx x 解出x 1=11�x 2=0 ∴X *=��������21x x =�11�0�T∴m i n z =�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲 9 4 3 70 乙 4 6 10 120 360 200 3002�用单纯形法求该问题的最优解。
�10分� 解�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润�则 ma x z =70x 1+120x 2 s.t . ��������������0300103200643604921212121x x x x x x x x � 2�用单纯形法求最优解� 加入松弛变量x 3�x 4�x 5�得到等效的标准模型� ma x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s.t . ������������������5,...,2,1,03001032006436049521421321j x x x x x x xx x x j 列表计算如下�CB XB b70 120 0θL x1 x2 x3 x4 x5 0x 3 360 94190 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 300 0 0 0 0 70 120↑ 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 �11/5� 0 0 1 - 3/5 100/11 120 x 2 30 3/10 1 0 0 1/10 10036 120 0 0 12 34↑ 0 0 0 �12 0 x3 1860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11114300070 120 0 170/11 30/11 0 0-170/11 �30/11 ∴X *=�11100�11300�111860�0�0�T ∴m a x z =70×11100+120×11300=1143000四、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� mi n z =5x 1�2x 2�4x 3 ������������0,,10536423321321321x x x x x x x x x解�用大M 法�先化为等效的标准模型� ma x z / =�5x 1�2x 2�4x 3 s.t . ���������������5,...,2,1,01053642353214321j y x x x xx x x x j 增加人工变量x 6、x 7�得到� ma x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s.t �����������������7,...,2,1,0105364237532164321j x x x x x x x x x x x j 大M 法单纯形表求解过程如下�C B X B b�5�2�400�M�MθLx1x2x3x4x5x6x7�M x64�3�12�10104/3�M x7106350�1015/3�9M�4M�7M M M�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�M x72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/3 0x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3 x220112�1�21�322�5�2�11/311/3�1�1/3 00�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值m i n z=�m a x z/=���322�=322五、�15分�给定下列运输问题��表中数据为产地A i到销地B j的单位运费�B1 B2 B3 B4 si A 1 A 2 A 3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 181�用最小费用法求初始运输方案�并写出相应的总运费��5分� 2�用1�得到的基本可行解�继续迭代求该问题的最优解。
�10分� 解�用“表上作业法”求解。
1�先用最小费用法�最小元素法�求此问题的初始基本可行解�B1 B2 B3 B4 S i A1 123410 8 2 × ×A 2 8 7 65 20 × × 218 A3 9 10 11930 × 20 10 ×dj 8 22 12 18 6060 ∴初始方案�Z=1×8+2×2+6×2+5×18+10×20+11×10=424 2 18 B 3 B4 A2 20 10 B 2 B3 A3 销 地 费 用 产地8 2 B1 B2 A12�①用闭回路法�求检验数�B1 B2 B3 B4 S i A1 1234�2 10 8 2 × ×A 2 8 �4 7 �2 65 20 × × 218 A3 9 0 10 119 130 × 20 10 ×dj 822 12 18 6060 ∵34�=1�0�其余j �≤0 ∴选34x 作为入基变量迭代调整。
②用表上闭回路法进行迭代调整�B1 B2 B3 B4 S i A1 123�1 4�3 10 8 2 × ×A 2 8 �3 7 �1 65 20 × × 12 8A3 9 0 10 11 �1 930 × 20 ×10 dj 8 22 12186060 调整后�从上表可看出�所有检验数j �≤0�已得最优解。
∴最优方案为� 销 地 费 用 产地销 地 费 用 产地最小运费Z =1×8+2×2+6×12+5×8+10×20+9×10=414六、�8分�有甲、乙、丙、丁四个人�要分别指派他们完成A 、B 、C 、D 四项不同的工作�每人做各项工作所消耗的时间如下表所示�ABCD甲 2 10 9 7 乙 15 4 14 8 丙 13 14 16 11 丁 4 15 13 9 问�应该如何指派�才能使总的消耗时间为最少� 解�用 “匈牙利法”求解。
效率矩阵表示为� ��������������9131541116141381441579102��������������591100532410011578��������������541200)0(3245)0(11528)0(** ��������������541200)0(3245)0(11528)0(**行约简 12 8 B3 B4 A2 20 10 B 2 B4 A3 8 2 B1 B2 A1 标号 列约简 √ √ √��������������3210)0()0(03445)0(133)0(60**至此已得最优解���������������001100000100100 ∴使总消耗时间为最少的分配任务方案为� 甲→C �乙→B �丙→D �丁→A 此时总消耗时间W =9+4+11+4=28七、�6分�计算下图所示的网络从A 点到F 点的最短路线及其长度。
此题在“《运筹学参考综合习题》�我站搜集信息自编�.d o c ”中已有。
解�此为动态规划之“最短路问题”�可用逆向追踪“图上标号法”解决如下� 4 37 3519125796 242446 8 5 1 54 54A B1 B2 B3 C1 C2 C3 D 1 D2 D3 E1 E2 F第11 页 共 11 页最佳策略为�A →B 2→C 1→D 1→E 2→F 此时的最短距离为5+4+1+2+2=1417 3 4321257 96 2424 46 8 5 1 5 4 5 4 AB1 B2 B3 C1 C2 C3 D 1 D2 D3 E1 E2 F5914 7711 85 912 14 14。