线性规划课程.ppt

《线性规划课程.ppt》由会员分享，可在线阅读，更多相关《线性规划课程.ppt（81页珍藏版）》请在三一文库上搜索。

1、线性规划,线性规划研究的主要问题,一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。 另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（ max 或 min ）。,线性规划问题及其数学模型,例一 P 8 分析：首先看利润的计算。 为制造的产品 的数量， 为制造的产品 的数量。 于是，利润函数是 再来看各项资源条件的限制，首先看设备的限制 再看原材料A的限制 最后看原材料B的限制 还要考虑数量不能为负数，则有,例一的数学模型,P9例二,第一段：

2、 第二段： 第三段：,规划问题的数学模型,三要素：决策变量、目标函数和约束条件 1.决策变量： X = (x1,x2,.,xn)T 2.目标函数：max(minz) = c1 x1 + c2 x2 + . + cnxn 3.约束条件： a11x1 + a12 x2 +.+ a1n xn (=) b1 a21x1 + a22 x2 +.+ a2n xn (=) b2 am1x1 + am2 x2 +.+ amn xn (=) bm x1,x2,xn0,模型特点,1 都用一组决策变量X = (x1,x2,xn)T表示某一方案，且决策变量取值非负； 2 都有一个要达到的目标，并且目标要求可以表示成决

