23对偶理论 记w=cBB-1,则上方条件在1≤j≤n时为ATw≤c,在j>n时为-B≤0，于是w是对属 问题可行解，而计算得b=cB-1b为原问题最优解，因此由弱对偶定理可知为对偶问题最优解 最代值一致。 由于DP)的对偶与LP)等价，若对偶问题有最优解，则同样得到原问题也有最优解，最优值 致。 从对偶定理出发，可以得到一个重要的判别条件 定理2.27（互补松弛定理） 若(LP)与DP)有可行解x 与w,则x”,w”都是最优解的充要条件为 [T(ATw*-c)=0 IwT(Ar*-6)=0 证明充分性：利用弱对偶定理第一条的证明过程，条件成立时即有Tx=w,由弱对偶定理第三 条可知两者都是最优解。必要性：考虑逆否命题，若这两个式子中有不成立的，仍然利用弱对偶定理 第一条证明过程，必然有cP*>w,与最优值相等矛盾，于是不可能二者都是最优解。 从而，只要知道了其中一个问题的最优解，就可以根据互补松弛定理解出另一个最优解。一个例 子是，若是标准，其优解用可行基划分表示为 ,则最优值为cBB-1b。练习2.6中 0 给出了标准型问题的对偶形式，取w=B-T召时，即满足厂w=Tx,验证可知满足约束条件（计算 发现AT和≤c即为原问题的最优判定条件)，于是这就是对偶问题的最优解。 对偶问题的另一个有趣的性质是，对LP)考虑绪论中提到的(K-T条件。构造乘子世，0，则 L红，，)=cTx-(Ar-)-x,写出此时的KT条件 c-ATw -wo=0 Ax≥6，x≥0 w≥0,0≥0 wT(Ax-b)=0,w=0 将0=c一ATw代入，即得到 Ax≥b,x20 w≥0，ATw≤c wT(Ar-6)=0,xT(ATw-c)=0 而这恰恰是原问题、对偶问题的要求与互补松弛条件。这意味者，对于线性规划问题，KT条件是一 个充分心要条件。 2.3.3灵敏度分析 最后，我们来给出对偶问题的一个实际含义。实际问题中，很多时候是基于某些采集数据来决定 模型的系数。此时，势必会出现系数的扰动及引起的变化。所谓灵敏度分析，便是当系数有微小变化 时最优解的反应
2.3 对偶理论 记 w = c T BB−1，则上方条件在 1 ≤ j ≤ n 时为 AT w ≤ c，在 j > n 时为 −w ≤ 0，于是 w 是对偶 问题可行解，而计算得 w T b = c T BB−1 b 为原问题最优解，因此由弱对偶定理可知 w 为对偶问题最优解， 最优值一致。 由于 (DP) 的对偶与 (LP) 等价，若对偶问题有最优解，则同样得到原问题也有最优解，最优值一 致。 从对偶定理出发，可以得到一个重要的判别条件： 定理 2.27 (互补松弛定理) ♡ 若 (LP) 与 (DP) 有可行解 x ∗ 与 w ∗，则 x ∗ , w∗ 都是最优解的充要条件为： x ∗T (AT w ∗ − c) = 0 w ∗T (Ax∗ − b) = 0 证明 充分性：利用弱对偶定理第一条的证明过程，条件成立时即有 c T x ∗ = b T w ∗，由弱对偶定理第三 条可知两者都是最优解。必要性：考虑逆否命题，若这两个式子中有不成立的，仍然利用弱对偶定理 第一条证明过程，必然有 c T x ∗ > bT w ∗，与最优值相等矛盾，于是不可能二者都是最优解。 从而，只要知道了其中一个问题的最优解，就可以根据互补松弛定理解出另一个最优解。一个例 子是，若原问题是标准型，其最优解用可行基划分表示为 B−1 b 0 ! ，则最优值为 cBB−1 b。练习2.6中 给出了标准型问题的对偶形式，取 w = B−T c T B 时，即满足 b T w = c T x，验证可知满足约束条件 (计算 发现 AT w ≤ c 即为原问题的最优判定条件)，于是这就是对偶问题的最优解。 对偶问题的另一个有趣的性质是，对 (LP) 考虑绪论中提到的 (K-T) 条件。构造乘子 w, w0，则 L(x, w, w0) = c T x − w T (Ax − b) − w T 0 x，写出此时的 K-T 条件： c − AT w − w0 = 0 Ax ≥ b, x ≥ 0 w ≥ 0, w0 ≥ 0 w T (Ax − b) = 0, wT 0 x = 0 将 w0 = c − AT w 代入，即得到： Ax ≥ b, x ≥ 0 w ≥ 0, AT w ≤ c w T (Ax − b) = 0, xT (AT w − c) = 0 而这恰恰是原问题、对偶问题的要求与互补松弛条件。这意味着，对于线性规划问题，K-T 条件是一 个充分必要条件。 2.3.3 灵敏度分析 最后，我们来给出对偶问题的一个实际含义。实际问题中，很多时候是基于某些采集数据来决定 模型的系数。此时，势必会出现系数的扰动及引起的变化。所谓灵敏度分析，便是当系数有微小变化 时最优解的反应。 24
23对偶理论 仍然考虑标准形式，在b作△b的扰动后，问题变为 min cx st.Ar=b+△b x≥0 假设已经得到了原间题的最优解®）=(B0),其满足可行性条件B一6≥0与最优性条件以 0 cB-1N≥0这里相当于对每个-合为整体向量) 定理2.28扰动问圈的最优解) 假设扰动后的b+Ab满足可行性条件B-1b+△)≥0，剥2B） B-1b+△是扰动后 0 问题的最优解，新的最优值即为B-1(亿+△b)。 证明由于最优性条件与6无关，只要6+△b仍满足可行性条件，(2知）= (B-16+△)保持最优 0 性条件，从而是扰动后的最优解。直接计算得扰动后的最优值。 记原问题目标函数最优值是()=B-1b,新问题最优值(b+△b)=B-1(b+△b),此时 化+△)-=c召B-1△b。当原问题最优解非退化（回顾其定义是B-b每个分量都大于0）时，只 要I△M足够小，总能满足B-1(b+△b)≥0。于是得结论： 定理2.29解的扰动) 当线性规划问题标准型的最优解 /B-1b 0非化时，有：0=B-a 证明由定义，了：)=1m0=B-TcB,这里对向量的除法代表除以每个分量后拼 成向量。 而根据之前的讨论，B-Tcg即为标准型问题对偶问题的最优解山。 25
2.3 对偶理论 仍然考虑标准形式，在 b 作 ∆b 的扰动后，问题变为 min c T x s.t. Ax = b + ∆b x ≥ 0 假设已经得到了原问题的最优解 xB xN ! = B−1 b 0 ! ，其满足可行性条件 B−1 b ≥ 0 与最优性条件 c T N − c T BB−1N ≥ 0(这里相当于对每个 cj − zj 合为整体向量)。 定理 2.28 (扰动问题的最优解) ♡ 假设扰动后的 b + ∆b 满足可行性条件 B−1 (b + ∆b) ≥ 0，则 xB xN ! = B−1 (b + ∆b) 0 ! 是扰动后 问题的最优解，新的最优值即为 c T BB−1 (b + ∆b)。 证明 由于最优性条件与 b 无关，只要 b + ∆b 仍满足可行性条件， xB xN ! = B−1 (b + ∆b) 0 ! 保持最优 性条件，从而是扰动后的最优解。直接计算得扰动后的最优值。 记原问题目标函数最优值是 z(b) = c T BB−1 b，新问题最优值 z(b + ∆b) = c T BB−1 (b + ∆b)，此时 z(b + ∆b) − z(b) = c T BB−1∆b。当原问题最优解非退化 (回顾其定义是 B−1 b 每个分量都大于 0) 时，只 要 ∥∆b∥ 足够小，总能满足 B−1 (b + ∆b) ≥ 0。于是得结论： 定理 2.29 (解的扰动) ♡ 当线性规划问题标准型的最优解 B−1 b 0 ! 非退化时，有 ∇bz(b) = B−T cB。 证明 由定义，∇bz(b) = lim∥∆b∥→0 z(b+∆b)−z(b) ∆b = B−T cB，这里对向量的除法代表除以每个分量后拼 成向量。 而根据之前的讨论，B−T cB 即为标准型问题对偶问题的最优解 w ∗。 25
第3章网络流与动态规划 内容提要 ▣运拾问题 ☐最小成本（循环）流 口最短路问题 口动态规划基本思路 口最大流问题 口背包问题、设各更新问题 3.1网络最优化 网络最优化问题包括运输问题、最短路问题、最大流问题等等，是线性规划的特例，也有着重大 的实际意义。因为网络模型的特殊数学结构，可以设计出比一般线性规划效率更高的求解算法。本节 讨时论两个重要的例子，由于重在解法与思路，省略部分证明的细节。 3.1.1运输模型 定义3.1（运输问题） 形如 t∑到=i=1m x≥0 i≤m,j≤n 的线性规划问题被称为运输问题。 至有时会放宽限制，将条件变为∑西≤与∑沿之山： 将8看作第i个工厂的货物量，山，看作第j个需求点的需求量，C看作第i个工厂到第j个需求 点的运费，运输问题的实际意义便是找一个总运费最小的供货方案。在收支平衡的情况（也即不放宽条 件的限制，∑∑=可=∑壮1s==1d,于是必须∑1s=∑=1d才可能有解。 4练习3.1计算运输问题的对偶问题。 解根据标准型对偶的结采，直接计算（注意矩阵A的形式）可得对偶问题为： max ∑+∑4 s.t.+y≤c i<m.j<n 事实上，由于∑泗1$：=∑=1山，所有出同加t、防同减t后满足的约束不变，目标函数也不变，因 此可以不妨取定某一个的值，如假设山1=0
第 3 章 网络流与动态规划 内容提要 h 运输问题 h 最短路问题 h 最大流问题 h 最小成本 (循环) 流 h 动态规划基本思路 h 背包问题、设备更新问题 3.1 网络最优化 网络最优化问题包括运输问题、最短路问题、最大流问题等等，是线性规划的特例，也有着重大 的实际意义。因为网络模型的特殊数学结构，可以设计出比一般线性规划效率更高的求解算法。本节 讨论两个重要的例子，由于重在解法与思路，省略部分证明的细节。 3.1.1 运输模型 定义 3.1 (运输问题) ♣ 形如 min Xm i=1 Xn j=1 cijxij s.t. Xn j=1 xij = si i = 1, . . . , m Xm i=1 xij = dj j = 1, . . . , n xij ≥ 0 i ≤ m, j ≤ n 的线性规划问题被称为运输问题。 有时会放宽限制，将条件变为 Pn j=1 xij ≤ si 与 Pm i=1 xij ≥ dj。 将 si 看作第 i 个工厂的货物量，dj 看作第 j 个需求点的需求量，cij 看作第 i 个工厂到第 j 个需求 点的运费，运输问题的实际意义便是找一个总运费最小的供货方案。在收支平衡的情况 (也即不放宽条 件的限制)， Pm i=1 Pn j=1 xij = Pm i=1 si = Pn j=1 dj，于是必须 Pm i=1 si = Pn j=1 dj 才可能有解。 练习 3.1 计算运输问题的对偶问题。 解 根据标准型对偶的结果，直接计算 (注意矩阵 A 的形式) 可得对偶问题为： max Xm i=1 siui + Xn j=1 djvj s.t. ui + vj ≤ cij i ≤ m, j ≤ n 事实上，由于 Pm i=1 si = Pn j=1 dj，所有 ui 同加 t、vj 同减 t 后满足的约束不变，目标函数也不变，因 此可以不妨取定某一个的值，如假设 u1 = 0
3.1网络最优化 对运输问题的解法和单纯形法的想法一致，都包含确定初始可行基解、最优判定与转轴运算的过 程。自然，由于运输问题的特殊性，可对算法进行一些调整。先引人回路的概念 定义3.2（回路） 对于一些互不相同的下标(，)，，(2,2)，若它们满足2p-1=即与p=m+1,其中 p=1,2,,k,且2+1定义为1，则称这些下标构成一个回路 若一族下标中能挑出一些组成回路，则称这族下标中存在回路。 直观来看，这就代表者这些下标构成的点在平面上顺次连接，可以形成一个封闭图形，且每次连 线交替运用水平线与竖直线。最简单的例子是，一个长方形的四个角的坐标可以形成一个回路。 有了回路的定义，就可以考虑运输问题的可行基解： 定理33（运输向题的可行基解） 在运输问题中，一个可行解工是可行基解当且仅当其至多有m十n-1个下标非零，且非零分量 的下标中不存在回路。 证明首先，虽然限制条件共有m十n个方程，但由于∑m1=∑”=1山的要求，最后一个方程可以 被其他方程推出，因此事实上只有m+n-1个独立方程，从而可行基分量个为m+n-1个。 将方程组（含最后一个）写成A红=b的形式，由于每个x)在恰好出现两次，也就对应A的每一列 恰好有i与m+两个元素为1，其他为0。若下标出现回路，假设回路中的分量为(1，i),,(2,2) 对应A的第a1,..,2列，考虑》，（一1）a:,由于相邻列前系数正负不同，对应相同的分量互相抵 消，因此此式结果为0，从而A的这些列线性相关，不可能成为可行基的一部分。 反之，若A的某些列线性相关，则假设∑kk账=0，k≠0，由于对每个G:必须有和它有共同 非零分量的列消去，通过操列可以得到其中存在回路 综上即证明了，非零分量的下标不存在回路等价于它们对应的列线性无关，而利用线代知识这又 等价于存在包含它们的可行基划分（这里由于A的各行不独立，可行基划分只需要找出互相线性无关 的m+n一1列，即可以去掉某行得到可逆矩阵B),于是它们构成可行基解。 根据这个要求，有一个简单的方法寻找可行基解： 算法3.4（运输问题初始化-西北角法） 注意：算法中对、的修改只是暂时的，在算法结束后还原。 1.初始化下标i=1.方=1。 2.若当前i,j对应的s为0，则i增加1；否则若山为0，则j增加1（都为0时只有i增加）。 当i>m或j>n时停止，否则进入下一步。 3.令=min{s,d},记录其下标为可行基（即使=0），并将s,山都减去，回到上 一步。 证明这个算法相当于：先让第一家工厂给第一个需求点供货，如果工厂货物量用完就换工厂，需求点 拿到足够的货物就换需求点，直到全部供完。以此思路容易证明可行性。 在这样的计算过程中，每次确定的，都只增不减，假设最后选出的下标为(，)到(，)，由 过程可以发现每一个比起前一个i增加1或j增加1，从(1,1)到(m,n)一共选出了m+n-1个x。 此外，这样的增加方式也与存在回路的定义矛盾，因为如此形成的是必须一条折线，不会存在环
3.1 网络最优化 对运输问题的解法和单纯形法的想法一致，都包含确定初始可行基解、最优判定与转轴运算的过 程。自然，由于运输问题的特殊性，可对算法进行一些调整。先引入回路的概念： 定义 3.2 (回路) ♣ 对于一些互不相同的下标 (i1, j1), . . . ,(i2k, j2k)，若它们满足 i2p−1 = i2p 与 j2p = j2p+1，其中 p = 1, 2, . . . , k，且 j2k+1 定义为 j1，则称这些下标构成一个回路。 若一族下标中能挑出一些组成回路，则称这族下标中存在回路。 直观来看，这就代表着这些下标构成的点在平面上顺次连接，可以形成一个封闭图形，且每次连 线交替运用水平线与竖直线。最简单的例子是，一个长方形的四个角的坐标可以形成一个回路。 有了回路的定义，就可以考虑运输问题的可行基解： 定理 3.3 (运输问题的可行基解) ♡ 在运输问题中，一个可行解 x 是可行基解当且仅当其至多有 m + n − 1 个下标非零，且非零分量 的下标中不存在回路。 证明 首先，虽然限制条件共有 m + n 个方程，但由于 Pm i=1 si = Pn j=1 dj 的要求，最后一个方程可以 被其他方程推出，因此事实上只有 m + n − 1 个独立方程，从而可行基分量个数为 m + n − 1 个。 将方程组 (含最后一个) 写成 Ax = b 的形式，由于每个 xij 在恰好出现两次，也就对应 A 的每一列 恰好有 i 与 m+j 两个元素为 1，其他为 0。若下标出现回路，假设回路中的分量为 (i1, j1), . . . ,(i2k, j2k)， 对应 A 的第 a1, . . . , a2k 列，考虑 P2k i=1(−1)iai，由于相邻列前系数正负不同，对应相同的分量互相抵 消，因此此式结果为 0，从而 A 的这些列线性相关，不可能成为可行基的一部分。 反之，若 A 的某些列线性相关，则假设 P k λkak = 0, λk ̸= 0，由于对每个 ai 必须有和它有共同 非零分量的列消去，通过排列可以得到其中存在回路。 综上即证明了，非零分量的下标不存在回路等价于它们对应的列线性无关，而利用线代知识这又 等价于存在包含它们的可行基划分 (这里由于 A 的各行不独立，可行基划分只需要找出互相线性无关 的 m + n − 1 列，即可以去掉某行得到可逆矩阵 B)，于是它们构成可行基解。 根据这个要求，有一个简单的方法寻找可行基解： 算法 3.4 (运输问题初始化-西北角法) ♠ 注意：算法中对 s、d 的修改只是暂时的，在算法结束后还原。 1. 初始化下标 i = 1, j = 1。 2. 若当前 i, j 对应的 si 为 0，则 i 增加 1；否则若 dj 为 0，则 j 增加 1(都为 0 时只有 i 增加)。 当 i > m 或 j > n 时停止，否则进入下一步。 3. 令 xij = min{si , dj}，记录其下标为可行基 (即使 xij = 0)，并将 si , dj 都减去 xij，回到上 一步。 证明 这个算法相当于：先让第一家工厂给第一个需求点供货，如果工厂货物量用完就换工厂，需求点 拿到足够的货物就换需求点，直到全部供完。以此思路容易证明可行性。 在这样的计算过程中，每次确定的 i, j 都只增不减，假设最后选出的下标为 (i1, j1) 到 (it , jt)，由 过程可以发现每一个比起前一个 i 增加 1 或 j 增加 1，从 (1, 1) 到 (m, n) 一共选出了 m + n − 1 个 xij。 此外，这样的增加方式也与存在回路的定义矛盾，因为如此形成的是必须一条折线，不会存在环。 27
3.1网络景优化 缤上即证明这个算法洗出的是可行甚解 凸练习3.2对以下的供求表利用西北角法计算初始可行基解（这里供给、需求表示总供给量与需求量 S,D交叉位置表示供给成本，不过计算初始可行基解的过程事实上与供给成本无关)。 |DID2D3D4|供给 10 122 20 4146 18 10 需求|5151515 解从左上角开始，S1的供给为15，D1的需求为5，可以完成供给，进入第二家 D1D2D3D4|剩余 S15当前 10 25 S3 10 剩余0151515 S1剩下的部分不足以供应完D2,因此供应10单位后换下一家工厂： ID1D2D3D4|剩余 S151 、0 当前 25 10 剩余051515 重复此过程，直到走到右下角： |D1D2D3D4I剩余 5 15 0 当 剩余|00010 完成初始解构造： |D1D2D3D4|剩余 5 95 0 S3 10 /0 剩余0000 值得注意的是，上面构造出可行基解时同时选取了可行基划分。虽然可行基解中未必有m+n-1 个非零分量，但可行基划分中得到的一定是m+n一1个下标。有了可行基划分以后，就需要判断其 28
3.1 网络最优化 综上即证明这个算法选出的是可行基解。 练习 3.2 对以下的供求表利用西北角法计算初始可行基解 (这里供给、需求表示总供给量与需求量， Si , Dj 交叉位置表示供给成本，不过计算初始可行基解的过程事实上与供给成本无关)。 D1 D2 D3 D4 供给 S1 10 2 20 11 15 S2 12 7 9 20 25 S3 4 14 6 18 10 需求 5 15 15 15 解 从左上角开始，S1 的供给为 15，D1 的需求为 5，可以完成供给，进入第二家： D1 D2 D3 D4 剩余 S1 5 当前 10 S2 25 S3 10 剩余 0 15 15 15 S1 剩下的部分不足以供应完 D2，因此供应 10 单位后换下一家工厂： D1 D2 D3 D4 剩余 S1 5 10 0 S2 当前 25 S3 10 剩余 0 5 15 15 重复此过程，直到走到右下角： D1 D2 D3 D4 剩余 S1 5 10 0 S2 5 15 5 0 S3 当前 10 剩余 0 0 0 10 完成初始解构造： D1 D2 D3 D4 剩余 S1 5 10 0 S2 5 15 5 0 S3 10 0 剩余 0 0 0 0 值得注意的是，上面构造出可行基解时同时选取了可行基划分。虽然可行基解中未必有 m + n − 1 个非零分量，但可行基划分中得到的一定是 m + n − 1 个下标。有了可行基划分以后，就需要判断其 28