运筹学习题集第二章.docx
- 文档编号:13676069
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:12
- 大小:22.06KB
运筹学习题集第二章.docx
《运筹学习题集第二章.docx》由会员分享,可在线阅读,更多相关《运筹学习题集第二章.docx(12页珍藏版)》请在冰点文库上搜索。
运筹学习题集第二章
运筹学习题集(第二章)
判断题
判断正误,如果错误请更正
第二章线形规划的对偶理论
1.原问题第i个约束是<=约束,则对偶变量yi>=0.
2.互为对偶问题,或则同时都有最优解,或则同时都无最优解.
3.原问题有多重解,对偶问题也有多重解.
4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.
5.原问题无最优解,则对偶问题无可行解.
6.设X,Y分别为{minZ=CX|AX>=b,X>=0}和{maxw=Yb|YA<=C,Y>=0}的可行解,则有
(1)CX<=Yb;
(2)CX是w的上界;
(3)当X,Y为最优解,CX=Yb;
(4)当CX=Yb时,有YXs+YsX=0;
(5)X为最优解且B是最优基时,则Y=CBB-1是最优解;
(6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解,则X=-λs是最优解.
7.原问题与对偶问题都可行,则都有最优解.
8.原问题具有无界解,则对偶问题可行.
9.若X,Y是原问题与对偶问题的最优解.则X=Y.
10.若某种资源影子价格为0,则该资源一定有剩余.
11影子价格就是资源的价格.
12.原问题可行对偶问题不可行,可用对偶单纯形法计算.
13.对偶单纯形法比值失效说明原问题具有无界解.
14.对偶单纯形法是直接解对偶问题的一种解法.
15.减少一个约束,目标值不会比原来变差.
16.增加一个约束,目标值不会比原来变好.
17增加一个变量,目标值不会比原来变差.
18.减少一个非基变量,目标值不变.
19.当Cj(j=1,2,3,……,n)在允许的最大范围内同时变化时,最优解不变。
选择题
在下列各题中,从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第二章线性规划的对偶理论
1.如果决策变量数列相等的两个线规划的最优解相同,则两个线性规划A约束条件相同B目标函数相同C最优目标函数值相同D以上结论都不对
2.对偶单纯形法的最小比值规则是为了保证A使原问题保持可行B使对偶问题保持可行C逐步消除原问题不可行性D逐步消除对偶问题不可行性
3.互为对偶的两个线性规划问题的解存在关系A若最优解存在,则最优解相同B原问题无可行解,则对偶问题也无可行解C对偶问题无可行解,原问题可能无可行解D一个问题无界,则另一个问题无可行解E一个问题无可行解,则另一个问题具有无界解
4.已知规范形式原问题(max)的最优表中的检验数为(λ1,λ2,……λn),松弛变量的检验数为(λn+1,λn+2,……λn+m),则对偶问题的最优解为A—(λ1,λ2,……λn)B(λ1,λ2,……λn)C—(λn+1,λn+2,……λn+m)D(λn+1,λn+2,……λn+m)
5.原问题与对偶问题都有可行解,则A原问题有最优解,对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个问题有最优解,另一个问题具有无界解D原问题与对偶问题都有最优解
计算题
线性规划问题和对偶问题
2.1对于如下的线性规划问题
minz=3x1+2x2+x3
s.t.x1+x2+x3
15
(1)
2x1-x2+x3
9
(2)
-x1+2x2+2x3
8(3)
x1x2x3
0
1、写出题目中线性规划问题的对偶问题;
2、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);
解答:
1、写出题目中线性规划问题的对偶问题;
解:
maxw=15y1+9y2+8y3
s.t.y1+2y2-y3
3
(1)
y1-y2+2y3
2
(2)
y1+y2+2y3
1(3)
y1
0、y2
0、y3
0
2、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);
解:
先将原问题化成以下形式,则有
minz=3x1+2x2+x3
s.t.x1+x2+x3+x4=15
(1)
-2x1+x2-x3+x5=-9
(2)
-x1+2x2+2x3+x6=8(3)
x1x2x3x4x5x6
0
X1
X2
X3
X4
X5
X6
右端
z
-3
-2
-1
0
0
0
X4
1
1
1
1
0
0
15
X5
-2
1
[-1]
0
1
0
-9
X6
-1
2
2
0
0
1
8
X1
X2
X3
X4
X5
X6
右端
z
-1
-3
0
0
-1
0
9
X4
-1
2
0
1
1
0
6
X3
2
-1
1
0
-1
0
9
X6
[-5]
4
0
0
2
1
-10
X1
X2
X3
X4
X5
X6
右端
z
0
-19/5
0
0
-7/5
-1/5
11
X4
0
6/5
0
1
3/5
-1/5
8
X3
0
3/5
1
0
-1/5
2/5
5
X1
1
-4/5
0
0
-2/5
-1/5
2
原始问题的最优解为(X1X2X3X4X5X6)=(2,0,5,8,0,0),minz=11
对偶问题的最优解为(y1y2y3y4y5y6)=(0,7/5,-1/5,0,19/5,0),maxw=11
2.2对于以下线性规划问题
maxz=-x1-2x2
s.t.-2x1+3x2
12
(1)
-3x1+x2
6
(2)
x1+3x2
3(3)
x1
0,x2
0
1、写出标准化的线性规划问题;
2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值;
3、写出这个(极大化)线性规划问题的对偶问题;
4、求出对偶问题的最优解和最优解的目标函数值;
5、第
(2)个约束右端常数b2=6在什么范围内变化,最优解保持不变。
解答:
1、写出标准化的线性规划问题:
令x1*=-x1
maxz=x1*-2x2
s.t.2x1*+3x2+x3=12
(1)
3x1*+x2+x4=6
(2)
-x1*+3x2-x5=3(3)
x1*x2x3x4x5
0
2、(6分)用单纯形表求出这个线性规划问题的最优解和最优的目标函数值
x1*
X2
X3
X4
X5
R
右端
Z’
1-M
3M-2
0
0
-M
0
3M
X3
2
3
1
0
0
0
12
X4
3
1
0
1
0
0
6
R
-1
[3]
0
0
-1
1
3
x1*
X2
X3
X4
X5
R
右端
Z’
1/3
0
0
0
-2/3
2/3-M
2
X3
3
0
1
0
1
-1
9
X4
[10/3]
0
0
1
1/3
-1/3
5
X2
-1/3
1
0
0
-1/3
1/3
1
x1*
X2
X3
X4
X5
R
右端
Z’
0
0
0
-1/10
-7/10
21/30-M
3/2
X3
0
0
1
-9/10
9/2
X1*
1
0
0
3/10
1/10
-1/10
3/2
X2
0
1
0
1/10
3/2
此时最优解为(X1、X2、X3、X4X5)=(-3/2,3/2,9/2,0,0)maxz=-3/2
3、写出这个(极大化)线性规划问题的对偶问题;
minw=12y1+6y2+3y3
s.t.-2y1-3y2+y3
-1
(1)
3y1+y2+3y3
-2
(2)
y1
0、y2
0、y3
0
4、求出对偶问题的最优解和最优解的目标函数值;
此时最优解为(y1、y2、y3、y4y5)=(0,1/10,-7/10,0,0)minw=-3/2
5、则有1
b2
11,最优解不变。
2.3已知LP问题:
maxz=x1+2x2+3x3+4x4
s.t.x1+2x2+2x3+3x4
20
(1)
2x1+x2+3x3+2x4
20
(2)
x1、x2、x3、x4
0
的最优解为(0,0,4,4)T,最优值为Z=28。
请用互补松弛定理计算其对偶问题的最优解。
解答:
首先写出此LP问题的对偶问题为:
minw=20y1+20y2
s.t.y1+2y2
1
(1)
2y1+y2
2
(2)
2y1+3y2
3(3)
3y1+2y2
4(4)
y1、y2、
0
将上述对偶问题的化成标准型,取松弛变量分别为v1、v2、、v3、v4,则有
minw=20y1+20y2
s.t.y1+2y2-v1=1(5)
2y1+y2-v2=2(6)
2y1+3y2-v3=3(7)
3y1+2y2-v4=4(8)
y1、y2、
0
利用互补松弛定理可知:
x3=4>0,又有x3v3=0,所以有v3=0代入(7)式
x4=4>0,又有x4v4=0,所以有v4=0代入(8)式,则有
2y1+3y2=3(9)
3y1+2y2=4(10)
从中可计算出y1=6/5、y2=1/5,则w*=28
2.4一个工厂用四种原料生产三种产品,生产每种产品要消耗的各种原料
数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各
种原料的限量如下表所示。
1、写出原料限制条件下利润最大化的线性规划模型;
2、写出以上问题的对偶问题;
3、已知利润最大的线性规划问题的最优解是产品A生产120件,产品B不生产,产品C生产52件,用互补松弛关系求四种原料的影子价格。
原料消耗
(吨/件)
产品
A
产品
B
产品
C
原料限量
(吨)
原料甲
12
8
10
2400
原料乙
6
10
15
1500
原料丙
15
18
——
1800
原料丁
——
20
22
2000
产品利润
(万元/件)
120
180
210
解答:
一个工厂用四种原料生产三种产品,生产每种产品要消耗的各种原料
数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各
种原料的限量如下表所示。
1.写出原料限制条件下利润最大化的线性规划模型;
maxz=120x1+180x2+210x3
s.t.12x1+8x2+10x3
2400
(1)
6x1+10x2+15x3
1500
(2)
15x1+18x2
1800(3)
20x2+22x3
2000(4)
x1
0,x2
0x3
0
2.写出以上问题的对偶问题;
minw=2400y1+1500y2+1800y3+2000y4
s.t.12y1+6y2+15y3
120
(1)
8y1+10y2+18y3+20y4
180
(2)
10y1+15y2+22y4
210(3)
y1
0,y2
0y3
0y4
0
3.已知利润最大的线性规划问题的最优解是产品A生产120件,产品B不生产,产品C生产52件,用互补松弛关系求四种原料的影子价格。
maxz=120x1+180x2+210x3
s.t.12x1+8x2+10x3+x4=2400
(1)
6x1+10x2+15x3+x5=1500
(2)
15x1+18x2+x6=1800(3)
20x2+22x3+x7=2000(4)
x1
0,x2
0x3
0x4
0x5
0x6
0x7
0
x4=440x5=0x6=0x7=856
minw=2400y1+1500y2+1800y3+2000y4
s.t.12y1+6y2+15y3-y5=120
(1)
8y1+10y2+18y3+20y4-y6=180
(2)
10y1+15y2+22y4-y7=210(3)
y1
0,y2
0y3
0y4
0y5
0y6
0y7
0
由互补松弛关系可知,x1x3x4x7
0,得到y5=y7=y1=y4=0
6y2+15y3=120
10y2+18y3-y6=180
15y2=210
解得y2=14y3=2.4y6=3.2
原材料甲的影子价格为:
0万元/吨
原材料乙的影子价格为:
14万元/吨
原材料丙的影子价格为:
2.4万元/吨
原材料丁的影子价格为:
0万元/吨
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 习题集 第二