《运筹学》习题集

《运筹学》习题集《运筹学》习题集PAGEPAGE8第一章 线性规划将下述线性规划问题化成标准形式1) minz＝－3x1＋4x2－2x3＋5x44x1－x2＋2x3－x4＝－2st. x1＋x2－x3＋2x4≤14－2x1＋3x2＋x3－ x4≥x1，x2，x3≥0，x4无约束2) minz＝2x1－2x2＋3x3－x1＋x2＋x3＝4st. －2x1＋x2－x3≤1 2 x≤0，x ≥0，x1 2 用图解法求解LP无可行解。1 minz＝2x＋1 1 4x＋6x≥61 1 st 2x＋2x1 x ，x 1 21 maxz＝3x＋1 1 2x＋x≤21 1 st 3x＋4x1 x ，x 1 21 maxz＝3x＋1 1 6x＋10x≤1201 1st 5≤x≤10123≤x≤821 maxz＝5x＋1 1 2x－x≥21 1 st －2x＋3x1 x ，x 1 2LP问题所有基解，指出哪些是基可行解，并确定最优解1 2 3 （1）minz＝5x－2x＋3x＋1 2 3 1 2 3 x＋2x＋3x＋4x＝71 2 3 st 2x＋2x＋x ＋2x＝31 2 3 4x1，x2，x3，x4≥0分别用图解法与单纯形法求解下列LP问题，并对照指出最优解所对应的顶点。1 maxz＝10x＋1 1 3x＋4x≤91 1 st 5x＋2x1 x ，x 1 21 maxz＝2x＋1 1 3x＋5x≤151 1 st 6x＋2x1 x ，x 1 2M法与两阶段法求解下列LP问题。1 2 minz＝2x＋3x＋x1 2 1 2 x＋4x＋2x≥1 2 1 1 2 st 3x＋2x x，x ，x1 1 2 1 2 maxz＋1 2 1 1 2 . 3x＋xSt. 2x＋x 1 1 2 1 2 x＋x－x1 2 1 2 maxz＝5x＋3x1 2 1 2 x＋2x －x≤181 2 1 2 st 2x＋x －3x≤1 2 1 2 1 2 x＋x －xx，x ，x1 2 1 2 maxz10x1

15x2

12x35x3xx 91 2 3st.

5x6x15x151 2 32xxx,1 2

x53

x,x01 2 3jj求下表中a～ljjcj（a）－1200CBXBbx1x2x3x4x50x46（b）（c）（d）100x51-13（e）01（a）-1200（a）x1（f）（］2-11/200x54（h）（I）11/210-7（j）（k）（l）3020人，周日去植树。根据经验，一天男生平均每人挖坑20个，3025102015棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）模型，不必求解。某糖果厂用原料A、、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中ABC价如下表所示。甲乙甲乙丙原料成本(元/千克)每月限量（千克）A≥60％≥15％2.002000B1.502500C≤20％≤60％1.001200加工费（元/千克）0.500.400.30售 价 3.402.852.257－12500月底已存货200货各多少，才能使总收入最多？请建立此问题的线性规划模型。月份 7 8 9 10 11 12买进单价282425272323售出单价292426282225某厂接到生产AB两种产品的合同，产品A200B300件。这两种产A每件需要2小时，产品B每件需要4小时。机械加工阶段又分粗加工和精加工两道工序，每件产品A410B712170010003000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、32工阶段允许设备可进行500小时的加班生产，但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料，为该厂制订一个成本最低的生产计划。或由一个技工和两个力工组成的小组来完成100804842和36100002000030000400800(第二章对偶与灵敏度分析写出以下线性规划问题的DLP1 2 minz＝2x＋2x＋1 2 1 2 x＋3x＋4x ≥21 2 1 2 st 2x＋x＋3x 1 2 1 2 x＋4x＋3x ＝1 2 x x x x 1 2 31 2 maxz＝5x＋6x＋1 2 1 2 x＋2x＋2x ＝51 2 1 2 st －x＋5x－x 1 2 1 2 4x＋7x＋3x 1 2 2 x1无约束，x≥0，x2 11 22 3maxz＝cx＋cx＋11 22 3a x＋a x＋a x ≤b111 122 133 1st a x a x a x st a x a x a x 211 222 233 2a x a x a x a x a x a x 311 322 333 3x x x x 1 2 3LP：1 2 3 minz＝2x＋3x＋5x＋1 2 3 1 2 3 x＋2x＋3x＋x ≥21 2 3 1 2 3 st －2x＋x－x＋3x 1 2 3 x≥0（j=1,2,3,4）xj写出DLP；用图解法求解DLP；2）的结果及根据对偶性质写出原问题的最优解。LP：1 2 maxz＝x＋2x＋1 2 x x ＋ － ≤2x x 1 2 31 2 1 2 st x－x＋x 2x＋x＋1 2 1 2 x x x x 1 2 3DLP；利用对偶问题性质证明原问题目标函数值Z≤1LP：maxz＝x1＋x2－x1＋x2＋x3 ≤2st －2x1＋x2－x3 ≤1xj≥0试根据对偶问题性质证明上述线性问题目标函数值无界。LP：1 2 3 maxz＝2x＋4x＋x＋1 2 3 x 1 2 x＋3x ＋x ≤82＋ x 1 2 1 23 st. x2＋x＋x3 x x x x 1 2 3x≥0xj写出DLP；已知原问题最优解X（2,4,用对偶单纯形法求解下列线性规划问题1 2 1) minz＝4x＋12x＋1 2 x1 ＋3x3 ≥3st 2x2＋2x3 ≥5x≥0(j=1,2,3)xj2)minz5x1