3、策变量的线性函数； 3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。 满足以上三个条件的数学模型称为线性规划,线性规划问题的数学模型,模型的简写形式,矩阵形式,系数矩阵,价值系数,决策变量,常数项,线性规划问题的标准形式,标准形式的转换,一、最小值化最大值（minmax) 二、约束条件的右端项小于0(b0) 三、约束条件为不等式(或） 四、变量无约束（x无约束） 五、变量小于0(x0),第二节 图解法,模型中只有两个或三个变量的线性规划问题，可用图解法。 例,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,作 图, 最 优 解：x1 = 4 x2 =

4、2,有唯一最优解，Z =14,x2,x1,(4 2),图解法解题步骤,1 、在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分。 2 、标出目标函数值增加的方向。 3、 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。 4、 将最优解代入目标函数，求出最优值。,线性规划问题的几种可能结局,无穷多最优解,无界解,x1,x1,x2,x2,x1,x2,无可行解,第三节 单纯形法原理,解的概念 1、可行解：满足约束条件（2）（3）的解为可行解。所有解的集合为可行解的集或可行域。 2、最优解：使目标函数达到最大值的可行解。

5、 3、 基：B是矩阵A中mm阶非奇异子矩（B0），则B是一个基。,则称 Pj ( j = 1 2 m) 为基向量。 Xj 为基变量，否则为非基变量,基解：以线性规划约束等式的系数矩阵A中任意m行m列组成的mm满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量其余变量称为非基变量，令非基变量为零，可求得基变 量的值，这样求出的解称为基解。 显然，基解的总数不超过 基可行解：满足非负约束条件的基解，简称基可行解。 可行基：对应于基可行解的基称为可行基。,令非基变量 x10，x2 0,则得：X (0, 0, 3, 1 )T,则：基变量为x2、x3，非基变量为x1、x4,令非基变量 x10，x4 0,

6、则得：X (0, 1, 5, 0 )T,不是基可行解,是基可行解,例 讨论下述约束方程的解 x1 2x2 x3 3 2x1 x2 x4 1,解,系数矩阵为：,则：基变量为x3、x4，非基变量为x1、x2,3）X (1/2, 1/2, 3/2, 1/2)T,不是基解,不是基可行解,1 可行解与最优解：,最优解一定是可行解，但可行解不一定是最优解。,线性规划解之间的关系,基解不一定是可行解，可行解也不一定是基解。,2 可行解与基解：,3 可行解与基可行解：,基可行解一定是可行解，但可行解不一定是基解。,基可行解一定是基解， 但基解不一定是基可行解。,4 基解与基可行解：,5 最优解与基本解：,最优

7、解不一定是基解， 基解也不一定是最优解。,问题：最优解与基可行解？,第四节 单纯形法,基本定理,定理 1 若线性规划问题存在可行解，则问题的可行域是凸集。 引理1 线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。 定理 2 线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。 引理2 若K是有界凸集,则K中任意一点可以表示为K的顶点的凸组合. 定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解。,单纯形法的思想,考虑：若线性规划问题有最优解，必有一个基可行解是最优解。 思路：找出一个基可行解，判断是否最优，否则，换一个基可行解。 几何意义

8、,找出一个初始可行解,是否最优,转移到另一个目标函数 （找更大的基可行解）,最优解,是,否,循 环,直到找出为止，核心是：变量迭代,结束,其步骤总结如下：,例,变成标准型,称松弛变量,约束方程的系数矩阵,为基变量,为非基变量,I 为单位矩阵且线性无关,令：,则：, 基本可行解为（0 0 12 8 16 12） 此时，Z = 0,然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。,注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。,当 时， 为换入基变量,确定换出变量,为0，于是为换出的非基变量,接下来有下式：,用高

9、斯法，将 的系数列向量换为单位列向量，其步骤是：,结果是：,代入目标函数：,有正系数表明：还有潜力可挖，没有达到最大值；,此时：令 得到另一个基本可行解 （0，3，6，2，16，0）,有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。,如此循环进行，直到找到最优为止。,本例最优解为： （4，2，0，0，0，4）,检验数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）： 以下用 表示基变量，用 表示非基变量。,把第i个约束方程移项，就可以用非基变量来表示基变量xi， 把以上的表达式带入目标函数，就有 其中：,所谓最优性检验

10、就是判断已求得的基本可行解是否是最优解。 最优性检验的依据检验数j 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。显然所有基变量的检验数必为零。,最优性检验,最优解判别定理,对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理

11、。设用非基变量表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小于等于零时，可知 是一个小于等于零的数，要使z的值最大，显然 只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。 *对于求目标函数最小值的情况，只需把 0改为 0,通过检验，我们知道这个初始基本可行解不是最优解。如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。 为了换基就要确定换入变量与换出变量。 1. 入基变量的确定 从最优解判别定理知道，当某个j0时，非基

12、变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量。 2.出基变量的确定 把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。,单纯形表,单纯形表,XB列中填入基变量 CB列中填入基变量的价值系数 b 列中填入填入约束方程组右端的常数 Cj行中填入基变量的价值系数 列的数字经计算后填入。 最后一行称

13、为检验数行，对应各费基变量xj的检验数是：,例 题：,2 3 0 0 0 0,12/2,8/2,12/4,3,x2,3,0,1,0,0,0,1/4,2,6,2,0,1,0,0,-1/2,1,0,0,1,0,0,-1/2,2 0 0 0 0 -3/4,6/2,2,16/4,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,0 0 0 -2

14、0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,无界解的判定：若 为一基可行解，有一个 ，并且 对 ，有 那么该线性规划问题具有无界解（或称无最优解）。 当所有非基变量对应检验数都小于等于零时，其中有非基变量对应检验数为零时，该问题的最优基可行解有无穷多个。,退化： 即计算出的（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几

15、个基变量等于零，这就是退化（会产生退化解）。 虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例是永远达不到最优解。,布兰德（Bland）法则,法则1、当有多个检验数是正数时，选对应变量中下标最小者为进基变量。即 确定进基变量为 法则2、当按 规则计算存在两个或两个以上最小比值时，选取下标最小的基变量为换出变量。 按布兰德法则计算时，一定能避免出现循环。,前面所讲的单纯形迭代过程，是在化为标准形式后约束条件的系数矩阵中含有单位阵的条件下进行的。如果化为标准形式后约束条件的系数矩阵中不含有单位阵呢？,人工变量法,对所有约束条件是 的不等式及等式约束情况，若不存在单位矩阵，就采

16、用人造基的方法。即对不等式约束减去一个非负的松弛变量后，在加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。,这样，可得到初始基可行解。（0，0，0，11，0，3，1） 不过，因为人工变量是是后加入原约束条件的虚拟变量，于是要求将它们从基变量中逐个替换出来。 经过迭代，基变量中不再含有非零的人工变量，这表示原问题有解。如果，最后，检验数全大于或等于零，仍含有某个非零的人工变量，则无可行解。,一、大M法,即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。这样，则必须将人工变量从基变量中换出，否则，就不能实现极值

17、。,人工变量是x6，x7,最优解为（4 1 9 0 0 0 0），Z = 2,用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。,第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：,.两阶段法：,对上述模型求解（单纯形法），若W=0,说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。,第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。,例：,第一阶段,1,1,第一阶段求得结果是W=0，得最优解是 （0，1，1，12，0）是这线性规划问题的基可行解。

18、 然后进入第二阶段的运算。,第二阶段,最优解为（4 1 9 0 0），目标函数 Z = -2,根据上表列出初始单纯形表 A,线性规划小结,A,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。 .要求解问题的目标函数能用数值指标来反映，且为线性函数； .存在着多种方案； .要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。,线性规划模型的应用,（一）、资源的合理利用,一般提法： 某厂计划在下一生产周期内生产B1,B2, Bn种产品，要消耗A1,A2, Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生

19、产计划，才能充分利用现有的资源，使获得的总利润最大？,例,有甲乙两个煤场，每月储备为60吨，100吨。他们担负三个居民区的用煤任务。这三个居民区每月需用煤分别为45吨，75吨，40吨。甲厂离这三个居民区分别为10公里，5公里，6公里。乙厂离这三个居民区分别为4公里，8公里，15公里。问这两个厂如何分配供煤量，才能使总运输量最小？,物资调用问题,设某种物资有m个发点（仓库或产地），记为A1,A2,Am；有n个收点（需求单位或销地），记为B1,B2,Bn。已知发点Ai的物资储备量为ai吨（i=1,m),收点Bj的需求量为bj吨（j=1,n), Ai到Bj每吨物资的运费为cij(i=1,m, j=1

20、,n)制定一个调运方案，使之满足各收发点的供需要求，又使总运费最少。,例： 现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,100 200,3 2 1 0 0 2 4 6,2.5米 1.3米,需要 根数,一 二 三 四,下料 下料 毛 件数 方式 坯型号,设变量为 第 j 种方法的所有 原料件数,（三）、合理下料问题,一般提法 设用某种原材料截取零件A1,A2, Am的毛坯。根据以往的经验，在一种原材料上可以有B1,B2, Bn种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又使原材料消耗最少？,例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？,设：Xj 表示Bj 种食 物用量。,（四）、合理配料问题,一般提法 某饲养场用n种饲料B1,B2, Bn配置成含有m种营养成分A1,A2, Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？,