?n??xij?1?j?1?ns.t. ??xij?1 ?i?1?xij?0 或 1 ?? (5)
(5)的可行解既可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,?,n中的一个置换表示。
(5)的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为?1），其非负可行解的分量只能取0或1，故约束xij?0或1可改写为xij?0而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中m?n，
ai?bj?1。
3.2 求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C?(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B?(bij) ，则以C或B为系数矩阵的指派问题具有相同的最优指派。
例8 求解指派问题，其系数矩阵为
?16?17 C???24??17?1?0 B1???7??1152122191919182222?18?? 17??16?解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
045342167?1?? 0??0?再将第3列元素各减去1，得
?10*37??*?0411? B2??*?7500??*?1350??以B2为系数矩阵的指派问题有最优指派
-6-
?1234? ??2134??
??由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例9 求解系数矩阵C的指派问题
?127979??89666??? C??717121412?
??15146610????4107106??解：先作等价变换如下
0?127979??50*2?2?6?89666?300*????7?717121412???0*1057????6?15146610?80*0?9??4?636?4107106???0 ??72?0??5??? 4?2??? 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n?5，
最优指派还无法看出。此时等价变换还可进行下去。步骤如下：
(1) 对未选出0元素的行打?； (2) 对?行中0元素所在列打?；
(3) 对?列中选中的0元素所在行打?； 重复（2）、（3）直到无法再打?为止。
可以证明，若用直线划 打?的列与没有打?的行，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令?行元素减去此数，?列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得
?7?4? ?0??11??00202?3000??8353?
?8004?4140??现在已可看出，最优指派为???12345?。 ???24135?
§4 对偶理论与灵敏度分析
-7-
4.1 原始问题和对偶问题
考虑下列一对线性规划模型：
maxcTx s.t. Ax?b,x?0 (P) 和
minbTy s.t. ATy?c,y?0 (D)
称（P）为原始问题，（D）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：
（1） 原始问题中的第j列系数与其对偶问题中的第j行的系数相同； （2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同； （3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同； （4） 在这一对问题中，不等式方向和优化方向相反。 考虑线性规划：
mincTx mins.t.Ax?b,x?0
把其中的等式约束变成不等式约束，可得
?A??b?cTx s.t. ??x???,x?0
??A???b?它的对偶问题是
?y??AT?1??c
?y2?其中y1和y2分别表示对应于约束Ax?b和?Ax??b的对偶变量组。令y?y1?y2，
max?bT?y??bT?1??y2??s.t. AT??则上式又可写成
maxbTy s.t. ATy?c
原问题和对偶的对偶约束之间的关系：
min max
变量行约束??0???0 行约束?无限制???0???0 变量??0???0???0 ??0???0???0 ?无限制?4.2 对偶问题的基本性质
1o 对称性：对偶问题的对偶是原问题。
2o 弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则存在
cTx?bTy。
3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
?是原问题的可行解，y?是对偶问题的可行解，4o 可行解是最优解时的性质：设x?,y?是最优解。 ??by?时，x当cx5o 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。
-8-
TT?,y?分别是原问题和对偶问题的最优解，则 6o 互补松弛性：若x?T(Ax??b)?0,x?T(ATy??c)?0 y例10 已知线性规划问题
min??2x1?3x2?5x3?2x4?3x5
x1?x2?2x3?x4?3x5?4 2x1?x2?3x3?x4?x5?3
j?1,2,?,5 4*3*已知其对偶问题的最优解为y1?,y2?;z?5。试用对偶理论找出原问题的最优
55解。
解 先写出它的对偶问题
maxz?4y1?3y2
y1?2y2?2 ①
y1?y2?3 ②
2y1?3y3?5 ③ y1?y2?2 ④ 3y1?y2?3 ⑤ y1,y2?0
**将y1的值代入约束条件，得②，③，④为严格不等式；由互补松弛性得,y2*****,y2?0；原问题的两个约束条件应取等式，故有 x2?x3?x4?0。因 y1 xj?0,**x1?3x5?4 **2x1?x5?3
**求解后得到x1?1,x5?1；故原问题的最优解为
X?[10001]';??5 。
4.3 灵敏度分析
在以前讨论线性规划问题时，假定aij,bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；
**bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这
些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨论了。
4.4 参数线性规划
参数线性规划是研究aij,bi,cj这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。
-9-
习 题 一
1．试将下述问题改写成线性规划问题：
mm??m?? max?min??ai1xi,?ai2xi,?,?ainxi??
xii?1i?1?i?1????x1?x2???xm?1 st.?
x?0,i?1,?,m?i2．试将下列问题改写成线性规划问题： maxz??cj?1nj|xj|
?n??aijxj?bi(i?1,2,?,m) st.?j?1
?x取值无约束?j3．线性回归是一种常用的数理统计方法，这个方法要求对图上的一系列点(x1,y1),(x2,y2),?,(xn,yn)选配一条合适的直线拟合。方法通常是先定直线方程为
y?a?bx，然后按某种准则求定a,b。通常这个准则为最小二乘法，但也可用其他准
则。试根据以下准则建立这个问题的线性规划模型：
min?|yi?1ni?(a?bxi)|
4．某厂生产三种产品I，II，III。每种产品要经过A,B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1,A2表示；有三种规格的设备能完成B工序，它们以B1,B2,B3表示。产品I可在A,B任何一种规格设备上加工。产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2与B2设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。 产 品 满负荷时的 设备 设备有效台时 I II III 设备费用(元) A1 A2 B1 B2 B3 原料费(元/件) 单 价(元/件) 5 7 6 4 7 0.25 1.25 10 9 8 0.35 2.00 12 11 0.50 2.80 6000 10000 4000 7000 4000 300 321 250 783 200 5．有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：
-10-
1第一章线性规划讲解
