2022年运筹学复习题 .pdf

《2022年运筹学复习题 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学复习题 .pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运筹学复习题复习范围：1.单纯形法求解线性规划问题2.对偶问题及互补松弛性3.表上作业法求解运输问题4.建立整数规划模型（不求解）5.匈牙利法求解指派问题6.求网络最大流专项练习：一、单纯形法求解线性规划问题例、用单纯形法求下列线性规划问题：0,825943510max21212121xxxxxxxxz解：化为标准型121231241234max105349528,0zxxxxxxxxxxxx用单纯形表进行计算Cj10 5 0 0 iCB基b x1x2x3x40 0 x3 x49 8 3 4 1 0 5 2 0 1 3 8/5 cj - zj10 5 0 0 0 10 x3 x121/58/5

2、 0 14/5 1 -3/5 1 2/5 0 1/5 3/2 4 cj - zj0 1 0 -2 5 10 x2 x13/2 1 0 1 5/14 -3/14 1 0 -1/7 2/7 cj - zj0 0 -5/14 -25/14 所有非基变量的检验数全部小于零，所以此线性规划问题有唯一最优解。最优解 X=（1，3/2，0，0） ；最优值 Z=35/2.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 解题步骤1. 化为标准形

3、2. 列表求解Key：寻找主元（检验数最大，检验比最小）主元变为 1，其余变为 0. 3. 结论（最优解和最优值）练习题：1. 0,242615532max21212121xxxxxxxxz2. 0,1823122452max21212121xxxxxxxxz3. 0,72342263542max32132132321321xxxxxxxxxxxxxxz4.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 0,337343113

4、1313132max321321321321xxxxxxxxxxxxz练习题答案1. 最优解 X=（15/4,3/4,0,0） ，最优值 max z=33/4 2. 最优解 X=（2,6,2,0,0） ，最优值 max z=34 3. 最优解 X=（1,0,2,7,0,0 ） ，最优值 max z=12 4. 最优解 X=（1,2,0,0,0） ，最优值 max z=8 注意细节1.右端项 b 用于计算检验比，只有系数大于0 时才计算检验比；价值系数cj用于计算检验数。2.注意自我检查：基变量一定对应到单位矩阵，其检验数一定等于0；最优表给出对偶问题的最优解，对应的最优值等于原问题的最优值。3

