文档介绍：该【运筹学习题集(第二章) 】是由【布罗奇迹】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【运筹学习题集(第二章) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学习题集(第二章)
2
判断题
判断正误,如果错误请更正
第二章线形规划的对偶理论
原问题第i个约束是<=约束,则对偶变量yi>=0.
互为对偶问题,或则同时都有最优解,或则同时都无最优解.
原问题有多重解,对偶问题也有多重解.
对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.
原问题无最优解,则对偶问题无可行解.
设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是最优解.
3
第二章线性规划的对偶理论
如果决策变量数列相等的两个线规划的最优解相同,则两个线性规划A约束条件相同B目标函数相同C最优目标函数值相同D以上结论都不对
对偶单纯形法的最小比值规则是为了保证A使原问题保持可行B使对偶问题保持可行C逐步消除原问题不可行性D逐步消除对偶问题不可行性
互为对偶的两个线性规划问题的解存在关系A若最优解存在,则最优解相同B原问题无可行解,则对偶问题也无可行解C对偶问题无可行解,原问题可能无可行解D一个问题无界,则另一个问题无可行解E一个问题无可行解,则另一个问题具有无界解
已知规范形式原问题(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)
4
原问题与对偶问题都有可行解,则A原问题有最优解,对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个问题有最优解,另一个问题具有无界解D原问题与对偶问题都有最优解
计算题
线性规划问题和对偶问题
minz=3x1+2x2+x3
+x2+x315(1)
2x1-x2+x39(2)
-x1+2x2+2x38(3)
x1x2x30
1、写出题目中线性规划问题的对偶问题;
2、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);
解答:1、写出题目中线性规划问题的对偶问题;
解:maxw=15y1+9y2+8y3
+2y2-y33(1)
y1-y2+2y32(2)
y1+y2+2y31(3)
y10、y20、y30
5
2、分别求出原始问题和对偶问题的最优解(求解的次序和方法不限);
解:先将原问题化成以下形式,则有
minz=3x1+2x2+x3
+x2+x3+x4=15(1)
-2x1+x2-x3+x5=-9(2)
-x1+2x2+2x3+x6=8(3)
x1x2x3x4x5x60
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
maxz=-x1-2x2
.-2x1+3x212(1)
-3x1+x26(2)
x1+3x23(3)
x10,x20
1、写出标准化的线性规划问题;
6
2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值;
3、写出这个(极大化)线性规划问题的对偶问题;
4、求出对偶问题的最优解和最优解的目标函数值;
5、第(2)个约束右端常数b2=6在什么范围内变化,最优解保持不变。
解答:1、写出标准化的线性规划问题:令x1*=-x1
maxz=x1*-2x2
*+3x2+x3=12(1)
3x1*+x2+x4=6(2)
-x1*+3x2-x5=3(3)
x1*x2x3x4x50
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
7
此时最优解为(X1、X2、X3、X4X5)=(-3/2,3/2,9/2,0,0)maxz=-3/2
3、写出这个(极大化)线性规划问题的对偶问题;
minw=12y1+6y2+3y3
.-2y1-3y2+y3-1(1)
3y1+y2+3y3-2(2)
y10、y20、y30
4、求出对偶问题的最优解和最优解的目标函数值;
此时最优解为(y1、y2、y3、y4y5)=(0,1/10,-7/10,0,0)minw=-3/2
5、则有1b211,最优解不变。
:
maxz=x1+2x2+3x3+4x4
+2x2+2x3+3x420(1)
2x1+x2+3x3+2x420(2)
x1、x2、x3、x40
的最优解为(0,0,4,4)T,最优值为Z=28。请用互补松弛定理计算其对偶问题的最优解。
解答:首先写出此LP问题的对偶问题为:
minw=20y1+20y2
+2y21(1)
2y1+y22(2)
2y1+3y23(3)
3y1+2y24(4)
y1、y2、0
将上述对偶问题的化成标准型,取松弛变量分别为v1、v2、、v3、v4,则有
minw=20y1+20y2
8
+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
,生产每种产品要消耗的各种原料
数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各
种原料的限量如下表所示。
写出原料限制条件下利润最大化的线性规划模型;
写出以上问题的对偶问题;
已知利润最大的线性规划问题的最优解是产品A生产120件,产品B不生产,产品C生产52件,用互补松弛关系求四种原料的影子价格。
9
原料消耗
(吨/件)
产品
A
产品
B
产品
C
原料限量
(吨)
原料甲
12
8
10
2400
原料乙
6
10
15
1500
原料丙
15
18
——
1800
原料丁
——
20
22
2000
产品利润
(万元/件)
120
180
210
解答:一个工厂用四种原料生产三种产品,生产每种产品要消耗的各种原料
数量(表中“—”表示相应的产品不需要这种原料)、各种产品的利润以及各
种原料的限量如下表所示。
写出原料限制条件下利润最大化的线性规划模型;
11