数学建模辅导2--线性规划及单纯形法.ppt

1、运筹学,在军事上，史记：决胜千里之外, 运筹帷幄之中. 田忌赛马。,运筹学：operational research,在工程上，丁渭修皇宫。,运筹学的主要内容,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,学 科 内 容,多目标规划,双层规划,组 合 优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策分析,可靠性分析,线性规划及单纯形法,线性规划问题及其数学模型 图解法 单纯形法原理 数学试验,第一节 线性规划问题及其数学模型,一. 问题的提出,线性规划主要解决：如何利用现有的资源，使得预期目标达 到最优。,例1 美佳公司计划制造、两种家

2、电产品。已知各制造一 件时分别占用的设备A、B的台时、调试工序及每天可用于 这两种家电的能力、各售出一件时的获利情况，如表1-1所 示。问该公司应制造两种家电各多少件，使获取的利润最 大？,表1-1,解：设公司制造、两种家电分别为 件。,问题： 可使得利润Z 最大？,设备A的工时限制：,设备B的工时限制：,解：公司制造、两种家电分别为 件。,调试工序的时间限制：,利润：,即要求：,表1-1,目标函数 objective function,约束条件,资源约束,非负约束,其中,约束条件可记 s. t. (subject to), 意思为“以为条件” “假定” 、“满足” 之意。,例2：捷运公司在下

3、一年度的14月份的4个月内拟租用仓库 堆放物资。已知各月份所需仓库面积列于下表1-2。仓库租 借费用随合同期而定，期限越长，折扣越大，具体数字见表 1-3。租借仓库的合同每月初都可办理，每份合同具体规定 租用面积和期限。因此该厂可根据需要，在任何一个月初办 理租借合同。每次办理时可签一份合同，也可签若干份租用 面积和租用期限不同的合同。试确定该公司签订租借合同的 最优决策，目的是使所租借费用最少。,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,表

4、1-2,表1-3,单位：100m2,单位；元/100m2,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,每一个问题都有一组变量称为决策变量，一般记为,下面从数学的角度来归纳上述两个例子的共同点。, 每个问题中都有决策变量需满足的一组约束条件线性 的等式或不等式。,对决策变量每一组值：,代表了,一种决策方案。通常要求决策变量取值非负，即,二. 线性规划问题的数学模型, 都有一个关于决策变量的线性函数称为目标函数。要 求这个目标函数在满足约束条件下实现最大化或最小化。,将约束条件及目标函数都是决策变量的线性函数的规划问题 称为线性规划。有时也将线性规划问题简记为

5、LP（linear programming)其数学模型为：,上述模型的简写形式为：,若令,用向量表示时，上述模型可写为：,若令,若令,线性规划问题的矩阵形式：,三. 线性规划问题的标准形式：,LP问题的数学模型的标准形式为：,其中常数项,LP问题标准形式的特征是：, 求目标函数的最大值； 约束条件为变量满足线性方程组与非负性两部分； 方程组中常数项皆非负。,下面分析如何将LP问题标准化：, 若目标函数为,引进新的目标函数,则,的最小值即为,的最大值,从而目标函数变换为：,即：,例1 将LP问题,化为标准形。,解：引进新的目标函数,于是原LP问题化为标准形式：, 当约束条件中含有不等式时，如：,

6、例2 将LP问题,化为标准形。,此时，对,引入变量,使得式变为：,同理对式,引入变量,使得式变为：,于是原LP问题化为标准形式：,引进变量x3,x4称为松弛变量。,例3 将LP问题,化为标准形。,对 式引进变量,同理对 式,引入变量,使得 式变为：,使得 式变为：,引进变量x4, x5称为剩余变量。,于是原LP问题化为标准形式：, 若约束条件中线性方程式的常数项为负数，则将该线性 方程式两端乘以-1。如：,例4 将LP问题,化为标准形。,例4 将LP问题,化为标准形。,解：将式 两边乘以-1得此LP问题的标准形式：, 若变量,无约束，则引进两个非负变量,将,表示为：,例5 将LP问题,化为标准

