04-第三章 线性规划和其原始-对偶算法-1(第3次课).pdf

第三章 线性规划及其原始－对偶算法（I ） 3.1 线性规划问题的历史 线性规划问题最早是由G.B.Dantzig 在1947 年以前设想出来的。他当时作为 联邦空军审计员的一名数学顾问，需要开发一个数学规划的工具，用于制定布置、 训练、后勤保障的方案。 由于这项工作，他于1948 年出版了《线性结构的规划》一书。 1948 年夏天：T.C. KoopmansG.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 c x Ax b (LP) ⎧ . . s t ⎨ x ≥0 ⎩ 其中x ∈R n ,c ∈R n ,b ∈R m , A ∈Rm×n 。 另外，总假设：b ≥0. 的元素都为整数，rank 记： ( ,A,b)c A( )m 可行域：P {x =∈Rn :Ax b ,x =≥0} 最优解集：P* {x =∈P :x是(LP)的最优解} 为了深入理解线性规划的目标函数和约束条件，我们首先介绍一些基本的概 念。 二、平面、半空间、多面体 1 n 1 n T (1) 超平面：对于α ∈R ,β ∈R ，定义超平面H {x =∈R :α x β} (2) 半空间： n T H L {x =∈R :α x ≤β} ——两个闭半空间 n αT β H U {x =∈R : x ≥ } i n T H L {x =∈R :α x β} ——两个不相交的开半空间 i n αT β H U {x =∈R : x } i H 是H 和 的边界超平面。 H L L α H ：超平面 的法线，因为∀z ∈H , y ∈H ，有 T T T α (y −z ) α y =−α z β =−β 0 ，即( αy⊥)z −