实用经济数学教学课件作者盛光进电子教案7线性规划及其应用

1、目 录,第七章 线性规划及其应用,7.1 线性规划问题,一、线性规划问题的数学模型,【例1】 某企业在计划期内要安排、两种产品的生产，已知每生产100kg产品所需设备A及原材料B、C的消耗如下表所示,已知每生产100kg的产品可获利2万元，生产100kg的产品可获利5万元，问怎样安排生产，才能使每天获得的利润最大？,7.1 线性规划问题,一、线性规划问题的数学模型,解 设生产、两种产品的日产量分别为 ,称 为决策变量它们不能任意取值，要受到设备、台时和原材料资源数量的限制。,由于设备A每天可供利用台时不能超过8，而生产 ，,单位产品需要 ，单位产品需要 台时，生产 单位产品需要 台时，故有,同理，因受原材料B、C的限制，可得到以下两个不等式,根据问题的实际意义， 应该取非负数,7.1 线性规划问题,该生产计划问题可用数学模型表示为,该问题需要满足的限制条件 称为问题的约束条件，记作,7.1 线性规划问题,【例2】 某家具厂需要A、B、C三种规格的小钢板分别为15、18和27块，这些小钢板是由两种大小不同的钢板截成。已知第一种钢板每张可截得A规格小钢板2块、B规格小钢板1块和C规格小钢板

2、1块，第二种钢板为1块、2块和3块。问各截这两种钢板多少张可得到所需三种规格小钢板，且使所用钢板张数最少？,同理，对于所需B规格小钢板，有,7.1 线性规划问题,对于所需C规格小钢板，有,该问题可用数学模型表示为,（1）决策变量 表示要寻求的方案，每一组值对应一种具体方案 （2）存在一定的约束条件，表示约束条件的数学式子都是线性等式或不等式。,该实际问题具有的特点：,7.1 线性规划问题,（3）有一个要求达到的目标，且表示问题最优化指标的目标函数是线性函数。 满足以上三个特征的问题称为线性规划问题，其数学模型称为线性规划模型。,其中，（1）称为目标函数，（2）称为约束条件,线性规划模型的一般形式（简记为LP1）为,7.1 线性规划问题,将线性规划问题的非标准型化为标准型的四种情况：,（1）目标函数由最小化变为最大化,（2）化约束不等式为等式约束,若某一模型为， ，则引进新函数,若某个约束条件为线性不等式，则引进非负变量（称为松弛变量），将其化为线性等式。,于是问题转化成求,对于 ，在不等式左边加上松弛变量 ，于是有,对于 ，在不等式左边减去松弛变量 ，于是有,7.1 线性规划问题,二、

3、线性规划问题的标准型,线性规划问题的标准型（简记为LP2）为,标准型具有以下特点：,其中，各约束条件的右端常数项,（1） 目标函数是求最大值；,（2） 约束条件为线性方程组；,（3）决策变量均有非负限制。,7.1 线性规划问题,【例3】 将下面的线性规划问题化为标准型,7.1 线性规划问题,（）将无约束的变量 化为有非负要求的变量,若某一变量 无非负限制，则称这种变量 为自由变量此时引进两个非负变量 ，并令 ，代入约束条件和目标函数中，使全部变量皆有非负限制。,7.1 线性规划问题,【例4】 将下面的线性规划问题化为标准型,（2）在第一个约束条件“=”号的两端同乘以-1；,7.1 线性规划问题,（4）因为 无非负约束，引进变量 ， ，令 ，用 替换 。于是所给线性规划问题的标准型为：,（3）在第二个约束条件“”号的左端加入松弛变量 ，在第三个约束条件“”号的左端减去松弛变量 ;,7.1 线性规划问题,三、线性规划问题解的概念,一般地，线性规划问题的数学模型的标准型（LP2）可写成：,用矩阵表示为：,其中,7.1 线性规划问题,称A为约束条件的系数矩阵一般情况下 , 是指 的各分量,【定