7、形。,例5 将LP问题,化为标准形。,解：,将上式代入目标函数及约束条件中，得到其标准形式：,例6 将LP问题,化为标准形。,解：由于（2）式常数项为负，不等式两边乘以-1得,解：,引进松弛变量：,此LP问题的标准形为：,第二节 图 解 法,一. 预备知识：,1. 平面上一条直线可把平面分成三部分：平面上的点， 直线一侧的点，直线另一侧的点。,y,x,0,5,5,例：,用集合表示：,2. 二元一次不等式的解集代表一个平面域。,例：,代表：,3. 梯度：,定义：设二元函数 若在点 的偏导数,存在，则称向量：,为,在点 处的梯度。记,其几何意义是：二元函数,在某点,沿梯度正向为增加最快的方向。,例

8、：函数,在原点 处的梯度为,0,x,y,2,3,二. 两个变量LP问题的图解法,图解法步骤：, 根据约束条件画出可行域。 根据目标函数Z的表达式画出目标直线Z=0,并表明目标 函数增加的方向。 在可行域中，找符合要求的距离目标直线Z=0的最远或 最近点，并求出该点坐标。,例1 解LP问题：, 画出可行域。, 令Z=0, 有,在原点的梯度：,所以,画出直线,解：,例1 解LP问题：,在原点的梯度：,所以,解：,例1 解LP问题：,解：, 随着直线,沿梯度方向去扫可行域，,目标函数,中的Z在增加。如：,经过点,时，,例1 解LP问题：,解：, 随着直线,沿梯度方向去扫可行域，,目标函数,中的Z在增

9、加。如：,经过点,时，,例1 解LP问题：,解：,由此可见，当目标函数沿,梯度的方向去扫可行域时， 在顶点,处取得最大值。,从而得最优解：,目标函数的最优值为：,例2 解LP问题：,解：, 画出可行域。, 令Z=0,有,画出直线,在原点的梯度：,所以,例2 解LP问题：,解：, 随着直线,沿梯度反方向去扫可行域，,目标函数,中的Z在减小。且在点,处取得最小值。,从而得最优解：,目标函数的最优值为：,例3 解LP问题：,解：, 画出可行域。, 令Z=0,有,画出直线,在原点的梯度：,所以,例3 解LP问题：,解：,沿梯度方向去扫可行域，,目标函数,在点, 先把目标直线Z=0平行,地拉到可行域内，

10、再让直线,处取得最大值。,从而得最优解：,目标函数的最优值为：,例4 解LP问题：,解：, 画出可行域。, 令Z=0,有,画出直线,在原点的梯度：,所以,仅为AB线段。,例4 解LP问题：,解：, 由于目标函数是减小，,故应沿梯度反方向去扫可 行域，先把目标直线拉到上面。,例4 解LP问题：,解：, 随着直线,目标函数,中的Z在减小。且在点,处取得最小值。,从而得最优解：,沿梯度反方向去扫可行域，,目标函数的最优值为：,例5 解LP问题：,解：, 画出可行域。, 令Z=0,有,画出直线,在原点的梯度：,所以,例5 解LP问题：,解：, 随着直线,沿梯度方向去扫可行域，,目标函数,中的Z在增加。

11、直到与直线,重合。,此时，线段CD上的所有点均是最优解。,其中，点C的坐标为：,点D的坐标为：,例5 解LP问题：,解：过,的直线方程为：,例6 解LP问题：,解：, 画出可行域。, 令Z=0,有,画出直线,在原点的梯度：,所以, 随着直线,沿梯度方向去扫可行域，,目标函数,中的Z一直在增加。所以，此LP问题无最优解。,为无界域。,例7 解LP问题：,解：, 画出可行域。,由于可行域为空集，所以此LP问题无可行解，当然无最优 解。,通过以上的讨论，LP问题的解有下面四种类型： 有最优解且有唯一的最优解。 有可行解且有无穷多最优解。 有可行解但无最优解。 (4) 无可行解,补充知识：凸集,凸集：

