《运筹学总结》由会员分享，可在线阅读，更多相关《运筹学总结（196页珍藏版）》请在金锄头文库上搜索。
1、东北大学信息科学与工程学院,运 筹 学,第一章 线性规划(LP),1.1 线性规划简史1.2 线性规划问题与模型1.3 线性规划的图解法1.4 线性规划问题的几何意义1.5 线性规划的基本概念1.6 单纯形法1.7 单纯形法的进一步讨论1.8 本章小结,1.1 线性规划简史,1939年, 苏联学者L.V.Kontorovich（康托洛维奇）提出类似线性规划的模型，并用于工业生产中。 1947年, 美国数学家G.B.Dantzig(丹捷格)首次提出著名的单纯形法； 1979年, L.G.Khachian证明椭球算法具有多项式时间性能的算法，从理论上能够超出单纯形法； 1984年, N.Karma
2、rkar设计一个多项式时间的内点算法，在实际上胜过了单纯形法。,1.2 线性规划问题与模型,线性规划的问题,例1: 生产计划问题,某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：,1.2 线性规划问题与模型(续),1.2 线性规划问题与模型(续),决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表
3、示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, unr, 0线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：0,1.2 线性规划问题与模型(续),是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第 1 步 -确定决策变量,设 I的产量II的产量利润,1.2 线性规划问题与模型(续),第 2 步
4、-定义目标函数,Max Z = x1 + x2,1.2 线性规划问题与模型(续),Max Z = 2 x1 + 3 x2,第 2 步 -定义目标函数,1.2 线性规划问题与模型(续),1.2 线性规划问题与模型(续),第 3 步 -表示约束条件,x1 + 2 x2 8 4 x1 164 x2 12x1、 x2 0,1.2 线性规划问题与模型(续),1.2 线性规划问题与模型(续),目标函数 Max Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,x1,x2,该计划的数学模型,1.2 线性规划问题与模型(续),求：最低成本的原料混合方案,Mi
5、n Z= 2x1 + 5x2 +6x3+8x4,1.2 线性规划问题与模型(续),解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4),Min Z= 2x1 + 5x2 +6x3+8x4,例3 某工厂生产A、B两种产品，有关资料如下表所示：,设总成本为z，A、B产品销量为x1、x2，产品C的销售量为x3，报废量为x4，则： max z = 4 x1 + 10 x2 + 3 x3 2 x4,例4 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：,设：xj为第 j 号类型船队的队数（j = 1，2，3，4），z 为总货运成本，则：,min z = 36x1 +
6、 36x2 + 72x3 + 27x4,1.2 线性规划问题与模型(续),2. 线性规划问题的共同特征,1.2 线性规划问题与模型(续),3.线性规划模型的一般形式,4. 线性规划问题的标准形式(1)一般形式,1.2 线性规划问题与模型(续),1.2 线性规划问题与模型(续),(2) 矩阵型,Max Z=CX AX=b X 0,C=(c1 c2 cn ),系数矩阵,资源向量,决策变量向量,价值向量,1.2 线性规划问题与模型(续),(3) 向量型,p1x1+ p2x2 + +pnxn=b,5. 一般线性规划的标准化,1.2 线性规划问题与模型(续),min Z=CX 等价于 max Z = -
7、CX “” 约束：加入非负松驰变量,例：,Max Z = 2x1 + 3x2x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,可正可负（即无约束）；,1.2 线性规划问题与模型,“” 约束： 减去非负剩余变量；,Max,例 ：,例,-6+6 X1+6 10+6令X1 = X1 +6 0 X1 16,练习：将 min Z = -X1+2X2 -3X3,化为标准型,解： 令X3 =X4 - X5, 加松弛变量X6, 减剩余变量X7, 令Z= -Z,Max Z= X1 -2X2 +3X4 -3X5,1.3 线性规划的图解法,1. 图解法(Graphical Solution) 2.
8、线性规划问题求解的几种可能结果 3. 由图解法得到的启示,例1. 数学模型,目标函数 Max Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,x1,x2,1.3 线性规划的图解(续),9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,x1 + 2x2 8,目标函数 Max Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,4x1 16,4 x2 12,1. 图解法,1.3 线性规划的图解(续),目标函数 Max Z
9、= 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,9 8 7 6 5 4 3 2 1 0,x2,可行域,1.3 线性规划的图解(续),9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,可行域,1.3 线性规划的图解(续),目标函数 Max Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,9 8 7 6 5 4 3 2 1 0,x2,2x1 + 3x2 = 6,1.3 线性规划的图解(续),目标函数 Max Z = 2x1
10、 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,9 8 7 6 5 4 3 2 1 0,x2,x1+ 2x2=84x1 =16,1.3 线性规划的图解(续),目标函数 Max Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,1.3 线性规划的图解(续),由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。,图解法求解步骤:,1.3 线性规划的图解(续),(a) 唯一最优解,2. 线性规划问题求解的几种可能结果,目标函数 Max
11、 Z = 2x1 + 3x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,(b)无穷多最优解,1.3 线性规划的图解(续),目标函数 Max Z = x1 + 2x2约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,(c)无界解Max Z = x1 + x2-2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,1.3 线性规划的图解(续),(d)无可行解Max Z = 2x1 + 3x2x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0可行域为空集,1.3 线性规划的图解(续),可行
12、域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,1.3 线性规划的图解(续),3. 图解法的几点结论（由图解法得到的启示）,1.4 线性规划的基本概念,1. 可行解与最优解,标准型可行解:满足AX = b, X0的解X称为线性规划问题的可行解。 最优解：使Z = CX达到最大值的可行解称为最优解。,1.4 线性规划的基本概念(续),2. 基(基阵) 由A中一个子矩阵B是可逆矩阵，则方阵B称为LP问题的一个基。,1.4 线性规划的基本概念(续),
13、AX=b的求解,A=(B N) X=(XB XN )TXB XN,(B N) = b,BXB +NXN=b BXB =b-NXN XB = B-1 b - B-1N XN,1.4 线性规划的基本概念(续),=,=,目标函数,约束条件,行列式0 基矩阵,右边常数,基矩阵、基变量、非基变量、基可行解、可行基,目标函数,约束条件,基矩阵,右边常数,1.4 线性规划的基本概念(续),基变量,5. 换入基变量、换出基变量、基变换,进基变量,离基变量,目标函数,约束条件,右边常数,1.4 线性规划的基本概念(续),目标函数,约束条件,新的基矩阵,右边常数,1.4 线性规划的基本概念(续),1.4 线性规划
14、的基本概念(续),例：,基变量x1、x2、x3，非基变量x4、x5、x6,基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基可行解，表示可行域的一个极点。 目标函数值为：z=20,1.4 线性规划的基本概念(续),基变量x1、x2、x4，非基变量x3、x5、x6,基解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，12/5，0，0） 是基可行解，表示可行域的一个极点。 目标函数值为：z=18,1.4 线性规划的基本概念(续),基变量x1、x2、x5，非基变量x3、x4、x6,基解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0），是基解，但不是可行解，不是一个极点。,1.4 线性规划的基本概念(续),基变量x1、x2、x6，非基变量x3、x4、x5,基解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基可行解，表示可行域的一个极点。目标函数值为：z=18,
