第一章：线性规划基础.ppt

第一章：线性规划 1.1 线性规划(Linear Programing --- L.P.)概述 一、L.P.概念： L.P.是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产和 经济管理等领域。以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。 二、发展史： 30年代末(苏)康特罗维奇书“生产组织与计划中的数学方法”， 为L.P.建立数学模型和求解奠定了基础。 1、(美)库普曼(T.C. Koopmans)建立了L.P.数学模型，获诺贝经济奖。 2、(美)丹泽(G.B. Dantzig)在1947年提出求解L.P.数模的通用方法 --- 单纯形法。 1946年，世界上第一台计算机问世，使单纯形法处理大规模L.P.数模成为可能。 三、 L.P.问题的求解过程 1、将实际问题转化为数学模型(数学公式)：建模。 2、求解数学模型： ? 图解法： 适合于 2 个变量的 L.P. 数学模型。 ? 单纯形法：适合于任意个变量的 L.P. 数学模型。 3、利用数学模型的最优解获得原问题的最优决策方案。 三、合理下料问题建模:寻求最佳下料方式, 使余料最少. 例 有一批长度为180公分的钢管,需截成70、52和35公分三种管料。它们的需求量应分别不少于 100、150和100个。问应如何下料才能使钢管的余料为最少? 解: 四、特殊的数学模型 1.6 人造基下的单纯形法 --- 两阶段法和大M法 一、什么时候会出现人造基 例：求解下列数模 Min Z = x1－2x2 s.t. x1 + x2 ≥ 2 -x1 + x2 ≥ 1 x2 ≤ 3 x1 , x2 ≥0 当数模的约束条件出现”＝”或”≥”时，要将数模化为规范型， 一般情况下就需要引入人工变量形成人造基。 ? 标准化：引入非负松弛变量 x3、 x4、 x5 令Z = -D , 化成标准型如下 Max D = -x1 + 2x2 s.t. x1 + x2 - x3 = 2 -x1 + x2 - x4 = 1 x2 + x5 = 3 xj ≥ 0 ，j=1~5 ? 规范化：引入非负人工变量 x6、 x7 化成规范型如下 Max D = -x1 + 2x2 s.t. x1 + x2 - x3 + x6 = 2 - x1 + x2 - x4 + x7 = 1 x2 + x5 = 3 xj ≥ 0 ，j=1~7， x5,x6,x7为基变量 规范型解基的形成只要三种可能： ① 由决策变量自然形成的解基： 由具体的物理变量组成，可含在最优解里， ② 由添加松弛变量形成的解基： 每步迭代后的解均是可行解。 ③ 由引入人工变量形成的解基(人造基)：由虚拟人工变量组成，改变了原s.t. 。 二、两阶段法 例：求解下列数模 Min Z = x1－2x2 　…① s.t. x1 + x2 ≥ 2　 …② -x1 + x2 ≥ 1　 …③ x2 ≤ 3　 …④ x1 , x2 ≥0　 …⑤ ? ? ? ? ? ? ? ? ? -1 o 1 2 3 x1 -2 -1 1 2 3 x2 ② ③ ④ ? ? a b c h ? ? ? ? ? 规范化：引入非负松弛变量 x3、 x4、 x5 和非负人工变量 x6、 x7 化成规范型如下 Max D = -x1 + 2x2 s.t. x1 + x2 - x3 + x6 = 2 - x1 + x2 - x4 + x7 =