12、在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,在凸集中，点A，B，C，D称为极点（或顶点）。,A,B,C,D,从图解法中我们了解到以下事实： 若LP问题的可行域存在，则可行域一定是凸集。 若LP问题的最优解存在，则最优解或最优解之一（如果有 无穷多最优解的话）一定是可行域凸集的某个顶点。,思路：最优解先在可行域中找。（可行域为空集，则无可 行解，故无最优解。） 最优解在可行域的顶点中找。 顶点是有限个，若两个顶点都是最优解，则两个顶点所连 线段上的所有点均是最优解）,定义：LP问题的可行域的顶点称为基本可行解。,可行解,可行域中的点,基本可行解,可行域中的顶点,最优解,1

13、.3 单纯形法 原 理,1. 复习：非齐次线性方程组解,例：解非齐次线性方程组,增广矩阵,（1）,为基变量。,称,基变量个数=,此方程组的解为,其中,为任意实数。,为非基变量，或自由变量。,称,称非基变量,为0的解 叫基解。,若对（1）式中的变量再加上非负限制,从而,解域为,注意：此时的,已经不是任意实数。,不是自由变量了。,而对于带有非负约束的方程组,解的每个分量都是非负数，就叫做可行解。,如果基解是可行的，就叫基可行解。,基可行解所对应的基称为可行基。,基解：,是可行基。,解的每个分量都是非负数，就叫做可行解。,如果基解是可行的，就叫基可行解。,基可行解所对应的基称为可行基。,基,可 行

14、最优基 基,非 可 行 基,基,可行基,非可行基,基与解的对应关系：,非可行解,可 行 基本 解 可行解,基本解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,所对应的解,例如,是可行解。,所对应的解,是基解。,也是可行解，故而是基本可行解。,所对应的解,例如,是非可行解。,是可行基。,但并不是所有基都有资格充当可行基。例如,（-6）,所对应的方程组为：,令非基变量,为0，得到基解：,非可行解。,即,非可行基。,基可行解很重要，可以证明以下定理：,定理1 若线性规划问题存在最优解，则问题的可行域是凸集。,定理2 线性规划问题的基可行解对应线性规划问题可行域 （凸集）的顶点

15、。,定理3 若线性规划问题最优解存在，则最优解一定在可行域顶 点处取得。,由此可看出，最优解要在基可行解（可行域顶点）中找。,通过以上分析，可得到以下几个结论：,（1）线性规划问题的可行域是一个凸集，可行域可能有 界，也可能无界，但其顶点数是有限个。（？）,（2）线性规划问题每个基本可行解对应于可行域的一个顶 点。,（3） 若线性规划问题有最优解，则必可在其可行域的某个 （或多个）顶点上达到最优值。,如何从一个可行基找另一个可行基？称基变换。,定义：两个基可行解称为相邻的，如果它们之间仅变换 一个基变量。对应的基称为相邻可行基。,例 LP问题,当前可行基 所对应的基本可行解,显然不是最优。,因

16、为从经济意义上讲，,意味着该厂不安排生产，因此没有利润。,(对应可行域的 ),相应地，将 代入 目标函数得,若让非基变量 取值从零增加，,相应的目标函数值Z也将随之增加。因此有可能找到一个,新的基本可行解，使其目标函数值有所改善。即进行基变,换，换一个与它相邻的基。再注意到 前的系数5比,前的系数2大，即 每增加一个单位对Z的贡献比 大。,故应让 从非基变量转为基变量，称为进基。又因为基,变量只能有三个，因此必须从原有的基变量,中选一个离开基转为非基变量，称为出基。谁出基？,又因为 仍留作非基变量，故仍有,（2）式变为,再让 从零增加，能取得的最大值为,此时， 已经从24降到了0，达到了非基的

