线性规划(管理运筹学课件)

1、2021-11-10第一节： 线性规划数学模型第二节：线性规划图解法第三节： 线性规划单纯形法2021-11-10第一节： 线性规划数学模型数学模型： 用字母、数字和运算符来精确地反映变量之间相互关系的式子或式子组。 数学模型三要素：决策变量；约束条件；目标函数。线性规划数学模型： （1）决策变量：连续变量 （2）约束条件：线性等式或不等式 （3）目标函数：线性函数线性规划由此得名2021-11-10第一节： 线性规划数学模型案例1：制定最佳生产计划问题 资源资源单位产品资源消耗量单位产品资源消耗量资源拥有量资源拥有量甲甲 乙乙A AB BC C1 1 2 24 4 0 00 0 4 48 8

2、16161212单位产品利润单位产品利润2 2 3 3案例信息表2021-11-10第一节： 线性规划数学模型案例1：制定最佳生产计划问题 建立数学模型（线性规划数学模型） 1. 决策变量：x1和x2 2. 目标函数：max Z = 2 x1+3 x2 3. 约束条件： x1+ 2x2 8 s.t. 4 x1 16 4x2 12 x1，x2 02021-11-10第一节： 线性规划数学模型案例2：人力资源规划问题 2：00 6：00 2名；名； 6：0010：00 12名；名；10：0014：00 20名；名；14：0018：00 6名；名；18：0022：00 26名；名；22：00 2：0

3、0 4名。名。x3x4x5x12:00 x16:00 x210:00 x314:00 x418:00 x522:00 x6x6+x1x2+2021-11-10第一节： 线性规划数学模型案例2：人力资源规划问题 x12:00 x16:00 x210:00 x314:00 x418:00 x522:00 x6x6+x1x2+MinZ=x1+x2+x3+x4+x5+x6x6+x1 2x1+x2 12x2+x3 20 x3+x4 6x4+x5 26x5+x6 4x1、x2、x3、x4、x5、x6 02021-11-10第一节： 线性规划数学模型案例3：合理剪裁问题原材料长：原材料长：7.4米米裁剪成：

4、裁剪成：1.5米、米、2.1米、米、2.9米的材料各米的材料各100根根问应如何下料，才能使原材料最省？问应如何下料，才能使原材料最省？7.5m2.9m2.1m1.5m2021-11-10第一节： 线性规划数学模型案例3：合理剪裁问题裁剪成裁剪成: 1.5M 2.1M 2.9M 余料余料 方案方案1 1 1 1 0.9 方案方案2 4 0 0 1.4 方案方案3 3 1 0 0.8 方案方案4 3 0 1 0.0 方案方案5 2 2 0 0.2 方案方案6 1 0 2 0.1 方案方案7 0 3 0 1.1 方案方案8 0 2 1 0.32021-11-10第一节： 线性规划数学模型案例3：合

5、理剪裁问题MIN Z = X1 + X2 +X3+ X4 + X5 + X6 + X7 + X8 X1 + 4X2 + 3X3 + 3X4 +2 X5 + X6 100 s.t. X1 + X3 + 2X5 + 3X7 + 2X8 100 X1 + X4 +2X6 + X8 100 X1,X2,X3,X4, X5,X6,X7,X8 02021-11-10第二节：线性规划图解法线性规划数学模型几个有关解的概念： 1. 决策变量：x1和x2 2. 目标函数：max Z = 2 x1+3 x2 3. 约束条件： x1+ 2x2 8 s.t. 4 x1 16 4x2 12 x1，x2 0 解 ：决策变

6、量的任意一组取值都称为解，如X=(3，6) 、 X=(1，1) ；非可行解：X=(3，6) 、 X=(1，5) 、 X=(9，9)；可 行 解：X=(0，0) 、 X=(1，1) 、 X=(2，4)；可 行 域：可行解一般不仅一个，为无穷多个，可行解的集合；最 优 解：使目标函数达到极值的可行解，如 X=(2，4)；最 优 值：与最优解相对应的目标函数值，如 Z=2 2 + 3 4 = 162021-11-10第二节：线性规划图解法图解法：顾名思义要通过绘图来实现对线性规划问题的求解。理论上N维空间，大脑思维三维空间，但实践上仅限二维空间。2021-11-10第二节：线性规划图解法图解法的基本