5、.对矩阵的某行乘以一个较大的数，总能做到所有检验数小于0，所以不要随便通分，如练习4。二、对偶问题及互补松弛性例、给出线性规划问题：)4,3,2, 1(096628342max321432214214321ixxxxxxxxxxxxxxxxzi要求： (1)写出其对偶问题；( 2) 已知原问题的最优解为X*= （2,2,4,0） ，试根据对偶理论，直接求出对偶问题的最优解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - 解：(

6、1) 对偶问题为123412412343413min86692234110 (1,2,3,4)iyyyyyyyyyyyyyyyyi(2)将最优解 (2,2,4,0)带入原问题的约束条件，986628332143221421xxxxxxxxxxx根据互补松弛性，40y另一方面，因为1230,0,0 xxx，相应的对偶问题的约束条件应取等号。所以12123322341yyyyyy解得名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - -

7、12345351yyy从而，对偶问题的最优解为Y=（4/5, 3/5, 1, 0）, 最优值为16解题步骤1. 写出对偶问题的步骤最大变最小；系数矩阵转置；变；价值系数与右端项互换。2. 互补松弛性的应用Key：约束条件对应决策变量第一步：把最优解带入约束条件，约束条件取不等号，相应的决策变量等于零；第二步：最优解不为零，对应的约束条件取等号；第三步：解方程练习题：1. 已知线性规划0,162210243max321321321321xxxxxxxxxxxxz的最优解是 X*= （6,2,0） ，(1)写出原问题的对偶问题；( 2)根据对偶理论直接求出对偶问题的最优解。2. 已知线性规划名师资

8、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - 0,1222282652max432143214314321xxxxxxxxxxxxxxxz其对偶问题的最优解为Y*= （4,1） ，(1)写出对偶问题；( 2)应用对偶问题的性质，求原问题的最优解。3. 已知线性规划0,33253232234max21212121212121xxxxxxxxxxxxxxz其最优解为 X*= （4/5, 3/5） ，(1)写出对偶问题；( 2)应用对偶

9、问题的性质，求对偶问题的最优解。4. 已知线性规划0,2023220322432max4321432143214321xxxxxxxxxxxxxxxxz其对偶问题的最优解为Y*= （1.2, 0.2） ，(1)写出对偶问题；( 2)应用对偶性质，求原问题的最优解名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 练习题答案1. 对偶问题最优解 Y=（1,1） ，最优值为 26 2. 原问题的最优解 X=（0,0,4,4） ，最优值

10、为 44 3. 对偶问题的最优解Y=（1,0,0,0,1） ，最优值为 5 4. 原问题的最优解 X=（0,0,4,4） ，最优值为 28 注意细节写对偶问题时，不要忘了决策变量的非负约束；注意计算最优值，自我检查最优解应满足所有的约束条件，且原问题的最优值应该等于对偶问题的最优值。三、表上作业法求解运输问题1、产销平衡问题例 下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。销 地 产地B1B2B3B4产量A1A2A34 1 3 1 2 7 4 5 5 6 0 1 8 8 4 销量6 5 6 3 20 解：先用沃格尔法求初始解销 地 产地B1B2B3B4

11、产量行罚数A1A2A34 1 3 1 2 7 4 5 5 6 0 1 8 8 4 3 0 2 2 1 1 5 2 2 4 4 销量6 5 6 3 列罚数2 2 1 1 1 1 1 1 1 1 5 得初始调运方案：B1B2B3B4A15 3 A26 2 A33 1 下面用位势法进行检验：B1B2B3B4uiA13 6 0 A21 1 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - A31 5 1 vi1 1 4 0 所有检验

12、数 0，此时问题已达到最优解总运费 min z =5*1+3*4+6*1+2*0+3*5+1*1=39 解题步骤1. 先用沃格尔法或者最小元素法求出初始解沃格尔法：优先供应罚数大的运输任务最小元素法：优先考虑所有任务中的最低运价。2. 再用位势法或者闭回路法进行检验位势法：令任意一个位势为0（不妨 u1=0） ，计算位势和检验数：数格对应的运价等于位势和；空格对应的运价减去位势和等于检验数。3. 若不是最优解，用闭回路法调整后回到第2 步检验数全部大于等于零，得到最优解；调整检验数小于零的空格所对应的闭回路：以该空格为第一个奇数顶点，找出偶数顶点中最小的运输量为调整量，奇数顶点加上调整量，偶数

13、顶点减去调整量。练习题：1. 求最优调运方案（写出min 值）销 地 产地B1B2B3B4产量A1A2A310 16 5 6 10 4 7 5 10 12 9 10 4 9 4 销量5 2 4 6 2. 求最优调运方案（写出min 值）销 地 产地B1B2B3B4产量A1A2A33 2 4 7 4 3 6 3 8 4 2 5 5 2 3 销量3 3 2 2 练习题答案1. 总运费为 118 2. 总运费为 32 注意细节1.对于 m 行 n 列的运输表，无论是初始解还是最优解，数格的个数应该等于m+n-1。并且数格不能形成闭回路。2.检查位势是否计算正确，数格处的位势和应等于数格所对应的运价3

14、.运价用于计算位势，得到的解（运输量）用于调整名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - - - - 4.如果计算出相同的罚数，任意选一个5.如果同时划掉一行及一列，则在此行此列任意选一个空格补0. 始终保持数格个数为 m+n-16.如果空格的检验数等于0，意味着最优解不唯一。2、产销不平衡问题解题步骤1. 先将产销不平衡问题化为产销平衡问题增加虚拟销地或产地；运价设为0，销量或产量等于产销不平衡的差值2. 再求解新得到的产销平衡问题

15、。例 下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。销 地 产地B1B2B3B4产量A1A2A33 2 4 7 4 3 6 3 8 4 2 5 5 2 6 销量3 3 2 2 解：此问题是一个产销不平衡问题，由产大于销，故增加虚拟销地B5，令销量为(5+2+6)-(3+3+2+2)=3，单位运价为 0 化为产销平衡问题。 用沃格尔法求初始解销地产地B1B2B3B4B5产量行罚数A1A2A33 2 4 7 4 3 6 3 8 4 2 5 0 0 0 5 2 6 3 1 1 1 2 0 3 1 1 1 销量3 3 2 2 3 列罚数1 1 1 1 4 3

16、2 1 1 0 得初始调运方案：B1B2B3B4B5A12 3 A20 2 A31 3 2 下面用位势法进行检验：B1B2B3B4B5uiA15 2 0 0 A23 -1 1 -1 A33 -1 1 vi3 2 4 4 0 调整-1 所在的闭回路，B1B2B3B4B5名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - A12 3 A20 2 A31 3 2 调整量为 0，改进后的解为B1B2B3B4B5A12 3 A22 0 A3

17、1 3 2 下面用位势法进行检验：B1B2B3B4B5uiA15 1 0 0 A21 4 2 -2 A32 -1 1 vi3 2 5 4 0 调整-1 所在的闭回路，B1B2B3B4B5A12 3 A22 0 A31 3 2 调整量为 1，改进后的解为B1B2B3B4B5A13 2 A22 0 A33 2 1 下面用位势法进行检验：B1B2B3B4B5uiA14 0 -1 0 A22 4 3 -3 A31 2 0 vi3 3 6 5 0 调整-1 所在的闭回路，B1B2B3B4B5A13 2 A22 0 A33 2 1 调整量为 2，改进后的解为B1B2B3B4B5A13 2 0 A22 0

18、A33 3 下面用位势法进行检验：B1B2B3B4B5uiA14 1 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - A21 3 2 -2 A31 3 1 0 vi3 3 5 4 0 所有检验数 0，此时问题已达到最优解总运费 min z =9+8+6+9=32练习题：3. 求最优调运方案（写出min 值）销地产地B1B2B3B4B5产量A1A2A3 A410 2 1 8 20 10 20 6 5 8 7 3 9 30

19、10 7 10 6 4 5 5 6 2 9 销量4 4 6 2 4 练习题答案3. 总运费为 90 四、建立整数线性规划（不求解）例 1、某服务部门各时段 (2h 为一段 ) 需要的服务人员数如表所示，按规定，服务员连续工作8h 为一班 . 现要求安排每个时间段开始上班的服务员人数，使服务部门服务员总人数最少？时段1 2 3 4 5 6 7 8 服务员最少数目10 8 9 11 13 8 5 3 答案书上 P124 例 1例 2、某钻井队要从以下10 个可供选择的井位中确定5 个钻井探油，使总的钻井 费用 最小。 若 10 个 井位的 代号 为 S1,S2,S3, S10，相应 的钻井 费用

20、为C1,C2,C3, C10，并且井位选择上要满足下列限制条件：选择 S1和 S7就不能选择钻探S8；反过来也一样；选择了 S3或 S4就不能选 S5，反过来也一样；在 S5 S6 S7 S8中最多只能选两个；试建立这个问题的整数规划模型。 （不求解）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 解： 令)102, 1S0S1jjjxj，（不选择选择则问题可以表示为)102, 11021125.min87655453871

