高等数学(经管类)第10章 线性规划课件.ppt

《高等数学(经管类)第10章 线性规划课件.ppt》由会员分享，可在线阅读，更多相关《高等数学(经管类)第10章 线性规划课件.ppt（126页珍藏版）》请在三一办公上搜索。

1、第十章 线性规划,10.1 线性规划问题10.2 图解法与运输问题10.3 单纯形法10.4 应用与实践10.5 拓展与提高,一 知识结构框图,第十章 线性规划,二 教学基本要求和重点、难点,第十章 线性规划,1教学基本要求,(1)线性规划问题的数学模型的建立及将数学模型化 为标准形式的方法；(2)线性规划问题的基、基变量、非基变量、可行 解、基本可行解、最优解的概念；(3)两个变量的线性规划问题的图解法,及图上作业法 解平衡型的运输问题；,第十章 线性规划,(4)性规划问题单纯形表的结构,单纯形法及改进的单 纯形法求解线性规划问题；(5)线性规划问题无可行解、有可行解而无最优解、有 惟一最优

2、解、有无穷多最优解等情况在单纯形方法 中的反映；(6)线性规划在生产实践、车辆调度等问题上的应用；(7)表上作业法解平衡型运输问题的方法。,第十章 线性规划,2教学重点与难点,（1）重点 熟练掌握用单纯形法解线性规划问题；“图解法”求解含两个变量的线性规划问题。,（2）难点 线性规划问题的概念、数学模型的建立；图上作业法(和表上作业法)求解运输型问题。,10.1线性规划问题,第十章 线性规划,10.1.1 数学模型,例1 设某食品厂生产甲乙两种产品，生产1t甲产品需要3个工日和10t小麦，可得盈利8千元；生产1t乙产品需要4个工日和8t小麦，可得盈利9千元。该食品厂一个月只能出300个工日，小

3、麦一月只能进700t，那么该厂应如何安排生产，才能在现有的条件下获得最大的盈利？,10.1线性规划问题,解：设甲、乙两种产品各生产x1，x2t，由于该厂一个月只能出300个工日，所以,又由于小麦一个月只能进700t，所以,如果设总的盈利为S，则,10.1线性规划问题,本题目的就是求出一组变量x1，x2的值，使它们满足不等式组,并且使S取得最大值，即,10.1线性规划问题,例2 在设计制造某一种产品时，需要用300cm长的圆钢，截成长度分别为90cm和70cm的两种坯料，要求截出长90cm的坯料1000根，70cm的坯料2000根，那么应该如何截取，才能使所用的圆钢最少？,10.1线性规划问题,

4、解：将长为300cm的圆钢截成长度为90cm和70cm的两种坯料，有4种比较经济的截法可供选择，如表 所示,现在的问题是以上4种截取法各截多少根，才能使花费的总圆钢数最少？,10.1线性规划问题,设用截法1、截法2、截法3、截法4的不同截法各截圆钢 根，因为4种截法获得90cm的坯料总数为，而它的需要量是1000根，所以,同样可得70cm长度的坯料的方程为,设S表示所使用圆钢的总根数，所以,10.1线性规划问题,目的是求出一组变量的值，使它们满足方程组,并且使S取得最小值，即,10.1线性规划问题,例3 一批工业物资，由三个仓库调运到三个工厂，其存需数量如表10-2所示，单位运价如表10-3所

5、示，问应怎样调运才能使总的运价最省？,10.1线性规划问题,解：调运矩阵为,其中xij表示从仓库Ai到工厂Bj调运物资的数量，单位t，,10.1线性规划问题,则根据已知条件得方程组：,根据运价表可以算出总运价是,于是问题就成为求出未知量，使它们满足前面的方程组，且使函数S取最小值。,10.1线性规划问题,共同的特点：就是问题的条件都可以用一组线性等式或线性不等式来表达，并且取最大(小)值的目标函数也是线性函数具有这样特点的问题便是线性规划问题，线性规划问题数学模型的一般形式为：,10.1线性规划问题,10.1.2 线性规划问题的标准形式,10.1线性规划问题,对于非标准化的模型都可以进行某种变