7、步骤第一步：绘制平面直角坐标系x1X2 1 2 3 4 5 6 7 801234 1. 决策变量：x1和x2 2. 目标函数：max Z = 2 x1+3 x2 3. 约束条件： x1+ 2x2 8 s.t. 4 x1 16 4x2 12 x1，x2 02021-11-10第二节：线性规划图解法图解法的基本步骤第二步：将约束条件按顺序在平面直角坐标系中反映出来x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 82021-11-10第二节：线性规划图解法图解法的基本步骤第二步：将约束条件按顺序在平面直角坐标系中反映出来x1X2 1 2 3 4 5 6 7 801234x1+ 2x

8、2 84 x1 16 2021-11-10第二节：线性规划图解法图解法的基本步骤第二步：将约束条件按顺序在平面直角坐标系中反映出来x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 84 x1 16 4x2 122021-11-10第二节：线性规划图解法图解法的基本步骤第三步：确定可行域并用阴影表示出来（可行域是凸集）x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 84 x1 16 4x2 122021-11-10第二节：线性规划图解法图解法的基本步骤第四步：将目标函数在平面直角坐标系中反映出来x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 8

9、4 x1 16 4x2 12max Z = 2 x1+3 x2x2= -2/3 x1+ Z/3 2021-11-10第二节：线性规划图解法图解法的基本步骤第五步：平移目标函数线，寻找最优解。x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 84 x1 16 4x2 12max Z = 2 x1+3 x2x2= -2/3 x1+ Z/3 唯一最优解：X =（4，2）最优值 ：Z = 14 2021-11-10图解法总结第二节：线性规划图解法1.显著优点：简单、直观、具体；2.致命缺点：只能求解具有两个变量的线性规划问题；3.学习目的：并非是要掌握一种线性规划问题的求解方法，而是要

10、通过图解法揭示线性规划问题的内在规律，为学习线性规划问题的一般算法（单纯形法）奠定基础。2021-11-10图解法所给出的一般性结论第二节：线性规划图解法1.最优解一定在可行域的边缘上，绝不会在可行域的内部；此例最优解在一个顶点上得到。2021-11-10 x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 84 x1 16 4x2 12x2= -2/3 x1+ Z/3 唯一最优解：X =（4，2）最优值 ：Z = 14 第二节：线性规划图解法图解法所给出的一般性结论2.最优解一定能在可行域的顶点上得到；可能有两种情况：唯一最优解和无穷多最优解。 1. 决策变量：x1和x2 2.

11、 目标函数：max Z = 2 x1+4 x2 3. 约束条件： x1+ 2x2 8 s.t. 4 x1 16 4x2 12 x1，x2 02021-11-10 x1X2 1 2 3 4 5 6 7 801234x1+ 2x2 84 x1 16 4x2 12无穷最优解：X =（4，2）最优值 ：Z = 16 第二节：线性规划图解法图解法所给出的一般性结论3.无最优解也可能有两种情况：无可行解和无界解。2021-11-10无可行解示意图：8765342121o1x2x第二节：线性规划图解法图解法所给出的一般性结论3.无最优解也可能有两种情况：无可行解和无界解。2021-11-10无界解示意图：1

12、x2x8765342121o2021-11-10第二节：线性规划图解法图解法所给出的一般性结论：1.如果线性规划问题有最优解，其最优解 一定可以在其可行域的顶点上得到2.如果线性规划问题在其可行域的两个顶 点上得到最优解，那么两顶点连线上的 所有点均为最优解点，即线性规划问题 有无穷多最优解。3. 线性规划问题的解可能有四种情况： （1）唯一最优解； （2）无穷多最优解； （3）无界解； （4）无可行解。2021-11-10第二节：线性规划图解法练习题： 1.决策变量：x1和x2 2.目标函数：min Z = 40 x1+36 x2 3.约束条件： 5x1+3x2 45 s.t. x1 8 x

13、2 10 x1，x2 02021-11-10 x1x2 5 10 150 x2 10510155x1+3x2 45x1 82021-11-10 x1x2 5 10 150 x2 10510155x1+3x2 45x1 8min Z = 40 x1+36 x2最优解：X =（8，5/3）最优值 ：Z = 3802021-11-10第三节： 线性规划单纯形法线性规划数学模型的一般形式 max(min) Z = c1 x1+ c2 x2 + cn xn a11 x1+ a12 x2 + a1n xn (=,) b1 a21 x1+ a22 x2 + a2n xn (=,) b2 s.t. am1 x

