练习题一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、某公司看中了例2.1中厂家所拥有的3种资源R 1、R2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。

如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

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

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

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

因此有如下线性规划问题：123min 170100150w y y y =++1231231235210..23518,,0y y y s t y y y y y y ++≥⎧⎪++≥⎨⎪≥⎩ *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。

答：略。

3、用单纯形法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0,,43222..min32131321321321x 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 6123456min 0*0*0*z x x x x x x =-++++12341232 =22 5 =3..13 6=41,2,3,4,5,60x x x x x x x x s t x x x x x x x x x +-+⎧⎪+++⎪⎨-++⎪⎪≥⎩因检验数σ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，为基变量：⎪⎪⎩⎪⎪⎨⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min53243232132 i x x x x x x x x x x t s x x z i因检验数σ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..4min2121212121x 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，构造新问题。

1234min z=4x +x +Mx +0*x123124143 3..2 3,0x x x s t x x x x x ++=⎧⎪++=⎨⎪≥⎩因检验数σ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 = 0.6000 1.2000 fval = 3.6000 （2）大M 法引入松弛变量x 4，x 5，x 6，x 7构造新问题。

1234567max 101512000z x x x x x x Mx =+++++-12341235123671753 95615 15..2 5,,0x x x x x x x x s t x x x x x x x +++=⎧⎪-+++=⎪⎨++-+=⎪⎪≥⎩ 单纯形表计算略；当所有非基变量为负数，人工变量7x =0.5，所以原问题无可行解。

请同学们自己求解。

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 软件求解下列线性规划问题：⎪⎩⎪⎨⎧≥=+=++++=0,,52622..2min32121321321x x x x x x x x t s x x x z解：用内点法的过程自己书写，参考答案：最优解[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 = 1.3333 2.3333 0.0000 fval = 5.00006、用分支定界法求解下列问题：（1） ⎪⎩⎪⎨⎧≥≤+≤++=且均为整数0,45956..85max21212121x x x x x x t s x x z ； （2）⎪⎩⎪⎨⎧≥≤+≤+-+=为整数且1212121210,35763..97maxx x x x x x x t s x x z 解：（1）调用matlab 编译程序bbmethodf=[-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（2）调用matlab 编译程序bbmethodf=[-7; -9];G=[-1 3; 7 1];h=[6; 35][x,y]=bbmethod(f,G ,h,[],[],[0;0],[],[1;0],1) x =5 0 y = -35最优解[5 0]；最优值357、用隐枚举法和Matlab 软件求解下列问题：（1）⎪⎪⎩⎪⎪⎨⎧==≥+≥++≤+-++=)3,2,1(1013344352..234min32321321321j x x x x x x x x x t s x x x z j 或；（2）⎪⎪⎩⎪⎪⎨⎧==≥-+-≤+-+≤+++++--+=)5,,2,1(101336118343742..32523max542154315432154321 j x x x x x x x x x x x x x x t s x x x x x z j 或解： 隐枚举法：（1）将（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（0，0，1），目标函数最优值2.（2）将（0，0，0，0，0）（0，0，0，0，1）（0，0，0，1，0）（0，0，1，0，0）…. （1，1，1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（1，1，0，0，0），目标函数最优值-5。

Matlab 软件求解： （1）调用代码：f=[4; 3;2];% 价值向量fA=[2,-5,3; -4,-1,-3;0,-1,-1]; % 不等式约束系数矩阵A ，[ ]中的分号“；”% 为行分隔符 b=[4; -3;-1];% 不等式约束右端常数向量b[x, fval]=bintprog(f, A, b, [], []);%调用函数bintprog 。

注意两个空数组的占位作用。

输出结果x= 0 0 1 fval=2（2）调用代码：f=[-3; -2;5;2;3];% 价值向量fA=[1,1,1,2,1; 7,0,3,-4,3;-11, 6,0,-3, 3]; % 不等式约束系数矩阵A ，[ ]中的分号“；”% 为行分隔符 b=[4; 8;-1];% 不等式约束右端常数向量b[x, fval]=bintprog(f, A, b, [], []);%调用函数bintprog 。

注意两个空数组的占位作用。

输出结果x=1 10 0 0fval=-5最优值5。

8、某地区有A 、B 、C 三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。

已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。

试制定一个使总运费最少的化肥调拨方案。

表2- 1解：设A 、B 、C 三个化肥厂为A 1、A 2、A 3，甲、乙、丙、丁四个产粮区为B 1、B 2、B 3、B 4；c ij 为由A i 运化肥至B j 的运价，单位是元/吨；x ij 为由A i 运往B j 的化肥数量（i=1,2,3;j=1,2,3,4）单位是吨；z 表示总运费，单位为元，依题意问题的数学模型为：3411min ij ij i j z c x ===∑∑112131122232132333142434111213142122232431323334663..3787x x x x x x x x x s t x x x x x x x x x x x x x x x ++=⎧⎪++=⎪⎪++=⎪++=⎨⎪+++=⎪⎪+++=⎪+++=⎩ 该题可以用单纯形法或matlab 自带工具箱命令（linprog ）求解。