2x2

4x33xx2x4st 1 2 3.6x3x5x

10x1 2 3,x,x01 2 3st1)2)3)4)1)2)3)

考虑如下线性规划问题1 2 1 2 1 2 1 2 minz＝60x＋40x＋80x3x＋2x＋x 4x＋x＋3x 2x＋2x1 2 1 2 1 2 1 2 x≥0xj写出DLP；用对偶单纯形法求解原问题；用单纯形法求解其对偶问题；对比以上两题计算结果。1 2 已知LP：maxz＝2x－x＋1 2 x x ＋ ＋ ≤6x x 1 2 31 st －x＋2x 1 x x ，，x x 1 2 3用单纯形法求最优解1 2 分析当目标函数变为maxz＝2x＋3x＋x31 2 给出线性规划问题2 1 2 maxz＝2x＋3x＋x1/3x1＋1/3x＋1/3x2 1 2 2 st 1/3x1＋4/3x＋7/3x2 x≥0xj用单纯形法求解得最终单纯形表如下cj23100CBXBBx1x2x3x4X52x1110－14－13x22012－11j00－3－5－1试分析下列各种条件下，最优解（基）的变化：目标函数中变量x36；1分别确定目标函数中变量x1x2的系数CC2在什么范围内变动时最优解不变；1约束条件的右端由 1 变为 2 ；3 3某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（/件。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316请构造数学模型使该厂利润最大，并求解。原料A、B的影子价格各为多少。现有新产品丙，每件消耗3千克原料A4千克原料B少为多少时才值得投产。工厂可在市场上买到原料A题最优基的不变的情况下，最多应购入多少？可增加多少利润？3.5某玩具公司分别生产三种新型玩具，每月可供量分别为1000、2000、2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500见下表。又知丙百货商店要求至少供应C1000A分配方案。甲乙丙可供量A54－1000B16892000C1210112000第三章运输问题根据下表，用表上作业法求最优解。BB1B2B3B4AAA123销量413612754556601388420根据下表，用表上作业法求最优解。BB1B2B3B4AAA123销量945139738462752533511求给出的产销不平衡问题的最优解BB1B2B3B4AAA123产量859销量511941287335154956食品厂123面粉厂产值某市有三个面粉厂，他们供给三个面食加工厂所需的面粉，各面粉厂的产量、各面食加23面食加工厂制作单位面粉食品的利润分别为121611食品厂123面粉厂产值面粉厂131022024118303811420销量152520光明仪器厂生产电脑绣花机是以产定销的。已知16和单台电脑绣花机平均生产费用见下表：1月份正常生产能力（台）60加班生产能力（台）10销量（台）104单台费用（万元）152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.5已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，0.1,0.27--8月份销16月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（仓储、维护）最少？设有AC三个化肥厂供应4数据如下表：1234产量A1613221750B1413191560C19202350最低需要量3070010最高需要量507030不限试求总费用为最低的化肥调拨方案第四章 动态规划现有天然气站A，需铺设管理到用气单位E各点是中间加压站，各线路的费用如图所标注（单位：万元，试设计费用最低的线路。B1B11513C1752 D17A57B2105C214E1110B3634D2C3一艘货轮在A港装货后驶往F港，中途需靠港加油、加淡水三次，从A港到F港3个码头F，试求最合30303030

1 2 3C150206030F1A5045B1B230604030C2C3405025D1D22040F2F3F《运筹学》习题集4ABC求最大回报。投资额及收益0101234A041486066B042506066C0646878761000S1与投入机器数Y1的关系为0.7S2与投入机器数Y2的关系为S2＝5Y2，机器0.9；请制定一个五年计划，使总产量最大。31 2 3 3AA的生产成本费用为x2xA13个月的需求量分d。现设开始时第一个月月初存货s＝0，第三个月的月末存s31 2 3 1所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，242所示。表1表26t，问应运输每种产品各多少件可使总利润最大。产品重量（t/件）利润（千元/件）128023130341809《运筹学》习题集《运筹学》习题集PAGEPAGE12用动态规划方法求解maxz4x1

9x2

2x232x4x

10x 1x ,

2 3,x01 2 3第五章 存储论800tt2000t0.2%300元，求最佳订购批量、经济周期与最小费用。150，0000.2元，不允许缺货，试比较每次订购费为1,000元或100小费用。某拖拉机厂生产一种小型拖拉机，每月可生产1000需要量为每年4,00015,000为10元，允许缺货（缺货费为20台月，求经济生产批量、经济周期与最小费用。81005元/月件。在不允许缺货条件下，比较生产速度分别为每月20件和40经济周期与最小费用。4,00015010%500元。求：不允许缺货条件下的最优存贮策略；允许缺货（100元/件年）条件下的最优存贮策略。150件，订购费为每次400元，存贮费为0.96元/件月，并不允许缺货。求经济订购批量、经济周期与最小费用；10%，求这时的最优存贮策略。15,000801元/个年，不允1000510004.9元。求该公司的最优采购策略。10,0002,000元，存贮费率为20%2,0001002,00080元。求最优采购策略。批量（件）0≤Q＜10000 10000≤Q＜30000单价（元） 1.00 0.98批量（件）0≤Q＜10000 10000≤Q＜30000单价（元） 1.00 0.980.96Q≥500000.94EOQ订购费、但