线性规划1
习题一
1.1 用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
(1) min z =6x1+4x2 (2) max z =4x1+8x2
st. 2x1+ x2≥1 st. 2x1+2x2≤10
3x1+ 4x2≥1.5 -x1+ x2≥8
x1, x2≥0 x1, x2≥0
(3) max z = x1+ x2 (4) max z =3x1-2x2
st. 8x1+6x2≥24 st. x1+x2≤1
4x1+6x2≥-12 2x1+2x2≥4
2x2≥4 x1, x2≥0
x1, x2≥0
(5) max z =3x1+9x2 (6) max z =3x1+4x2
st. x1+3x2≤22 st. -x1+2x2≤8
-x1+ x2≤4 x1+2x2≤12
x2≤6 2x1+ x2≤16
2x1-5x2≤0 x1, x2≥0
x1, x2≥0
1.2. 在下列线性规划问题中,找出所有基本解,指出哪些是基本可行解并分别代入目标函数,比较找出最优解。
(1) max z =3x1+5x2 (2) min z =4x1+12x2+18x3
st. x1 + x3 =4 st. x1 +3x3- x4 =3
2x2 + x4 =12 2x2+2x3 - x5=5
3x1+ 2x2 + x5 =18 xj ≥0 (j=1,…,5)
xj ≥0 (j=1,…,5)
1.3. 分别用图解法和单纯形法求解下列线性规划问题,并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。
(1) max z =10x1+5x2
st. 3x1+4x2≤9
5x1+2x2≤8
x1, x2≥0
(2) max z =100x1+200x2
st. x1+ x2≤500
x1 ≤200
2x1+6x2≤1200
x1, x2≥0
9
1.4. 分别用大M法和两阶段法求解下列线性规划问题,并指出问题的解属于哪一类:
(1) max z =4x1+5x2+ x3 (2) max z =2x1+ x2+ x3
st. 3x1+2x2+ x3≥18 st. 4x1+2x2+2x3≥4
2x1+ x2 ≤4 2x1+4x2 ≤20
x1+ x2- x3=5 4x1+8x2+2x3≤16
xj ≥0 (j=1,2,3) xj ≥0 (j=1,2,3)
(3) max z = x1+ x2 (4) max z =x1+2x2+3x3-x4
st. 8x1+6x2≥24 st. x1+2x2+3x3=15
4x1+6x2≥-12 2x1+ x2+5x3=20
2x2≥4 x1+2x2+ x3+ x4=10
x1, x2≥0 xj ≥0 (j=1,…,4)
(5) max z =4x1+6x2 (6) max z =5x1+3x2+6x3
st. 2x1+4x2 ≤180 st. x1+2x2+ x3≤18
3x1+2x2 ≤150 2x1+ x2+3x3≤16
x1+ x2=57 x1+ x2+ x3=10
x2≥22 x1, x2≥0,x3无约束
x1, x2≥0
1.5 线性规划问题max z=CX,AX=b,X≥0,如X*是该问题的最优解,又λ>0为某一常数,分别讨论下列情况时最优解的变化:
(1) 目标函数变为max z=λCX;
(2) 目标函数变为max z=(C+λ)X;
(3) 目标函数变为max z=C
X,约束条件变为AX=λb。
1.6 下表中给出某求极大化问题的单纯形表,问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有:
(1) 表中解为唯一最优解;
(2) 表中解为无穷多最优解之一;
(3) 表中解为退化的可行解;
(4) 下一步迭代将以x1替换基变量x5 ;
(5) 该线性规划问题具有无界解;
(6) 该线性规划问题无可行解。
x1 x2 x3 x4 x5
x3 d 4 a1 1 0 0
x4 2 -1 -5 0 1 0
x5 3 a2 -3 0 0 1
cj -zj c1 c2 0 0 0
1.7 战斗机是一种重要的作战工具,但要使战斗机发挥作用必须有足够的驾驶10
员。因此生产出来的战斗机除一部分直接用于战斗外,需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj(j=1,…,n),又每架战斗机每年能培训出k名驾驶员,问应如何分配每年生产出来的战斗机,使在n年内生产出来的战斗机为空防作出最大贡献?
1.8. 某石油管道公司希望知道,在下图所示的管道网络中可以流过的最大流量是多少及怎样输送,弧上数字是容量限制。请建立此问题的线性规划模型,不必求解。
1.9. 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下: 班 次 时 间 所需人数
1 6:00-10:00 60
2 10:00-14:00 70
3 14:00-18:00 60
4 18:00-22:00 50
5 22:00-2:00 20
6 2:00-6:00 30
设司机和乘务人员分别在各时间区段一开始时上班,并连续工作八小时,问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。
1.10 某班有男生30人,女生20人,周日去植树。根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多?请建立此问题的线性规划模型,不必求解。
1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。
问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立此问题的线性规划的数学模型。
甲 乙 丙 原料成本(元/千克) 每月限量(千克)
A ≥60%≥15 2.00 2000
B 1.50 2500
C ≤20%≤60 ≤50 1.00 1200
加工费(元/千克 0.50 0.40 0.30
售 价 3.40 2.85 2.25
1.12. 某商店制定7-12月进货售货计划,已知商店仓库容量不得超过500件, 11
6月底已存货200件,以后每月初进货一次,假设各月份此商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收入最多?请建立此问题的线性规划模型,不必求解。
月 份 7 8 9 10 11 12
买进单价 28 24 25 27 23 23
1.13 .某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日,春夏季4000人日,如劳动力本身用不了时可外出干活,春夏季收入为2.1元/人日,秋冬季收入为1.8元/人日。该农场种植三种作物:大豆、玉米、小麦,并饲养奶牛和鸡。种作物时不需要专门投资,而饲养动物时每头奶牛投资400元,每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草,并占用人工秋冬季为100人日,春夏季为50人日,年净收入400元/每头奶牛。养鸡时不占土地,需人工为每只鸡秋冬季需0.6人日,春夏季为0.3人日,年净收人为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡,牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。
1.14 某厂接到生产A、B两种产品的合同,产品A需200件,产品B需300件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段,产品A每件需要2小时,产品B每件需要4小时。机械加工阶段又分粗加工和精加工两道工序,每件产品A需粗加工4小时,精加工10小时;每件产品B需粗加工7小时,精加工12小时。若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时,精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。此外在粗加工阶段允许设备可进行500小时的加班生产,但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料,为该厂制订一个成本最低的生产计划。
该三种产品l季度初无库存,要求在4季度末各库存150件。已知该厂每季度生产工时为15000小时,生产I、Ⅱ、Ⅲ产品每件分别需时2、4、3小时。因更换工艺装备,产品I在2季度无法生产。规定当产品不能按期交货时,产品I,Ⅱ每12
件每迟交一个季度赔偿20元,产品Ⅲ赔偿10元;又生产出来产品不在本季度交货的,每件每季度的库存费用为5元。问:该厂应如何安排生产,使总的赔偿加库存的费用为最小(要求建立数学模型,不需求解)。
1.16 某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成,或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成,或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元,他们每周都工作48小时,但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务,该公司需要每周总有效工作小时数为:第一项工作10000小时。第二项工作20000小时,第三项工作30000小时。又能招收到的工人数为技工不超过400人,力工不超过800人。试建立数学模型,确定招收技工和力工各多少人。使总的工资支出为最少(建立数学模型,不需求解)。
复习思考题
1.17 试述线性规划数学模型的结构及各要素的特征。
1.18 求解线性规划问题时可能出现哪几种结果,哪些结果反映建模时有错误。
1.19 什么是线性规划问题的标准型式,如何将一个非标准型的线性规划问题转化为标准型式。
1.20 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。
1.21 试述单纯形法的计算步骤,如何在单纯形表上去判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
1.22 如果线性规划的标准型式变换为求目标函数的极小化min Z,则用单纯形法计算时如何判别问题已得到最优解。
1.23 在确定初始可行基时,什么情况下要在约束条件中增添人工变量,在目标函数中人工变量前的系数为(一M)的经济意义是什么。
1.24 什么是单纯形法计算的两阶段法,为什么要将计算分两个阶段进行,以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。
1.25 简述退化的含义及处理退化的勃兰特规则。
1.26 举例说明生产和生活中应用线性规划方面,并对如何应用进行必要描述。
1.27 判断下列说法是否正确:
(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的; (b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大;
(c)线性规划问题的每一个基解对应可行域的一个顶点;
(d)如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点; 13
(e)对取值无约束的变量xj,通常令xj=xjˊ-xj",其中xjˊ≥0,xj"≥0,在用单纯形法求得的最优解中有可能同时出现xjˊ>0,xj">0。
(f)用单纯形法求解标准型式的线性规划问题时,与大于0对应的变量都可以被选作换人变量;
(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负;
(h) 单纯形法计算中,选取最大正检验数对应的变量为换入变量,将使目标函数值得到最快的增长;
(i)一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果;
(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示;
(k)若Xˊ、X"分别是某一线性规划问题的最优解,则它们的线性组合也是该线性规划问题的最优解。
14