1701018020
▲ 图8.2.2
1701018021
1701018022
1701018023
1701018024
1701018025
电话公司不得不向大学讨饶：中心点的电话网不要架设了，收费则从2单位减为 单位。北卡罗来纳州的三所大学不费力气，就让电话公司乖乖地减少了收费。
1701018026
1701018027
可是，电话公司却不放心，究竟还会出现怎样的“新招”，让电话线的收费标准进一步降低？也就是说，是否再也没有其他安排能使收费标准的“折扣”不会大于 比2？这是一个猜想。在提出来20年里都未得到证明，成为数学难题。1987年，我国青年数学家堵丁柱证明了这一猜想是正确的。
1701018028
1701018029
2.人事指派问题，0—1规划一例
1701018030
1701018031
工厂为了电工、图书管理员和木工这三个工作岗位，招聘到甲、乙、丙三人，他们的各科考试成绩及总分如下：
1701018032
1701018033
物理 语文 制图 总分
1701018034
1701018035
甲8 7 5 20
1701018036
1701018037
乙8 6 7 21
1701018038
1701018039
丙10 5 7 22
1701018040
1701018041
如果按照总分从高分到低分的录取方法，那么丙会被录取为文化程度较高的图书管理员；乙的总分次之，当去做电工；总分最低的甲去做木工。这样的安排很不妥当。实际上，丙的语文成绩只有5分，做图书管理员不合适；甲做木工，可是制图成绩最差；乙当电工，但物理得分不及丙。总之，“从总分的高分到低分的”用人办法会有不合理情形发生。
1701018042
1701018043
这属于人事指派问题，以下是一个写成数学形式的例子。
1701018044
1701018045
车间里有4位师傅Ai（i=1，2，3，4），他们都能独立完成四项不同的任务Bi（i=1，2，3，4）。由于他们各有特长，所以完成四项任务所需的时间不同（见表8.2.1）。
1701018046
1701018047
表8.2.1 四位师傅完成四项任务所需时间（单位：小时）
1701018048
1701018049
1701018050
1701018051
1701018052
规定每项任务安排一人，且仅安排一人。问怎样安排才能使完成四项任务所需的总时间最少？
1701018053
1701018054
把问题数学化令xij表示是否安排Ai做任务Bj：
1701018055
1701018056
1701018057
1701018058
1701018059
并规定：每个人都有一项工作且每项工作都有一人做。即有约束条件：
1701018060
1701018061
1701018062
1701018063
1701018064
目标函数是
1701018065
1701018066
T x=+3 14 10 5 10 11x 12+x 13++x 14x 21+4 12 10x 22+x 23+x 24+9 14 15 13x 31+x 32+x 33+x 34+7x 41++x 42x 43+x 44
1701018067
1701018068
问题是，要求在满足约束条件（*）的情况下，求使目标函数T最小的解。
1701018069