17、取值，变 成非基变量。从而得到新的可行基 。,将（2）式,（2）,可行基,留在左边，非基变量,移到右边,（3）,（3）,用代入法的：,用代入法的：,由此得到一个新的基本可行解：,目标函数值：,从目标函数值明显看出， 比 明显地得到了改 善。,此基本可行解对应可行域的,代入目标函数得：,这一过程用增广矩阵的行初等变换表示为：,1/6,（-1）,（-2）,按最小比值规则：,主元素,目标函数系数行,按最小比值规则：,3/2,（-5）,（-1/3）,（-1/3）,所对应的 LP问题,可行基,令非基变量 为0，得到最优解,最优值,此基本可行解对应可行域的,其结果与图解法一致。,总结：在迭代过程中要保持常

18、数列向量非负，这能保证基 可行解的非负性。最小比值也是为了保证解的非负性。 主元素不能为0。因为行的初等变换不能把0变成1。 主元素不能为负数。因为用行的初等变换把负数变成1会 把常数列中对应的常数变成负数。,练习： LP问题,标准化,最优解：,目标函数值：,表 1-7 P/29,表 1-8 P/30,表 1-9 P/30,例2 解LP问题：,对单纯形矩阵作初等行变换，有：,按最小比值原则：,确定主元素。,（-1）,（-1）,3. 无穷多个解情况：,至此，检验行已没有正数， 当前解即为最优解。,此时对应的LP问题为：,0,此时对应的LP问题为：,0,此时对应的LP问题为：,0,1,当,时，不管

19、 取何值，均有目标函数,取得最大值1。此时约束方程为：,其中 为基变量。,其中 为基变量。,用非基变量表示出基变量：,其中， 为自由变量。设为 有:,其中c是满足非负性的任意常数。,再由,的非负性，知：,解出,（其中 ）,最优解为：,最优值为：,另解：,当前最优基变量 对应最优解为：,再强行让检验数为0的 进基，再找一个最优解：,确定主元素。,1/3,按最小比值原则：,2,以 与 的连线段：,即,为全部解的一般形式。,为全部解的一般形式。,若令：,有,（其中 ）,LP当前解已是最优的四大特征：, 存在一组(初始)可行基（其系数矩阵为单位阵）。, 检验行的基变量系数=0。, 检验行的非基变量系数

20、0。,全部 唯一解。,存在 无穷多个解。, 常数列向量0。,下面的问题是：所给LP的标准型中约束矩阵中没有现成的 可行基怎么办？, 人工变量法（也称大M法）,针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。,例6 用单纯形法求解LP问题,第五节 单纯形的进一步讨论,解：先将其化为标准形式,再强行加上人工变量，使其出现单位矩阵：,但这样处理后：不易接受。因为 是强行引进，称为,人工变量。它们与 不一样。 称为松弛变量和剩,余变量，是为了将不等式改写为等式而引进的，而改写前后,两个约束是等价的。人工变量的引入一般来说是前后不等,价的。只有当最优解中，人工变量都取值零时（此时人工,变量实质上就

21、不存在了）才可认为它们是等价的。,处理办法：把人工变量从基变量中赶出来使其变为非基变 量。为此，发明者建议把目标函数作如下处理：,其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人,工变量取值大于零，目标函数就不可能实现最优。,对此单纯形矩阵作初等行变换，有：,M,M,（-1）,（-3）,（-4M）,1/6,（-6M-3）,2,（-3）,3/2,（-1/3）,（-3）,至此，检验行已没有正数，当前解即为最优解。,最优值为：,去掉人工变量 ，即得原LP问题的最优解：,例7/P34 求解LP问题,解：从上面已看出，此LP问题无解。下面用大M法求解看一,下会出现什么情况。引进人工变量，上述问题化为：,例7/P34 求解LP问题,对单纯形矩阵作初等行变换，有：,M,（-2）,（-2-2M）,至此，检验行已没有正数，当前解即为最优解。,但此时基变量为：,含非零的人工变量,矛盾。说明原问题无可行解。,使用大M法小结：,对LP问题,式中,则在每个约束方程左边加上一个人工变量,（1.1）,（1.2 ）,式（1.2）中含有一个m阶单位阵。以,为基变量。得到一个初始基本可行解：,我们可以从 出发进行迭