21、102110102211jxxxxxxxxxxxxxxxtsxCxCxCzj，（或练习题：现有资金总额为 B。可供选择的投资项目有n 个，项目 j 所需投资额和预期收益分别为 aj和 cj（j=1,2, ,n ） 。此外 , 由于种种原因，有三个附加条件：第一，若选择项目1，就必须选择项目2，反之不一定；第二，项目3 和 4 中至少选择一个；第三，项目5，6 和 7 恰好选择两个 . 应当怎样选择投资项目才能使总预期收益最大？练习题答案书上 P124 例 2练习题：某公司拟在市东、西、南三区建立门市部。有7 个位置点 Ai（i=1，7）可供选择，规定：在东区，由 A1，A2，A3三个点中至多选

22、两个；在西区，由 A4，A5两个点中至少选一个；在南区，由 A6，A7两个点中至少选一个。如选用 Ai 点，设备投资估计为bi 元，每年可获利润估计为ci 元，但总投资不能超过 B 元，问应选择哪几个点可使年利润最大？例 3、某集团公司有 n 个销售某种产品的零售店Bj (j=1,2,n)，其每年的销售量为 bj( j=1,2,m)，现该集团公司打算在m 个地点开设生产该产品的生产厂，每个地点最多只能建一个工厂，若在第i 地建厂其生产能力为ai ( i=1,2,m)，每名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

23、 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - 年的固定成本为di，从工厂Ai到零售站Bj的单位运费为cij(i=1,2,m；j=1,2,n)。问应该在哪些地点选厂及做怎样的运输计划，使本年度花费最少？解： 设从工厂 Ai到零售店 Bj每年的运输量为xij（i=1,2,m；j=1,2,n） ，令)2, 101miiiyi，（地建厂，选择不在地建厂，选择在则该问题可以表示为)2, 1;,2, 110,0.min11111njmiyxbxyaxtsxcydziijmijijnjiiijminjijijmiii，（或练习题：工厂 A1和 A2生产某种物资

24、 . 由于该种物资供不应求，故需要再建一家工厂 . 相应的建厂方案有A3和 A4两个。这种物资的需求地有四个，生产能力、需求量、单位物资运费见下表。工厂A3或 A4开工后 , 每年的生产费用估计分别为1200万元或 1500万元. 现要决定应该建设工厂A3或 A4, 才能使今后的总费用 (即全部物资运费和新工厂生产费用之和) 最少? B1B2B3B4生产能力A12 9 3 4 400 A28 3 5 7 600 A37 6 1 2 200 A44 5 2 5 200 需求量 ( kt/ 年) 350 400 300 150 练习题答案名师资料总结 - - -精品资料欢迎下载 - - - - -

