2013-2014-2运筹学模拟题-新(1)培训课件

1、学习-好资料更多精品文档管理科学基础模拟题得分评分人、单项选择题：（本大题共10小题，每小题2分，共20分。每小题 的备选答案中只有一个正确答案，请将选定的答案代 号填在括号内。）略得分评分人二、问答题（每题4分，共20分）某公司正在制造两种产品，已知制造每件产品所占用设备的工时及调试 时间，已知每天可用能力及单位产品利润，问如何制定生产计划使获利 最大。产品1产品2每天可用能力设备A0515设备B6224调试工序115单位利润21使用“管理运筹学”软件，得到的计算机解如图所示，回答下面的问题:学习-好资料更多精品文档aEXIKliKKXIX3fEXIXjiE工501.5a榕弛卿全輕对禺曲格0

2、.25.5半前值 上限X11n2.667韓顶数范因当前值 上除751841524(1)写出相应问题的数学模型;两种产品的最优产量是多少，此时最大学习-好资料更多精品文档利润是多少;(2) 写出对偶问题的数学模型；对偶问题的最优解是什么；(3) 如果要增加设备工时生产，选择哪个(A、B、调试时间)，为什么;(4)哪些工时数没有使用完，没用完的加工工时数为多少;(5)产品I价格在什么范围内变化，最优解不变?(6)如设备A工时数增加到30，总利润能增加多少，原问题最优解是 否发生变化。学习-好资料更多精品文档飞药结果輸出目标函数最优值药8.5变重最优解相差值x13.50M21.50约束松弛靡I余变重

3、对偶悄格122.502 0.2530.5目标函數系數范国: 变重下限当前值上限x1123x2.6671 2常數项数范国： 约束下限当前值上限17.530无上限2 1024303458得分评分人三、计算题（60分）1、（20分）某厂 I、II、山三种产品分别经过 A、B 两种设备加工。已知生产单 位各种产品所需的设备台时， 设备的现有加工能力及每件产品的预期利润如下表所 示：IIIIII设备能力（台.h）A63545B34530单件利润（元）415（1）建立线性规划模型，求获利最大的产品生产计划。（2） 如果上述最优解不变，求产品I 的单件利润的变化范围。3）若有一种新产品，生产一件所需的设备台

4、时分别为：A 设备 3 小时，B设备 2 小时，单件利润为 2.5 元，问该新产品是否值得生产?（4）如果 A 设备工时减小到 30，问对原问题会造成什么影响?答:更多精品文档学习一好资料溝优解如下目标函数最优値为：35变里最优解相差值502D2687330约束松弛療1余变里对偶价格10.3332o667目标函数系数范H：变里下限当前值 上限13吃无下限胡3333常数项数范IS:约束下眼4513.6G756.667当前值 上阴1304560222.53045学习-好资料更多精品文档(1)maxz =4x1x25x36X| - 3x2- 5x3冬 45 s.t.3xi +4X2+5X3兰 30

5、x0,x0,x041500CB基 B-1bX1X2X3X4X50X445635100X53034501Cj- Zj415000X4153-101-15X363/54/5101/5Cj- Zj1-300-14X151-1/301/3-1/35X33011-1/52/5Cj- Zj0-8/30-1/3-2/3贝 V，xi =5,X2=0, x3=3，最大赢利 z =35(2)产品 I 的利润变化范围为3, 611-(4) (-) -5 1 _03- 110-(4 .) 1-5 ( -1) 0 3 5_ 1 20 -(4 ：；几)(-)-5035-1 _ _2(3)值得生产。二=2.51-3It J

6、32_(4)如果 A 设备工时减小到 30,问对原问题会造成什么影响?学习-好资料5更多精品文档妾量于埶I軸束耒件牛敎H目标醐II1髭|X3价個柔欽41|5约宋弟件|iiI昶|略XI皐正|员|无000蟻忧解如下U4MIC3M!aX9UXKXMEXia4MEKXKKMmXlUXIfliXiaXKaX娈重最优解相差值50M202.667M330约束時撫I余变里対偶恰格弓标函數最优繭为：35.333.6E7目标国数最址11为：自0最饥解相差值02M202x3G0漏优韶如下咙1020 x13x2M3无下限3333甫敎 项數范国约束130222.54G13.66756.667当前伯 上限45603145

7、当前佰 上限下限当前值上限X1无T限4无下阻1x333335无HR常数项数豳m下限当上限10303023030无上取1I20目标団数岳数范国b = B-1bIB-ib= 3L30J=（0，6）（，）利润变化-1（45-30）=-53学习-好资料更多精品文档41500CB基 B-1bXiX2X3X4X50X430635100X53034501Cj- Zj415000X403-101-15X363/54/5101/5Cj- Zj1-300-14xi01-1/301/3-1/35X36011-1/52/5Cj- Zj0-8/30-1/3-2/3学习-好资料更多精品文档101250目标函敎系数范I变星

