2、（共13分）已知某运输问题各产地的产量、各销地的销量以及各产地至销地的单位运价如下表所示。假设B1销地的需求量必须满足；B2销地的需求量若不满足，则不满足部分每吨罚10元；B3销地需求量至少满足15吨。
销地 产地 A1 A2 A3 销量 B1 10 15 25 35 B2 3 15 30 10
（1）列出产销平衡运输表；
（2）用表上作业法求出总费用最低的调运方案。
共 9 页 第 5 页
B3 10 20 45 35 产量 30 15 25 3、（共12分）已知纯整数线性规划问题如下所示
maxz??3x1?4x2?3x1?x2?4 ??x1?2x2?4?x、x?0且为整数2?1其松弛问题的最优单纯形表为： cj CB -3 -4 XB x1 x2 cj-zj b 4/5 8/5 -3 x1 1 0 0 -4 x2 0 1 0 0 x3 -2/5 1/5 -2/5 0 x4 1/5 -3/5 -9/5 注：x3、x4为松弛问题的剩余变量。
（1）用割平面法求整数规划问题的最优解(要求：以第二行建立割平面约束)； （2）写出割平面约束在平面直角坐标系（x1,x2）中所表示的区域。
共 9 页 第 6 页
4、（共9分）用动态规划方法求解问题：
maxz?2x1?x2?4x3?x1?2x2?3x3?9
s.t.??x1,x2,x3?0
共 9 页 第 7 页
225、（共10分）
（1）求下图所示的网络的最大流（每个弧旁的数字表示该弧的容量和流量）。 （2）该网络的最小割集是什么？
共 9 页 第 8 页
相关推荐：
loading