《线性规划》 (2)ppt课件

1、2.1 问题的提出问题的提出2.2 线性规划的数学模型线性规划的数学模型2.3 图解法图解法2.4 单纯形法单纯形法【例2-1】某商场决议：营业员每周延续任务5天后延续休憩2天，轮番休憩。根据统计，商场每天需求的营业员如表1-2所示。表1-2 营业员需求量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。 星期星期需求人数需求人数星期星期需求人数需求人数一一300五五480二二300六六600三三350日日550四四400【例1-1】、 【例1-2】【解】 设xj(j=1，2，7)为休憩2天后星期一到星期日开场上班的营业员，那么这个问题的线性规划模型为 7 ,2, 1,055

2、0600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj星星期期需求需求人数人数星星期期需求需求人数人数一一300五五480二二300六六600三三350日日550四四4001 x10 c1404 =3001042 x267 c2301 =30013 x3146 c3350 =35004 x4170 c4400 =40005 x597 c5480 =48006 x6120 c6600 =60007 x717 c7550 =5500最

3、优解：Z617人普通地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2,n，目的函数的变量系数用cj表示, cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。那么线性规划数学模型的普通表达式可写成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或为了书写方便，上式也可写成： 11max(min)(, )1,2,0,1,2,njjjnij

4、jijjZc xa xbimxjn 或在实践中普通xj0,但有时xj0或xj无符号限制。线性规划的数学模型由决策变量 Decision variables 目的函数Objective function及约束条件Constraints构成。称为三个要素。n其特征是：n1处理问题的目的函数是多个决策变量的n 线性函数，通常是求最大值或 最小值；n2处理问题的约束条件是一组多个决策变量n 的线性不等式或等式。怎样区分一个模型是线性规划模型？图解法的步骤：1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；2.绘制目的函数图形。先过原点作一条矢量指向点c1

5、,c2)，矢量的方向就是目的函数添加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目的函数图形；3.求最优解。根据目的函数求最大或最小挪动目的函数直线，直线与可行域顶点相交的对应坐标就是最优解。普通地，将目的函数直线放在可行域中，求最大值时直线沿着矢量方向挪动，求最小值时沿着矢量的反方向挪动。对于只需两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。x1x2O1020304010203040(300,400)(15,10)最优解X=(15,10)最优值Z=850040221xx305 . 121xx0, 0305 . 1402212121x

6、xxxxx例2-212max300400Zxx246x1x2246最优解X=(3,1)最优值Z=5(3,1)121212123643600 xxxxxxxx、min Z=x1+2x2例2-3(1,2)246x1x2246X23,1X11,3(5,5)006346321212121xxxxxxxx、min Z=5x1+5x2例2-4有无穷多个最优解即具有多重解,通解为 01 ,)1 ()2() 1 (XXX 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 246x1x2246(1,2)006346321212121xxxxxxxx、无界解(无最优解)max Z=x1

7、+2x2例2-5x1x2O102030401020304050500,050305 .140221212121xxxxxxxx无可行解即无最优解max Z=10 x1+4x2例2-6由以上例题可知，线性规划的解有4种方式：1.有独一最优解(例2-2例2-3)2.有多重解(例2-4)3.有无界解(例2-5)4.无可行解(例2-6)1、2情形为有最优解3、4情形为无最优解 灵敏度分析：建立数学模型和求得最优解后，研讨线性规灵敏度分析：建立数学模型和求得最优解后，研讨线性规划的一个或多个参数系数划的一个或多个参数系数ci , aij , bj 变化时，对最优解产变化时，对最优解产生的影响。生的影响。

8、1、当一个系数发生变化时，其他系数坚持不变；、当一个系数发生变化时，其他系数坚持不变；2、两个及两个以上系数同时发生变化。、两个及两个以上系数同时发生变化。例例2-7. 某工厂在方案期内要安排某工厂在方案期内要安排、两种产品的消费，知消费单位产两种产品的消费，知消费单位产品所需的设备台时及品所需的设备台时及A、B两种原资料的耗费、资源的限制，如下表：两种原资料的耗费、资源的限制，如下表：问题：工厂应分别消费多少单位问题：工厂应分别消费多少单位、产品才干使工厂获利最多？产品才干使工厂获利最多？线性规划模型：线性规划模型： 目的函数：目的函数：Max z = 50 x1 + 100 x2 约束条件

9、：约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0图解法：A，B，C，D，E是可行域的顶点，最优解为B(50, 250)x1x2z=27500=50 x1+100 x2CBADE1、当一个系数发生变化时，其他系数坚持不变、当一个系数发生变化时，其他系数坚持不变1)目的函数中的系数目的函数中的系数 ci 的灵敏度分析的灵敏度分析 思索例思索例2-7的情况，的情况， ci 的变化只影响目的函数等值线的斜率的变化只影响目的函数等值线的斜率，目的函数，目的函数 z = 50 x1 + 100 x2 在在 z = x2 (斜率为斜率为0 ) 到到

