∑x
i=1
n
ij
=1
xij=0 或 1
上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0；可以用1,L,n中的一个置换表示。
问题中的变量只能取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??1
1521221919191822
22?18?? 17??16?
解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
04534216
7?1?? 0??0?
再将第3列元素各减去1，得
?10*37??*?0411? B2=?*
?7500??*?1350??
以B2为系数矩阵的指派问题有最优指派
?1234?
??2134??
??
由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例9 求解系数矩阵C的指派问题
-6-
?127979??89666?
??
C=?717121412?
??
15146610?????4107106?
解：先作等价变换如下
容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，
最优指派还无法看出。此时等价变换还可进行下去。步骤如下：
(1) 对未选出0元素的行打∨； (2) 对∨行中0元素所在列打∨；
(3) 对∨列中选中的0元素所在行打∨； 重复（2）、（3）直到无法再打∨为止。
可以证明，若用直线划没有打∨的行与打∨的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令∨行元素减去此数，∨列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得
0?127979??50*2
?89666??2300*???
?7?717121412?→?0*1057
???
?6?15146610?80*0?9
??4?636?4107106???0
∨
?7?6
2?0??5?∨? 4?2??∨
?7
?4? ?0??11??0
0
38842030100504
2?0??3? ?4?0??
现在已可看出，最优指派为??
?12345?
。 ??
?24135?
§4 对偶理论与灵敏度分析
4.1 原始问题和对偶问题
考虑下列一对线性规划模型：
max和
cTx s.t. Ax≤b,x≥0 (P)
minbTy s.t. ATy≥c,y≥0 (D)
-7-
称（P）为原始问题，（D）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：
（1） 原始问题中的第j列系数与其对偶问题中的第j行的系数相同； （2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同； （3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同； （4） 在这一对问题中，不等式方向和优化方向相反。 考虑线性规划：
mincTx
min
s.t.Ax=b,x≥0
把其中的等式约束变成不等式约束，可得
?A??b?
cTx s.t. ??x≥??,x≥0
??A???b?
它的对偶问题是
?y?
?AT?1?≤c
?y2?
令y=y1?y2，其中y1和y2分别表示对应于约束Ax≥b和?Ax≥?b的对偶变量组。
max
[b
T
?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
?=by?时，x?,y?是最优解。 当cx
5o 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。
?,y?分别是原问题和对偶问题的最优解，则 6o 互补松弛性：若x
?(Ax??b)=0,x?(Ay??c)=0 y
例10 已知线性规划问题
minω=2x1+3x2+5x3+2x4+3x5
s.t. x1+x2+2x3+x4+3x5≥4
-8-
T
T
T
TT
2x1?x2+3x3+x4+x5≥3 xj≥0,已知其对偶问题的最优解为y1=解。
解 先写出它的对偶问题
maxz=4y1+3y2
y1+2y2≤2 ①
y1?y2≤3 ②
2y1+3y3≤5 ③ y1+y2≤2 ④ 3y1+y2≤3 ⑤ y1,y2≥0
将y1,y2的值代入约束条件，得②，③，④为严格不等式；由互补松弛性得
*****x2=x3=x4=0。因 y1,y2>0；原问题的两个约束条件应取等式，故有
**
x1+3x5=4 **2x1+x5=3
*
*
*
j=1,2,L,5
4*3
,y2=;z=5。试用对偶理论找出原问题的最优
55
求解后得到x1=1,x5=1；故原问题的最优解为
X=[10001]';ω=5 。
4.3 灵敏度分析
但实际上这些系数往往是估在以前讨论线性规划问题时，假定aij,bi,cj都是常数。计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；
*
*
**
bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这
些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者
这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨论了。
4.4 参数线性规划
参数线性规划是研究aij,bi,cj这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。
§5 投资的收益和风险
5.1 问题提出
市场上有n种资产si（i=1,2,L,n）可以选择，现用数额为M的相当大的资金风险损失率为作一个时期的投资。这n种资产在这一时期内购买si的平均收益率为ri，
qi，投资越分散，总的风险越少，总体风险可用投资的si中最大的一个风险来度量。
-9-
购买si时要付交易费，（费率pi），当购买额不超过给定值ui时，交易费按购买ui
计算。另外，假定同期银行存款利率是r0，既无交易费又无风险。（r0=5%）
已知n=4时相关数据如表1。
表1
qi
si
s1 s2 s3 s4
ri(%) pi(%) ui(元)
28 2.5 1 103 21 1.5 2 198 23 5.5 4.5 52 25 2.6 6.5 40
试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。
5.2 符号规定和基本假设 符号规定：
si：第i种投资项目，如股票，债券
ri,pi,qi：分别为si的平均收益率，交易费率，风险损失率 ui：si的交易定额 r0：同期银行利率
xi：投资项目si的资金 a：投资风险度 Q：总体收益
基本假设：
1． 投资数额M相当大，为了便于计算，假设M=1； 2． 投资越分散，总的风险越小；
3． 总体风险用投资项目si中最大的一个风险来度量； 4． n种资产si之间是相互独立的；
5． 在投资的这一时期内，ri,pi,qi，r0为定值，不受意外因素影响； 6． 净收益和总体风险只受ri,pi,qi影响，不受其它因素干扰。 5.3 模型的分析与建立
1． 总体风险用所投资的si中最大的一个风险来衡量，即 max{qixi|i=1,2,L,n} 2．购买si所付交易费是一个分段函数，即 交易费=?
?pixi,?piui,
xi>uixi≤ui
而题目所给定的定值ui（单位：元）相对总投资M很少，piui更小，可以忽略不计，这样购买si的净收益为(ri?pi)xi。
3． 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型：
-10-