?x1?4x2?2x3?8 ? ?3x1?2x2?6?x,x,x?0?123解 编写Matlab程序如下： c=[2;3;1];
a=[1,4,2;3,2,0]; b=[8;6];
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
1.6 可以转化为线性规划的问题
很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如： 例4 问题为
min|x1|?|x2|???|xn|s. t. Ax?b其中x?[x1?xn]T，A和b为相应维数的矩阵和向量。
要把上面的问题变换成线性规划问题，只要注意到事实：对任意的xi，存在ui,vi?0满足
xi?ui?vi，|xi|?ui?vi 事实上，我们只要取ui?xi?|xi||x|?xi，vi?i就可以满足上面的条22件。
这样，记u?[u1?un]T，v?[v1?vn]T，从而我们可以把上面的问题变成
min s. t. ??(ui?1ni?vi)
?A(u?v)?b
?u,v?0
§2 运输问题(产销平衡)
例5 某商品有m个产地、n个销地，各产地的产量分别为a1,?,am，各销地的需求量分别为b1,?,bn。若该商品由i产地运到j -6-
销地的单位运价为cij，问应该如何调运才能使总运费最省？
解：引入变量xij，其取值为由i产地运往j销地的该商品数量，数学模型为
min??cxi?1j?1mnijij
?n??xij?ai,i?1,?,m?j?1?ms.t. ??xij?bj,j?1,2,?,n
?i?1?xij?0??显然是一个线性规划问题，当然可以用单纯形法求解。
对产销平衡的运输问题，由于有以下关系式存在：
?n?n?m?m?bj??????xij?????xij???ai j?1i?1?j?1?j?1?i?1?i?1nm其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习
惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。
表上作业法是单纯形法在求解运输问题时的一种简化方法，其求解工作在运输表上进行逐步迭代如下：先按某一规则找出一个初始解（初始调运方案）；再对现行解作最优性判断；若这个解不是最优的，就在运输表上对它进行调整改进，得一新解；再判断，再改进，直到得到最优解。
§3 指派问题（又称分配问题Assignment Problem）
3.1 指派问题的数学模型
例6 拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？
容易看出，要给出一个指派问题的实例，只需给出矩阵
-7-
C?(cij)，C被称为指派问题的系数矩阵。
引入变量xij，若分配i干j工作，则取xij?1，否则取xij?0。上述指派问题的数学模型为
min??cxi?1j?1nnijij
?n??xij?1,i?1,2,?,n?j?1n??s.t.??xij?1,j?1,2,?,n ?i?1?xij?0 或 1 ,i,j?1,2,?,n??? (5)
(5)的可行解既可以用一个矩阵(称为解矩阵)表示，其每行每
列均有且只有一个元素为1，其余元素均为0，也可以用1,?,n中的一个置换表示。
(5)的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为
，其非负可行解的分量只能取0或1，故约束xij?0或1可改写?1）
为xij?0而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中m?n，ai?bj?1。
3.2 求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C?(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B?(bij) ，则以C或B为系数矩阵的指派问题具有相同的最优指派。
利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B，而最优解不变。若能在B 中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B为系数阵的指派问题的最优解，从而也
-8-
是原问题的最优解。
由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。
下面通过一例子来说明该算法。 例7 求解指派问题，其系数矩阵为
?16?17 C???24??17151922?211918??
221817??192216?解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
?1?0 B1???7??1047?421?? 510??360?再将第3列元素各减去1，得
?10*37??*?0411? B2??*?7500??*?1350??以B2为系数矩阵的指派问题有最优指派
???1234??? 2134??由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例8 求解系数矩阵C的指派问题
?127979??89666??? C??717121412?
??15146610????4107106??
-9-
解：先作等价变换如下
?7?6?7?6?4?127979??50*20?89666??2300*????717121412???0*1057???15146610???980*0??36?4107106???06 ?2?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 对偶理论与灵敏度分析
4.1 原始问题和对偶问题
-10-
数学建模（教案）第一章--线性规划
