线性规划概论与图解法

1、第一章 线性规划与单纯形方法1第一章线性规划与单纯形方法1.2 线性规划基本概念1.3 线性规划问题的数学模型1.4 线性规划问题解的概念1.1 线性规划（概论）2线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1.1 线性规划（概论）3线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）4线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算

2、法（Simpler）1963年Dantzig写成“Linear Programming and Extension”5线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）1963年Dantzig写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”6线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）1963年Da

3、ntzig写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法” 7线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）1963年Dantzig写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法” 线性规划是研究线性不等式组的理论，或者说是研究（高维空间中

4、）凸多面体的理论，是线性代数的应用和发展。8生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1.2 线性规划基本概念9例1.1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？10解：将一个实际问题转化为线性规

5、划模型有以下几个步骤：11解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量12解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x213解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （

6、油漆工工时限制）14解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）4变量取值限制： 一般情况，决策变量只取正值（非负值） x1 0, x2 0 15解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件： 4x1+

7、3x2120（木工工时限制） 2x1+x2 50 （油漆工工时限制）4变量取值限制： 一般情况，决策变量只取正值（非负值） x1 0, x2 0 16数学模型 max S=50 x1+30 x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0线性规划数学模型三要素： 决策变量、约束条件、目标函数17例1 .2 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？1.3 线性规划问题的数学模型1

8、8各种食物的营养成分表19解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： min S=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 020其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题21线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a

9、1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1,x2.xn 022线性规划问题隐含的假定：比例性假定可加性假定连续性假定确定性假定23线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。24线性规划问题隐含的假定：连续性假定：线性规划问题中的决策变量应取连续值。确定

10、性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。25线性规划问题的标准形式(1)：Max S=c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 . am1x1+am2x2+.+amnxn=bm x1,x2.xn 0其中：bi 0(i=1,2,.m)26线性规划问题的标准形式(2)： n Max S = cjxj j=1 n s.t. aijxj = bi (i=1,2,.m) j=1 xj 0 (j=1,2,.n)其中： bi 0 (i=1,2,.m)27线性规划标准型的矩阵形式(3

11、)（矩阵表达型）： Max S = CX s.t. AX = b X 0其中：28如何将一般问题化为标准型：若目标函数是求最小值 Min S = CX 则令 S= - S, 变为 Max S= - CX2. 若约束条件是不等式若约束条件是“”不等式, 将原条件变为： n aijxj + xs = bi j=1 xs 0是新引入的非负松驰变量29如何将一般问题化为标准型：3. 若约束条件是“”不等式，则变为 n aijxj - xt = bi j=1 Xt 0是引入的非负松驰变量4. 若约束条件右面的某一常数项 bi0这时只要在bi相对应的约束方程两边乘上-1。30如何将一般问题化为标准型：5.

12、 若变量 xj无非负限制，引进两个非负变量xj xj” 0 令xj = xj- xj” 通过以上步骤，任何形式的线性规划总可以化成标准型。31例1.3 将下列问题化成标准型:Min S = -x1+ 2x2- 3x3s.t. x1+ x2 + x3 7 x1 - x2 + x3 2 -3x1 + x2 + 2x3 = 5 x1 , x2 0 x3 无非负限制32标准型：Max Z = x1- 2x2+ 3x3 - 3x4s.t. x1+ x2+ x3 - x4 + x5 = 7 x1- x2+ x3 - x4 - x6 = 2 -3x1+ x2+ 2x3 - 2x4 = 5 x1, x2,x3

13、,x4, x5,x6 0注：标准型还不一定是便于求解的形式。33课堂练习：请阅读P1 P3 中的例1.1、例1.2、例1.4。之后完成P31 1.1(1)(2)(4)；1.2。请独立完成：P34 1.8341.4 线性规划问题解的概念线性规划问题的解：（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。35线性规划问题图解法：例 1.1的数学模型 max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 036x2504030201010203040 x14x1+3x2 120由 4x1+3x2 12

14、0 x1 0 x2 0围成的区域max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 037x2504030201010203040 x12x1+x2 50由 2x1+x2 50 x1 0 x2 0围成的区域max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 038x2504030201010203040 x12x1+x2 504x1+3x2 120可行域同时满足：2x1+x2 504x1+3x2 120 x1 0 x2 0的区域可行域max S=50 x1 + 30 x2

15、 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 039x2504030201010203040 x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 040 x2504030201010203040 x1可行域目标函数是以S作为参数的一组平行线x2 = S/30-（5/3）x1max S=50 x1

16、 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 041x2504030201010203040 x1可行域当S值不断增加时，该直线x2 = S/30-（5/3）x1沿着其法线方向向右上方移动。max S=50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 042x2504030201010203040 x1可行域当该直线移到Q2点时，S（目标函数）值达到最大：Max S=50*15+30*20=1350此时最优解=（15，20）Q2（15，20）max S=50 x1 + 30 x2 s.t. 4x1

17、 + 3x2 120 2x1 + x2 50 x1 x2 043二个重要结论：1。满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。2。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。44解的讨论：最优解是唯一解；45解的讨论：1。最优解是唯一解2。无穷多组最优解：例1.1的目标函数由 max S=50 x1+30 x2变成： max S=40 x1+30 x2 s.t. 4x1+ 3x2 120 2x1+ x2 50 x1,x2 046x2504030201010203040 x1可行域目标函数是同约束条件：4x1+3x2 120平行的直

18、线x2 = S/30-（4/3）x1max S=40 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 x2 047x2504030201010203040 x1可行域当S的值增加时，目标函数同约束条件：4x1+3x2 120重合，Q1与Q2之间都是最优解。Q1（25，0）Q2（15，20）48解的讨论：最优解是唯一解；无穷多组最优解：无界解：例：max S = x1 + x2 s.t. -2x1+ x2 40 x1 - x2 20 x1 x2 049x2504030201010203040 x1该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解

19、或无最优解。-2x1+x2 40 x1-x2 2050解的讨论：无可行解：例：max S=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为空集，即无可行解，也不存在最优解。51解的情况：1。有可行解2。有唯一最优解3。有无穷最优解4。无最优解5。无可行解52课堂练习： P34 1.7 (偶数号)53线性规划问题解的概念线性规划标准型的矩阵形式：Max S = C X （1- 9） s.t. A X = b （1-10） X 0 （1-11）其中54解、可行解、最优解1。满足约束条件（1-10）的X，称为 线性规划问题的解。2。满足

20、约束条件（1-10）与（1-11） 的X，称为线性规划的问题可行解。 3。使目标函数（1-9）取得最优的可行解X 称为线性规划的问题最优解。Max S = CX （1- 9） s.t. AX=b （1-10） X 0 （1-11）55基、基向量、基变量1。设 r(A) = m,并且B是A的m 阶非奇异 的子矩阵（det(B) 0),则称矩阵 B为线性规划问题的一个基。2。设矩阵 B =（P1，P2 . Pm)是一个基 ，其列向量 Pj 称为对应基B的基向量。 3。与基向量 Pj 相对应的变量xj就称为 基变量，其余的就称为非基变量。56基础解.基础可行解.可行基1。对于某一特定的基B，非基变量取 0 值的解，称为基础解。2。满足非负约束条件的基础解，称 为基础可行解。3。与基础可行解对应的基，称为可 行基。57为了理解基础解.基础可行解.最优解的概念，用下列例子说明：例1.4：max S = 2x1 + 3x2 （1-12 ） s.t. -2x1 + 3x2 6 （1-13-1） 3x1 - 2x2 6 （1-13-2） x1 + x2 4 （1-13-3） x1, x2 0 （1-14 ） 58将该问题化为标准形