二、填空选择题:(每空格2分,共16分)
1、线性规划的解有划的唯一最优解、无穷多最优解、无界解和无可行解四种。
2、在求运费最少的调度划的运划的输问题中,如划的果某划的一非基变量的检验数为4,则说明如果在该空格中增加一个运量运费将增加划的4 。
3、“如果线性规划的原问题存在可行解,则其对划的偶问题一定存在可行解”,这句话对还是划的错?错
4、如果某一整数规划:
MaxZ=X划的1+X2划的
X1+9/1划的2≤1/3
X1,X2≥0且均为整数
所对应的线性规划(松弛问题)的最优划的解为X1=3/2,X2=10/3,MaxZ=6/29,我们现在划的要对X1进行分枝,划的应该分为X1≤1和X1≥2。
5、在用逆向解法求动态规划时,f k(s k)的含义是:从第k个阶段到第n个阶段的最优解。
6.假设某线性规划的可行解的集合为D,而其所对应的整数规划的可行解集合为B,那么D 和B的关系为 D 包含 B
7.已知下表是制订生产计划问题的一张LP最优单纯形表(极大化问题,约束条
问:(1)写出B-1=
?
?
?
?
?
?
?
-
-
-
1
3/2
0.
3/1
3
1
2
(2)对偶问题的最优解: Y=(5,0,23,0,0)T
8. 线性规划问题如果有无穷多最优解,则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______;
9. 极大化的线性规划问题为无界解时,则对偶问题_无解_________;
10. 若整数规划的松驰问题的最优解不符合整数要求,假设X
i =b
i
不符合整数要
求,INT(b
i )是不超过b
i
的最大整数,则构造两个约束条件:Xi≥INT(b
i
)+
1 和 Xi≤INT(b
i
),分别将其并入上述松驰问题中,形成两个分支,即两个后继问题。
11. 知下表是制订生产计划问题的一张LP 最优单纯形表(极大化问题,约束条
问:(1)对偶问题的最优解: Y =(4,0,9,0,0,0)T (2)写出B -1=
????? ?
?611401102
二、计算题(60分)
1、已知线性规划(20分)
MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤8
1,X 2≥0
2)若C 2从4变成5,最优解是否会发生改变,为什么?
3)若b 2的量从12上升到15,最优解是否会发生变化,为什么?
4)如果增加一种产品X 6,其P 6=(2,3,1)T ,C 6=4该产品是否应该投产?为什么? 解:
1)对偶问题为
Minw=5y1+12y2+8y3 y1+2y2+3y 3≥3
y1+4y2+2y 3≥4 y1,y2≥0
2)当C 2从4变成5时, σ4=-9/8 σ5=-1/4
由于非基变量的检验数仍然都是小于0的,所以最优解不变。 3)当若b 2的量从12上升到15 X
=
9/8 29/8 1/4
由于基变量的值仍然都是大于0的,所以最优解的基变量不会发生变化。 4)如果增加一种新的产品,则 P 6’=(11/8,7/8,-1/4)T σ6=3/8>0
所以对最优解有影响,该种产品应该生产
2、已知运输问题的调运和运价表如下,求最优调运方案和最小总费用。(共15解:初始解为
计算检验数
由于存在非基变量的检验数小于0,所以不是最优解,需调整 调整为:
重新计算检验数
所有的检验数都大于等于0,所以得到最优解
3、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者,规定每个承包商只能且必须承包一个项目,试在总费用最小的条件下确定各个项目的承包者,总费用为多少?各承包商对工程的报价如表2所示:
答最优解为:
X= 0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
总费用为50
4.考虑如下线性规划问题(24分)
Max z=-5x1+5x2+13x3
s.t. -x1+x2+3x3≤20
12x1+4x2+10x3≤90
x1,x2,x3≥0
回答以下问题:
1)求最优解
2)求对偶问题的最优解
3)当b1由20变为45,最优解是否发生变化。
4)求新解增加一个变量x6,c6=10,a16=3,a26=5,对最优解是否有影响
5)c2有5变为6,是否影响最优解。
答:最优解为
13
2)对偶问题最优解为
Y=(1/22,1/11,68/33,0,0)T
3)
当b1=45时
X= 45/11
-11/90
由于
0,所以最优解将发生变化
2
’=(3/11,-3/4)T
4)P
6
σ6=217/20>0
所以对最优解有影响。
=6
5)当C
2
σ1=-137/33
σ4=4/11
σ5=-17/22
由于σ
大于0所以对最优解有影响
4
5.求如图所示的网络的最大流和最小截集(割集),每弧旁的数字是(c ij, f ij)。(15分)
V1
(5,0) (3,3)
(3,3)
V S (4,1)V2
(4,0)
(9,3) (8,4)
V3Vt
(6,0)
最大流为:14
V3 (6,6)
6.考虑如下线性规划问题(20分)
Max z=3x1+x2+4x3
s.t. 6x1+3x2+5x3≤9
3x1+4x2+5x3≤8
x1,x2,x3≥0
回答以下问题:
1)求最优解;
2)直接写出上述问题的对偶问题及其最优解;
3)若问题中x2列的系数变为(3,2)T,问最优解是否有变化;
4)c2由1变为2,是否影响最优解,如有影响,将新的解求出。
2)对偶问题为
Minw=9y1+8y2
6y1+3y2≥3
3y1+4y2≥1
5y1+5y2≥4
y1,y2≥0
对偶问题最优解为y1=1/5,y2=3/5
3)若问题中x2列的系数变为(3,2)T
’=(1/3,1/5)T
则P
2
σ2=-4/5<0
所以对最优解没有影响
4)c2由1变为2
σ2=-1<0
所以对最优解没有影响
7.求如图所示的网络的最大流和最小截集(割集),每弧旁的数字是(c ij, f ij)。(10分)
V1(4,4 ) V3
(9,5) (6,3)
V S(3,1) (3,0) (4,1) Vt
(5,3) (7,5)
V 2 (5,4) V 4
解:
Vt
最大流=11
8. 某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过A 、B 、C 三种设备加工。已知生产单位各种产品所需的设备台时,设备的现有加工能力及每件产品的预期利润见表:
1)建立线性规划模型,求获利最大的产品生产计划。(15分)
2)产品Ⅲ每件的利润到多大时才值得安排生产?如产品Ⅲ每件利润增加到50/6元,求最优计划的变化。(4分)
3)产品Ⅰ的利润在多大范围内变化时,原最优计划保持不变。(2分) 4)设备A 的能力在什么范围内变化时,最优基变量不变。(3分)
5)如有一种新产品,加工一件需设备A 、B 、C 的台时各为1、4、3h ,预期每件为8元,是否值得生产。(3分)
6)如合同规定该厂至少生产10件产品Ⅲ,试确定最优计划的变化。(3分) 解:1)建立线性规划模型为: MaxZ=10x1+6x2+4x3 x1+x2+x 3≤100 10x1+4x2+5x 3≤600 2x1+2x2+6x 3≤300 x j ≥0,j=1,2,3
获利最大的产品生产计划为:X*=(x1,x2,x3,x4,x5,x6)’=(100/3,200/3,0,0,0,100)’ Z*=2200/3 2)产品Ⅲ每件利润到20/3才值得生产。如果产品Ⅲ每件利润增加到50/6元,最优计划的变化为:X*=(x1,x2,x3,x4,x5,x6)’=(175/6,275/6,25,0,0,0)’ Z*=775 3)产品Ⅰ的利润在[6,15]变化时,原最优计划保持不变。 4)设备A 的能力在[60,150]变化时,最优基变量不变。 5)新产品值得生产。
6)最优计划的变化为:X*=(x1,x2,x3,x4,x5,x6)’=(190/6,350/6,10,0,0,60 )’ Z*=706.7 9. 给出成性规划问题:(15分) Min z=2x 1+3x 2+6x 3
x 1+2x 2+x 3≥2 -2x 1+x 2+3x 3≤-3 x j ≥0 j=1,…,4
要求:
(1)写出其对偶问题。(5分)
(2)利用图解法求解对偶问题。(5分)
(3)利用(2)的结果,根据对偶问题性质写出原问题最优解。(5分) 解:1)该问题的LD 为: MaxW=2y1-3y2 y1-2y 2≤2 2y1+y 2≤3 y1+3y 2≤6 y1≥0,y 2≤0
2)用图解法求得LD 的最优解为:Y*=(y1,y2)’=(8/5,-1/5)’ W*=19/5 3)由互补松弛定理:
原问题的最优解为:X*=(x1,x2,x3)’=(8/5,1/5,0)’
10. 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量,各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于
A1-B3和B4 28t 和4t A2-B1和B4 16t 和4t A3-B2和B4 28t 和16t 最小总运费为:460元
11. 求解下列0-1规划问题
maxz=3x 1+2x 2-5x 3-2x 4+3x 5
x 1+x 2+x 3+2x 4+x 5≤4 7x 1+3x 3-4x 4+3x 5≤8 11x 1-6x 2+3x 4-3x 5≥3 x j =0或1 (j=1, (5)
解:最优解为:x1=x2=1,其他为0 ,最优目标函数值为5