《新编经济应用数学 线 概 数 第五版 教案3.2.2新》由会员分享，可在线阅读，更多相关《新编经济应用数学 线 概 数 第五版 教案3.2.2新（15页珍藏版）》请在金锄头文库上搜索。
1、3.2.2 线性规划数学模型教学目的：会建立简单的线性规划问题的数学模型，熟练掌握线性规划问题的标准形和线性规划问题的图解法，掌握线性规划问题的单纯形法，了解两阶段法。内 容：1. 线性规划问题的数学模型2. 图解法3单纯形法4. 两阶段法教学重点: 线性规划问题的数学模型、两个变量的线性规划问题的图解法、单纯形法教学难点: 线性规划问题的数学模型建立，两阶段法教 具：多媒体课件教学方法: 启发式教学，精讲多练教学过程：1.引入新课：本节介绍线性规划问题的数学模型，两个变量的线性规划问题的图解法。本节介绍线性规划问题的单纯形法及两阶段法。2.教学内容：一、线性规划问题的数学模型【例1】某生产车
2、间生产甲、乙两种产品，每件产品都要经过两道工序，即在设备A和设备B上加工，但两种产品的单位利润却不相同。已知生产单位产品所需的有效时间（单位：小时）及利润见表3-10。问生产甲、乙两种产品各多少件，才能使所获利润最大。表1 甲、乙产品资料甲乙时间（小时）设备A3260设备B2480单位产品利润50元/件40元/件解 该问题所需确定的是甲、乙两种产品的产量。先建立其数学模型。设分别表示产品甲和乙的产量。称为决策变量。根据问题所给的条件有又因产量不能是负值，故 以上是决策变量受限的条件，把它们合起来称之为约束条件：上述问题要确定的目标是：如何确定产量和，才能使所获利润为最大。利润的获取和密切相关，
3、以表示利润，则得到一个线性函数式所给问题目标是要使线性函数取得最大值（用max表示），即目标函数是max综上所述，本例的数学模型可归结为： max这里“s.t.”是“subject to”的缩写，表示“在 约束条件之下”，或者说“约束为”。【例2】已知某配送中心现有、三种原材料，可加工出A、B两种产品，每吨原材料加工情况及对A、B两种产品的需求情况见表2。表2 加工件数产品原材料需要件数A320300B012100单价1千元/吨1千元/吨1千元/吨问如何配用原材料，既满足需要，又使原材料耗用的总成本最低？解 因目标是原材料耗用的总成本最低（用min表示），故设、种原材料需求量分别为，则问题可写
4、成如下数学模型：s.t.（1）每一个问题都求一组变量，称为决策变量，这组变量取值一般都是非负的；（2）存在一定的限制条件，称为约束条件，通常用一组线性方程或线性不等式来表示；（3）都有一个目标要求的线性函数，称为目标函数，要求目标函数达到最大值或最小值一般地，约束条件和目标函数都是线性的，我们把具有这种模型的问题称为线性规划问题，简称线性规划一个线性规划问题的数学模型的一般形式：求一组决策变量的值，使 （或）， 其中为已知常数一个线性规划问题的数学模型，必须含有三大要素：决策变量，约束条件与目标函数满足约束条件的一组变量的取值：，称为线性规划问题的一个可行解使目标函数取得最大（或最小）的可行解
5、称为最优解，此时，目标函数的值称为最优值二、图解法【例3】用图解法求解例1的线性规划问题max解 在平面直角坐标系中作直线如图1所示。图1 图1阴影部分里所有点（包括边界上的点），满足该问题的所有约束条件。这个范围以外的点，则不能同时满足上述各约束条件。满足所有约束条件的点称为可行点。每一点代表该线性规划问题的一个可行方案，即一个可行解。所有可行点的集合，称为该问题的可行域，故该问题的可行解有无数个。能使目标函数值达到最优值（最大值或最小值）的可行解，这种解称为最优可行解，简称最优解。将目标函数写成：50x1+40x2 = k，其中为任意常数。当为不同值时，此函数表示相互平行的直线，称为等值线
6、。令=0，得到的直线50x1+40x2 = 0，叫做0等值线。先作通过原点的0等值线l3: 50x1+40x2 = 0它与可行域的交点为。将这条直线沿目标函数增大的右上方平移，过顶点E时，在可行域中取最大值；如继续向右上方平移，则等值线将离开可行域（等值线与可行域没有交点）。故E点坐标就是最优解。求直线l1和l2交点E的坐标，即解方程组得到x1=10，x2=15，这时最优值=1100。即例1中，甲产品产量为10件，乙产品产量为15件时，所获利润最大，最大利润为1100元。图解法求解线性规划问题的步骤如下：（1）在平面直角坐标系x1ox2内，根据约束条件作出可行域的图形。（2）作出目标函数的0等
7、值线，即目标函数值等于0的过原点的直线。（3）将0等值线沿目标函数增大的方向平移，当等值线移至与可行域的最后一个交点（一般是可行域的一个顶点）时，该交点就是所求的最优点。若等值线与可行域的一条边界重合，则最优点为无穷多个。（4）求出最优点坐标（两直线交点坐标可联立直线方程求解），即得到最优解(x1, x2)，及最优值（x1, x2）。【例4】 用图解法解线性规则问题min解 在直角坐标系中作直线如图3-3所示,得可行域OCEA。作0等值线 图3-3该等值线斜率与斜率相等，所以。当向右上方平移时，都变大，这时变小。当与边界线AE重合时，目标函数值最小。故边界AE上的所有点，包括两个端点E和A都是
8、此问题的最优解，此时目标函数的最优值为： 这是线性规划问题有无穷多个最优解的情况。【例5】用图解法解线性规划问题 max解 在直角坐标系中, 作直线得可行域，如图3-4所示的阴影部分，它是无界区域。作0等值线 图3-4并将向右上方平移，因可行域无界，目标函数的值趋于无穷大，所以该线性规则无最优解。【例6】 用图解法解线性规划问题 max解 在直角坐标系中作直线，图3-5如图3-5所示，可知可行域为空集，所以此问题没有可行解，当然也没有最优解。由上述几例可见，线性规划问题的解的情况可以归结为：有可行解且有惟一最优解；有可行解且有无穷多最优解；有可行解但无最优解；无可行解。上述结论对于两个以上变量
9、的线性规划问题也是适用的。三、单纯形法1线性规则问题的标准形形如 称为线性规划问题的标准形式，简称标准形求目标函数的最小值令，则可将求转化成求，即约束条件为不等式的，则引入一个非负变量，将线性不等式转化为线性方程，其中称为松弛变量对于，引入，在不等式的左边加上变量，于是不等式化为对于，引入，在不等式的左边减去变量，于是不等式化为若时，可在约束条件的两边同乘以，化为如果有某个变量无非负约束，那么可引进两个非负的变量，令，代入约束条件和目标函数中，使全部变量都非负【例7】将下面的线性规划问题化为标准形：解 （1）令，则目标函数为（2）引进松弛变量，使约束条件为不等式的转化为等式：（3）将变为（4）
10、无非负限制，令，其中，将其代入目标函数及约束条件，得于是，该线性规划的标准形为 2. 单纯形法定义设线性规划的标准形为如果变量只在某一个约束方程中系数为，在其余约束方程中系数均为，则称为该约束条件的一个基变量；如果每个等式约束条件都有一个基变量，则称等式约束条件为这些基变量的典型方程组不失一般性，若线性规划的约束条件是典型方程组，则个变量的线性规划问题的典型方程组为 是基变量，称变量为非基变量令非基变量，可求得约束方程的一个解为此解称为基本解在基本解中，若所有的，则称此解为基本可行解定理1 如果线性规划问题有最优解，那么最优解必是某个基本可行解。由等式约束条件得将其代入目标函数，得 此式就是目
11、标函数用非基变量表示的式子式中系数称为非基变量的检验数定理2设是非基变量的检验数，则(1) 若非基变量的所有检验数（），则基本可行解就是最优解；(2) 若非基变量的所有检验数（），且其中有一个检验数等于，则有无穷多个最优解；(3) 若存在非基变量的检验数，且对应的系数列均小于等于，即，则该线性规划问题无最优解单纯形法的基本思路是对可行域这一凸多边形的一个顶点（第一个基本可行解）出发进行检验，如果不是最优，则换一个（迭代）更优的顶点（另一个基本可行解），使一次比一次更接近最优解（逐步优化），直到取得最优解为止。由定理1知道，线性规划问题的最优解可以通过只考虑它的基本可行解来确定。【例8】用单纯形
12、法求解例1的线性规划问题max解 先引入松弛变量，将问题化为标准形式：目标函数改写为，将约束条件的增广矩阵和改写后的目标函数的系数填入下表中，得到的表称为单纯形表。表1 单纯形表基变量x1 x2 x3 x4bx3x43 2 1 02 4 0 16080-f50 40 0 00单纯形表中，约束条件的系数矩阵中出现一个2阶单位矩阵，b列非负，目标函数行对应于单位矩阵的元素为0，这时其余的元素即为检验数。系数矩阵中已有2阶单位矩阵，其所在的列对应的变量x3，x4是基变量，变量 x1，x2是非基变量。令x1=0，x2=0，由标准形式等式可得x3=60，x4=80，于是得到一个基本可行解，记为X（0）=
13、（0，0，60，80）T，这是初始可行解，其对应的目标函数值f (0) = 0，将其填入表中右下角。它表示：没有安排生产甲、乙产品，利润为0元。由定理2最优解判定准则知，当所有检验数非正时，这个解就是最优解，否则解仍可改善。观察表1中检验数，50、40均为正数，解仍可改善。若将x1或x2变为非零变量都可使目标函数值增加。其中x1的系数更大，它能让目标函数增加较快，故先将x1转变为基变量，这时称之为进基变量，之后有一个基变量被换出，称为出基变量。变量调换完成之时，即可得到一个改善后的基本可行解。具体调换程序如下：确定x1为进基变量后，x1可由原来的零值变为正值，x2仍为非基变量，取为零。方程组就为 当x1增加时，对f 的贡献是正数，当然x1取值越大越好。但要求变量非负，即 则解得这就是说，要使换基后，所对应的解仍为基本可行解，x1只能由0增大到20，这时x3由60下降为0，x4由80下降为20，基变量