4、义2】 使目标函数（3）达到最大值的可行解称为最优解。,【定义3】 设（LP2）没有多余的约束，则系数矩阵A中任意一个 阶可逆子矩阵B（ ）称为线性规划问题的一个基（矩阵）。不妨设为,7.1 线性规划问题,与B中的每一个列向量对应的变量 称为基变量，除基变量以外的变量称为非基变量,【定义4】 对应于基 ，如果令所有的非基变量等于0，则由约束方程组（4）可解出 个基变量的惟一解 ，称这个解为基解，如果该基解还满足 ，则该基解称为对应于基B的基可行解。,7.1 线性规划问题,【例5】 已知线性规划问题,则约束方程组的系数矩阵为,取 ，则 , 是该线性规划问题的一个基，对应的基变量为 ，非基变量为 .令 ，求解方程组得 ，所以,7.1 线性规划问题,是对应的一个基解，且是基可行解,是对应的一个基解因为 ，故 不是基可行解,同理，可求得本问题的另一个基可行解为,7.2 线性规划问题解的性质,一、图解法 【例1】 求解7.1节例1中的线性规划问题：,解 (1) 建立平面直角坐标系 ，画出可行域.,因为 ，所以满足约束条件的点都落在第一象限及坐标轴的正半轴上.,在坐标系中画出直线 满足约束条件 的

5、所有点落在直线 上及原点所在一侧的半平面内.,7.2 线性规划问题解的性质,上述三个平面点集在第一象限的交集即为可行域（包含边界），如图可行域内任意一点的坐标都是该线性规划问题的可行解。,满足约束条件 的所有点位于直线 上及以该直线为分割线的原点所在一侧的半平面内.,7.2 线性规划问题解的性质,图解法的基本步骤如下： （1）根据约束条件画出可行域； （2）根据目标函数 Z的表达式画出目标函数等值线 Z=0，并标明目标函数值增加的方向； （3）在可行域中，寻求符合要求的等值线与可行域边界相切的点或点集，并求出最优解和最优值。,(2) 绘制目标函数等值线. 试探性给定 Z 值，如 、 ，画出相应的等值线，如图不难发现，等值线离原点越远，Z 的值越大.,(3) 确定最优解.,7.2 线性规划问题解的性质,画出等值线 ,即 ，容易看出，等值线与直线BC平行，且等值线离原点越远，目标函数值越大。当等值线向右上方移动时，它与可行域边界相切时不是一个点，而是在整个线段BC上相切，这时在B点、C点及BC线段上的任意点都使目标函数值达到最大，即该线性规划问题有无穷多最优解，若取最优点B，则最优解为 最

6、优值为16。,解 此题的约束条件同例1，因此，其可行域完全相同。,【例2】 求解线性规划问题,7.2 线性规划问题解的性质,【例3】 求解线性规划问题,作等值线 ，即 ，容易看出，等值线离原点越远，目标函数值越大。但由于问题可行域无界，等值线可以无限制地向右上方移动，即目标函数值可以增大至无穷大。该情况下称问题具有无界解或无最优解,解 首先在平面直角坐标系 中画出可行域，它是无界区域，如图所示,7.2 线性规划问题解的性质,【例4】 求解线性规划问题,解 在平面直角坐标系 中，画出半面 ，它在第一象限的部分表示为区域1；画出半平面 ，它在第一象限的部分表示为区域2。容易看出区域1与区域2没有公共部分，即该问题的可行域为空集，所以此问题没有可行解，当然也就没有最优解。,7.2 线性规划问题解的性质,二、线性规划问题解的性质,若线性规划问题的可行域不是空集，则可行域没有凹入部分，没有空洞，即任意两点连线上的点仍在可行域中，这样的点集称为凸集。,含两个变量的线性规划问题的解有下面四种情况：,（1）有可行解且有惟一最优解，如例1；,（2）有可行解且有无穷多最优解，如例2；,（3）有可行解但无最