6、换使之标准化。具体方法如下：,(1)引入松弛变量,10.1线性规划问题,(2)引入剩余变量,如果约束条件不标准，例如第k个方程为：,时，则引进变量，使,引进的变量 称为剩余变量(也可以称为松弛变量)。,10.1线性规划问题,(3)目标函数的标准化,如果一模型的目标函数求值不标准，即求最小值，则令,那么问题转化成求,(4)如果约束条件中，某个方程的常数项为负值时，则对其等号两端同乘以(-1)，使常数项化为正数，从而使之标准化。,10.1线性规划问题,例4 将例1给出的线性规划问题数学模型化为标准形式。,解：引入松弛变量，则标准形式 数学模型,10.1线性规划问题,10.1.3 线性规划问题的基本

7、概念,线性规划问题的数学模型用矩阵形式可表示为,10.1线性规划问题,假定在方程组有无穷多个解(mn)时，最终目的是从这无穷多个解中选出使,最大的解，称为最优解。,10.1线性规划问题,10.1线性规划问题,为了简化，令XD=0，即XD的每一分量令其取零值时，得,由于B是满秩矩阵，故 是惟一存在的，于是,这样由XB和零组成的解称为基本解；满足约束条件的解称为可行解；满足约束条件的基本解称为基本可行解；对应基本可行解的基称为可行基；使目标函数达到最优值的可行解称为最优可行解，如果这样的可行解又是基本的，则称为最优基本可行解。,10.1线性规划问题,例5 某线性规划问题的约束方程为,讨论线性规划问

8、题的基本概念。,解：不难验证A与 的秩是相等的，都等于2，而且A的全部二阶方阵为3个，即,三个方阵全是满秩的，故都是线性规划的基。,10.1线性规划问题,(1)对应于基B1，方程组的等价形式为,是基变量，,是非基变量，若令非基变量取0值，则有,10.1线性规划问题,从而,是一个基本解。,所以该解不是可行解。,10.1线性规划问题,(2)对应于基,令非基本变量x2=0，则,10.1线性规划问题,而且是基本可行解。,10.1线性规划问题,为了便于理解线性规划问题的基本概念，现将线性规划问题,的解、可行解、基本解、基本可行解、最优可行解、最优基本可行解系统表示如下：,10.1线性规划问题,10.1线

9、性规划问题,定理10.1 对于标准化模型问题,其中A为m行n列矩阵，矩阵的秩为。,(1)若存在一个可行解，则必存在一个基本可行解；,(2)若存在一个最优解，则必存在一个最优基本可行解。,10.2 图解法与运输问题,第十章 线性规划,10.2.1 两个变量线性规划问题的图解法,例 6 用图解法求解线性规划问题,10.2 图解法与运输问题,解:满足约束条件的点都在如图所示的阴影OABC区域内，该区域就是可行域。可行域内任一点的坐标都是 这个线性规划问题的可行解。,画出以S为参数的直线族S=x1+x2(相互平行)称为目标函数等值线。,B点的坐标是方程组,10.2 图解法与运输问题,例7 用图解法解线

10、性规划问题,等值线可与可行域的边界线段BC重合：,10.2 图解法与运输问题,例8 用图解法解线性规划问题,可行域无界，等值线向右上方无论移动多么远，都不会碰到可行域右上方边界。这就是说，可行域内目标函数值无上界，因而无最大值，也就无最优值。,10.2 图解法与运输问题,10.2.2 运输问题,1.运输问题的一般模型,设某物资有个m产地：联合供应n个销地。各产地产量(单位：吨)、各销地销量(单位：吨)、各产地至销地单位运价(单位：元/吨)如表所示。,问题是应如何调运使总运费最少？,10.2 图解法与运输问题,例9 在A1、A2两个粮库里分别装有大米34吨和38吨，要运往B1、B2、B3三个市场

11、去出售。三个市场的需求量分别是19吨、25吨和28吨，各仓库到各市场的运价(元/吨)如表10-6所示。如何调运才能使总消费最省？,10.2 图解法与运输问题,2.运输问题的图上作业法,由于运输问题的特殊结构，可以在示意图(也称为交通图)上完成其求解的过程。这种求解运输问题的方法，称为图上作业法。,10.2 图解法与运输问题,把某物资从m个产地或仓库(统称为发点“O”，发货量记在圈“O”里面)，调运到n个需要地(称为收点“”，将收货量记在方块“”里面)，物资调运的方向用“”表示，称“”为流向线。,10.2 图解法与运输问题,(1)对流,在物资调运流向图的某一段交通线上，同时有同一物资在同一线路上