14、1+ am2 x2 + amn xn (=,) bm x1 ， x2 ， ， xn 0 2021-11-10第三节： 线性规划单纯形法 max(min) Z = c1 x1+ c2 x2 + cn xn a11 x1+ a12 x2 + a1n xn = b1 a21 x1+ a22 x2 + a2n xn = b2 s.t. am1 x1+ am2 x2 + amn xn = bm线性规划数学模型的标准形式bi 0 i =1,2,m xj 0 j =1,2,n 2021-11-10第三节： 线性规划单纯形法标准形式的转化1.无约束变量x的处理： x=y-z, 其中y,z02.负数变量x的处理

15、： x=-y,其中y03.目标函数极小化的处理： Min CX=- Max(-CX)4.非等式约束条件的处理： 加松弛变量或减剩余变量5.右端项为负：两端同乘“-1”2021-11-10第三节： 线性规划单纯形法标准形式的转化1.无约束变量x的处理： x=y-z, 其中y,z02.负数变量x的处理： x=-y,其中y03.目标函数极小化的处理： Min CX=- Max(-CX)4.非等式约束条件的处理： 加松弛变量或减剩余变量5.右端项为负：两端同乘“-1”2021-11-10第三节： 线性规划单纯形法标准形式的转化Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 1

16、1 -4x1 + x2 + 2x3 3 2x1 - x3 = -1 x1 ， x2 ， x3 0 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 = 3 -2x1 + x3 = 1 x15 02021-11-10第三节： 线性规划单纯形法基本步骤w 1. 找出一个初始的基可行解；找出一个初始的基可行解；w 2. 判断其最优性；判断其最优性；w 3. 转移至另一个较优的基可行解；转移至另一个较优的基可行解；w 4. 重复重复2、3两步直至最优。两步直至最优。2021-11-1034用单纯形法求解案例用单纯形法

17、求解案例1 w 1. 决策变量：决策变量：x1和和x2w 2. 目标函数：目标函数：max Z = 2 x1+3 x2w 3. 约束条件：约束条件： x1+2 x2 8w s.t. 4 x1 16 w 4 x2 12w x1，x2 02021-11-1035用单纯形法求解案例用单纯形法求解案例1 w 转换为标准形式：转换为标准形式：w max Z = 2 x1+3 x2w x1+2 x2 + x3 = 8w s.t. 4 x1 + x4 = 16 w 4 x2 + x5 = 12w x1,x2,x3,x4 ,x5 02021-11-1036用单纯形法求解案例用单纯形法求解案例1 w max Z

18、 = 2 x1+3 x2 +0 x3 +0 x4 +0 x5w x1+2 x2 + x3 = 8w s.t. 4 x1 + x4 = 16 w 4 x2 + x5 = 12w x1,x2,x3,x4 ,x5 02021-11-1037单纯形表单纯形表2021-11-1038用单纯形法求解案例用单纯形法求解案例1 wmax Z = 2 x1+3 x2 +0 x3 +0 x4 +0 x5w x1+2 x2 + x3 = 8w s.t. 4 x1 + x4 = 16 w 4 x2 + x5 = 12w x1,x2,x3,x4 ,x5 0cj 2 3 0 0 0bCBXBx1 x2 x3 x4 x50

19、00 x3x4x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 181612 j 2 3 0 0 0w=02021-11-10用单纯形法求解案例用单纯形法求解案例1 w x2入基入基,即即x2 增加增加; x2 增加会引起增加会引起x3和和x5的减少的减少,而而x4不受影响。不受影响。 x2 增加增加首先使首先使x5减少为减少为“0”，即，即x5出基。新的基为出基。新的基为XB=（ x3 ， x4 ， x2）。）。w max Z = 2 x1+3 x2w x1+2 x2 + x3 = 8w s.t. 4 x1 + x4 = 16 w 4 x2 + x5 = 12w x1,x2,x3

20、,x4 ,x5 02021-11-1040用单纯形法求解案例用单纯形法求解案例1 w 将新的基变量将新的基变量x3 ， x4 ， x2 求解出来并将目标函数转化为非基变量求解出来并将目标函数转化为非基变量x1 ， x5,的函数。的函数。 w max Z = 2 x1+0 x2 +0 x3 +0 x4 x5 + 9w x1 + x3 - x5 = 2w s.t. 4 x1 + x4 =16 w x2 + x5 = 3w x1,x2,x3,x4 ,x5 02021-11-1041用单纯形表求解案例用单纯形表求解案例1 bcj 2 3 0 0 0CBXB x1 x2 x3 x4 x5003x3x4x