10、z = x1 + x2 (斜率为斜率为 -1 )之间时，原最优解之间时，原最优解 x1 = 50，x2 = 250 仍是最优解。仍是最优解。 z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 ，斜率为 - (c1 / c2 ) ，当 -1 - (c1 / c2 ) 0 * 时，原最优解仍是最优解。假设产品的利润100元不变，即 c2 = 100，代到式*并整理得 0 c1 100 假设产品的利润 50 元不变，即 c1 = 50 ，代到式*并整理得 50 c2 + 2) 约束条件中右边系数 bj 的灵敏度分析当约束条件中右边系数 bj

11、变化时，线性规划的可行域发生变化，能够引起最优解的变化。思索例2-7的情况： 假设设备台时添加10个台时，即 b1变化为310，这时可行域扩展，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1=60，x2 = 250 。添加的利润：(5060+ 100250) - (50 50+100 250) = 500元， 单位台时添加的利润为：500 / 10 = 50 元。阐明在一定范围内每添加减少1个台时的设备才干就可添加减少50元利润，称为该约束条件的对偶价钱。 假设原料 A 添加10 千克时，即 b2变化为410，这时可行域扩展，但最优解仍为 x2 = 250 和 x1

12、+ x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价钱为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此添加10千克值添加了库存，而不会添加利润。 在一定范围内，当约束条件右边常数添加1个单位时： 1假设约束条件的对偶价钱大于0，那么其最优目的函数值得到改善变好； 2假设约束条件的对偶价钱小于0，那么其最优目的函数值遭到影响变坏； 3假设约束条件的对偶价钱等于0，那么最优目的函数值不变。2、当有多个系数同时变化时、当有多个系数同时变化时例例2-7的计算报告的计算报告百分之一百法那么： 对于一切变化的目的函数决策系数约束条

13、件右边常数值，当其一切允许添加的百分比与允许减少的百分比之和不超越100%时，最优解不变对偶价钱不变，最优解仍是原来几个线性方程的解。允许添加量 = 上限 - 如今值 c1 的允许添加量为 100 - 50 = 50 b1 的允许添加量为 325 - 300 = 25允许减少量 = 如今值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50允许添加的百分比 = 添加量 / 允许添加量允许减少的百分比 = 减少量 / 允许减少量 例：例： c1 变为变为 74 , c2 变为变为 78, 那么那么 (74 - 50) / 50 + (1

14、00 - 78 ) / 50 = 92%，故最优解不变；，故最优解不变；b1 变为变为 315 , b3 变为变为 240, 那么那么 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价钱不变最，故对偶价钱不变最优解仍是原来几个线性方程的解。优解仍是原来几个线性方程的解。在运用百分之一百法那么进展灵敏度分析时，要留意：在运用百分之一百法那么进展灵敏度分析时，要留意：1当允许添加量允许减少量为无穷大时，那么对恣意添加量减少量，其允许添当允许添加量允许减少量为无穷大时，那么对恣意添加量减少量，其允许添加减少百分比均看作加减少百分比均看作0；2百分之一百法那

15、么是充分条件，但非必要条件；也就是说超越百分之一百法那么是充分条件，但非必要条件；也就是说超越100%并不一定变化；并不一定变化；3百分之一百法那么不能用于目的函数决策变量系数和约束条件右边常数值同时变化的百分之一百法那么不能用于目的函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，需求重新进展求解。情况。这种情况下，需求重新进展求解。 影子价钱 当约束条件中的常数项添加一个单位时，最优目的函数值添加的数量。 对偶价钱 当约束条件中的常数项添加一个单位时，最优目的函数值改良的数量。 目的为max时，影子价钱=对偶价钱 目的为min时，影子价钱=-对偶价钱作业 阅读教材第四章 教材

16、第二章习题2、6 教材第三章习题1、2线性规划问题的规范型为:1目的函数求最大值2约束条件都为等式方程3决策变量xj非负4约束条件右边常数bi非负 在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为一致的规范方式。1、线性规划的规范化、线性规划的规范化普通方式普通方式目的函数：目的函数： Max Min z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： s.t. a11 x1 + a12 x2 + + a1n xn =, b1 a21 x1 + a22 x2 + + a2n xn =, b2 am1 x1 + am2 x2 + + amn xn =

17、, bm x1 ，x2 ， ，xn 0 规范方式规范方式目的函数：目的函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0 ，bi 01极小化目的函数的问题： 设目的函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 那么该极小化问题与下面的极大化问题有一样的最优解，即 Max z =