8、下限当前值上限11无下限46*2无下限13M333335无上限當数顷数范围约束下限当前值上限10253022530无上限b = B-1. b(5)如果 A 设备工时增加到 70,问对原问题会造成什么影响?对岸i格-2200 0 5I1B-1b 二31532蛍 7)5更多精品文档学习一好资料蠢涪陶出潇结果輪出“皿“皿.为优解如卞目标函數最优値为35变里最优解相差值50M202.667M330约束松葩撫I余变重对偶悄格1D.33320刃黒鉀数篥辛辭:当苗佰上限M1346x2无下限13.667x3333356.67卓娥瞒约萸下膿当前僧上限1304560222.53045I最优績相差值xl&6

9、670竝02卸x320嫉松匏测余甕里肘雋价格1033320.667目标函埶荼埶范国:下限当前值上限34IE无下限13.667x3333356,667常埶项埶范圉:下限当前值上限3050602253050目标函埶最此值为：3G.6S8更多精品文档学习-好资料更多精品文档護结锁出亍韓结果输出XXXU-UXXXXXXKKU：: JXWXXXXXKB 目棕陌数最优值为目怔函數竝优值为:W最优解相差值变里最优解相差佰100d10004.3332 04333M301 E7K301.667约束松弛测余査里刃擱价格L333肖前值rsri in ersri 1102a目标函数乘数范闻 麥重下限01.333当前值

10、上限1202D目标函数系数范圉上限“-无上眼K134无上限K1342无下限15.333无下限15.333K3予T眼56,6673无下限56.E67常數项数范闻:當数项数范闻：约束下限当前值上限约束下服当前值上限t h h a. 8 .iJ,a h无上限匕1G0SC16070无上限2D3040203035I2、已知运输问题的供需关系表与单位运价表，试求最优调运方案。销地产地曱乙丙丁产量132765027523603254525销量60402015答:销地产地曱乙丙丁产量135155022520156032525销量60402015填一个数字划一条线，最后一个数字划两条线，m+n-1个基变量，m+

11、n-1个非空格3、已知运输问题的供需关系表与单位运价表，试求最优调运方案。学习-好资料更多精品文档销地产地曱乙丙产量142582353731324销量485答:销地产地曱乙丙丁产量188252734004销量4852当同时出现行或列要划掉的时候，要在同时划去的一行或一列中的某个 格中填入数字0。当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0,则说明该运输问题有多重（无穷多最优解）。当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在 迭代过程中，在同时划去的一行或一列中的某个格中填入数字0,表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰 好为m+n-1

12、个。作业题:4、分配甲、乙、丙、丁四人去完成 4 项任务。每人完成各项任务时间如下表所示,试确定总花费时间最少的指派方案。ABCD甲791012乙13121617丙15161415丁11121516答：最优指派方案为x13=x22=X34 =&1-1，最优值为 48。学习-好资料更多精品文档5、从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完 成各项工作的时间如表所示。规定每项工作只能由一个人去单独完成， 每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某 种原因决定不同意承担第4项任务。在满足上述条件下，如何分配工作, 使完成四项工作总的花费时间为最少。工作屮

13、乙丙J戊110231592510152斗315514715420151368人甲乙内J戊110231592510152431551471542015130085GO0000用匈牙利法求解得最优分配方案为：甲-2，乙-3,丙-1,戊-4，对丁不分 配工作。作业题：分配甲、乙、丙、丁四人去完成 5 项任务。每人完成各项任务时间如下表所示。由 于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项,试确定总花费时间最少的指派方案。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：假设增加一个人戊完成各项工作的时间取A、B、C、D、

14、E 最小值。学习-好资料更多精品文档得效率矩阵为:ABCDE甲-2529314237乙3938262033丙3427284032丁2442362345戊2427262032一各行减最小值，各列减最小值：得A B C D E最有指派方案甲 4乙191850丁I1戊.4变换得75$78177甲C乙184170186544-187 0711 16446进一步AB C D E乙18丙11丁0戊.30 11300 01472 018 30 318 00 120 2学习-好资料更多精品文档A B C D E甲0 1 0 00乙0 0 0 10丙0 0 0 01丁1 0 0 00戊也0 1 0 0一甲一一

15、B，乙一一 C,D，丙一一 E, 丁一一 A最低费用=29 + 26+ 20+ 32+ 24= 1316、某构件公司商品混凝土车间生产能力为20T/ 小时，每天工作 8 小时，现有2 个施工现场分别需要商品混凝土 A150T ，商品混凝土 B100T ，两种混凝土的 构成、单位利润及企业所拥有的原料见表10.4.2 ，现管理部门提出1、 充分利用生产能力；2、 加班不超过 2 小时；3、 产量尽量满足两工地需求；4、 力争实现利润 2 万元/天。AB拥有资源水泥0.350.2550T砂0.550.65130T单位利润10080试建立目标规划模型拟定一个满意的生产计划。解1、 确定变量设 X1、

