销量 3 3 2 2 用位势法计算u和v：
A B C vj 甲 3 4 3 乙 3 2 丙 3 5 丁 4 2 4 ui 0 -2 1 非基变量检验数为：
A B C vj 甲 1(2) 3 乙 5(7) 4(4) 2 丙 1(6) 2(8) 5 丁 0(5) 4 ui 0 -2 1 所有检验数均为正数或零，故已得到最优解，最小运输成本为32。因为非基变量检验数中有0，故原问题有无穷多最优解。
指派问题
1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h) 如下表，问如何分派工作，使总的消耗时间最少？
A B C D 消耗工作 工人 3 3 5 3 甲 3 2 5 2 乙 1 5 1 6 丙 4 6 4 10 丁 解：变换效率矩阵如下： 3 3 5 3 逐 (0) 0* 2 0* 逐 (0) 0* 2 0* 3 2 5 2 0 3 0 行 1 列 1 (0) 3 0* 1 5 1 6 ?标 0* 4 (0) 5 ?标 0* 4 (0) 5 4 6 4 10 记 0* 2 0* 6 记 0* 2 0* 6 每行每列都有两个以上的0 未找到最优解 ?4 (0) 0* ?8 1 (0) 2 3 0* 0* 重 0* (0) 新 1 0* 2 3 0* (0) ?5 0* 4 (0) 5 ?标 0* ?1 0* 2 0* 6 记 (0) ?2 ?6 ?3 ?7 划线过程(发现有4条直线)
4 (0) 5 2 0* 6 找到最优解
答：容易看出，共有四个最优解：①甲?B，乙?D，丙?A，丁?C；
②甲?D，乙?B，丙?A，丁?C；③甲?B，乙?D，丙?C，丁?A；④甲?D，乙?B，丙?C，丁?A；OBJ=10。
隐枚举法
1、用隐枚举法求解
max z＝4x1＋3x2＋2x3 ?2x1?5x2?3x3?4??4x1?x2?3x3?3 s.t?x?x?13?2?x1,x2,x3?0或1?解：原模型变为：
max z＝4x1＋3x2＋2x3 ?2x1?5x2?3x3?4??4x1?x2?3x3?3? ?x2?x3?1?4x?3x?2x?223?1??x1,x2,x3?0或1求解过程如表所示。 点 （0，0，0）T （0，0，1）T （0，1，0）T （0，1，1）T （1，0，0）T （1，0，1）T （1，1，0）T （1，1，1）T 过滤条件 4x1＋3x2＋2x3≥2 4x1＋3x2＋2x3≥5 4x1＋3x2＋2x3≥7 约束 ④ × √ √ √ × √ √ √ ① √ √ √ × √ √ ② √ × √ √ √ ③ √ √ √ √ z值 2 5 7 9 ①②③④
***所以该0－1规划最优解为x1?x2?x3?1,z*?9。
割平面法
1、用割平面法求解下面整数规划。
maxz?7x1?9x2
??x1?3x2?6? s.t?7x1?x2?35?x,x?0且为整数?12①②③
b 7/2 9/2 （下表为最优表） cj? 7 9 0 0 CB XB x1 x2 x3 x4 9 x2 0 1 7/22 1/22 7 x1 1 0 3/22 －1/22 0 0 cj－zj －28/11 －15/11 解： 线性规划的最优解为：
x1?9/2,x2?7/2,x3?x4?0,maxz?63
由最终表中得：
x2?717x3?x4? 22222711x3?x4?3? 22222④
将系数和常数项分解成整数和非负真分式之和，上式化为；
x2?移项后得： 即：
711711x3?x4???x3?x4?? 2222222222只要把增加的约束条件加到B问题的最优单纯形表中。 cj? 7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 7/22 1/22 0 7/2 7 x1 1 0 3/22 0 9/2 －1/22 * 0 x5 0 0 1 －7/22－1/22 －1/2 0 0 0 cj－zj －28/11 －15/11 这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到： 表4－4 cj? 7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 0 0 1 3 7 x1 1 0 0 1/7 32/7 －1/7 0 x3 0 0 1 1/7 11/7 －22/7 0 0 0 cj－zj －1 －8 由计算结果知还没有得到整数解，重新再寻找割平面方程。 由x1行得：
x1?1132 x4?x5?777将系数和常数项分解成整数和非负真分数之和：
164x4?x5?x5?4? 777164得到新的约束条件：?x4?x5??
777164?x4?x5?x6?? 777x1?在的最优单纯形表中加上此约束，用对偶单纯形法求解： cj? 7 9 0 0 0 CB 9 7 0 0 cj－zj 9 7 0 0 cj－zj x2 x1 x3 x4 XB x2 x1 x3 x6 x1 0 1 0 0 0 0 1 0 0 0 x2 1 0 0 0 0 1 0 0 0 0 x3 0 0 1 0 0 0 0 1 0 0 x4 0 1/7 1/7 －1/7* －1 0 0 0 1 0 x5 1 －1/7 －22/7 －6/7 －8 1 －1 －4 6 －2 0 x6 0 0 0 1 0 0 1 1 －7 －7 b 3 32/7 11/7 －4/7 3 4 1 4 **则最优解为x1?4,x2?3，最优目标函数值为z*=55。
2、用割平面法求解
maxz?x1?x2?2x1?x2?6?4x?5x?20 ?12s..t??x1,x2?0??x1,x2?Zcj XB b x1 5/3 x2 8/3 1 1 0 0 cB 1 1 x1 1 0 0 x2 0 1 0 x3 5/6 －2/3 －1/6 x4 －1/6 1/3 －1/6 ?i ?j 解：切割方程
211?x3?x4?0，化简得?x3?x4??2。将切割方程333加入松弛问题，代入单纯形表可得：
cj 1 1 0 0 0 cB 1 1 0 XB b 5/3 8/3 -2 x1 1 0 0 0 x2 0 1 0 0 0 1 0 0 x3 5/6 －2/3 [-1] -1/6 0 0 1 0 x4 －1/6 1/3 [-1] -1/6 -1 1 1 0 x5 0 0 1 0 5/6 -2/3 -1 -1/6 x1 x2 x5 ?j 1 1 0 x1 x2 x3 0 4 2 1 0 0 0 ?j 得到最优解为X*?(0, 4, 2, 0, 0)T，是整数解，故原问题的最优解
**为x1?0、x2?4，最优值为z*?4。
不确定型决策
1、用不确定性决策的几个准则进行分析决策。（乐观系数为α=0.6） 自然状态 需求量大 需求量一般 需求量小 损益值 S1 S2 S3 行动方案 大批量生产A1 中批量生产A2 小批量生产A3 解：一、悲观法 自然状态 损益值 行动方案 大批量生产A1 36 20 14 14 16 10 悲观法 -8 0 3 乐观法 需求量大 S1 36 需求一般 S2 14 需求量小 S3 -8 min{rij} jmax{rij} j-8 36 中批量生产A2 小批量生产A3 ij20 14 16 10 0 3 0 3 20 14 r*?maxmin{rij}?3故应选择方案A3。
一、乐观法
r*?maxmax{rij}?36
ij故应选择方案A1。
选乐观系数为α=0.6，则有：
d1??max{r1j}?(1??)min{r1j}?0.6?36?0.4?(?8)= 18.4
jjd2=0.6×20+0.4×0= 12 d3=0.6×14+0.4×3= 9.6
故选方案A1。
首先按公式hij?max{rij}?rij（i=1，…，m；j=1，…，n）计算后悔值，
j结果如下表： 自然状态 后悔值 行动方案 大批量生产A1 中批量生产A2 小批量生产A3 *i需求量大 S1 0 16 22 j需求一般 S2 2 0 6 需求量小 S3 11 3 0 max{hij} j11 16 22 根据表中数据有：h?min{max{hij}}=11，因此，按此方法应选方案A1。 等可能准则
因为自然状态只有三个，按各自然状态出现的概率均为1/3来计算各方案的期望损益值，有
131ER(A1)??r1j?(36?14?8)?14
3j?131ER(A1)?(20?16?0)?12
31ER(A1)?(14?10?3)?9
3故应选方案A1。
决策树