运筹学习题运筹学练习题(2)

⑦ 求解一道运筹学的线性规划问题模型的建立

某农场有100公顷土地及15000元资金可用于发展生产.农场劳动力情况为秋冬季3500人日,春夏季4000人日,如劳动力本身用不了时可外出干活,春夏季收入为2.1元/人日,秋冬季收入为1.8元/人日.该农场种植三种作物：大豆、玉米、小麦,并饲养奶牛和鸡.种作物时不需要专门投资,而饲养动物时每头奶牛投资400元,每只鸡投资3元.养奶牛时每头需拨出1.5公顷土地种饲草,并占用人工秋冬季100人日,春夏季为50人日,年净收入400元/每头奶牛.养鸡时不占用土地,需人工为每只鸡秋冬季需0.6人日,春夏季为0.3人日,年净收入为2元/每只鸡.农场现有鸡舍允许最多养3000只鸡,牛栏允许最多养32头奶牛.三种作物每年需要的人工及收入情况如表所示.试决定该农场的经营方案,使年净收入为最大. 大豆玉米麦子

秋冬季需人日数20 35 10 春夏季需人日数50 75 40

年净收入（元/公顷） 175 300 120

设大豆、玉米、麦子各所需土地x1、x2、x3（公顷）,牛和鸡各饲养x4和x5（只）,根据题意可以列出下表： 见下图点击可以放大.

目标函数 Max z=175x1+300x2+120x3+400x4+2x5; 满足条件 x1+x2+x3+1.5x4<=100;

400x4+3x5<=15000;

20x1+35x2+10x3+100x4+0.6x5<=3500; 50x1+75x2+40x3+50x4+0.3x5<=4000; x4<=32; x5<=3000; x1,??,x5>=0

⑧ 对某厂I、II、III三种产品下一年各季度的合同预订数如表1所示。 产品季度 1 2 3 4

I 1500 1000 2000 1200 II 1500 1500 1200 1500 III 1000 2000 1500 2500

该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时为15000.8小时，生产I、II、III产品每件分别需要2.1、4.3、3.7小时。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季度赔偿20.5元，产品III赔10.8元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5.1元。问该厂应如何安排生产，使总的赔偿加库存的费用为最小

解：设xij为第j季度产品i的产量，sij为第j季度末产品i的库存量，dij为第j季度产品i的需求量。

下面为期末考试第一大题题库答案，可缩印

① 医院，2点开始每时段人数x i（1….6）

（1）x1+x2>=10; x2+x3>=15; x3+x4>=25;

x4+x5>=20; x5+x6>=18; x1+x6>=12; x1,x2,x3,x4,x5,x6>=0

（2）minz=(x1+x2+x3+x4+x5+x6)*8*10+(x1'+x2'+x3'+x4'+x5'+x6')*8*15 x1+x2+x1'+x2'>=10; x2+x3+x2'+x3'>=15; x3+x4+x3'+x4'>=25; x4+x5 +x4'+x5'>=20; x5+x6+x5'+x6'>=18; x1+x6 +x1'+x6'>=12; x1,x2,x3,x4,x5,x6,x1',x2',x3,'x4',x5',x6'>=0

② 30万投资，i年投资J项目

max z=1.2x31+1.6x23+1.4x34

x11+x12=300000 x21+x23=1.2x11 x31+x34=1.2x21+1.5x12 x12<=150000 x23<=200000 x34<=100000 x11,x12,x21,x23,x31,x34>=0

③ 糖果厂ABC原料，Xij，糖果j原料

Max z = 0.9X11+1.4X12+1.9X13+ 0.45X21+0.95X22+1.45X23 -0.05X31+0.45X32+0.95X33 Xij>0 X11+X21+X31<2000 X12+X22+X32<2500 X13+X23+X33<1200 X11/(X11+X12+X13)>0.6 X13/(X11+X12+X13)<0.20 X21/(X21+X22+X23)>0.15 X23/(X21+X22+X23)<0.6 X33/(X31+X32+X33)<0.5

④ 饲料700蛋白，Xi，i为饲料种类（18x5）

⑤ 杂粮批发，5000担，进货Xi，出货Yi，i=1.2.3

Max=3250-0.15y1+3.25y2+2.95y3-2.9x3-2.85x1 2.85x1<=2万+3.1y1 1千+x1-y1<=5千 Y2<=1千+x1-y1 y3<=1千+x1-y1-y2 Y3=x1+x3-y1-y2-1千 y1<=1千 Xi，yi>=0

⑥ Xi（i=1..5）1.2.3需土地，4.5牛鸡

Max z=175x1+300x2+120x3+400x4+2x5; x1+x2+x3+1.5x4<=100;400x4+3x5<=15000; 20x1+35x2+10x3+100x4+0.6x5<=3500; 50x1+75x2+40x3+50x4+0.3x5<=4000; x4<=32;x5<=3000; x1,……,x5>=0

（7）1.2.3种产品，1季度无库存，4末150件 xij，i产量，sij，j季度末i库存，dij，i需求

〈=取d+ 〉=取d- AB都做或不做Xa-Xb=0 AB不同时做

A优先B Xa-Xb>=0

（运输问题）

闭合回路检验数要为正，

闭合回路中，选最小的，+的加最小，-的减最小 （指派）没有圈0的行打钩 已打钩行所有含去0元素列打钩 打钩列含去0元素行打钩，然后重复 没有打钩行画横线，打钩列竖线 没有被线覆盖找最小元素

打钩行减去最小，打钩列加最小 人少任务多加人，人多任务少加任务 前向弧>0 ，后向弧不为0

取值 调整

前向弧 取差值 +最小值 后向弧 直接取流量 减最小值

1所有的非基变量等于0。

2引入的松驰变量，在目标函数中的系数为0。 3Xj为自由变量，引进Xj,Xj〞,同时令Xj＝Xj′－Xj〞。 4．用单纯型法求解时当基变量检验数δj_≤_0时 5．用大M法，系数应为－M。

6可以根据最终_表中人工变量不为零判断线性规划问题无解。 7．在线性规划标准形式中，所有基变量的目标函数系数为0。 8一般可以加入人工变量构造可行基。 9基变量时应遵循最小比值θ法则。

10．标准型是基为单位矩阵，基变量的目标函数系数为0。 11问题无解时情况下，单纯形迭代应停止。 12求极小值，人工变量取M 13.大M法中，M表示充分大正数。 14目标规划，优先因子

15 m供应地n个需求地平衡条件为 ?ai=?bi

i?1mnj?1

16检验数为1，运费增加1。

17检验数出现负值的点闭回路内调整。 18在运输问题，基变量处Cij=ui+Vj。

nnm19指?ai_＞?bi的运输问题、?ai_＜?bi的运输问题。

i?1mj?1i?1j?120．转角点所对应的变量必为基变量。 21． (2，2)调整量300_ 300，100.300 400 600.300。

22，－2的含义该检验数所在格单位调整量。 23表上作业法，一次1个“入基变量”。 24“出基变量”的个数为1个 25出现退化，则填入数字0 26运输问题模型，方程数N+M个。

27n任务n人完成，取值为1的变量数为n个。 28匈牙利法，配元应是独立零元素_。 29图的要素是点、点与点之间构成的边 30用边或有向边某种特定的关系。

31最短路0≤fij≤cij逐步推算，标记平衡和最短路线。