[数学]Chapter 2 线性规划.ppt

例题5 分配问题及匈牙利算法(Assignment Problem),,本章篇目,,一、问题的提出和数学模型,例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作问：如何分配，能使所需的总时间最少？,,,,,甲 乙 丙 丁,工作,人,译英文 译日文 译德文 译俄文,2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9,,,1.1 数学模型 Mathematical Model,线性规划（Linear Programming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入线性规划通常研究资源的最优利用、设备最佳运行等问题例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。

应用模型举例,【例1.1】最优生产计划问题某企业在计划期内计划生产甲、乙、丙三种产品这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？,表1.1 产品资源消耗,分析：设变量xi为第i种（甲、乙、丙）产品的生产件数（i＝1，2，3）根据题意，我们知道三种产品的生产受到设备能力（机时数）的限制对设备A，三种产品生产所占用的机时数不能超过200，于是我们可以得到不等式： 3x1+ x2+ 2 x3 ≤ 200； 对设备B，三种产品生产所占用的机时数不能超过200，于是我们可以得到不等式： 2x1+2x2+4x3 ≤ 200；,对材料C，三种产品生产所消耗的材料数不能超过360公斤，于是我们可以得到不等式： 4x1+5x2+x3 ≤ 360； 对材料D ，三种产品生产所消耗的材料数不能超过300，于是我们可以得到不等式： 2x1+3x2+5x3 ≤ 300；,同时，我们有一个追求目标，即获取最大利润。

于是可写出目标函数z为相应的生产计划可以获得的总利润：z=40x1+30x2 +50x3,【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为：,,,最优解X=(50,30,10);Z=3400,,这是一个典型的利润最大化的生产计划问题其标中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；例题中x1、x2、x3 称为决策变量;不等式组称为约束条件,( 有时在它前面加“s.t.”表示“subject to”的意思，意思是“满足于……”);函数Z称为目标函数,随讨论问题的不同,Z也可以求最小值.,线性规划的数学模型由 决策变量 Decision variables ;目标函数Objective function及约束条件Constraints构成称为三个要素怎样辨别一个模型是线性规划模型？其特征是： 1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或 最小值； 2．解决问题的约束条件是一组多个决策变量 的线性不等式或等式书本还例举了诸如合理用料问题;配料问题;投资问题;均衡配套生产问题等.,线性规划的一般模型 一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2…,n，目标函数的变量系数用cj表示, cj称为价值系数。

约束条件的变量系数用aij表示，aij称为工艺系数约束条件右端的常数用bi表示，bi称为资源限量则线性规划数学模型的一般表达式可写成,,,在实际中一般xj≥0,但有时xj≤0或xj无符号限制1.2 线性规划的标准型 Standard form of LP,Max（或Min）z = c1x1 + c2x2 + … + cnxn,a11x1 + a12x2 + … + a1nxn = b1a21x1 + a22x2 + … + a2nxn = b2 . .am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0,注：本教材默认目标函数是 max,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量xj均非负、右端常数bi项非负 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式,如果目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则可以令z ＝ -f ，该极小化问题与下面的极大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z,线性规划的标准形式也写成下列形式：,或用矩阵形式,如何将非标准形式的线性规划问题转化为标准形式,１当约束条件为ai1 x1+ai2 x2+ … +ain xn ≤ bi可以引进一个新的变量s ，使它等于约束右边与左边之差s=bi–(ai1 x1+ ai2 x2 + … + ain xn )显然，s 也具有非负约束，即s≥0，这时新的约束条件成为ai1 x1+ai2 x2+ … +ain xn+s = bi,２当约束条件为 ai1x1+ai2x2+ … +ainxn ≥ bi 时，类似地令 s=(ai1x1+ai2x2+ … +ainxn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1x1+ai2x2+ … +ainxn-s = bi,,为了使约束由不等式成为等式而引进的变量s称为“松弛变量”（slack variable）。

如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量例1.12】将下列线性规划化为标准型,【解】（１）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以令,(2) 第一个约束条件是≤号，在≤左端加入松驰变量x4，x4≥0,化为等式,(3)第二个约束条件是≥号，在≥号 左端减去剩余变量x5，x5≥0也称松驰变量,4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松驰变量x6，x6≥0，同时两边乘以－15）目标函数是最小值，为了化为求最大值，令Z′=－Z,得到max Z′=－Z，即当Z达到最小值时Z′达到最大值，反之亦然综合起来得到下列标准型,当某个变量xj≤0时,令x/j=－xj 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式例1.13】将下例线性规划化为标准型,【解】 此题关键是将目标函数中的绝对值去掉 令,则有,得到线性规划的标准形式,对于a≤x≤b(a、b均大于零)的有界变量化为标准形式有两种方法，一种方法是增加两个约束x≥a及x≤b，另一种方法是令Ｘ′=x－a，则a≤x≤b等价于0≤Ｘ′≤b－a，增加一个约束Ｘ′≤b－a并且将原问题所有x用Ｘ′＋a替换。

1.如何化标准形式？ 可以对照四条标准逐一判断 标准形式是人为定义的，目标函数可以是求最小值 2.用WinQSB软件求解时，不必化成标准型 图解法时不必化为标准型 3.单纯形法求解时一定要化为标准型 作业：教材P34 T 8,1.3 图解法 Graphical Method,线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解图解法求解线性规划问题的步骤如下： (1)分别取决策变量x1 ,x2 为坐标向量建立直角坐标系 （2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过,判断确定不等式所决定的半平面各约束半平面交出来的区域(存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解这些符合约束限制的点集合，称为可行集或可行域3.绘制目标函数图形先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；,4.求最优解依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解x1,x2,O,,10,,20,,30,,40,,10,,20,,30,,40,,,,,(3,4),,(15,10),最优解X=(15,10),最优值Z=85,,,,,,,,,,例1.7,,,,,2,4,6,x1,x2,2,4,6,,,,,,,,,,,,,最优解X=(3,1) 最优值Z=5,(3,1),min Z=x1+2x2,例1.8,,,2,4,6,x1,,2,,4,,6,,,,,,,,,,X（2）＝（3,1）,X（1）＝（1,3）,(5,5),min Z=5x1+5x2,例1.9,有无穷多个最优解 即具有多重解,通解为,0≤α≤1,当α=0.5时 Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2),x2,,,2,4,6,x1,x2,2,4,6,,,,,,,,,,,无界解(无最优解),max Z=x1+2x2,例1.10,由以上例题可知，线性规划的解有4种形式：,1.有唯一最优解(例1.7例1.8),2.有多重解(例1.9),3.有无界解(例1.10),4.无可行解(例1.11),1、2情形为有最优解 3、4情形为无最优解,1.通过图解法了解线性规划有几种解的形式 2.作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动,作业：教材P34 T7,学习要点,1.4 线性规划的有关概念 Basic Concepts of LP,设线性规划的标准型max Z=CX （1.1）AX=b （1.2）X ≥0 （1.3） 式中A 是m×n矩阵，m≤n并且r（A）=m，显然A中至少有一个m×m子矩阵B，使得r（B）=m。

基 (basis)A中m×m子矩阵B并且有r（B）=m，则称B是线性规划的一个基（或基矩阵basis matrix ）当m=n时，基矩阵唯一，当m