所以有：
?min2x1?3x2?4x3?s.t.?x?2x?x?x??3?1234 ??2x?x?3x?x??41235??x1,x2,x3,x4,x5?0???1?2?110??由题A????21?，以x4,x5为基向量，单纯性表如下： ?301??x x x x x RHS
12345
-2 x -1 x -2 45-3 -2 1 -4 -1 -3 0 1 0 0 0 1 0 -3 -4
由此检验数为?1??2＜0，以x5为离基变量，x1为进基变量，旋转得：
x4x1
x2
x3
x4
x5
RHS
0 0 1 -4 ?52*-1 12320 1 0 -1 1?21?2 4 -1 2 x11?2 同理，检验数小于零，以x4为离基变量，x2为进基变量，旋转得：
x2x1
x2
x3
95x4 x5 RHS0 0 1 0 1 0 ??85?15 2851?575 2?51?5 15 25 x12?5 11 5
28?112?由最优化准则可得原问题的最优解为：x*??0?，最优值为：
5?55?
T第三章 整数线性规划
1、某厂产生A,B两种产品，每件产品均要在甲、乙、丙各台设备上加工。每件第j种产品在第i台设备上加工消耗工时为aij,i?1,2,3;j?1,2。现在各台设备可
用于生产这两种产品的工时分别为bi,i?1,2,3.每件第j种产品可以提供利润
cj,j?1,2.根据需要A,B产品的生产量不能少于kj＞0件，j?1,2。而生产的A,B产品数量必须取整数。问如何安排生产能使该厂利润最大？是建立该数学问题的数学模型。
解：设生产A,B两种产品的数量分别为x1,x2 则要使利润最大则目标函数为：
maxz?c1x1?c2x2
根据题意可得限制条件有：
?a11x1?a12x2?b1?ax?ax?b2?211222??a31x1?a32x2?b3 ?x?k11??x2?k2??x1,x2为整数?综上可得该问题的数学模型为：
?max??s.t.????????
2、指派问题
z?c1x1?c2x2a11x1?a12x2?b1a21x1?a22x2?b2a31x1?a32x2?b3
x1?k1x2?k2x1,x2为整数设有n项任务要完成，恰有n个人有能力去完成任何一项任务，第i个人完成第j项任务需要的时间为cij,i?1,?,n;j?1,?,n.试写出一个使总花费时间最少的人员分配工作方案的数学模型。
解：由题可运用0?1变量，根据题意可设xij表示
?1,指派第i个人完成第j项任务xij??
0,不指派第i个人完成第j项任务?要使总花费时间最少，则：
minz???cijxij
i?1j?1nn根据题意可得限制条件有：
?n??xij?1,i?1,?,n?j?1??n ??xij?1,j?1,?,n?i?1?xij?0或1，i,j?1,?,n???综上可得其数学模型为：
nn??minz???cijxiji?1j?1?n??s.t.?xij?1,i?1,?,n j?1??n?xij?1,j?1,?,n??i?1?xij?0或1，i,j?1,?,n?
6、用分支定界法解下述ILP问题：
?maxz?3x1?2x2?s.t.2x?3x?14?12 ?2x?x?912??x1,x2?0,且为整数?解：由题记原问题的松弛问题为P0，显然P0满足替代问题的要求：
P0:maxz?3x1?2x2
?????2x1?3x2?142x1?x2?9x1,x2?0,且为整数
P0的最有解为：x1?3.25,x2?2.5均不是整数，则从中选x2进行分枝。
在P0中分成两个问题P1和P2，如下：
P1:maxz?3x1?2x2 P2:maxz?3x1?2x2
???????2x1?3x2?14??2x1?x2?9? ?x2?2??x1,x2?0,且为整数?2x1?3x2?142x1?x2?9x2?3x1,x2?0,且为整数
由此P1的最优解为x1?3.5,x2?2,z?14.5，P2的最优解为x1?2.5,x2?3,z?13.5 由于两个子问题的最优解仍不是原问题的可行解，所以选取边界较大的子问题P1继续分枝，在P1分别分成两个子问题P11和P12，如下：
P11:maxz?3x1?2x2 P12:maxz?3x1?2x2
?????????2x1?3x2?14??2x1?x2?9??x2?2 ??x1?3??x1,x2?0,且为整数?2x1?3x2?142x1?x2?9x2?2x1?4x1,x2?0,且为整数
由此P,z?14 11的最优解为x1?3,x2?2,z?13，P12的最优解为x1?4,x2?1这两个解均为原问题的可行解，所以保留可行解中最大的，即：
x1?4,x2?1,z?14
总体过程如下：
??P11:?x1?3,x2?2,z?13???P:x?3.5,x?2,z?14.5??112P0:?x1?3.25,x2?2.5,z?14.75??12:?x1?4,x2?1,z?14??P?P:?x?2.5,x?3,z?13.5?2?21
第四章 非线性规划
5、判别以下函数哪些是凸函数，哪些是凹的，哪些是非凸非凹的？
2（1）f?x1,x2??60?10x1?4x2?x12?x2?x1x2 2（2）f?x1,x2???x12?5x2?2x1x2?10x1?10x2
22（3）f?x1,x2,x3??x12?3x2?9x3?2x1x2?6x2x3?2x1x3
解：(1)f?x?的Hesse矩阵为：
?2?1??2f?x?????12??
???2f?x?的各阶顺序主子式分别为：
2?12＞0，?3＞0
?12?2f?x?是正定的，所以f?x?是凸函数。 （2）f?x?的Hesse矩阵为：
??22??f?x????2?10??
??2?2f?x?的各阶顺序主子式分别为：
?2＜0，
?22?16＞0
2?10所以f?x?是凹函数。 （3）f?x?的Hesse矩阵为：
?2?22???2?f?x????266?
?2618????2f?x?的各阶顺序主子式分别为：
2＞0，
2?2?8＞0，?2?2622?26626?0 18?2f?x?是半正定的，所以f?x?是凸函数。 7、证明下列规划为凸规划
2?minx13?2x1x2?2x2（1）?问：该问题是否存在最优解？
?s.t.x1?1解：由题可得目标函数f?x?的Hesse矩阵为：