运筹学练习题

一、填空题（每空3分 共15分）

1. 用图解法求解下列线性规划问题, 则该线性规划问题为 (无解，无界或有最优解)。

min z?2x1?2x2

??2x1?x2?2?s.t. ?x1?x2?1 ，

?x,x?0?122. 用割平面法求解整数线性规划。若其线性规划松弛问题的最优单纯形表为：

z x1 x2 x1 x2 x3 x4 0 0 -1/4 -1/4 1 0 1/6 -1/6 0 1 5/6 -1/6 -3/2 1 5/3 则由x2行生成的割平面条件为 。

223. 非线性规划问题 min f(x1,x2)?x12?4x2?2x3?2x1?4x3 的最优解为_____________。

1124. 用最速下降法求解UMP问题：min f(x1,x2)?x12?x2，取初始点x(0)?(3,2)T，则在x(0)32处的搜索方向p(0)? 。

5. 用障碍函数法求解如下非线性规划问题：

min x1?2x2

?x12?x2?0s.t. ?

x?01?所采用的对数形式的障碍函数Bdk(x)? （罚参数记为dk）。 二、判断题（每小题3分 共15分）

1. 若线性规划问题有最优解，则此最优解一定为某个基本可行解。 （ ） 2. 若线性规划原始问题和对偶问题都有可行解，则该线性规划问题一定有最优解。 （ ） 3. 若整数线性规划问题没有可行解，则其线性规划松弛问题也没有可行解。 （ ） 4. 两个凸函数的乘积不一定是凸函数。 （ ） 5. 凸规划的局部最优解不一定是整体最优解。 （ ） 三、计算题（共70分）

1．（6分）某企业生产需要m种资源，记为A1,?,Am，其拥有量分别为b1,?,bm，现用来生产n种产品，记为B1,?,Bn。产品Bj的每个单位的利润为cj，又生产每单位的Bj需消耗资源

Ai的量为aij，j?1,?,n，i?1,?,m。在现有资源条件下，企业应如何安排生产，使利润最大？建立这个资源利用问题的线性规划模型。 2．（20分）已知线性规划问题（P）：

min z?x1?x3

1

?x1?2x2?5?1s.t. ?x2?x3?3

?2?x1,x2.x3?0（1）用单纯形算法计算线性规划问题（P）的最优解和最优值；

5（2）当（P）中目标函数的x1的系数c1由1变为（?）时，求新线性规划问题的最优解和

4最优值；

（3）当（P）中右端向量b由??5???3??变为???8???1??时，求新线性规划问题的最优解和最优值。 ?（注意：问题（2）和（3）应在线性规划问题（P）的最优单纯形表基础上继续求解）

3. （12分）验证下列非线性规划为凸规划

min f(x2?x221,x2,x3)?2x12?2x3?x1x3?x1x2?x1?2x2

?x2?x212?x3?0s.t. ??x1?x2?2x3?16

???x1?x2?x3?04.（12分）已知线性规划问题：

max z?2x1?x2?5x3?6x4

?s.t. ?2x1?x3?x4?8?2x1?2x2?x3?2x4?12

??x1,?,x4?0（1）写出此问题的对偶问题。

（2）已知其对偶问题最优解为（4,1）T，试用对偶理论找出原问题的最优解。 5.（12分）求下列问题的K-T点：

min f(x)?(x?3)2 s.t. 0?x?5 6．（8分）用罚函数法求解如下非线性规划问题

min x2

s.t. 2?x?0

取ck?k，k=1,2,…

2