16、X2分别为两种商品混凝土的产量2、 约束条件(1) 目标约束：P1级：要求生产能力充分利用，即要求剩余工时越小越好。X1X2d-d1=160(T)其中要求0P2级：要求可以加班，但每日不超过 2 小时，日产量不能超过 200TX1X2d2_ d2-200仃)其中要求d2 T0P3级：两个工地需求尽量满足，但不能超过需求。X1d3F50(T)其中要求：d3=0学习-好资料更多精品文档X2df =100仃)dji0因需求量不能超过其需要，故d3,d/=oP4级：目标利润超过 2 万元。100 x1+80X2+d5-d5=20000(元)，其中要求d5 T0(2)资源约束：i)水泥需求不超过现有资源

17、0.35xi+0.25x2三 50ii )砂需求不超过现有资源0.55xi+0.6x2 w130(3)非负约束：xi 0, X2 0,di：di 0(i=1,2,5)3、目标函数。依目标约束中的要求，第三层目标中有2 个子目标，其权数可依其利润多少的比例确定，即 100 : 80，简化为 5 : 4，故 Wi=5 , W2=4。故目标函数为:Zmin *P1d1_ P2d2P3(5d 4d) P4d5_整理得该问题的目标规划模型为：Zmin二Rdl P?d2卩3(5小3一4d)卩4小5一约束：x1x2d-d/ = 160 x1x2 df-d；=200 xdf-150X2dT-100100 x1

18、+80 x2+d一* =200000.35x1+0.25x2 500.55x1+0.6x20, X20,diP0(i=1,2,5绝对约束，严格控制，若要求超过预定目标值，不低于/不小于/超过，充分利用(剩余越小越好) ,d1二0 min(di-)希望各目标值与预期目的值之间不足的偏差都尽量小，而超过的偏差不限学习-好资料更多精品文档若要求不超过预定目标值，不超过min(di+)希望各目标值与预期目的值之间超过的偏差尽量小，即允许不到目的值。若要求恰好达到预定目标值，min（di+d）超过或不足的偏差尽量小尽量满足，但不超过di+= 0 min（ di-）取orAH制*设欝工时（JJ/O）5 村

19、料（百吨-哗ti）3P3,利飆K万元廊说】4九2工厂莊制定生产计划时,必须按重要程度考虑如下工个目标：冃标P3翌求住产这两种产品的利润最少建最少建达到达到12万元 目际舄 要求K产品的产常尽町能是E严品产量的E5f3目标Pi为龙分利用设备工时，必须便设备的空闲时阖尽可能小 问工厂应如何决定产品A和B的产塑？解 首先根据题意建立目标规划模型乜设心和巧井别为两产品的产嵐，很据预 先提出的目标及资源限制，垮虑间题的诙東条件如下：利润约束4j；（+ 3- 十叭=12产品产量妁束 斗- 1.5心-爲+詰=0设备工时约東2町 7 在十石2原材料约束3巧*3工$12根JK握出的目标要求三个目标函数为啓 53

20、 卜血）*同,便梵和为垠小，则可 建立一牛有冃标优先级的线性目标规划樵型：叭+ P3（J3+d；） +4心寸乳2兀-d +d；=12yXh町旨hd：20 （i = t2,3）学习-好资料更多精品文档7、用图解法求解下列多目标规划模型，并说明是否所有目标都可以实现:min f = RdP2d2F3d3x1x2d/ - d=102x1x2d - d2=26-x12x2d3- d36Xi，X2，d,di-0(i= 1,2,3)答：最短路线 A-B2-C1-D1-E，其长度为 8。9、用标号法求网络中从Vs到Vt的最大流量，图中弧旁数字为容量Cij5答：最大流为20。10、用标号法求s到t的最大流及其

21、流量，并求最小截集及其截量。学习-好资料更多精品文档11、已知如表所列资料前序紧一e间匸序时间（天）序工前序紧工s工间35-Z77.a2方4/q5-J1-7gC2J/C7rf/3方-5c3要求：（a）绘制网络图。（b）计算各工序的最早开工、最早完工、最迟开 工、最迟完工时间及总时差，并指出关键工序。（c）若要求工程完工时间 缩短2天，缩短哪些工序时间为宜。学习-好资料更多精品文档工序iJ序间工时ESEFLSLFTF关键 工序C12707181h13505050虚24077992m2537108111e2757129U2b34459590g4529119110I48791610171a563111411U0丰虚670141414U0*虚690141417173f7105141914190890161617171d811316191720119102161817191k10111192019200*因本题未涉及到缩短工序时间