25、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - 书上 P125 例 3练习题：书上 P136 例 7，例 8 书上 P148 5.4，5.5 解题步骤建立数学模型就是回答三个问题：1. 决策变量是什么？2. 目标函数是什么？3. 约束条件有什么？注意细节仔细分析题意，决策变量就是题目所问的问题。变量是人数、机器设备台数或产品件数等都要求是整数，在约束条件中一定要写出整数限制！对某一个项目要不要投资， 建不建厂这样选择性的决策问题，使用 0-1 变量，在约束条件中要再次表明变量取值0

26、或 1. 遇到人员的合理安排问题（实际上是指派问题），使用双下标的 0-1 变量：xij=1 表示安排第 i 人去做 j 工作， xij=0表示不安排第 i 人去做 j 工作。确定决策变量和目标函数后，从题目的第一句话开始考察需要满足的约束条件，不要有遗漏。五、匈牙利法求解指派问题例、求指派问题（ min） （要求写出解和值） ：671124598311045982c名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 解：变换系

27、数矩阵：6711224598431104159822c459001542093376054540010420433710试指派：独立 0 元的个数小于 4，试指派不成功，调整系数：重新试指派：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - 独立 0 元个数为 4，指派成功，最优解为0001100001000010；最优值为： 2+4+1+8=15. 解题步骤1. 变换系数矩阵，目的：使每行每列中都出现零元素：原系数矩阵每行都

28、减去该行的最小元素；新得到的系数矩阵每列减去该列的最小元素。2. 试指派，目的：寻找独立0 选择多的礼让选择少的，选择少的优先指派3. 独立 0 元个数不足则变换矩阵，目的：增加新的0 用最少的直线通过所有0 元素（行不勾列勾）调整系数（没有划线的元素中的最小元素为我们的调整量，所有没划线的元素减去调整量，划一次线的元素不变，划两次线的元素加上调整量）4. 写出最优解和最优值练习题：1. 求指派问题（ min） （要求写出解和值）：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16

29、 页，共 22 页 - - - - - - - - - 12797989666717121412151466104107106c2. 求指派问题（ min） （要求写出解和值）：31231195715103732554857784749c3. 求指派问题（ min） （要求写出解和值）：15182124192322182617161919212317c4. 求指派问题（ min） （要求写出解和值）：10114287111014125691214131511107c名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

30、 - - - - - - 第 17 页，共 22 页 - - - - - - - - - 练习题答案1. 最优解为0100000010000010010010000，最优值为 32 2. 最优解为0010000001010001000000010，最优值为 17 3. 最优解为0100100000100001，最优值为 70 4. 最优解为00010100000100000001，最优值为 22 注意细节寻找独立 0 元素时：从只有一个0 元素的行开始，给0 加圈，划去同列的0；然后从只有一个0 元素的列开始，总之，选择性多的要礼让选择性少的！最少直线数应等于独立零元素的个数，若不相等，说明试

31、指派过程有误。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - - - - 打勾的目的，是要让最少的直线覆盖所有的零。自我检查：是否所有零都被直线覆盖，是否直线数等于独立零元个数。如果人事不等（不是方阵） ，增加一行（或列）零。 （即虚拟人或事，道理同产销不平衡的运输问题）六、求网络最大流例、求下图中的网络最大流解：寻找可增广链：1. 24414stvvvv，可增加流量 t =2；2. 34125stvvvv，可增加流量 t =1；3.

32、233222514stvvvvvv，可增加流量t=2；4. 12236stvvvv，可增加流量 t =1。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - 所以，最大流 =15 解题步骤1. 寻找可增广链：前向可增加；后向可减少！2. 找到可增广链后，修改网络流量（没有可增广链时达到最大流）练习题：1. 求下图中的网络最大流（2，1）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

33、- - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - 2. 求下图中的网络最大流3. 求下图中的网络最大流4. 发点 S1，S2分别可供应 10 和 15个单位，收点 T1和 T2可接收 10个和 25 个单位，求最大流，边上的数为jic。S1v1T13 2 2 4 7 6 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 22 页 - - - - - - - - - 练习题答案1. 最大流 =5

34、 2. 最大流 =14 3. 最大流 =9 4. 最大流 =22 注意细节1. 寻找可增广链时，不要忽略后向可减少的情况2. 找到可增广链后，修改网络流量；再从头寻找新的可增广链，直到再找不到可增广链时停止3. 可行流：中间点：流入等于流出收发点：发点总流出量 =收点总流入量达到最大流时，最大流 =发点流出量 =收点流入量4. 如果题目只有容量数据， 没有可行流， 则把初始可行流设为0. 如果网络有若干个发点和收点，则添加两个新点vs和 vt，分别连结这若干个发点和收点。（P263 ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 22 页 - - - - - - - - -