12、的往返运输，称为对流运输。,10.2 图解法与运输问题,(2)迂回,在交通图成圈的时候，流向图中有些流向在圈内，称为内圈流向。有些流向在圈外，称为外圈流向。如果流向图中，内圈流向的总长或外圈流向的总长超过整个圈长的一半，就称为迂回运输。,10.2 图解法与运输问题,示例,10.2 图解法与运输问题,一个物资调运方案中，如果没有对流和迂回，那就是运输量最小的方案。因此用图上作业法解运输问题时，应避免对流和迂回。具体步骤为：先找出一个没有对流的初始可行方案，再检查有没有迂回，如果没有迂回，这个方案已是最优方案。如果有迂回，则调整这一方案，直到没有迂回为止。,10.2 图解法与运输问题,对于交通图不

13、成圈的情况，为了做一个没有对流的流向图，要按照法则I：“取一端，它的供需归邻点”的方法进行。,10.2 图解法与运输问题,例10 产地A1,A2,A3和销地B1,B2,B3,B4都在公路线上，其交通图如图所示。试做最优调运方案。,10.2 图解法与运输问题,解：,10.2 图解法与运输问题,对于交通图成圈的情况，先按照法则：“丢边破圈，直到无圈。”,例11 某物资7万吨，由发点A1,A2,A3发货，发量分别为3，3，1(万吨)，运往收点B1,B2,B3,B4，收量分别为2，3，1，1，(万吨)。收发量平衡。问应如何调运，才使吨公里数最小。,10.2 图解法与运输问题,解：(1)先丢边破圈化为不

14、成圈的交通。丢边时，尽量丢掉两端同是收点、发点，且边长较长的边。,10.2 图解法与运输问题,然后再在无圈的交通图10-14上，利用法则I作一个没有对流的流向图如图10-15所示,10.2 图解法与运输问题,(2)检查有无迂回方法是：对流向图中只有一边没有流向的各圈进行检查有无迂回。,圈的全圈长=7+5+4+4+3=23，外圈长=5+4+3=12,10.2 图解法与运输问题,(3)对方案进行调整。,丢A3B4，补回原先丢的A1B4,10.2 图解法与运输问题,然后，再在图10-17上做一个没有对流的流向图，如图10-18。,10.2 图解法与运输问题,在图10-18中，再补回A3B3，A3B4

15、两边，就得新流向图，如图10-19。,10.2 图解法与运输问题,经检验图10-19所示流向图已无迂回，所以就是最优流向图。根据这一流向图得调运方案，如表10-7所示。,(万吨公里),10.3 单纯形法,第十章 线性规划,对于标准形式的线性规划问题,单纯形法求最优解主要思想是：先求出一个基本可行解，然后判断它是否是最优解，如果不是，再找一个更好的基本可行解，再判断新的基本可行解是否是最优解。,10.3 单纯形法,10.3.1引例,例11 求解线性规划问题,10.3 单纯形法,解：首先引入松弛变量，使模型标准化,先求初始基本可行解。观察方程组,10.3 单纯形法,增广系数矩阵,显然，变量x3,x

16、4列系数构成的矩阵是单位矩阵，可作为基。于是把变量x3,x4当作基变量，变量x1,x2当作非基变量。,10.3 单纯形法,令非基变量x1=x2=0，得到一个基本可行解，目标函数值S=30+10=0。,为了找到更优的解，需从非基变量x1,x2中选作为进基变量。,原来的基变量x3,x4中相应的会有一个出基。为了保证换基后，解的可行性，采用“最小比值原则”，即从进基变量x1所对应的系数列(称为主列)中选择 的“1”为主元。,10.3 单纯形法,利用初等行变换，将主列中的主元变成“1”，其余元素变为零，并使目标函数中的系数变成零，得到与原方程组同解的方程组,10.3 单纯形法,令非基变量x2=x4=0

17、，得基本可行解，它所对应目标函数值S=36+10=18，,选非基x2变量入基，将进基主列中的系数“2”选为主元。利用初等行变换，将主列中的主元变成“1”，其余元素变为零,10.3 单纯形法,此时，令非基变量x3=x4=0，得基本可行解,目标函数,中非基变量x3，x4的系数全为负，只能使其为零，才能使S最大，所以基本可行解,为最优解。,10.3 单纯形法,10.3.2 单纯形表,(1)作初始单纯形表,将目标函数S=CX作为一个方程去处理，即,并将其放于AX=b之下，同时认为A已含有一个m阶单位阵，例如是前m列。则可得下表,10.3 单纯形法,初始单纯形表,10.3 单纯形法,(2)化初始表为标准