18、- c1x1 - c2x2 - - cnxn 必需留意，虽然以上两个问题的最优解一样，但它们最优解的目的函数值却相差一个符号，即 Min f - Max z2约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn )显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+ s = bi 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2

19、x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于时称为“松弛变量；当不等式为“大于等于时称为“剩余变量。假设原问题中有假设干个非等式约束，那么将其转化为规范方式时，必需对各个约束引进不同的松弛变量。4决策变量符号的问题：a.当某个决策变量xj0时,令x/j=xj 。 b. 当某一个决策变量xj没有符号限制时，可以令 xj = xj- xj 其中 xj0，xj0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj

20、和xj的大小。 3右端项有负值的问题： 在规范方式中，要求右端项必需每一个分量非负。当某一个右端项系数为负时，如 bi0，那么把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。 c. 绝对值不等式 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束 ：974321xxx可将其化为两个不等式，再参与松驰变量化为等式： 974974321321xxxxxxd. axb (a、b均大于零)有两种方法：一种方法是添加两个约束xa及xb另一种方法是令x=xa，那么axb等价于0 xba，添加一个约束xba并且将原问题一切x用x=

21、x+a交换。【例2-8】将以下线性规划化为规范型 3213minxxxZ无符号要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx【解】:目的函数为min，令Z=-Z； 由于x3无符号要求 ，即x3取正值也可取负值，规范型中要求变量非负，所以令 0,33333 xxxxx其中 (4)第二个约束条件是号，在号 左端减去剩余变量(Surplus variable)x5，x50。也称松驰变量3213minxxxZ无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx(3) 第一个约束条件是号，在左端参与松驰变量 (

22、slack variable) x4，x40,化为等式；(5)第三个约束条件是号且常数项为负数，因此在左边参与松驰变量x6，x60，同时两边乘以1。 综合起来得到以下规范型： 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、【例2-9】 ：将以下线性规划问题转化为规范方式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0 解：首先,将目的函数转换成极大化： 令 z=

23、-f = -2x1+3x2-4x3 其次思索约束，有2个不等式约束，引进松弛变量x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。经过以上变换，可以得到以下规范方式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5 = 8 - x 1 - x 2 -x3 = 9 x 1 , x 2 , x 3 ,x4 ,x5 0【例2-10】将下例线性规划化为规范型无约束、211212145|maxxxxxxxxZ【解】 此题关键是将目的函数中的绝对值去掉。令 ： 00000000000022222

24、22211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 那么有：得到线性规划的规范方式 112211223114112234max()()540Zxxxxxxxxxxxxxxxxxx 、 、 、 、 、作业 教材第五章习题5、7中线性规划化为规范型2、普通单纯形法、普通单纯形法 设线性规划的规范型设线性规划的规范型 max Z=CX 1.1 AX=b 1.2 X 0 1.3式中式中A 是是mn矩阵，矩阵，mn并且并且rA=m，显然，显然A中至少有中至少有一个一个mm子矩阵子矩阵B，使得，使得rB=m。基 (basis)A中mm子矩阵B并

25、且有rB=m，那么称B是线性规划的一个基或基矩阵basis matrix 。当m=n时，基矩阵独一，当mn时，基矩阵就能够有多个，但数目不超越mnC【例2-11】线性规划 32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj 求一切基矩阵。 【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵 10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵

26、只需9个，即由线性代数知，基矩阵B必为非奇特矩阵并且|B|0。当矩阵B的行列式等于零即|B|=0时就不是基 。当确定某一矩阵为基矩阵时，那么基矩阵对应的列向量称为基向量(basis vector)，其他列向量称为非基向量 。基向量对应的变量称为基变量(basis variable)，非基向量对应的变量称为非基变量 在上例中B2的基向量是A中的第一列和第四列，其他列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。010152B10261001115A可行解(feasible solution) 满足式1

27、.2及1.3的解X=x1,x2，xn)T 称为可行解 。根本可行解(basis feasible solution) 假设根本解是可行解那么称为是根本可行解也称基可行解。 例如，例如， 与与X=0，0，0，3，2，都是例，都是例2-11 的可行解。的可行解。 TX) 1 ,27,21, 0 , 0( 根本解根本解(basis solution) 对某一确定的基对某一确定的基B，令非基变量等于零，令非基变量等于零，利用式利用式1.解出基变量，那么这组解称为基的根解出基变量，那么这组解称为基的根本解。本解。 最优解(optimal solution) 满足式1 .1的可行解称为最优解，即是使得目的函数到达最大值的可行解就是最优解，例如可行解 是例2的最优解。TX)8 ,0,0,0,53(非可行解(Infeasible solution) 无界解 (unbound solution)显然，只需根本解中的基变量的解满足式1.的非负要求，那么这个根本解就是根本可行解。 在例2-11中，对B1来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，那么式1.为2610352121xxxx,610151B对B2来说，x1,x4,为