x14?10，x15?90(就地贮存)，x21?50，x22?50，所有空格检验数σij≥0，表中已得最优解：x32?20，x33?60，x34?70，其余xij?0；最小运费：Z*?2260。
但考虑非基变量x23的检验数σ23=0，该问题有无穷多最优解，用闭回路法调整得另一最优解：x14?10，x15?90(就地贮存)，x21?50，x23?50，x32?70，x33?10，x34?70，其余xij?0。(见下表)
1 2 3 vj 甲 18 5 50 17 4 乙 14 8 7 70 7 丙 17 13 50 12 10 12 丁 12 15 9 70 10 9 戊 90 -3 0 0 0 ui 3 1 0 三、针对目标规划模型：
?MinZ?P1d1??P2d3??P3d2
(1)用图解法求出问题的满意解。 (2)若将目标函数改为：
????MinZ?Pd?Pd?Pd?d?1122333?
??x1?2x2?d1??d1??4???x?2x?d?d222?4?1 ????x1?2x2?d3?d3?8?3x?2x?122?1???x,x?0;d,dii?0,i?1,2,3?12答案：
满意解会如何变化。
(1) 满意解为图中A(4,0)、B(6,1)、C(2,3)所围成的区域。
x2 3x1?2x2?12 ?x1?2x2?4 d1?d1?C(2,3) x1?2x2?4 d3?d3?B(6,1) d2? d2?x1?2x2?8 x1 O A(4,0)
(2) 满意解为B(6,1)、C(2,3)线。
6
第五章整数规划练习题答案
一. 判断下列说法是否正确
1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。(?)
2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。(?) 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。(?) 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。(?) 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。
工作 工人 A B C D E 甲 9 4 6 8 5 乙 8 5 9 10 6 丙 9 7 3 5 8 丁 4 8 6 9 5 戊 10 5 3 6 3 答案：
设原矩阵为A，因求极大问题，令B=[M-aij]，其中M=Max{aij}=10，则：
??16425??1?05314??04213??25104??104?4003?B???132???1??2575?02641????21540???62415?04???1??513?????0?50203?
??05747????05747????04646???1?1?1??4213??4213??3102?
?24?3???4?3???0?34003?????154??2??154?????m?4?n?5l?m?4???52?3??????52?3???11540???60203????4646?????4646????03535?????312??0010??34?3???0100????00?1154?001??。
?62?3? m=5=n，得最优解。解矩阵X*??00????01000???3535????10000??即，甲?D，乙?C，丙?E，丁?B，戊?A，最大产值=10+8+9+8+8=43。
7
三. 对整数规划
MaxZ?8x1?5x2?2x1?3x2?12 ?x?x?6?12?x,x?0,整数?12解得其松弛问题最优表如下： cj CB XB b 5 x2 3/2 8 x1 15/4 75/2 σj 要求：用割平面法完成求解过程。 答案：
(1) 产生高莫雷约束：
根据Max{fi}，应选取x1所在行为源行：x1?313产生高莫雷约束为：?x3?x4?0。
4883133?1??3?x3?x4?3，即，x1??0??x3??0??x4?3?
4884?8??8?8 x1 0 1 0 5 x2 1 0 0 0 0 x3 x4 1/4 -1/4 1/8 3/8 -9/4 -7/4 θ (2) 将高莫雷约束加入松弛变量x5，写入原表最后一行形成下表并用对偶单纯形法求解：
cj CB XB b 5 x2 3/2 8 x1 15/4 0 x5 -3/4 75/2 σj
8 5 0 0 0 θ CB b x1 x2 x3 x4 x5 5 2 0 1 1/3 0 -2/3 8 3 1 0 0 0 1 0 2 0 0 1/3 1 -8/3 34 0 0 -5/3 0 -14/3 σj b列均为整数，所有σj均非负，已得最优整数解：X*=(3, 2)T，Z*=34。 cj XB x2 x1 x4 8 x1 0 1 0 0 5 x2 1 0 0 0 0 x3 1/4 1/8 -1/8 -9/4 0 x4 -1/4 3/8 -3/8 -7/4↑ 0 x5 0 0 1 0 θ → 8
第六章 动态规划的基本方法习题
1. 已知网络图各段路线所需费用如图所示：
2 1 2 3 3 2 2 A线 2 6 1 3 5 1 4 1 7 3 3 2 1 2 5 6 1 B线 3 3
4 5 2 4 图中A线和B线上的数字分别代表相应点的有关费用。试求从A线到B线的最小费用路线及其总费用。 答案：
2 2 7 1 2 3 2 A线 4 3 4 5 2 4 6 2 6 1 3 7 9 5 1 4 1 10 14 7 3 3 2 13 1 2 15 10 5 6 3 16 1 B线 17 14 3 0 3 3 2 2 8 8 采取顺序标号法解得最小费用路线有两条，即图中的粗实线，其费用为17。 2. 用动态规划方法求解
22MaxZ?x1x2x3?x1?x2?x3?6 s.t??xi?0,i?1,2,3答案：
按问题的变量个数划分为一个三阶段决策问题；设状态变量为s1、s2、s3、s4；并记s1≤6；取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合；令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。
设各阶段状态转移方程为：s1=x1+x2+x3≤6，s2=s1-x1，s3=s2-x2，s4=s3-x3=0(即s3=x3)
9
则有各阶段允许决策集合：x3=s3，0≤x2≤s2，0≤x1≤s1 用逆推法，从后向前依次有：
22)?s3 及最优解x*① f3(s3)?Max(x33=s3
x3?s322???②f2(s2)?Max?x2?f3(s3)??Max?x?s?Maxx?(s?x)h2(s2,x2) 23?222??0Max0?x2?s20?x2?s2?0?x2?s2??x2?s2?x2?s2(舍去)dh2??(s2?x2)2?2x2(s2?x2)?(s2?x2)?s2?3x2??0 得?由 s2dx2x2??3?d2h2又2??4s2?6x2dx2则：f2(s2)?x2?s23??2s2?0
431?s2 及最优解x2?s2 273?243??2423??x?f(s)?Maxx?s?Maxx?(s?x)?Maxh1(s1,x1) ③f1(s1)?Max?12212111?0?x1?s1????0?x1?s1?0?x?s11?27?27??0?x1?s1?x1?0(舍去)?2dh184?321222?x1(s1?x1)?x1?(s1?x1)?x1(s1?x1)(2s1?5x1)?0得?x1?s1由 dx12727275???x1?s1(舍去)d2h14820又2?(s1?x1)2(2s1?5x1)?x1(s1?x1)(2s1?5x1)?x1(s1?x1)2 dx12727272d1即h2dx1??2x1?s15202283?s1(s1?s1)2??s1?0 27557521652?24?424??(s1?x1)3??s1?(s1?s1)3?s1及最优解x1则：f1(s1)?Max?x1?s1
0?x1?s12727531255??25?165?Maxf1(s1)?Max?s1? 由于0≤s1≤6不知道其具体值，故须再对s1求一次f1(s1)的极值：0?s1?60?s1?63125??显然，s1=6时f1(s1)才能达到最大值。所以f1(s1)?f1(6)=??按计算的顺序反推，可求得最优解为：x116516s1??65=39.81312 3125312522s1??6?2.4，f1(s1)?39.81312； 55*?s2?s1-x1?6?2.4?3.6则x2?11434s2??3.6?1.2，f2(s2)?s2??3.63?6.912 33272722?s3?s2-x*2?3.6?1.2?2.4则x3?s3?2.4， f3(s3)?s3?2.4=5.76 22???x2x3?39.81312。 ?2.4，x2?1.2，x3?2.4，MaxZ?x1即最优解为：x1 10