1、1 2(1. 一 直优化问题的数学模 型 为：习 题一min f (x) = (x 3)2 + (x 4)2 g (x) = x x 5 0 1 1 2 2试 用图解法求出：s.t. g2 (x) = x1 x2 + 5 0 g (x) = x 0 3 1 g4 (x) = x2 0（1） 无 约束最优点，并求出最优 值 。（2） 约 束最优点，并求出其最优 值 。（3） 如 果加一个等式约束 h(x) = x1 x2 = 0 ， 其约束最优解是什 么 ？*解 ： （ 1） 在 无 约 束 条 件 下， f(x) 的可 行域 在整 个 x1 0x2 平面 上， 不 难 看出 ， 当 x =（
2、3， 4）时， f(x) 取最 小 值 ，即 ，最 优点 为 x* =（ 3，4 ） ：且 最优 值为 ： f (x* ) =0（2 ）在 约束 条 件 下， f(x) 的可 行域 为图 中阴 影部 分所 示， 此时 ，求 该问 题的 最优 点就 是在约 束集 合即 可行 域中 找一 点 (x1 , x2 ) ，使 其落 在半 径最 小 的 同心 圆上 ，显 然， 从图 示中 可以看 出， 当 x* = 15 , 5 ) 时， f(x) 所在 的圆 的半 径最 小。4 4 g (x) = x x 5 = 0 15 x1 =其中 ：点 为 g1 (x) 和 g2 (x) 的交 点， 令 1 1
3、2 2 求解 得到 ： 45即最 优点 为 x* = g2 (x) = x1 x2 + 5 = 015 , 5 ) ：最 优值 为： f (x* ) = 65 x = 2 44 4 8（ 3） . 若增 加一 个等 式约 束， 则由 图可 知， 可行 域为 空集 ，即 此时 最优 解不 存在 。2.一 个矩形无盖油箱的外 部 总面积限定为 S， 怎样设计可 使 油箱的容量 最 大？试列 出 这个 优 化 问题的数学模型，并回答 这 属于几维的 优 化问题 .解： 列出 这个 优化 问题 的数 学模 型为 ：max f (x) = x1x2 x3 x1x2 + 2x2 x3 + 2x1x3 Ss
4、.t. x1 0 x2 0 x3 0该优化问题属于三维的优化问题。 ij nn 1 2 n 1 2 nn 1 2 1 2 1 21x = s/ 3, y = s/ 3, z = s/ 12 v = s33s = =1 =s 218 2 3 习题二3.计算一般二次函数 f(x) = 1 XT AX + bT X + c 的梯度。2解：设： A= (a ) ,b= (b,b ,.b )T , X = (x , x ,.x )T 则：f(x) = 1n n na xx + bx + c，将它对变量 x (i = 1, 2,.n) 球偏导数得： ij i j i i i2 i=1 j=1 i=1 1
5、n 1 n n n f (x) a1 jxj + ai1xi + b1 a1 jxj ai1xi 2 j=1 2 i=1 j=1 i=1 x1 1 n 1 n n n b f (x) a2 jxj + ai2 xi + b2 a jxj ai2 xi f(x) = = 2 j=1 2 i=1 1 2 = + 1 + b j=1 i=1 2 x2 2 2 b f (x) 3 1 n 1 n n x3 anjxj + ainxi + bn anjxj ainxi 2 j=11 T2 i=1 j=1 i=1 = (AX + A X) + b25.求下列函数的梯度 和 Hesse 矩阵（1 ） f(x
6、) = x2 + 2x 2 + 3x 2 4xx 2 0 -4 解： 2 f (x) = 0 4 0 1 2 3 1 3 x 2ex1x2 4 0 6 6x + ex1x2 +xx ex1x2 （2 ） f(x) = 3xx 2 + ex1x2 解： 2 f (x) =2 2 1 21 2 1 2 1 2 1 2 6x + ex x +xx ex x 6x +x2ex x 2 1 2 1 1 6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：（1 ） f(x , x ) = x2 + 2x 2 + 3xx1 2 1 1 2 2 1解： 2 f (x) 不是半正定， 即 f(x) 非凸，
7、然 后判断 - f(x) ， 经验证： 2 ( f(x) 不是 半正定，由此可知： f(x) 非凸非凹。（2 ） f(x , x ) = 2x2 4xx + 3x 2 5x 6解： 2 f (x) 半正定，故 f(x) 为凸函数。1 1 2 22 1 2 1 2T1 2 2 2k1（3 ） 2 2 2f(x1 , x2 , x3 ) = x1 + 2x2 3x3 4x1x2解： 2 f (x) 不是半正定， 即 f(x) 非凸， 然 后判断 - f(x) ， 经验证： 2 ( f(x) 不是 半正定，由此可知： f(x) 非凸非凹。7.设约束优化问题的数学模型为：min f(x) = x2 +
8、 4x + x 2 4x +10 g1 (x) = x1 x2 + 2 0s.t. g (x) = x2 x 2 2x + 2x 0试 用 K-T 条件判别点 x = 1,1T 是否为最优点。解：对于点 x = 1,1T ， g (x) =0， g (x) 0 ，点满足约束条件，故点 X 是可行解。1 2 2 1 且 g1 (x) 是起作用约束， I = 1 , f(x) = , g1 (x) = ， 由 gi (x) 0 条件下 的 2 1K-T 条件得： f(x) i gi(x) = 0, i 0 ，得到 1 = 2 ，点 x = 1,1iI满足 K -T 条件。又因 2 f (x) 正定
9、，故 f(x) 为严格凸函数，该最优化问题是凸规划问题，由x* = 1,1T 是 K-T 点，所以 x* = 1,1T 也是该问题的全局最优点。8.设约束优化问题：min f(x) = (x 2)2 + x 2 g1 (x) = x1 0s.t. g (x) = x 0 g (x) = 1 + x2 + x 0 3 1 2它的当前迭代点为 x = 1, 0T ，试 用 K -T 条件判定它是不是约束最优解。解：对于点 x = 1, 0T g (x ) = 1 0, g (x ) = 0, g (x ) = 0 ，点 x = 1, 0T 是 可 行 点 ，k 1 k 2 k 3 k k 2 0
10、且起作用的约束条件是， g2 (x), g3 (x) ， I = 2, 3 , f(xk ) = ， g2 (xk ) = 0 1 2 g3 (xk ) = ，由约束条件为 gi(x) 0 时的 K-T 条件得，应有： 2 = 1 T f(x) + i gi (x) = 0,i 0 解得： ，所以 x = 1, 0 = 1 k为 K-T 点。iI 31 2k 现判断该问题是否为凸规划问题，因 2 f (x) 正定，故 f(x) 为凸函数， g (x), g (x) 为 线性函数，亦为凸函数， 2g (x) 半正定，所以 g (x) 为凸函数，所以该优化问题为凸3 3规划问题，即点 x = 1,
11、 0T 是该问题的约束最优解。习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。max f (x) = 3x1 + x2 + 2x3 12x1 + 3x2 + 6x3 + x4 = 9（ 1） 8x1 + x2 4x3 + 2x5 = 10s.t. 3x1 x6 = 0 xj 0, ( j = 1, 2.6) 12 3 6 3 0 0 解：令 A= 8 1 -4 0 2 0 = (P1 , P2 , P3 , P4 , P5 , P6 ) 3 0 0 0 0 -1 （1 ） 基解 x = (0, 16 , 7 , 0, 0, 0) 不是基可行解，1 3 6（2
12、） 基解 x2 = (0,10, 0, 7, 0, 0) 不是基可行解，（3 ） 基解 x3 = (0, 3, 0, 0, 3.5, 0) 是基可行解，且 f(x) = 3 ，7 21（4 ） 基解 x4 = ( , 4, 0, 0, 0,45) 不是基可行解，4（5 ） 基解 x5 = (0, 0, , 8, 0, 0) 不是基可行解，2（6 ） 基解 x = (0, 0, 3 , 0,16, 0) 是基可行解，且 f(x) = 3 ，6 2（7 ） 基解 x = (1, 0, 1 , 0, 0, 3) 不是基可行解，7 2（8 ） 基解 x8 = (0, 0, 0, 3, 5, 0) 是基
13、可行解，且 f(x) = 0 ，（9 ） 基解 x = ( 5 , 0, 0, 2, 0, 15) 不是基可行解。9 4 43 9 9（1 0） 基解 x10 = ( 4 , 0, 0, 0, 4, 4) 是基可行解，且 f(x) = 4 。16 7（1 1） 基解 x11 = (0, 3 , 6 , 0, 0, 0) 不是基可行解。（1 2） 基解 x12 = (0,10, 0, 7, 0, 0) 不是基可行解。7（1 3） 基解 x13 = (0, 3, 0, 0, 2 , 0) 是基可行解，且 f(x) = 3 。 5 1 2 5 1 2 4（1 4） 基解 x = (0, 0, 5 ,
14、 8, 0, 0) 不是基可行解。14 2（1 5） 基解 x = (0, 0, 3 , 0, 8, 0) 是基可行解，且 f(x) = 3 。15 2（1 6） 基解 x16 = (0, 0, 0, 3, 5, 0) 是基可行解，且 f(x) = 3 。2. 用单纯形法求解下列线性规划问题：max f (x) = 10x1 + 5x2（ 1） 3x1 + 4x2 9s.t. x + 2x 8 x1 , x2 0解：将现行规划问题化为标准形式如下：min( f (x) = 10x1 5x2 + 0x3 + 0x4 3x1 + 4x2 + x3 = 9s.t. x + 2x + x = 8 x1
15、 , x2 , x3 , x4 0作初始单纯形表，并按单纯形表步骤进行迭代，如下：CB XB b -10x1-5x20x30x4i0 x3 9 3 4 1 0 30 x4 8 5 2 0 1 1.60 -10 -5 0 00 x3 4.2 0 2.8 1 -0.6 1.5-10 x1 1.6 1 0.4 0 0.2 416 0 -1 0 2-5 x2 1.5 0 1 514 314-10 x1 1 1 0 17 2717.5 0 0 514 2514此时， 均为正，目标函数已不能再减小，于是得到最优解为： x* = (1, 3 , 0, 0)j 2目标函数值为： f(x* ) = 17.53.
16、 分别用单纯形法中 的 大 M 法和两阶段法求解下列线性规划问题：CB XB b 5x1-2x23x3-6x4-6x4-6x4iM x 7 1 2 3 4 1 0 1.75M x 3 2 1 1 2 0 1 1.5-10M 5-3M -2-3M 3-4M -6-6M 0 0M x 1 -3 0 1 0 1 -2 1-6 x 1.5 1 0.5 0.5 1 0 0.5 39-M 11+3M 1 6-M 0 0 3M+33 x 1 -3 0 1 0 1 -2-6 x 1 2.5 0.5 0 1 -0.5 1.53 29 1 0 0 M-6 M+15 1 2 3 4 6min f (x) = 5x1
17、 2x2 + 3x3 6x4 x + 2x + 3x + 4x = 7（ 1） 1 2 3 4s.t. 2x1 + x2 + x3 + 2x4 = 3 x1 , x2 , x3 , x4 0解： （ 1）大 M 法：把原问题化为标准形式，并加入人工变量如下：min f (x) = 5x1 2x2 + 3x3 6x4 + Mx5 + Mx6 x1 + 2x2 + 3x3 + 4x4 + x5 = 7s.t. 2x + x + x + 2x + x = 3 x1 , x2 , x3 , x4 , x5 , x6 0作初始单纯形表，并按单纯形表步骤进行迭代，如下：565434因为 M 是一 个很 大
18、的 正数 ，此 时 j 均为正，所以，得到最优解： x* = (0, 0,1,1, )T ，最优值为 f(x* ) = 3（ 2）两 阶段法 1 2 3 4 6首先 ，构 造一 个仅 含人 工变 量的 新的 线性 规划 如下 ：按单纯形法迭代如下：min g(x) = 0x1 + 0x2 + 0x3 + 0x4 + x5 + x6 x1 + 2x2 + 3x3 + 4x4 + x5 = 7s.t. 2x + x + x + 2x + x = 3 x1 , x2 , x3 , x4 , x5 , x6 0CB XB b 0x10x20x30x41x41x4i1 x5 7 1 2 3 4 1 0
19、1.751 x6 3 2 1 1 2 0 1 1.5-10 -3 -3 -4 -6 0 01 x5 1 -3 0 1 0 1 -2 10 x4 1.5 1 0.5 0.5 1 0 0.5 3-1 4 0 -1 0 0 30 x3 1 -3 0 1 0 1 -20 x4 1 2.5 0.5 0 1 -0.5 1.5最优 解为 ： x* = (0, 0,1,1, 0, 0) ，最优值： g(x) = 0* T因人工变量 x5 = x6 = 0 ，则原问题的基可行解为 :如下表所示：x = (0, 0,1,1, ) ,进入第二阶段计算CB XB b 5x1-2x23x3-6x43 x3 1 -3 0
20、 1 0-6 x4 1 2.5 0.5 0 13 29 1 0 0由上 表可 知， 检验 数均 大于 等于 0， 所 以 得到最优解： x* = (0, 0,1,1, )T最优值为 f(x* ) = 3 。4.某糖果厂用 原 料 A， B， C 加工成三中不同牌号的糖果， 甲， 乙， 丙， 已知各种牌号 糖果 中 A,B,C 含量， 原料成本， 各种原料的每月限用量， 三中牌号糖果的单位加工费及 售 1 2 3s.t. 3 1 2 3 1 2 3价如下表所示， 问 该厂每月应生产这三种牌号糖果各多少千克， 使该厂获利最大？试建 立这个问题的线性规划数学模型。甲 乙 丙 原料成本（元 /千克）
21、每月限用量（千克）A 60% 15% 2.00 2000B 1.50 2500C 20% 60% 50% 1.00 1200加工费 0.50 0.40 0.30售价 3.40 2.85 2.25解：设 xi, yi, zi 0,i = 1, 2, 3 表示甲、乙、丙中分别含 A、B 、C 的含量，构造此问题的 数学规划模型如下：max f (x) = 0.9x1 + 1.4x2 + 1.9x3 + 0.45y1 + 0.95y2 + 1.45y3 0.5z1 + 0.45z2 + 0.95z3 x1 + y1 + z1 2000 x2 + y2 + z2 2500 x3 + y3 + z3 1
22、200 0.4x1 0.6x2 0.6x3 0s.t. 0.85y 0.15y 0.15y 0 0.2x + 0.2x 0.8x 0 1 2 3 0.6y1 0.6 y2 + 0.4 y3 0 0.5z1 + 0.5z2 0.5z3 0 xi, yi, zi 0,i = 1, 2, 35.求解下列线性规划问题的对偶问题min f(x) = 2x1 + 2x2 + 4x3 2x1 + 3x2 + 5x3 2（1） x + x + 7x 3 x1 + 4x2 + 6x3 5 x1 , x2 , x3 0max f (x) = 5x1 + 6x2 + 3x3 x1 + 2x2 + 2x3 = 5（2
23、） x1 + 5x2 x3 3s.t. 4x1 + 7x2 + 3x3 8 x 无约束 , x 0, x 0CB XB b 4x112x218x30x40x50 x4 -3 -1 0 -3 1 00 x5 -5 0 -2 -2 0 14 12 18 0 0s.t. 3y1 2 3 1 2 3 2 3 5解： （1）由表 3.7 可得该问题的对偶问题为：max g( y) = 2y1 + 3y2 + 5y3 2y1 + 3y2 + y3 2 + y + 4 y 2 5y1 + 7 y2 + 6 y3 4 y1 0, y2 , y3 0（2） 该问题的对偶问题为：min g( y) = 5y1 +
24、 3y2 + 8y3 y1 3y2 + 4 y3 = 5 2y1 + 5y2 + 7 y3 6s.t. 2y1 y2 + 3y3 3 y 无约 束 , y 0, y 06用对偶单纯形法求解下列线性规划问题：min f(x) = 4x1 +12x2 +18x3 x + 3x 3（1 ） 1 3s.t. 2x2 + 2x3 5 x1 , x2 , x3 0解： （1）首先，将 “ ”约束条件两边反号，再加入松弛变量，得：min f (x) = 4x1 +12x2 +18x3 + 0x4 + x5 x1 3x3 + x4 = 3s.t. 2x 2x + x = 5 x1 , x2 , x3 , x4 , x5 0建立初始单纯形表如下图所示，所有 j 0 。 则对应对偶问题解是可行的，则继续迭代：计算 min 3, 5 = 5 ， 所以 x5 为换出变量， = min 6, 9 = 6 ， 确定 x2 为换入变量 。 继续迭代，得到如下单纯形表：
