σ1=-137/33
σ4=4/11 σ5=-17/22
由于σ4大于0所以对最优解有影响
五．运输问题
例1：某建材公司所属的三个水泥厂A1,A2,A3生产水泥运往四个销售点B1,B2,B3,B4。已知各水泥厂的日产量（百吨），各销售点的日销售量（百吨）以及各工厂到各销售点的单位运价（百元/百吨）如表所示，问该公司应如何调运产品，在满足各销售点销量的前提下，使总运费为最小？ 销地 产地 A1 A2 B1 B2 B3 B4 产量 10 90 40 7 7 4 20 8 4 2 30 3 5 9 40 2 1 6 50 A3 销量 解：用伏格尔法得到初始方案如下 销地 产地 A1 B1 B2 B3 B4 产量 2 10 行位势 7 8 10 3 0 A2 7 4 20 20 4 20 30 2 10 4 30 2 5 50 9 40 3 50 -1 1 90 2 A3 6 40 0 销量 列位势 用位势法进行检验 令u1?0由u1?v3?3得v3?3；
由u2?v3?5得u2?2；由u2?v2?4得v2?2
5
由u2?v4?1得v4??1；由u3?v2?2得u3?0 由u3?v1?4得v1?4
计算各空格处的检验数
?11?7?(0?4)?0;?14?2?(0?1)?0;?33?9?(3?0)?0; 故这时的方案为最优，这时的运输方案为 销地 产地 A1 A2 ?12?8?(0?2)?0?21?7?(4?2)?0?34?6?(?1?0)?0
B1 B2 B3 B4 20 10 20 10 30 50 A3 总运费为390百元。
例2.下列表3是一个指派问题的效率表(工作时间表)，其中A i为工作人员(i=1, 2, 3, 4)、Bj为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小。
答案：
A1 A2 A3 A4
六．整数规划—0—1规划
七．用动态规划方法求解最短路问题（连续型，离散型） 例1：某公司有资金10万元，若投资用于项目
i(i?1,2,3)的投资额为xi时，其收益分别为g1(x1)?4x1,g(x2)?9x2,g(x3)?2x3,
6
A1 A2 A3 A4
B1 4 2 5 6 B2 1 2 6 3 B3 7 3 4 2 B4 4 5 3 4 B1 4 ② 5 6 B2 ① 2 6 3 B3 7 3 4 ② B4 4 5 ③ 4 问应如何分配投资数额才能使总收益最大？
答案：4．解：状态变量sk为第k阶段初拥有的可以分配给第k到底3个项目的资
金额；决策变量xk为决定给第k个项目的资金额；状态转移方程为sk?1?sk?xk；最优指标函数fk(sk)
表示第k阶段初始状态为sk时，从第k到第3个项目所获得的最大收益，fk(sk)即为所求的总收益。递推方程为：
fk(sk)??gmax0?xk?skkx(k?)fk?sk(?1?k)?(1,2,3)
f4(s4)?0
当k=3时有
f3(s3)?f3(s3)?max?2x?230?x3?s323
当x3?s3时，取得极大值2s，即：
max?2x??2x230?x3?s323 当k=2时有：
f2(s2)?
max?9x0?x2?s22222?f3(s3)?
?max?9x0?x2?s2?2s3?
2?max?9x0?x2?s22?2(s2?x2)??9x2?2(s2?令 h2(s2,x2)用经典解析方法求其极值点。
x2 )dh2由 dx2解得： 而 所以
?9?2(s2?x2)(?1)?094
x2?s2?
dh2dx29422?4?0x2?s2?是极小值点。
2极大值点可能在[0，s2]端点取得：
f2(0)?2s22， f2(s2)?9s
当f2(0)?f2(s2)时，解得 s2?9/2
*当s2?9/2时，f2(0)?f2(s2)，此时，x2?0
当s2?9/2时，
f2(0)?f2(s2)，此时，x2?s21*
当k=1时，
f1(s1)?max?4x0?x1?s1?f2(s2)?
7
当 f2(s2)?9s2时，
f1(s1)??max?4x0?x1?s11111?9s1?9x1?
0?x?s
10?0?1?0但此时 s2?s1?x1?max?9s?5x1??9s1
矛盾，所以舍去。
29，与/2s2?9/21当
f2(s2)?2s2时，
2f1(10)?max?4x0?x1?10?2(s1?x1)2?
令 由
h1(s1,x1)?4x1?2(s1?x )1dh1dx1?4?4(s2?x2)(?1)?0
解得： x2?s1?1
dh22而 dx22?1?0 所以 x1?s1?1是极小值点。
比较[0,10]两个端点 x1?0时，f1(10)?200 x1?10时，f1(10)?40 所以
再由状态转移方程顺推： 所以
**x1?0*
s2?s1?x1?10?0?1 0*因为 s2?9/2
x2?0，s3?s2?x2?10?0?10 x3?s3?10
*因此
最优投资方案为全部资金用于第3个项目，可获得最大收益200万元。
八．工程计划网络问题
1. 绘制工程网络题
2. 3.
求完工期及关键路径
估计工程在确定工期内完成的概率
例1：下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。 9 2 4 9
5
4 0 10 1 12
5 3
答案：答案：
8
6 4 5