内容发布更新时间 : 2024/12/23 12:48:47星期一 下面是文章的全部内容请认真阅读。

练习题一

1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。

minf(x)tgi?x??0,i?1,2,Lm，讨论解的可行域D，若存在一点答：针对一般优化模型s.. hj?x??0,j?1,L,pX*?D，对于?X?D 均有f(X*)?f(X)则称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X(1),X(2),L,X(K)L ，满足f(X(K?1))?f(X(K))，则迭代法收敛；收敛的停止准则有x(k?1)?x(k)??，

x(k?1)?x(k)x(k)??，

f?x(k?1)??f?x(k)???，

f?x(k?1)??f?x(k)?f?x(k)???，?f?x(k)???等等。

练习题二

1、某公司看中了例中厂家所拥有的3种资源R1、R2、和R3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例的对偶问题）。

解：确定决策变量 对3种资源报价y1,y2,y3作为本问题的决策变量。

确定目标函数 问题的目标很清楚——“收购价最小”。

确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

因此有如下线性规划问题：min w?170y1?100y2?150y3

*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。

答：略。

3、用单纯形法求解下列线性规划问题：

minz?4?x2?x3z?x1?x2?x3?2?x1?2x2?x3?x1?x2?2x3?2?x?2x?x?2x?x?x?3?2?234123 （1）s.t.?； （2）s.t.??x2?x3?x5?5?x?x?43??1???xi?0(i?1,2,?,5)?x1,x2,x3?0min

解：（1）引入松弛变量x4，x5，x6

cj→ CB 0 0 0 基 x4 x5 x6 cj-zj b 2 3 4 1 x1 1 2 -1 1 -1 x2 [1] 1 0 -1 1 x3 -2 1 1 1 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 因检验数σ2<0，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。

cj→ CB -1 0 0 基 x2 x5 x6 cj-zj b 2 1 4 1 x1 1 1 -1 2 -1 x4 1 0 0 0 1 x3 -2 [3] 1 -1 0 x4 1 -1 0 1 0 x5 0 1 0 0 0 x6 0 0 1 0 因检验数σ3<0，故确定x3为换入非基变量，以x3的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x5作为换出的基变量。

cj→ CB -1 1 0 基 x2 x3 x6 cj-zj b 8/3 1/3 11/3 1 x1 5/3 1/3 -4/3 7/3 -1 x2 1 0 0 0 1 x5 0 1 0 3 0 x4 1/3 -1/3 1/3 2/3 0 x5 2/3 1/3 -1/3 1/3 0 x6 0 0 1 0 因检验数σj>0，表明已求得最优解：X*?(0,8/3,1/3,0,0,11/3)，去除添加的松弛变量，原问题的最优解为：X*?(0,8/3,1/3)。

（2）根据题意选取x1，x4，x5，为基变量：

cj→ CB 基 b 0 x1 -1 x2 1 x3 0 x4 0 x5 0 0 0 x1 x4 x5 cj-zj 2 2 5 1 0 0 0 -2 [1] 1 -1 1 -2 1 1 0 1 0 0 0 0 1 0 因检验数σ2<0最小，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。

cj→ CB 0 -1 0 基 x1 x2 x5 cj-zj b 6 2 3 0 x1 1 0 0 0 -1 x2 0 1 0 0 1 x3 -3 -2 [3] -1 0 x4 2 1 -1 1 0 x5 0 0 1 0 因检验数σ3<0最小，故确定x3为换入非基变量，以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x5作为换出的基变量。

cj→ CB 0 -1 1 基 x1 x2 x3 cj-zj b 9 4 1 0 x1 1 0 0 0 -1 x2 0 1 0 0 1 x3 0 0 1 0 0 x4 1 1/3 -1/3 2/3 0 x5 1 2/3 1/3 1/3 因检验数σj>0，表明已求得最优解：X*?(9,4,1,0,0)。

4、分别用大M法、两阶段法和Matlab软件求解下列线性规划问题：

z?4x1?x2maxz?10x1?15x2?12x3?3x1?x2?3?5x1?3x2?x3?9?9x?3x?6??5x?6x?15x?1512?123（1）s.t.?； （2）s.t.???x1?2x2?3?2x1?x2?x3?5??x1,x2,x3?0?x1,x2?0?

min解：（1）大M法

根据题意约束条件1和2可以合并为1，引入松弛变量x3，x4，构造新问题。

cj→ CB M 0 基 x3 x4 b 3 3 4 x1 [3] 1 1 x2 1 2 M x3 1 0 0 x4 0 1 cj-zj 4 0 x1 x4 cj-zj 4 1 x1 x2 cj-zj 3/5 6/5 1 2 4-3M 1 0 0 1 0 0 1-M 1/3 [5/3] -1/3 0 1 0 0 1/3 -1/3 M -4/3 2/5 -1/5 M-7/5 0 0 1 0 -1/5 3/5 1/5 因检验数σj>0，表明已求得最优解：X*?(3/5,6/5)。 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构造新问题。

单纯形表计算略；当所有非基变量为负数，人工变量x7=，所以原问题无可行解。 请同学们自己求解。 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软件求解下列线性规划问题：

解：用内点法的过程自己书写，参考答案：最优解X?[4/3 7/3 0]；最优值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、用分支定界法求解下列问题：

maxz?5x1?8x2 （1） ?s.t.?x1?x2?6?5x1?9x2?45； ??x1,x2?0且均为整数解：（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

maxz?7x1?9x22）??x1?3x2?6s.t.??7x?1?x2?35 ?x1,x2?0且x1为整数 （