《1172线性规划问题及其数学模型》由会员分享，可在线阅读，更多相关《1172线性规划问题及其数学模型（52页珍藏版）》请在金锄头文库上搜索。
1、,第 一 章 线性规划与单纯形法,预备知识：,1、融会贯通地理解要解决的问题， 搞清在什么条件下，要追求什么目标？ 2、这个要实现的目标是由一组变量决定的 决策变量。 定义决策变量，每一个问题用一组决策变量 （x1 , x2 , x3 , xn）来表示某一方案， 每组决策变量的值就代表一个具体方案； 3、用决策变量的线性函数来表示写出所要追求的目标，我们称之为目标函数。 按问题的不同，可能要求这目标函数实现最大化或最小化。 4、这些决策变量需要一定的限制和约束，这些约束条件可以用一组线性等式或线性不等式来表示。,小结1：建模的基本步骤,设置决策变量，它们体现解决问题的方案。,确定目标函数，它是
2、决策变量的函数。,确定决策变量的取值范围，给出优化方向。,确定约束条件，它们是含有决策变量的不等式或等式。,小结2：数学模型的共同特征,（1）每一个线性规划问题都用一组决策变量 ,每组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；(2)要有各种资源和使用有关资源的技术数据创造新价值的数据；资源的数据:,(3) 存在可以量化的约束条件， 这些约束条件可以用一组线性等式或线性不等式来表示;(4) 要有一个达到目标的要求， 它可用决策变量的线性函数(称为目标函数)来表示。 按问题的不同，要求目标函数实现最大化或最小化。具有上述特征的数学模型称为线性规划模型,一类是在有限的人力、物力
3、、财力的条件下，研究如何合理地计划和安排，使得某一目标达到最大（产量最大、利润最大）。 另一类是任务确定后，如何计划和安排，用最少的人力、物力和财力，去实现该任务，使得成本最小。,线性规划研究对象：,决策变量 目标函数 约束条件,线性规划的一般模型形式,目标函数,约束条件 Subject to,资源系数 (右边项),价值系数,工艺系数,它们的对应关系可用表格表示：,1.2 二维线性规划问题的图解法,对于只有两个决策变量的LP，可以在平面直角坐标系上作图表示其有关概念，并进行求解。,因存在 ，所以必须在直角坐标系的第1象限内作图，求解。,定义1 在LP 问题中，凡满足约束条件的解 称为LP 问题
4、的可行解，所有可行解的集合称为可行解集（或可行域）。,定义2 使目标函数取得最优值的可行解，称 为最优解。 相应的目标函数值称为最优值.,图解法的步骤：,建立平面直角坐标系,根据约束条件找出可行域,图示目标函数,确定最优解,【例1】,x2= - (2/3) x1 + z / 3,目标函数等值线,定义3 当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。,max z=2x1+3x2 s.t. x1+ 2x284x1 164x212 x1 0, x20,最优解,8,4,0,x1,x2,最优解为x=(4,2)T,最优值z=14,4,3,Q4（3，0）,Q2（4，
5、2）,Q1（4，0）,可行域,目标函数等值线:x2=-(2/3)x1+z/3,Q3（2，3）,LP图解法的基本步骤：,1、在平面上建立直角坐标系；,2、图示约束条件，确定可行域和顶点坐标；,3、图示目标函数（等值线）和其移动方向；,4、寻找最优解。,max z=x1+3x2 s.t. x1+ x26-x1+2x28x1 0, x20,可行域,目标函数等值线 x2= -x1/3+z/3,最优解,最优解必落在可行域的顶点上,LP 问题从解的角度可有两种分类方式：, 有可行解, 无可行解,有唯一最优解 b. 有无穷优多最解,线性规划问题解的几种情况：,唯一最优解无穷多最优解无界解无可行解,（1）有最
6、优解,（2）无最优解,第一种分类,第二种分类,有最优解 无最优解,（无界解）,【 例1 】 max z=2x1+ 3 x2 s.t. x1+ 2x284x1 164x212 x1 0, x20,目标函数等值线,最优解,8,x1,x2,无穷多最优解(多重最优解),4,结论： LP 若有最优解，必在可行域的某个顶点上取到； 若在两个顶点上同时取到，则这两点的连线上 任一点都是最优解。,例： max z=x1+x2 s.t. -2x1+ x24x1 - x2 2x1 0, x20,目标函数等值线,4,2,无界解,即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。 一般来说，这说明模型有错，忽
7、略了一些必要的约束条件。,无可行解,增加的约束条件,当存在矛盾的约束条件时，为无可行域。在例1的数学模型中增加一个约束条件:,则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解,唯一最优解,无穷多最优解,无界解,无可行解,小结:,线性规划的可行域和最优解的情况 可行域为封闭的有界区域 有唯一的最优解 有无穷多个最优解 可行域为非 封闭的无界区域 有唯一的最优解 有无穷多个最优解 目标函数无界 可行域为空集 没有可行解，原问题无最优解,1、可行域为封闭的有界区域,唯一最优解,无穷 多个最优解,2.可行域为非封闭的无界区域,唯一最优解,无穷多个最优解,无界解,3、可行域为空集,无可行解,
8、两个变量的LP问题的解的启示：,(1)可行域非空时，它是有界或无界凸多边形（凸集） ，顶点个数只有有限个。,(4)若最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。,(5)若在两个顶点上同时取到最优解，则这两点的连线上 任一点都是最优解,(2)求解LP问题时，解的情况有： 唯一最优解；无穷多最优解；无界解；无可行解。,(3)若可行域非空且有界则必有最优解， 若可行域无界，则可能有最优解，也可能无最优解。,求解线性规划问题最优解的方法：确定可行域 = 凸集(凸多边形)确定可行域顶点 = 求基可行解寻找最优解，如果最优解存在，则必在可行域的某一顶点= 在基可行解中寻找,由图解法得到的
9、结论：,图解法优点：,直观、易掌握。有助于了解解的结构。,图解法缺点：,只能解决低维问题，对高维无能为力。,1.3 线性规划问题的标准型式,一般式矩阵式向量式,化标准形式,其中 bi 0 (i=1,2,m),一般标准式：,其中 bi 0 (i=1,2,m),向量式：,矩阵式：,化标准式：,2. 约束条件,3. 变量,1. 目标函数,4. 右端项系数,(1)目标函数 若目标函数是求最小值，即min z=CX。 因为求 min z 等价于求 max (-z)， 故令 z = - z， 于是得到max z= -CX。 这就同标准型的目标函数的形式一致了。,化标准式：,令Z = -Z,(2)约束条件
10、若约束方程为不等式，则有两种情况： 一种是约束方程为“”不等式，则可在“”不等式的左端加入非负松弛变量，把原“”不等式变为等式； 另一种是约束方程为“”不等式，则可在“”不等式的左端减去非负剩余变量(也可称松弛变量)，把不等式约束条件变为等式约束条件。,下面举例说明:,(3)变量,其中,若 xk 为自由变量，即 xk 可为任意实数，,可令,设 xk没有非负约束， 若 xk0，可令 xk ， = - xk ， 则 xk 0；,右端项bi 0时，只需将等式两端同乘（-1）则右端项必大于零,1.4 线性规划问题的解的概念,1.可行解、可行解集（可行域）最优解、最优值 2.基、基变量、非基变量 3.基
11、本解，基本可行解 4.可行基、最优基,1. 可行解，可行域，最优解,满足约束条件(1-5)，(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解； 其中使目标函数达到最大值的可行解称为最优解 最大的目标函数值称为最优值； 全部可行解的集合称为可行域。,对于标准的LP来说,2. 基，基向量，基变量，非基变量,设A是约束方程组mn维的系数矩阵，其秩为m， B是矩阵A中mm阶非奇异子矩阵（B的行列式B0）， 则称B是线性规划问题的一个基阵或基。,此标准型最多有 个基,（1）基,LP的基有：B1， B2 ，B3,B4不是LP的基,（2）基向量，基变量，非基向量,（a)称 pi (i=1
12、,2,m) 为基向量，它们是一组线性无关的向量组；,(b)对应的向量xi (i=1,2,m) 为基变量；,(d)对应的变量xj (j= m+1,n) 为非基变量，非基变量也称为自由变量或独立变量，可自由取值。,(c)其他向量pj (j= m+1,n) 为非基向量，有n-m个，,上述基B 中 （B0）,2. 基，基向量，基变量，非基向量,基变量 在有n个变量、m个约束方程的标准型线性规划问题中， 若取其中的m个变量，且这些变量在约束方程中对应的m个系数列向量是线性无关的，则它们组成一组基变量。 确定了一组基变量后，其它n-m个变量称为非基变量。,令方程组（1-5)的基是B，设XB是对应于这个基B
13、的 基变量，记XB=（X1，X2，Xm）T,若令上式的非基变量Xm1Xm2Xn0，,约束方程变成m元一次方程，利用,X=（X1，X2，Xm，0，0）T，称X为基解。,该基解所得非零分量的个数不大于方程的个数m,3 . 基解 , 基可行解 (1) 基解,可以求出一个解：,满足非负约束条件(1-6)的基解。称为基可行解。,(2) 基本可行解,一个基可行解的非零分量个数也不超过m个， 并且都是非负的。,一个基解的非零分量个数不超过m个， 其分量可以有负的；,基可行解和基解的数目最多是 个。 一般基可行解的数目要小于基解的数目。,4. 可行基,对应于基可行解的基，称为可行基。,当基可行解为最优解时,对
14、应的基称最优基。,基可行解的非零分量个数 m 时，此时的基可行解 称为退化解。,关于标准型解的若干基本概念小结：,可行解与非可行解满足约束条件和非负条件的解 X 称为可行解，满足约束条件但不满足非负条件的解 X 称为非可行解。基解 令非基变量 XN = 0，求得基变量 XB ,则(XB , XN)称为基解，其中 XB = B 1 b , XN =0 。 (XB , XN )是基解的必要条件为XB 的非零分量的个数 m 。基可行解 基解 中, XB 的非零分量都 0 时，称为基可行解，否则为基非可行解。 基可行解的非零分量个数 m 时，称为退化解。,可行解,不可行解,基 解,基可行解,满足全部约束条件的解，对应可行域内的所有点,只满足约束方程，不满足非负条件的解，对应所有约束直线的交点,满足全部约束条件，且有n-m个分量为0的解，对应可行域的顶点,以上提到的几种解的概念，它们之间的关系可用下面图表明。,是基本解 不是可行解,可行解示例,对于LP：,基本可行解,可行基,反之，如果有一个基变量也取零值，则称它是退化解, 即基解中的非零分量的个数小于m个时， 则该基解是退化解。 在以下讨论时，假设不出现退化的情况。 以上给出了线性规划问题的解的概念和定义， 它们将有助于用来分析线性规划问题的求解过程。,在LP的一个基可行解中，如果它的所有的基变量都取正值，则称它是非退化的解；,