18、表,标准单纯形表,10.3 单纯形法,(3)最优表判别,通过对标准单纯形表的最后一行 的分析知，非基变量系数全为非负时，目标函数值S最大。显然通过目标函数中非基变量系数的正负就可检验解是否最优，所以称非基变量系数为检验数。,10.3 单纯形法,例12 用“单纯形法”求解下面的线性规划问题,10.3 单纯形法,解：列初始表,选基变量x1,x4,x6。,选x3入基，使x4出基，得标准表。,10.3 单纯形法,选x2入基，使x1出基，得标准表。,10.3 单纯形法,已无负检验数，所以是最优表。得出最优解,10.3 单纯形法,例13 用“单纯形法”求解下列线性规划问题,解：引入松弛变量使模型标准化,1

19、0.3 单纯形法,列初始表,该表已是标准表，但检验数有负值“-1”，因而应使其所对应的x2列进基，但此列无正元素不能进基。故此问题就无最优基本可行解，即无最优解。,10.3 单纯形法,通过以上例子得出，用“单纯形法”求解线性规划问题时，最优解有以下三种情况：,(1)有惟一解，此时最优表检验数均为正数。(2)有无穷多解，此时最优表检验数中有零数。(3)无最优解。此时标准单纯形表的负检验数 所对列的元素无正数。,10.3 单纯形法,10.3.3 改进的单纯形法,利用初等行变换，从第一列起，一列一列地化为单位列。直到化成能够分离出单位列为止。这时约束条件以单位阵做基的系数矩阵，所对应的方程组与原约束

20、条件所对应的方程组同解。将原线性规划问题转化为与之同解的可分离出单位阵的新的线性规划问题。,10.3 单纯形法,例14 用改进的单纯形法求解下列线性规划问题,10.3 单纯形法,解:先将模型标准化，令,10.3 单纯形法,首先选第一列进基，从 中，选第一行中的“2”为主元，做初等行变换，将第一列化为单位列，得,约束条件系数矩阵,10.3 单纯形法,再选第二列进基，选 中的“1”为主元，做初等行变换，将第二列化为单位列，得,10.3 单纯形法,它所对应的方程组为,10.3 单纯形法,将原线性规划问题转化为新的线性规划问题,10.3 单纯形法,首先列初始表,10.3 单纯形法,化为标准表,该表已是

21、最优表，可得最优解,10.3 单纯形法,一般形式的约束方程组化出单位阵的方法：,设约束条件方程组为,10.3 单纯形法,其增广矩阵为,10.3 单纯形法,当系数矩阵A(增广矩阵的前n列)不能直接分离出单位阵时，通过下面的方法化出阶单位阵：,(1)在第一列，求，假设最小为a11，将a11作为主元，做初等行变换，将第一列化为单位列。,10.3 单纯形法,(2)在第二列，求 若ai2恰为a12，则此列不能进基，转第三列来讨论。若ai2为a12除以外的元素，则将第二列化为单位列。,10.3 单纯形法,(3)继续对第三列施行步骤(2)，此时选中的主元不能与前二列中化为1的元素在同一行，若在同行则转第四列

22、讨论。若不同行，化第三列为单位阵。,(4)重复步骤(3)，直到化出阶单位阵。,10.4 应用与实践,10.4.1 应用,1.生产安排问题,例15 设某厂生产A、B两种产品，已知制造1单位A需要煤9吨，电力4KW，劳力3个，盈利7百万；制造1单位B需要煤3吨，电力6KW，劳力9个，盈利6百万。若这个工厂一个月中只有煤360吨，电力200KW，劳力300个，问应如何安排A、B两种产品的生产，才能获得最大盈利。,10.4 应用与实践,解：设该厂一个月生产A、B产品各x1,x2单位，根据题意得数学模型为：,10.4 应用与实践,引入松弛变量x3,x4,x5，使模型标准化得：,10.4 应用与实践,该模

23、型对应的初始单纯形表,它是标准表，但两个检验数均为负。,10.4 应用与实践,利用初等行变换，将上表化为,检验数仍有负值,10.4 应用与实践,检验数都非负，故为最优表。最优解为：,10.4 应用与实践,2.车辆调度问题,例16 某运输公司有许多载量为5吨的汽车，某一天它接受了表中的几项运输任务，并假定装、卸点任意两点间的距离都是已知的。那么怎么安排汽车去完成这些任务才能做到最节约？,10.4 应用与实践,分析：车辆调度的意义；车辆调度问题和物资调运问题；,车辆调度问题主要解决的是：怎样安排车辆去完成运输任务并且使空驶的吨公里数最小。,物资调运问题主要解决的是：怎样才能使物资运输吨公里的数最小