21、2 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/42163 j 2 0 0 0 -3/4w=92021-11-10用单纯形法求解案例用单纯形法求解案例1 w x1入基入基,即即x1 增加增加; x1 增加会引起增加会引起x3和和x4的减少的减少,而而x2不受影响。不受影响。 x1 增加增加首先使首先使x3减少为减少为“0”，即，即x3出基。新的基为出基。新的基为XB=（ x1 ， x4 ， x2）。）。w max Z = 2 x1+0 x2 +0 x3 +0 x4 x5 + 9w x1 + x3 - x5 = 2w s.t. 4 x1 + x4 =16 w x2 + x5

22、 = 3w x1,x2,x3,x4 ,x5 02021-11-10用单纯形法求解案例用单纯形法求解案例1 w 将新的基变量将新的基变量x1 ， x4 ， x2 求解出来并将目标函数转化为非基变量求解出来并将目标函数转化为非基变量x3 ， x5,的函数。的函数。 w max Z = 0 x1+0 x2 -2 x3 +0 x4 +1/4 x5 + 13w x1 + x3 - x5 = 2w s.t. -4 x3 + x4 + 2 x5 = 8 w x2 + x5 = 3w x1,x2,x3,x4 ,x5 02021-11-1044用单纯形表求解例用单纯形表求解例2-1 bcj 2 3 0 0 0C

23、BXBx1 x2 x3 x4 x5203x1x4x2 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4283 j 0 0 -2 0 1/4w=132021-11-10用单纯形法求解案例用单纯形法求解案例1 w x5入基入基,即即x5 增加增加; x5 增加会引起增加会引起x4和和x2的减少的减少,而而x1不但不减少反而随不但不减少反而随之增加。之增加。 x5 增加首先使增加首先使x4减少为减少为“0”，即，即x4出基。新的基为出基。新的基为XB=（ x1 ， x5 ， x2）。）。w max Z = 0 x1+0 x2 -2 x3 +0 x4 +1/4 x5 + 13w

24、x1 + x3 - x5 = 2w s.t. -4 x3 + x4 + 2 x5 = 8 w x2 + x5 = 3w x1,x2,x3,x4 ,x5 02021-11-1046用单纯形法求解案例用单纯形法求解案例1 w 将新的基变量将新的基变量x1 ， x5 ， x2 求解出来并将目标函数转化为非基变量求解出来并将目标函数转化为非基变量x3 ， x4,的函数。的函数。 w max Z = 0 x1+0 x2 -3/2 x3 -1/8 x4 +0 x5 + 14w x1 +1/4 x4 = 4w s.t. -2 x3 +1/2 x4 + x5 = 4 w x2 +1/2 x3 1/8 x4 =

25、 2w x1,x2,x3,x4 ,x5 02021-11-10用单纯形表求解案例用单纯形表求解案例1 bcj 2 3 0 0 0CBXBx1 x2 x3 x4 x5203x1x5x2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0442 j 0 0 -3/2 -1/8 0w=14唯一最优解：X =（4，2，0，0，4）最优值 ：Z = 14 2021-11-10第三节： 线性规划单纯形法最优性检验与解的判别最优性检验与解的判别1.唯一最优解：唯一最优解：对于极大值问题所有非基变量的检验数均小于“0”；对于极小值问题所有非基变量的检验数均大于“0”。2.无穷多最优

26、解无穷多最优解：对于极大值问题所有非基变量的检验数均小于等于“0”且至少存在一个非基变量的检验数均等于“0” ；对于极小值问题所有非基变量的检验数均大于等于“0”且至少存在一个非基变量的检验数均等于“0” 。3.无界解：无界解：若在确定入基变量后，无法确定出基变量，即入基变量的增加不会引起任何一个原基变量的减少，这表明原基变量并不限制入基变量的增加幅度，入基变量可以任意增加，所以目标函数无界。2021-11-1049单纯形法习题一单纯形法习题一 1. 决策变量：决策变量：x1和和x2 2. 目标函数：目标函数：max Z = 2 x1+4 x2 3. 约束条件：约束条件： x1+2 x2 8