7、优解，如例3；,（4）无可行解，如例4。,7.2 线性规划问题解的性质,性质4 若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解）一定可以在基可行解(顶点)中找到,线性规划问题解的性质如下：,性质1 求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解,性质2 若线性规划问题的可行域存在，则可行域是一个凸集,性质3 线性规划问题的基可行解 对应于可行域的顶点,7.3 单纯形法,介绍初始基可行解的求法，最优性判定以及如何找到下一个基可行解。,【例1】用单纯形法求解7.1节例1对应的线性规划问题。,解 该问题的标准型为,一、典型线性规划的单纯形法,如果线性规划的标准型的系数矩阵中，含有一个单位子矩阵且约束条件右端常数均非负，则称此线性规划是典型线性规划。,则约束方程组（2）的系数矩阵,判断该基可行解是否为最优解？通过方程组（2）将基变量用非基变量表达为,注1 由于中含有一个单位子矩阵 ，且右端常数非负，故可取该单位子矩阵作为初始基，得到一个初始基可行解。,7.3 单纯形法,代入目标函数（1），得,从目标函数（4）可以看出，非基变量 的系数都是正数，

8、因此， 的值增大（目前取值为0）都可以使目标函数值增大。又因为目标函数中基变量的系数为零，虽然非基变量 增大会影响到基变量 的取值，但在满足约束条件时， 的改变不会造成目标函数值改变，所以，目标函数中该非基变量 的系数的符号就成了判断当前基可行解是否是最优解的准则。,注2 称消去基变量后的目标函数中非基变量 的系数为 的检验数，记为 ，若对于每一个非基变量 均有 ，则当前基可行解即为最优解，否则不是最优解。,7.3 单纯形法,初始基可行解 对应的检验数 ，均大于0，所以当前基可行解不是最优解，又 的增大都能使目标函数得到改善，这时有不止一个非基变量可以增大而改善目标。单纯形法中每次只能选一个变量增大，一般可选择检验数最大的那个非基变量，如本例中 ，故选 。记 为 增大后的取值，则必须合理确定 的最大可能取值，使所产生的下一个解还是基可行解。根据基可行解的定义，如果 变为基变量，则 中必定有一个要变为非基变量，且需保证所有变量都是非负。所以，由条件,并结合式（3）可得,7.3 单纯形法,从式（5）中可以看出，应取,即 增大到3时， ，这就决定了用 去替换 ，得到下一个基可行解,注3 上述的 增大到3， 减少到0的过程，即从一个基可行解到另一个基可行解的过程称为换基过程。而在此过程中 称为进基变量， 称为出基变量。,7.3 单纯形法,对于新的基可行解 ，可以采用相同的原理进行最优性检验和换基，直到找到最优解。通过式（3）将基变量用非基变量表达为,代入目标函数（4），有,得 的检验数 。因 ，说明目标函数还有改善的空间，于是再用上述方法，确定 为进基变量，由（6）有,=2,7.3 单纯形法,为出基变量，新的基可行解为,通过式（6）将基变量用非基变量表达为,代入目标函数（7）得,由于 ，所有检验数均为非负，因此当前基可行解为最优解。即生产A产品200kg，B产品300kg，才能得到最大利润，最大利润为19万元。,7.3 单纯形法,通过例1不难发现，建立在单纯形原理基础上的线性规划问题求解实质上是不断地运用消元法的过程。为简化叙述和计算，借助矩阵的初等行变换，可将上述单纯形法的计算过程重新整理如下。,根据式（2）、（4），得初始单纯形矩阵,

《实用经济数学教学课件作者盛光进电子教案7线性规划及其应用》由会员E****分享，可在线阅读，更多相关《实用经济数学教学课件作者盛光进电子教案7线性规划及其应用》请在金锄头文库上搜索。