最优化方法练习题答案
- 格式:docx
- 大小:299.85 KB
- 文档页数:30
练习题一
1、建立优化模型应考虑哪些要素? 答:决策变量、目标函数和约束条件。
2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。
答:针对一般优化模型()()min ()
..
0,1,2, 0,1,
,i j f x s t g x i m h x j p
≥===,讨论解的可行域D ,若存在一点*X D ∈,对于X D ∀∈ 均有*()()f X f X ≤则称*X 为优化模型最优解,最优解存在;迭代算法的收敛性是指迭代所得到的序列(1)(2)()
,,
,K X X X ,满足(1)()()()K K f X f X +≤,
则迭代法收敛;收敛的停止准则有(1)()k k x x ε+-<,
(1)()
()
k k k x x x ε+-<,
()()(1)()k k f x f x ε+-<,
()()()
(1)()()k k k f x f x f x ε+-<,()()k f x ε∇<等等。
练习题二
1、某公司看中了例中厂家所拥有的3种资源R 1、R
2、和R 3,欲出价收购(可能用于生产附加值更高的产品)。如果你是该公司的决策者,对这3种资源的收购报价是多少?(该问题称为例的对偶问题)。
解:确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。
确定目标函数 问题的目标很清楚——“收购价最小”。
确定约束条件 资源的报价至少应该高于原生产产品的利润,这样原厂家才可能卖。
因此有如下线性规划问题:123min 170100150w y y y =++
*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯形法)。
答:略。
3、用单纯形法求解下列线性规划问题:
(1)⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0
,,4322
2..min
32131
3213213
21x x x x x x x x x x x t s x x x z ; (2)⎪⎪⎩⎪⎪⎨
⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min 53243232132 i x x x x x x x x x x t s x x z i
解:(1)引入松弛变量x 4,x 5,x 6
因检验数σ2<0,故确定x 2为换入非基变量,以x 2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x 4作为换出的基变量。
因检验数σ3<0,故确定x 3为换入非基变量,以x 3的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x 5作为换出的基变量。
因检验数σj >0,表明已求得最优解:*(0,8/3,1/3,0,0,11/3)X =,去除添加的松弛变量,原问题的最优解为:*(0,8/3,1/3)X =。
(2)根据题意选取x 1,x 4,x 5,为基变量:
因检验数σ2<0最小,故确定x 2为换入非基变量,以x 2的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x 4作为换出的基变量。
因检验数σ3<0最小,故确定x 3为换入非基变量,以x 1的系数列的正分量对应去除常数列,最小比值所在行对应的基变量x 5作为换出的基变量。
因检验数σj >0,表明已求得最优解:*(9,4,1,0,0)X =。
4、分别用大M 法、两阶段法和Matlab 软件求解下列线性规划问题:
(1)⎪⎪⎩⎪⎪⎨
⎧≥≤+≥+=++=0,3263933..4min
2121212121x x x x x x x x t s x x z ; (2)⎪⎪⎩⎪⎪⎨⎧≥≥++≤++-≤++++=0,,52151565935
..121510max 321321321321321x x x x x x x x x x x x t s x x x z
解:(1)大M 法
根据题意约束条件1和2可以合并为1,引入松弛变量x 3,x 4,构造新问题。
因检验数σj>0,表明已求得最优解:*(3/5,6/5)
X 。
Matlab调用代码:
f=[4;1];
A=[-9,-3;1,2];
b=[-6;3];
Aeq=[3,1];
beq=3;
lb=[0;0];
[x,fval] = linprog(f,A,b,Aeq,beq,lb)
输出结果:
Optimization terminated.
x =
fval =
(2)大M法
引入松弛变量x4,x5,x6,x7构造新问题。
x=,所以原问题无可行解。单纯形表计算略;当所有非基变量为负数,人工变量
7
请同学们自己求解。
Matlab调用代码:
f=[-10;-15;-12];
A=[5,3,1;-5,6,15;-2,-1,-1];
b=[9;15;-5];
lb=[0;0;0];
x = linprog(f,A,b,[],[],lb) 输出结果: 原题无可行解。
5、用内点法和Matlab 软件求解下列线性规划问题:
解:用内点法的过程自己书写,参考答案:最优解[4/3 7/3 0]X =;最优值5 Matlab 调用代码: f=[2;1;1]; Aeq=[1,2,2;2,1,0]; beq=[6;5]; lb=[0;0;0];
[x,fval] = linprog(f,[],[],Aeq,beq,lb) 输出结果:
Optimization terminated. x = fval =
6、用分支定界法求解下列问题:
(1) ⎪⎩⎪⎨⎧≥≤+≤++=且均为整数0,45956..85max
2121212
1x x x x x x t s x x z ; (2)⎪⎩⎪⎨⎧≥≤+≤+-+=为整数
且12
121212
10,35763..97max
x x x x x x x t s x x z 解:(1)调用matlab 编译程序bbmethod
f=[-5; -8];G=[1 1;5 9];h=[6; 45]
[x,y]=bbmethod(f,G ,h,[],[],[0;0],[],[1;1],1) x =
3 3 y =
-39
最优解[3 3];最优值39