27、s.t. 4 x1 16 4 x2 12 x1，x2 02021-11-1050单纯形法习题二单纯形法习题二 Max z =2x1 + 4x2 + x3 x1 + 3x2 + x3 8 2x1 + x2 6 x2 + 2x3 6 x1 + x2 + x3 9 x14 02021-11-1051单纯形法习题三单纯形法习题三 Max z =2x1 + 4x2 + x3 x1 + 2x2 - x3 18 2x1 + 4x2 16 x1 + x2 - x3 12 x14 02021-11-10第三节： 线性规划单纯形法单纯形法的进一步讨论：人工变量法单纯形法的进一步讨论：人工变量法 Min z = -

28、3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 = 3 -2x1 + x3 = 1 x15 02021-11-10第三节： 线性规划单纯形法单纯形法的进一步讨论：人工变量法单纯形法的进一步讨论：人工变量法 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x15 02021-11-10第三节： 线性规划单纯形法单纯形法的进一步讨论：人工变量的大单纯形法的进一步讨论：人工变量的大M法法

29、Min z = -3x1 + x2 + x3 + Mx6 + Mx7 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x15 0例1：2021-11-10 表 1 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b0MMx4x6x7 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 111 3 1 -3+6M 1-M 1-3M 0 M 0 02021-11-10 表 2 cj-3 1 1 0 0 M MCBXB x1 x2 x3 x

30、4 x5 x6 x7b0M1x4x6x3 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2-2 0 1 0 0 0 110 1 1 -1 1-M 0 0 M 0 3M-12021-11-10 表 3 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b011x4x2x3 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2-2 0 1 0 0 0 112 1 1 -1 0 0 0 1 M-1 M+12021-11-10 表 4 cj-3 1 1 0 0 M MCBXBx1 x2 x3 x4 x5 x6 x7b-311x1x2x31 0 0

31、1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3 4 1 9 0 0 0 1/3 1/3 M-1/3 M-2/3唯一最优解：X =（4，1，9，0，0）最优值 ：Z = -2 2021-11-10大大M法例法例2 Max z = 2x1 + 4x2 + x3 x1 + x2 + x3 6 x1 + x2 - 2x3 4 x1 - 2x2 + x3 8 x1 ， x2 ， x3 02021-11-1060 Max z = 2x1 + 4x2 + x3 - Mx7 x1 + x2 + x3 + x4 = 6 x1 + x2 - 2x3

32、+ x 5 = 4 x1 - 2x2 + x3 - x6 + x7 = 8 x17 02021-11-10 表 1 cj 2 4 1 0 0 0 -MCBXBx1 x2 x3 x4 x5 x6 x7b 0 0-Mx4x5x7 1 1 1 1 0 0 0 1 1 -2 0 1 0 0 1 -2 1 0 0 -1 1 6 4 8 2+M 4-2M 1+M 0 0 -M 02021-11-10 表 2 cj 2 4 1 0 0 0 -MCBXB x1 x2 x3 x4 x5 x6 x7b 0 2-Mx4x1x7 0 0 3 1 -1 0 0 1 1 -2 0 1 0 0 0 -3 3 0 -1 -1

33、 1 2 4 4 0 2-3M 5+3M 0 -2-M -M 02021-11-10 表 3 cj 2 4 1 0 0 0 -MCBXB x1 x2 x3 x4 x5 x6 x7b 1 2-Mx3x1x7 0 0 1 1/3 -1/3 0 0 1 1 0 2/3 1/3 0 0 0 -3 0 -1 0 -1 1 2/3 16/3 2 0 2-3M 0 -3/5-M -1/3 -M 0无可行解：人工变量仍然保留在基中（大于零），所以原问题的第三个约束条件永远都不成立，即原问题无可行解。2021-11-10第三节： 线性规划单纯形法单纯形法的进一步讨论：人工变量的两阶段法单纯形法的进一步讨论：人工

34、变量的两阶段法 Min z = -3x1 + x2 + x3 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x15 0两阶段法例1：2021-11-10第三节： 线性规划单纯形法单纯形法的进一步讨论：人工变量的两阶段法单纯形法的进一步讨论：人工变量的两阶段法 Min z = x6 + x7 x1 - 2x2 + x3 + x4 = 11 -4x1 + x2 + 2x3 - x5 + x6 = 3 -2x1 + x3 + x7 = 1 x15 0例1：第一阶段第一阶段2021-11-102021-11-10 表 2（第一阶段） cj