下载文档原格式
第三章 线性规划的对偶理论内涵一致但从相反角度提出的一对问题互为对偶（Dual ）问题。
例如，我们可以问当四边形的周长一定时，什么形状的面积最大？答案当然是正方形；我们也可以这样来问，四边形的面积一定时，什么形状的周长最短？答案同样是正方形。
对偶现象相当普遍，它广泛地存在于数学、物理学、经济学等诸多领域。
每一个线性规划问题都有和它相伴随的另一个问题，一个问题称为原问题，则另一个则称为其对偶问题。
原问题与对偶问题有着非常密切的关系，以至于可以根据一个问题的最优解，得出另一个问题最优解的全部信息。
然而，对偶性质远不仅是一种奇妙的对应关系，它在理论和实践上都有着广泛的应用。
§1对偶问题的提出对偶理论是以对偶问题为基础的，研究对偶理论，首先必须讨论对偶问题的提出。
对偶问题可以从经济学和数学两个角度来提出，本教材仅限于从经济学角度提出对偶问题。
[例3-1] 构造例2-1的对偶问题我们已构造了例2-1追求最大利润的数学模型（见第6页），现在让我们从另外一个侧面来反映一下该问题。
倘若工厂有意放弃甲、乙两种产品的生产，而将其所拥有的资源转让出去；假设有一厂商要购买该工厂的三种资源，那么对三种资源的报价问题将成为关注的焦点。
设1y 、2y 和3y 分别代表厂商对A 、B 、C 三种资源的报价，那么站在厂商的立场上，该问题的数学模型又将是什么样子的呢？首先分析一下厂商购买所付出的代价32112168y y y w ++=。
自然，作为买方厂商当然是希望价格压得越低越好，因此厂商追求的应是付出代价的最小值，即：32112168min y y y w ++=然而，价格能否无限地压低呢？答案当然是否定的，因为最低报价必须以卖方能够接受为前提，否则报价再低也是没有意义的。
落实到这一问题上就是必须保证企业让出资源的收益不低于自己生产创造的利润，即：1y + 42y ≥ 221y +43y ≥ 31y ，2y ，3y ≥ 0至此我们得到了一个完整的线性规划模型：32112168min y y y w ++=1y + 42y ≥ 221y +43y ≥ 31y ，2y ，3y ≥ 0将站在厂商的立场上建立起来的数学模型同站在工厂立场上所建立的数学模型加以对比，可以发现它们的参数是一一对应的。
资料](https://img.taocdn.com/s1/m/6c262ea48bd63186bdebbc41.png)
线性规划的对偶原理3。
1 线性规划的对偶问题一、 对偶问题的提出换位思考家具厂的线性规划问题,该问题站在家具厂管理者的角度追求销售收入最大213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。
他 需要与家具厂谈判付给该厂每个工时的价格。
如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图,肯把资源出租给他, 又使自己付的租金最少.目标：租金最少；1y —付给木工工时的租金；2y -付给油漆工工时的租金2150120m in y y w +=所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入 502421≥+y y2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入 30321≥+y y3）付给每种工时的租金应不小于零 0,021≥≥y y二、 原问题与对偶问题的数学模型1. 对称形式的对偶原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。
原问题:⎪⎩⎪⎨⎧≥≥=0min X b AX CX z对偶问题:⎪⎩⎪⎨⎧≥≤=0max Y C YA Yb w2. 非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型）,即⎪⎩⎪⎨⎧≥==0min X b AX CX z则其对偶问题的数学模型为⎪⎩⎪⎨⎧≤=是自由变量Y C YA Yb w max可把原问题写成其等价的对称形式:min z =CX AX ≥b AX ≤b X ≥0即 min z =CX⎥⎦⎤⎢⎣⎡-A A X ≥⎥⎦⎤⎢⎣⎡-b bX ≥0设Y 1=(y 1,y 2,…,y m ）， Y 2=（y m+1，y m+2，…,y 2m ）。
第三章 线性规划及其原始－对偶算法（I ）3.1 线性规划问题的历史线性规划问题最早是由G .B.Dantzig 在1947年以前设想出来的。
他当时作为联邦空军审计员的一名数学顾问，需要开发一个数学规划的工具，用于制定布置、训练、后勤保障的方案。
由于这项工作，他于1948年出版了《线性结构的规划》一书。
1948年夏天：T.C. Koopmans&G .B.Dantzig 提出了“线性规划”的名称； 1949年：G .B.Dantzig 提出了单纯形方法。
在此之前：Fourier, W.Karush, L.V . Kantorovich 等人的工作都曾涉及到线性规划的有关工作。
1950－1960：线性规划的理论得到了进一步的发展；1975年：L.V . Kantorovich 和T.C. Koopmans 获得诺贝尔经济奖－对资源最优分配理论的贡献；1979年：L.G .. Khanchian 的椭球算法； 1984年：N. Karmarkar 的投影尺度算法。
3.2 线性规划问题的几何解释一、线性规划问题的标准型min ..0c xAx b s t x Τ=⎧⎨≥⎩ (LP)其中,,,n n m m n x R c R b R A R ×∈∈∈∈。
另外，总假设： 的元素都为整数，rank 0.b ≥),,(c b A m A =)(记： 可行域： {:,n P x R Ax b x =∈=≥0}}最优解集：*{:(LP)P x P x =∈是的最优解为了深入理解线性规划的目标函数和约束条件，我们首先介绍一些基本的概念。
二、平面、半空间、多面体(1) 超平面：对于1,n R R αβ∈∈，定义超平面{:n T H x R x }αβ=∈= (2) 半空间：{:{:n T L nTU H x R x H x R x }}αβαβ=∈≤=∈≥——两个闭半空间{:{:i n T L in TUH x R x H x R x }}αβαβ=∈<=∈>——两个不相交的开半空间H 是和L H iL H 的边界超平面。
α：超平面H 的法线，因为,z H y H ∀∈∈0，有 ()T T T y z y z αααββ−=−=−=，即)(z y −⊥α即：法向量α与所有平行于超平面H 的向量垂直。
又：,iL z H w H ∀∈∈，有()T T T w z w z αααββ−=−<−=0即：法向量α与由超平面指向内部的任意向量构成钝角，也即L H α是指向超平面的外部的。
L H对于线性规划的标准型，超平面{:n T H x R c x }β=∈=是目标函数的T c x 一个等值面，价格向量c 是等值面的法线。
(3) 多面体（polyhedron ）：由有限个闭半空间的交集形成的一个集合。
(4) 多胞形（polytope ）：非空有界多面体。
思考题：证明一个标准型的线性规划问题的约束区域是一个凸多面体。
三、仿射集、凸集和锥(1) 线性组合：1pi i i x λ=∑，其中，1212,,,,,,,p n p x x x R λλλR ∈∈L L 。
(2)仿射组合：1pii i x λ=∑，其中，1212,,,, ,,,p np x x x R λλλR ∈∈L L ，。
11pi i λ==∑(3) 凸组合：1pii i x λ=∑，其中，1212,,,, ,,,p np x x x R λλλR ∈∈L L ，，11pi i λ==∑10(1,2,,i i p )λ≥≥=L 。
(4) 凸锥组合：1pi i i x λ=∑，其中，1212,,,, ,,,p n p x x x R λλλR ∈∈L L ，0(1,2,,)i i p λ≥=L 。
例如，考虑两个点1x 和2x 的情况： 令121,,s s s R λλ=−=∈，则121212112(1)()x x s x sx x s x λλ+=−+=+−x x s x Δ+=1， 所以，相异点1x 和2x 的：z 所有仿射组合：由这两个点确定的整条直线；（R s ∈∀，所以是整条直线）z 所有凸组合：连接这两个点的线段；（10≤≤s ，所以是线段） z 凸组合是仿射组合；反之不成立，只有当1x ＝2x 时成立。
(5) 仿射集：，S 必包含S 12,,n S R x x S ⊂∀∈1x 和2x 的所有仿射组合。
（包含两个点，必包含经过这两个点的直线）S S (6) 凸集：，S 必包含S 12,,n S R x x S ⊂∀∈1x 和2x 的所有凸组合。
（包含两个点，必包含经过这两个点的线段）S S显然：z 超平面是仿射集且凸集； z 闭半空间：凸集但不是仿射集；z 线性流形{:}n x R Ax b ∈=是仿射集且凸集；z 线性规划的可行域{:,n P x R Ax b x 0}=∈=≥是凸集但不是仿射集； (7) 内点与边界点：给定集合,,n S R x S ⊂∈0ε∃>，使得{:||||}n B y R x y S ε=∈−<⊂则称x 是的一个内点。
反之，S x 是的一个边界点。
S 对于一个凸集，一个关键的几何特性是下述的分割定理：定理3.1（分割定理）：令是S n R 中的凸子集，且x 是的一个边界点，则存在一个包含S x 的超平面H ，使得或包含在中，或包含在中。
S L H U H 基于这个分割定理，我们可以定义一个支撑超平面H ： 1). H 和的交是非空的； S 2). 包含。
L H SH给定凸多面体及其支撑超平面P H ，称F P H =I 为的一个面。
P z 若dim ：就有一个顶点；()0F =Pz 若dim ：就有一条边； ()1F =P z 若dim dim ()：就有一个面； ()F =1P −P (8) n R 的一个子集的维数：C 仿射子空间：对于一个子空间和一个向量n S R ⊂n R α∈，集合{|S y x x S α}α==+∈称之为n R 的一个仿射子空间。
即：用一个向量把一个子空间转换成为一个仿射子空间。
dim(S α)=dim()=中线性独立向量的最大个数S S 子集C 的维数：包含C 的任意一仿射子空间的最小维数。
(9) 锥：非空集合，若n C R ⊂,x C 0λ∀∈≥总有x C λ∈，则称是一个锥。
C 四、顶点和基可行解 多面体的顶点：几何实体；线性等式与不等式组的基可行解：代数上的定义。
在线性规划的理论中，将这两个概念联系在一起，用几何直觉导引出代数工具。
顶点：在凸集中的一个点C x ，如果x 不是C 另外两个不同点的凸组合，则称它是C 的一个顶点。
即：一个顶点是这样一个点，它不能位于凸集中另外两个点的连线的线段之中——凸多面体的“端点”。
min ..0c xAx b s t x Τ=⎧⎨≥⎩ (LP)其中,,,n n m m n x R c R b R A R ×∈∈∈∈m n ，≤。
可行域 {:,n P x R Ax b x =∈=≥0}令，对于12(,,,)n A A A A =L x P ∈有：1212(,,,)n n x xA A A x ⎛⎞⎜⎟⎜⎟b =⎜⎟⎜⎟⎝⎠L M即：1122n n x A x A x A b +++=L 。
称j A 为变量j x 对应的列。
定理3.2 x P ∈，则x 是的一个顶点P ⇔x 的正分量对应的A 中的各列是线性独立的。
证明：不仿设，其中12(,,,,0,0,,0)(,0)T T p B x x x x x ==L L 0(1,2,,)i x i p >=L ，记(,)A B N =，B N x x x ⎛⎞=⎜⎟⎝⎠，其中B 是A 的前列。
则，p B Ax b Bx b =⇔=。
""⇒ 用反证法，假设x 是p 的一个顶点，但B 的各列不线性独立，则存在一个非零向量w ，使得0Bw =。
令12,B B B B x x w x x w δδ=+=−，由于，所以对于充分小的0B x >0δ>，有。
显然120,0B B x x ≥≥12B B Bx Bx b ==。
定义：1122(,0),(,0)T T B Bx x x x ==，则12Ax Ax b ==，所以12,x x P ∈，且121122x x x =+，与x 是p 的一个顶点矛盾。
用反证法，假设"⇐"x 不是的一个顶点，则存在p 12,,0y y P λ1,∈<<使得12(1)x y y λλ=+−。
因为，所以0N x =120N N y y ==。
令1w x y =−，则为非零向量，且，所以w 10B B B Bw Bx By b b =−=−=B 中各列线性相关，与假设矛盾。
证毕令，),(N B A =m mB R×∈为满秩矩阵，是(LP)的一个基，B N x x x ⎛⎞=⎜⎝⎠⎟，bAx =⇔bNx Bx N B =+⇔bB Nx B x N B 11−−=+，，令=0，若⇔N B Nx B b B x 11−−−=N x 100B b x −⎛⎞=≥⎜⎟⎝⎠，称之为(LP)的一个基可行解。
推论3.1 x 是(LP)的一个基可行解⇔x P ∈是的一个顶点。
P 推论3.2 (LP)的可行域至多有各顶点。
m n C由于假设的元素都为整数，所以任一个基解其分量的绝对值是有界的。
),,(c b A 定理3.3 令x 是一个基解，则有，其中βα1!||−≤m j m x |}{|max ,ij ji a =α，|}{|max 1j mj b ≤≤=β注：该结论及其证明的思想非常有用。
证明：因为B B B det *1=−，而0det ≠B 为整数，则必有，所以分母绝对值大于或等于1，而1|det |≥B *B 每个元素等于B 的)1(−m 阶子式的行列式，而B 的阶子式的行列式是)1(−m A 中的)!1(−m 个)1(−m 个元素连乘积之和，其绝对值不大于。
由于每一个是1)!1(−−m m αj x 1−B 中的m 个元素与中的个元素对应乘积之和，所以。
b m βα1!||−≤m j m x 定理3.4 假定标准的线性规划问题满足(i) rank m A =)(, (ii) φ≠P , (iii) 目标函数有下界，则在最优值相等的意义下，它与下述线性规划等价：x c T ni M x x bAx t s xc i T ,,2,1, 0..min L =≤≥=其中，是集合的最大下界。
|}||,max{||},||,max{|,)!1(z b c a m M j i ij m ==+=βαβαz }0,|{≥=x b Ax x c T 由该定理：我们总可以假定可行域是有界区域。