24、。,10.4 应用与实践,把空车看成是货物，其发、收(供、需)点及发、收(供、需)量按如下方法决定：(1)如果某点的卸货总量大于装货总量，则该点是空车的发点，其发量等于卸货总量减装货总量之差；(2)如果某点装货总量大于卸货总量，则该点是空车的收点，其收量也是二者之差；(3)如果某点卸货总量与装货总量相等，则该点是“平点”，空车在运输时可以不考虑。,10.4 应用与实践,求车辆调度的最优方案，也就是求空车运输的最优方案。其主要步骤可分为：,第一，确定空车的收发点和收发量，并查出其距离，列表示之；第二，确定空车调运的数学模型，并求解；第三，求解并结合具体情况合理调派车辆。,10.4 应用与实践,解

25、：第一，根据定空车收、发点及收、发量的原则，定空车收、发点及收、发量，并查距离列表,10.4 应用与实践,第二，根据空车运输表列出数学模型并求解。,设空车调运矩阵表为：,10.4 应用与实践,于是得问题的数学模型为：,10.4 应用与实践,将模型标准化为,10.4 应用与实践,列初始表,10.4 应用与实践,利用行初等变换化为标准表,检验数有负值，所以它不是最优表。,10.4 应用与实践,表中检验数都非负，已是最优表。,10.4 应用与实践,得空车调运的最优方案为：,S=1000吨公里,10.4 应用与实践,10.4.2 用Mathematica求解线性规划问题,内部命令Constrained

26、Max和ConstrainedMin是用来求目标函数在约束条件下并且假设所有变量都大于、等于零时的最大值和最小值。,10.4 应用与实践,例17 求函数 在约束条件下的最大值。,解：,时，函数取得最大值,10.4 应用与实践,解：,10.4 应用与实践,例19 动物的生长对饲料中的三种营养成分:蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质70g，矿物质3g、维生素10mg，某饲养厂能买到5种不同的饲料，每种饲料1kg所含营养成分如表10-25所示，每种饲料1kg的成本如表10-26所示。,10.4 应用与实践,求既能满足动物的生长需要,又使总成本最低的饲料配方。,10.4 应用与

27、实践,解：该问题的线性规划模型为,10.4 应用与实践,可知：该公司可分别购买第四种饲料39.74kg和第五种饲料25.64kg配成的混合饲料，所耗成本24.74元为满足营养条件下的最低成本。,10.5 拓展与提高,第十章 线性规划,本节将介绍运输问题的另一种解法表上作业法。用表上作业法解运输问题需要做以下工作：,(1)给出初始方案；(2)对方案进行检验；(3)调整方案。,主要介绍用最小元素法作初始调运方案；用位势法检验；用闭回路调整法调整方案。,10.5 拓展与提高,例20 现有工业物资一批，由三个仓库调到三个工厂，其收发量及单位运价(每吨物资的运价)如表所示，试求总运价最低的调运方案。,1

28、0.5 拓展与提高,按上面所提的三步，用表上作业法解决这一问题，设调运矩阵为：,10.5 拓展与提高,(1)用最小元素法作初始方案,所谓最小元素法，就是运价(运距)小的先分配。,10.5 拓展与提高,得到初始方案，即调运方案,10.5 拓展与提高,(2)位势法判断方案是否最优,先造一张表，表中移入初始方案，并在收、发点下各增加一行和一列，称为位势行与位势列。,位势的求法：任一填数格所在行与列的位势之和应等于该填数格的运价(运距)数。,10.5 拓展与提高,根据位势表求出检验数表。检验数的求法是：各格的运价(运距)数减去该格所在行与列的位势之和即为检验数。,10.5 拓展与提高,由位势的定义可得，填数格的检验数必等于零。只需对所有非填数格求出检验数，并列入检验数表中。,判别准则：检验数全为非负值，则方案最优。,10.5 拓展与提高,(3)闭回路调整法调整方案,10.5 拓展与提高,经过调整就得一个新的调运方案,10.5 拓展与提高,重用位势法检验，求出位势数和各格的检验数列于表10-36和表10-37。,10.5 拓展与提高,检验数全非负，所以该方案已是最优方案。,初始方案的总费用为3900元，新方案的总费用为3800元，新方案比老方案节省100元。,