运筹学练习题2014

1运筹学练习题20141.用单纯形法求解以下线性规划问题。minf=-2x1-x2+3x3-5x4s.t.x1+2x2+4x3-x4≤62x1+3x2-x3+x4≤12x1+x3+x4≤4x1,x2,x3,x4≥02.用大M法求解以下线性规划问题。maxz=-3x1+x2s.t.x1+3x2≥32x1-3x2≥62x1+x2≤8-4x1+x2≥-16x1,x2≥03.有个玩具制造商在不同的地方开设了三个工厂，从这些厂将汽车零件运至设在全国各地的四个仓库，并希望运费最小。下表列出了运价及三个厂的供应量和四个仓库的需求量。1234供应量121355022241303143270需求量405025354.请用分支定界法求解下列整数规划问题，x1和x2均为整数。maxz=5x1+8x2s.t.x1+x2≤65x1+9x2≤45x1,x2≥05.某工程队三年内有4项工程可以选择施工，每项工程的预期收入和支出以及每年可用的资金如下表所示。假设每项工程都要在3年内完成，问如何选择方案使得总收入最大（只建模，不求解）。第1年第2年第3年预期收入142220235430356515437425可用资金1214126.某小型化工厂生产A、B、C三种化肥，每吨加工工时消耗分别为6小时、8小时和10小仓库运价工厂150150年份投入工程2时，化工厂每月工时为200小时。A、B、C每吨利润分别为400元、700元和800元，每月销量分别为11、10、5吨。该化工厂的经营目标是：首先，每月的利润不能低于1.5万；其次，要能充分利用生产能力；最后，产量以销量为准。试制订生产计划。（只建模，不求解）7.用图解法解决下列目标规划问题：minz=p1(d1-+d1+)+p2d2-+p3d3+s.t.x1+x2+d1--d1+=103x1+4x2+d2--d2+=508x1+10x2+d3--d3+=300x1,x2,di-,di+≥0(i=1,2,3)8.求下图中A到F的最短路线及最短距离。9.出租车司机清晨从车站（标点V1）赶往飞机场（标点V10），请寻找行车时间最短路线。10.某产品生产项目分解为a,b,c,…l各项活动，各个活动的内容、紧前工序以及时间表如下表所示。试绘制网络图，找出关键路线，并计算所有工序的最早开始时间、最晚开始时间、最早完成时间、最晚完成时间以及时差。活动活动内容紧前工序所需时间（周）a市场调查-4b资金筹备-10c可行性分析a3d产品设计a6e产品研制d8f制订成本计划c,e2AB3B2C1C3D1D2D3E1E2FC2B135459543175184644242697512v1v2v7v10v9v3v8v6v4v544742555124910815556131533g制订生产计划f3h购买设备b,g2i购买原材料b,g8j调试设备h5k招聘人员g2l准备投产i,j,k1在上例中，可以通过增加人员等方式加快完工时间，但直接费用也会增加。相关信息如下表所示（费用单位：元）。工序正常情况加急处理缩短一天工期增加的直接费用kijTij正常完工时间Cij工序直接费用Tij’最快完成时间Cij’工序直接费用a(1,2)4200042000-b(1,7)10100062600400c(2,4)3250023000500d(2,3)65000472001100e(3,4)810000412400600f(4,5)25001700200g(5,6)35002850350h(7,8)2200001210001000i(7,9)815000418000750j(8,9)580031600800k(6,9)2300013700700l(9,10)1160011600-