第9章线性规划方法及其应用讲解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第9章 线性规划方法及其应用,8/8/2024,1,第9章 线性规划方法及其应用8/1/20231,线性规划,（Linear Programming）,作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：,一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；,二是如何在现有资源条件下进行组织和安排，以产生最大收益。,因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。,8/8/2024,2,线性规划（Linear Programming）作为运筹学的,1、,康托洛维奇,生产组织与计划中的数学方法,一本小册子，1939;,2、康托洛维奇“最佳资源利用的经济计算”1942完成、1959发表的著作；,3、自1947年,丹兹格,（G.B.Dantzing）提出求解线性规划问题的一般方法-单纯形法之后，线性规划在理论上趋于成熟，应用日益广泛与深入；随着电子计算机的发展和计算速度的不断提高，其适用的领域更加广泛，它已成为必不可少的重要手段之一。,8/8/2024,3,1、康托洛维奇生产组织与计划中的数学方法,一,4、,1975年库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获诺贝尔经济学奖；,5、冯诺伊曼和摩根斯坦1944年发表的,对策论与经济行为,涉及与线性规划等价的对策问题及线性规划对偶理论。,8/8/2024,4,4、1975年库伯曼斯(Koopmans)因,线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。,最优化/,运筹学,的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。,解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划的基础是线性变换。,8/8/2024,5,线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分,数,学,规,划,非线性规划,整数规划,动态规划,学,科,内,容,多目标规划,双层规划,组,合,优,化,最优计数问题,网络优化,排序问题,统筹图,随,机,优,化,对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,8/8/2024,6,数非线性规划整数规划动态规划学多目标规划双层规划组最优计数问,9.1 线性规划是什么,9.2 建立线性规划模型的一般步骤,9.3 线性规划问题的图解法,9.4 线性规划问题解的性质,9.5 解线性规划问题的单纯形法,9.6 线性规划的应用,8/8/2024,7,9.1 线性规划是什么8/1/20237,9.1 线性规划是什么,8/8/2024,8,9.1 线性规划是什么8/1/20238,9.1 线性规划是什么,我们先通过几个实际问题来认识什么是线性规划.,【例9.1】,某企业生产 三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表9.1所示.,表9.1 企业生产数据表,1.利润最大化问题,8/8/2024,9,9.1 线性规划是什么我们先通过几个实际问题来认识什么是线,9.1 线性规划是什么,试问：该企业怎样安排生产才会使每天的利润最大？,解,设该企业每天生产产品 的数量分别为 （单位：吨），则总利润的表达式为,我们希望在现有资源条件下总利润最大.现有资源的限制为,（原料甲的限制）,（原料乙的限制,）,此外，由于未知数（我们称之为,决策变量,）是计划产量，,应有为非负的限制，即,8/8/2024,10,9.1 线性规划是什么试问：该企业怎样安排生产才会使每天的,9.1 线性规划是什么,由此得到问题的数学模型为,其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍,），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日,生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.,其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍,），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日,生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.,其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍,），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日,生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.,其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍,），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日,生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.,其中 为英文“subject to”的缩写，表示决策变量 受它后面的条件约束.最优解为 （具体解法后面介绍,），代入总利润的表达式 得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日,生产的最优安排是：产品 不生产，生产25吨，生产25吨，可实现最大利润250千元/日.,8/8/2024,11,9.1 线性规划是什么由此得到问题的数学模型为其中,9.1 线性规划是什么,类似于例9.1的这类问题称为最优生产计划问题.其一般描述是利用 种资源 组织生产 种产品 .以 表示资源 的限制，表示产品 的单位利润，表示单位产品,消耗资源 的数量（代表该企业当前的技术水平），情况如表9.2所示.现在的问题是：如果该企业生产的这 种产品 都可以卖出，如何合理充分地利用现有的资源，给出一个使总利润达到最大的产品生产计划？,8/8/2024,12,9.1 线性规划是什么类似于例9.1的这类问题称为最优生产,有了解决上述问题的经验，我们可以假设产品 的计划产量分别为 单位，则问题的数学模型为,9.1 线性规划是什么,8/8/2024,13,有了解决上述问题的经验，我们可以假设产品 的,模型中 的都是实际问题给定的常数；未知量 为决策变量.这类决策问题的应用领域非常广泛.,注,本章的数学模型均可用软件求解。,2.成本最小化问题,【,例9.2,】,某钢铁厂熔炼一种新型不锈钢，需要4种合金 为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表9.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料 各多少吨，能够使成本最小？,9.1 线性规划是什么,8/8/2024,14,模型中,9.1 线性规划是什么,下料问题的一般描述：已知有一批原材料，每根长度为,L,，由于生产的需要，要求截出规格分别为 的零件 根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例9.4的建模过程列出此一般问题的数学模型.,总之，类似例9.1、9.2的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的,共同点，即每一个问题都用一组决策变量 来表示某一方案，追求的目标可以用关于决策变量 的线性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量 的线性等式或不等式表示.,8/8/2024,15,9.1 线性规划是什么下料问题的一般描述：已知有一批原材料,9.1 线性规划是什么,这类问题所构成的数学模型,称为,线性规划,模型,.,有时也直接将线性规划模型称为线性规划问题.,针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案。,8/8/2024,16,9.1 线性规划是什么这类问题所构成的数学模型,称为线性规,9.2 建立线性规划模型的,一般步骤,8/8/2024,17,9.2 建立线性规划模型的8/1/202317,9.2 建立线性规划模型的一般步骤,从9.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：,第1步,理解要解决的问题.搞清在什么条件下追求什么目标.,第2步,定义,决策变量,.每一个问题都用一组决策变量,来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值,是非负的,.,第3步,确定,约束条件,.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.,第4步,列出,目标函数,.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.,8/8/2024,18,9.2 建立线性规划模型的一般步骤从9.1节中对实际问题,9.2 建立线性规划模型的一般步骤,对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.,线性规划的一般形式可表示为：,8/8/2024,19,9.2 建立线性规划模型的一般步骤对于一些比较复杂的线性规,9.2 建立线性规划模型的一般步骤,其中称 为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的 为常数.,当要求决策变量 均为整数时，称（9.1）为,纯整数线性规划问题,；,当要求决策变量 均取0或1时，称（9.1）为,整数线性规划问题,.,当要求决策变量 既取实数又取整数时，称（9.1）为混合整数线性规划问题.,我们把满足所有约束条件的解称为线性规划问题（9.1）的,可行解,.全体可行解的集合称为问题（9.1）的,可行域,记为,.使目标函数值最大（或最小）的可行解称为该线性,8/8/2024,20,9.2 建立线性规划模型的一般步骤其中称,9.2 建立线性规划模型的一般步骤,规划问题的,最优解,，与此最优解相应的目标函数值称为,最优目标函数值,，,简称,最优值,.,因此，若记 ，求解线性规划问题（9.1），本质上就是寻找一点,，使得,均满足不等式,【,例9.3,】,某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备（台时），A、B两种原材料的消耗以及资源的限制情况如表2.11所示.问：该工厂应分别生产多少甲产品和乙产品才能使工厂获利最大？,8/8/2024,21,9.2 建立线性规划模型的一般步骤 规划问题的最优解，与,9.2 建立线性规划模型的一般步骤,解,首先，确定决策变量.工厂目前要决策的是甲产品和乙产品的生产量，可以分别用变量 来表示.由于它们表示产品产量，所以只取非负数.,其次，根据问题的限制条件，列出表示约束条件的线性不等式：,8/8/2024,22,9.2 建立线性规划模型的一般步骤解 首先，确定决策变量,9.2 建立线性规划模型的一般步骤,，（非负限制）,，（台时数限制）,，（原材料 限制）,，（原材料 限制）,最后，根据实际问题所追求的目标，列出其线性函数表达式.由于问题的目标是工厂获利最大，假如产品都能销售，则总利润可表示为 ，最大利润记为,8/8/2024,23,9.2 建立线性规划模型的一般步骤，（非负限制），（台时,9.2 建立线性规划模型的一般步骤,综上所述，就得到了描述该问题的线性规划模型：,8/8/2024,24,9.2 建立线性规划模型的一般步骤综上所述，就得到了描述该,计算最优解为：,即在现有资源条件下，该企业在计划期内生产的最优计划是：,产品甲生产100单位，,产品乙生产200单位，,可实现最大利润130000元.,9.2 建立线性规划模型的一般步骤,8/8/2024,25,计算最优解为：9.2 建立线性规划模型的一般步骤8/1/2,9.2 建立线性规划模型的一般步骤,【例9.4】,某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？,8/8/2024,26,9.2 建立线性规划模型的一般步骤 【例9.4】某医院,9.2 建立线性规划模型的一般步骤,解 设 为时段 开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：,8/8/2024,27,9.2 建立线性规划模型的一般步骤解 设 为时段 开,9.2 建立线性规划模型的一般步骤,计算最优解为：故该医院需雇用150名护士，最佳安排见表9.10所示.,8/8/2024,28,9.2 建立线性规划模型的一般步骤计算最优解为：,9.2 建立线性规划模型的一般步骤,线性规划的一般形式，可行解、最优解等概念,线性规划问题建模过程：,第1步,理解要解决的问题。,第2步,定义决策变量。,第3步,确定约束条件。,第4步,列出目标函数。,8/8/2024,29,9.2 建立线性规划模型的一般步骤线性规划的一般形式，可行,9.3 线性规划问题的图解法,8/8/2024,30,9.3 线性规划问题的图解法8/1/202330,9.3 线性规划问题的图解法,1.图解法,对一个线性规划问题建立数学模型之后，就面临着如何求解的问题.这里先介绍含有两个决策变量 的线性规划问题的图解法.它简单直观，有助于了解线性规划问题求解的基本原理.,8/8/2024,31,9.3 线性规划问题的图解法1.图解法8/1/2023,图解法的步骤可概括为：,（1）在平面上建立直角坐标系 ；,（2）图示约束条件，找出可行域（由于 ，可行域必位于第一象限）；,（3）图示目标函数，即画出目标函数等值线；,（4）对 （或 ）问题朝着增大（或减少）纵截距的方向平行移动目标函数等值线，至与可行域的边界相切时为止.切点（即某个边界点）就是代表最优解的点；,（5）寻找该点的坐标得到最优解.,以下结合实例来具体说明.,8/8/2024,32,图解法的步骤可概括为：8/1/202332,9.3 线性规划问题的图解法,【例9.5】,用图解法求解线性规划问题,8/8/2024,33,9.3 线性规划问题的图解法 8/1/202333,9.3 线性规划问题的图解法,解 先画出线性规划的可行域如图9.1阴影部分.,再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点 .,最后求解线性方程组,求解得到点 的坐标，从而得到最优解 ，最大值,8/8/2024,34,9.3 线性规划问题的图解法解 先画出线性规划的可行域如,9.3 线性规划问题的图解法,8/8/2024,35,9.3 线性规划问题的图解法8/1/202335,9.3 线性规划问题的图解法,【例9.6】,用图解法求解线性规划问题,解 先画出线性规划的可行域，如图9.2阴影部分.,8/8/2024,36,9.3 线性规划问题的图解法【例9.6】用图解法求解线性规,9.3 线性规划问题的图解法,8/8/2024,37,9.3 线性规划问题的图解法8/1/202337,9.3 线性规划问题的图解法,再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点B.最后求解线性方程组,得到解出点B的坐标 ，从而得到最优解 ，最大值,例9.5与例9.6中求解得到的问题的最优解是惟一的，但对一般线性规划问题，求解结果还可能出现其他情况.,8/8/2024,38,9.3 线性规划问题的图解法再画出目标函数等值线，朝着增大,9.3 线性规划问题的图解法,2.线性规划解的其他情况,（1）多重最优解的情况,【例9.9】,若将例9.5中的目标函数变为,，则代表目标函数的直线平移到最优位置后将和直线 重合.此时，不仅顶点A，B都代表了最优解，而且线段上AB的所有点都代表了最优解.这个线性规划问题有无穷多最优解，这些最优解都对应着相同的最大值,8/8/2024,39,9.3 线性规划问题的图解法2.线性规划解的其他情况8/,MAX,8/8/2024,40,MAX8/1/202340,9.3 线性规划问题的图解法,（2）无界解的情况,（3）无可行解的情况,8/8/2024,41,9.3 线性规划问题的图解法（2）无界解的情况（3）无可行,9.3 线性规划问题的图解法,（2）无界解的情况,【例9.10】,对下述线性规划问题,用图解法求解结果如图2.3(a)所示.从图中可以看出，由于可行域是无界区域，当目标函数等值线沿箭头方向平行移动时，始终与该无界区域相交.此时，目标函数值无上界，因此无最优解，也称,最优解无界,.,8/8/2024,42,9.3 线性规划问题的图解法（2）无界解的情况8/1/20,9.3 线性规划问题的图解法,（3）无可行解的情况,【例9.11】,对线性规划问题,由图2.3(b)可以看出，同时满足所有约束条件的点不存在，即可行域为空集，也就是没有可行解，故不存在最优解.,8/8/2024,43,9.3 线性规划问题的图解法（3）无可行解的情况由图2.3,9.3 线性规划问题的图解法,当根据实际问题建立的线性规划模型的求解结果出现（2）,（3）两种情况时，一般说明建模有错误.前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意.下面再给出一个求目标函数最小化的线性规划问题.,【例9.12】,求解线性规划,8/8/2024,44,9.3 线性规划问题的图解法当根据实际问题建立的线性规划模,9.3 线性规划问题的图解法,解 画出此线性规划问题的可行域，如图中的阴影部分.目标函数 ，它在坐标平面上可表示为以f为参数，以-2/4为斜率的一组等值线.当等值线移动到B点时，目标函数在可行域中取最小值.B点的坐标可以从线性方程组,中求出，为 .这就是所求线性规划问题的最优解，且 .,8/8/2024,45,9.3 线性规划问题的图解法解 画出此线性规划问题的可行,9.3 线性规划问题的图解法,8/8/2024,46,9.3 线性规划问题的图解法8/1/202346,9.3 线性规划问题的图解法,1.通过图解法了解线性规划有几种解的形式,2.作图的关键有三点,(1)可行解区域要画正确,(2)目标函数增加的方向不能画错,(3)目标函数的直线怎样平行移动,8/8/2024,47,9.3 线性规划问题的图解法1.通过图解法了解线性规划有几,9.4 线性规划问题解的性质,8/8/2024,48,9.4 线性规划问题解的性质8/1/202348,1.线性规划问题的标准形,前面曾给出了线性规划问题的一般形式，可以看出，其中有的要求目标函数最大化，有的要求目标函数最小化；约束条件可以是“,”或“”形式的不等式，也可以是等式；决策变量一般是非负约束，但也允许在 范围内取值，即无约束。为了进一步研究和讨论，就需要把线性规划问题的一般形式化为统一的标准形式。,9.4 线性规划问题解的性质,8/8/2024,49,1.线性规划问题的标准形前面曾给出了线性规划问题的一般形,线性规划的一般形式可表示为：,8/8/2024,50,线性规划的一般形式可表示为：8/1/202350,这里的标准形式有以下规定：,（1）目标函数是求最大值；,（2）所有约束条件均用等式表示；,（3）所有决策变量均取非负数；,（4）所有约束常数均为非负数.,9.4 线性规划问题解的性质,8/8/2024,51,这里的标准形式有以下规定：9.4 线性规划问题解的性质8,于是，具有个约束条件和个决策变量的线性规划问题的,标准形,为：,9.4 线性规划问题解的性质,8/8/2024,52,于是，具有个约束条件和个决策变量的线性,在约束条件,0,（,j=1,，,2,，,，,n,）,下，求一组未知变量（,j,=,1，2，,，,n,）的值，使得,。常记为如下更为紧凑的形式,或,其缩写形式为：,8/8/2024,53,在约束条件,其中 b和C为已知非负常数，A为已知常数矩阵，且rank(A)=m。一般可以通过以下方法，把,非标准形线性规划问题化为标准形：,（1）目标函数的标准化,如果线性规划问题是求目标函数的最小值，即,则令 ，得 ，这就同标准形的目标函数的形式一致了.但要注意，如果要求原问题的最优值，应取最优值的相反数.,9.4 线性规划问题解的性质,8/8/2024,54,其中 b和C为已知非负常数，A为已知常数矩阵，,（,2）约束条件的标准化,当约束条件为,形式的不等式时，可在不等式左边加上一个非负的新变量（称为,松弛变量,(slack variables),），把不等号变为等号；,当约束条件为,形式的不等式时，可在不等式左边减去一个非负的新变量（称为,剩余变量,），把不等号变为等号.,9.4 线性规划问题解的性质,8/8/2024,55,（2）约束条件的标准化 9.4 线性规划问题解的性质8/1,（3）决策变量的标准化,如果某一决策变量是一个符号不受限制的“自由变量”，可以引入两个非负的新变量 和 ，并作变换 ，将决策变量标准化。,9.4 线性规划问题解的性质,8/8/2024,56,（3）决策变量的标准化 9.4 线性规划问题解的性质8/1,（4）约束常数的标准化,如果有某约束常数为负数，可在等式（或不等式）两边同时乘以，把约束常数变为正数.,9.4 线性规划问题解的性质,8/8/2024,57,（4）约束常数的标准化 9.4 线性规划问题解的性质8/1,【例9.13】,把下面的线性规划问题化为标准形：,【解】此例只有约束条件不符合标准形，为此引入非负的松弛变量 ，并分别把它们加到第1个和第2个不等式的左边，即得标准形：,注意，所加松弛变量 表示没有被利用的资源，当然也没有利润，所以在目标函数 中的系数应为零.,9.4 线性规划问题解的性质,8/8/2024,58,【例9.13】把下面的线性规划问题化为标准形：9.4 线,9.4 线性规划问题解的性质,【例9.14】,将下面线性规划问题化为标准形,【解】令 ，把求 改为求 ；用 替换 ，其中 ；在第1个约束不等式的左边加入松弛变量 ，在第2个约束不等式的左边减去剩余变量 ，这样即可得到该问题的标准形为,8/8/2024,59,9.4 线性规划问题解的性质【例9.14】将下面线性规划问,，,9.4 线性规划问题解的性质,标准形,原问题,8/8/2024,60,，9.4 线性规划问题解的性质标准形原问题8/1/202,2.线性规划的解,可行解与最优解,满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。,使目标函数最大或最小化的可行解称为最优解。,8/8/2024,61,2.线性规划的解 8/1/202361,基本解与基本可行解,在线性规划问题中，将,约束方程组的,m,n,阶矩阵,A,写成由,n,个列向量组成的分块矩阵,8/8/2024,62,基本解与基本可行解 8/1/202362,如果,B,是,A,中的一个m阶的非奇异子阵，则称,B,为该线性规划问题的一个基。不失一般性，不妨设,则称 为基向量，与基向量相对应的向量,为基变量，而其余的变量为,非基变量。,8/8/2024,63,如果B是A中的一个m阶的非奇异子阵，则称B为,如果 是方程组 的解,则 就是方程,组 的一个解，它称之为对应于基,B,的,基本解,，简称基解。,满足非负约束条件的基本解，称为,基本可行解,。对应于基本可行解的基，称为可行基。,8/8/2024,64,如果,线性规划问题的以上几个解的关系，可用下图来描述：,8/8/2024,65,线性规划问题的以上几个解的关系，可用下图来描述：8/1/20,【,定义9.1,】,如果集合K中任意两点s,t之间连线上所有的点都是集合K中的点，即对于任意的 ，都有 ，则称K为凸集.,例如图9.5中（a）,（b）,（c）为凸集，而（d）,（e）不是凸集.,3.线性规划问题解的基本性质,(a)(b)(c)(d)(e),图9.5 凸集与非凸集示例,9.4 线性规划问题解的性质,8/8/2024,66,【定义9.1】如果集合K中任意两点s,t之间连线上所有的,【,定理9.1,】,线性规划问题的可行域,是一个凸集.,这两个定理我们不给予数学证明.结合图解法，我们可以清晰地了解到线性规划问题解的有关性质.定理9.1说明：联结线性规划问题任意两个可行解的线段上的点（坐标）仍是可行解.定理9.2则告诉我们：如果一个线性规划问题有最优解，则一定可以从可行域的有限个顶点中找到.,【,定理9.2,】,若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到.,9.4 线性规划问题解的性质,8/8/2024,67,【定理9.1】线性规划问题的可行域是一个凸集.这两个定理,【,定义9.2,】,如果凸集,K,中的点,x,不能成为任何线段的内点，即对任意 ，都不存在 ，使得 ，则称,x,为,K,的一个顶点.,例如三角形、正方形、凸多边形、凸无界区域的顶点及圆周上的点，都是相应凸集的顶点.,从图解法的例子中知道线性规划问题的可行域是一个凸集，且如果问题有最优值，都是在顶点上达到.,这些性质推广到一般，就是下面几个重要定理.,9.4 线性规划问题解的性质,8/8/2024,68,【定义9.2】如果凸集K中的点x不能成为任何线段的内点，,9.4 线性规划问题解的性质,1.将非标准形化为标准形的方法,2.线性规划问题的解,3.线性规划问题解的性质,（1）线性规划问题的可行域,是一个凸集。,（2）若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到。,8/8/2024,69,9.4 线性规划问题解的性质 1.将非标准形化为标准形的方,9.5 解线性规划问题的单纯形法,8/8/2024,70,9.5 解线性规划问题的单纯形法 8/1/202370,单纯形法是求解线性规划的一种通用方法，1947年由美国数学家丹兹格（G.B.Dantzig）给出.下面结合9.1中的利润最大化问题介绍单纯形法的基本内容.由9.1中的例9.1提供的,数学模型,为:,9.5 解线性规划问题的单纯形法,8/8/2024,71,单纯形法是求解线性规划的一种通用方法，1947,（1）先化为标准形.引入松弛变量 得到,标准形,9.5 解线性规划问题的单纯形法,8/8/2024,72,（1）先化为标准形.引入松弛变量,（2）再把目标函数,改写成,并把它加入到约束方程组中去，即得到方程组,9.5 解线性规划问题的单纯形法,8/8/2024,73,（2）再把目标函数改写成并把它加入到约束方程组中去，即得到方,将此方程组的系数及常数项b,列成一个数表，即,.,9.5 解线性规划问题的单纯形法,称此表为,初始单纯形表,.表中的数字被分成了4部分，位于左下角的每个数字称为检验数.此时与,对应的检验,数都是负数，因此，若不令,，只要有一个,是正数，则它与负数相乘后仍是负数，移项到右边，,函数,值,就会增大，为此转到下一步.,8/8/2024,74,将此方程组的系数及常数项b列成一个数表，即.9.5 解线性,（3）在负检验数中选绝对值最大的负数（即,7,），在对应的列中，将该列中的正数分别去除对应的常数项，选择比值最小者所对应的元素为主元（称为最小比值原则）.在这里,然后用矩阵的初等行变换，将主元化为1，把同列的其他元素化为0.这一过程如下：,将矩阵,可知位于第2行、第3列的元素3为主元，标为 ,9.5 解线性规划问题的单纯形法,8/8/2024,75,（3）在负检验数中选绝对值最大的负数（即7），在对应的列中,的第2行乘以1/3，得,再将矩阵的第2行乘以（,2,）加到第1行，第2行乘以7加到第3行，得,此时的目标函数值已经由原来的0增加到700/3,.,由于检验数中仍有负数，按照最小比值原则，可知位于第1行、第2列的元素4/3为主元,.同样,用矩阵的初等行变换，将主元化为1，把同列的其他元素化为0，,9.5 解线性规划问题的单纯形法,8/8/2024,76,的第2行乘以1/3，得 再将矩阵的第2行乘以（2）加到,过程如下：,将矩阵A,的第1行乘以3/4，得,这时表中已经没有负检验数，表明目标函数已经达到最大值.最后这张表称为,最优单纯形表,.易知最优解为,最优值为,250,.从而原线性规划问题的最优解为,对应的目标函数最优值为,250,.,9.5 解线性规划问题的单纯形法,再将矩阵的第2行乘以（,2,）加到第1行，第2行乘以7加到,第3行，得,8/8/2024,77,过程如下：将矩阵A的第1行乘以3/4，得 这时表中已经没有,上述求解线性规划问题的方法称为,单纯形法,.,单纯形法步骤如下,：,第,1,步，将线性规划化成标准形；,第,2,步，写出初始单纯形表；,第,3,步，对检验数进行检验.若检验数均为非负数，则得到最优单纯形表.若有负数，则在检验数绝对值最大的负数所对应的列中，按最小比值原则选主元，用初等行变换化主元为1，主元所在列其余元素化为0，得到一张新单纯形表.再检验该表是否为最优单纯形表，若不是，重复上述过程，直到得出最优单纯形表.,第,4,步，从最优单纯形表直接写出最优解和最优值.,9.5 解线性规划问题的单纯形法,8/8/2024,78,上述求解线性规划问题的方法称为单纯形法.9.5 解,从上例求解过程看到，单纯形表中,所对应的列始终不变，故在实际计算中可省去不写.上例的求解过程本质上是矩阵的初等行变换过程，我们可以把此例的单纯形法求解过程简化为,9.5 解线性规划问题的单纯形法,8/8/2024,79,从上例求解过程看到，单纯形表中 所对应的列始终不变，故在实,9.5 解线性规划问题的单纯形法,所以最优解及最优值分别为,【,注1,】,若在计算过程中，单纯形表出现某检验数为负，但其所在的列无正元素的情况，则可以证明该问题无最优解.,8/8/2024,80,9.5 解线性规划问题的单纯形法所以最优解及最优值分别为【,【解】引入松弛变量，化为标准形,9.5 解线性规划问题的单纯形法,【例9.15】,解线性规划问题,8/8/2024,81,【解】引入松弛变量，化为标准形9.5 解线性规划问题的单,初始单纯形表为,由于检验数,1,所在列无正数元素，故此问题无最优解.,9.5 解线性规划问题的单纯形法,8/8/2024,82,初始单纯形表为由于检验数1所在列无正数元素，故此问题无最优,【,注2,】在上例的初始单纯形表中，由虚线隔开的左上部分，,所在列的元素构成一个二阶单位矩阵,我们称,为基变量.,一般地，对含有,n,个变量、,m,个约束的线性规划问题，当把它化为标准形后，若恰有一个,m,阶单位矩阵，就可以用前面的单纯形法求出最优解（若最优解存在）；若基变量不足,m,个，则用改进单纯形法或对偶单纯形法求解.由于这两种方法用到较多的数学知识，这里不再介绍，但WinQSB软件中的线性规划程序已经包含了改进单纯形法和对偶单纯形法,.,9.5 解线性规划问题的单纯形法,8/8/2024,83,【注2】在上例的初始单纯形表中，由虚线隔开的左上部分，所在列,9.5 解线性规划问题的单纯形法,1.判断基本可行解.有3种情形：已是最优解，是无界解，不能确定.前2种情形计算结束，第3种情形需要继续迭代，先进基后出基，初等变换求下一个基本可行解，直到出现最优解或无界解为止。,2.判定方法,唯一最优解的判定,：所有非基变量的检验数非零,则线 规划具有唯一最优解。,多重最优解的判断,:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。,无界解的判断:,某个检验数大于0且该检验数所在列中所有元素小或等于，则线性规划具有无界解。,8/8/2024,84,9.5 解线性规划问题的单纯形法1.判断基本可行解.有3种,9.6 线性规划的应用,8/8/2024,85,9.6 线性规划的应用8/1/202385,9.6 线性规划的应用,线性规划在国内外很多部门的规划、管理、决策过程中有大量成功的应用，并收到了良好的效果.但是，应用线性规划来解决某一类实际问题时，由于问题的复杂性和情况的多变性，要真正建立一个反映实际问题的、能得出正确结论的理想模型，并不是一件容易的事情.它要求建模者具有丰富的经验、较强的创造力和比较熟练的技巧.本节通过一些被简化了的问题，介绍建立线性规划模型的基本思路和基本技巧.,8/8/2024,86,9.6 线性规划的应用 线性规划在国内外很多部门,1.办学规模问题,【例9.16】某人准备投资1200万元办一所中学，为了考虑社会效益和经济效益，对该地区教育市场进行调查，得出一组数据，如表,9.12,所示.,表9.12 市场调查表,9.6 线性规划的应用,班级,班级学生数,配备教师数,硬件建设费（万元）,教师年薪（万元）,初中,50,2.0,28,1.2,高中,40,2.5,58,1.6,根据物价部门的有关文件，初中是义务教育阶段，收费标准适当控制，预计除书费、办公费外，初中每个学生每年可收取600元，而高中每个学生每年可收取1500元.因生源和环境等条件限制，办学规模以2030个（含20与30）班为宜.教师实行聘任制.初、高中的教育周期均为3年.请你合理地安排招生计划，使年利润最大.问：大约经过多少年可以收回全部投资？,8/8/2024,87,1.办学规模问题9.6 线性规划的应用班级班级学生数配备教,解 设初中编制班数为,x,高中编制班数为,y,又设年利润为 f,（单位：万元），那么,即,.于是此问题的线性规划模型为,解得最优解,代入,中得,9.6 线性规划的应用,8/8/2024,88,解 设初中编制班数为x,高中编制班数为y,又设年利润为 f,故学校的最优规模和招生计划分别为,最优规模：初中18个班，高中12个班；,招生计划：第1年初中招生6个班约300人，高中招生4个班约160人.以后每年按此计划招生.,设经过n,年可收回投资.,第1年利润为,第2年利润为,211.6=23.2,(万元);,以后每年的利润均为34.8万元.故依题意应有,解得,(年).即约经过36年可以收回全部投资.,9.6 线性规划的应用,8/8/2024,89,故学校的最优规模和招生计划分别为 设经过n年可收回投资.,2.投资问题,【例9.17】某投资人在今后3年内有,A,B,C,D,共 4个投资项目，项目,A,在3年内每年初投资，年底可获利润20%，并可将本金收回；项目,B,在第1年年初投资，第2年年底可获利润60%，并将本金收回，但该项目投资不得超过5万元；项目,C,在第2年初投资，第3年底收回本金，并获利润40%，但该项目投资不得超过3万元；项目,D,在第3年初投资，于该年底收回本金，且获利润30%，但该项目投资不得超过2万元.该投资人准备拿出6万元资金，问如何制订投资计划，使该企业在第3年底，投资的本利之和最大？,9.6 线性规划的应用,8/8/2024,90,2.投资问题9.6 线性规划的应用8/1/202390,【解】这是一个连续投资问题.设决策变量,x,ij,为第,j,年投资到第,i,个项目的资金(,i,=,1,2,3,4,分别对应于项目,A,B,C,D,；分别对应于投资年份),见列表9.13.,表9.13 投资项目,投资机会,项目名称,第1年年初 第2年年初 第3年年初,A,B,C,D,9.6 线性规划的应用,8/8/2024,91,【解】这是一个连续投资问题.设决策变量xij为第j年投资,下面分析每年资金的使用情况并建立线性规划模型.,第1年初，,有,A,B,两个项目，企业只能提供6万元资金，故有,:,.项目,B,不得超过5万元，有,第2年初,，有,A,C,两个投资项目.此时第1年初投资到项目,A,的资金已全部收回，本利和为,.这些资金可用于第2年的投资，,，而且要求,9.6 线性规划的应用,于是,；,；,8/8/2024,92,下面分析每年资金的使用情况并建立线性规划模型.项目B不得超,9.6 线性规划的应用,第3年初,，第1年初投资到项目,B,的资金全部收回，本利和为,;,第2年初投资于项目,A,的资金也全部收回，本利和为,以上两笔资金可供该年继续投资.第3年内还有,A,D,两个项,目的投资，可得,，而且要求,第3年底,，到期把所有本利和收回.所能收回的资金有第2年,初投资到项目,C,的本利和,，第3年初投资到项目,A,的,本利和,及投资到项目,D,的本利和,，则第3年底获,得的本利和为,;,8/8/2024,93,9.6 线性规划的应用第3年初，第1年初投资到项目B的资金,将上述目标函数和约束条件整理后即可得出该问题完整的,线性规划模型,:,求解得到最优投资方案如表9.14所示，且在第3年底收回投资的本利和最大为11.528万元.,9.6 线性规划的应用,8/8/2024,94,将上述目标函数和约束条件整理后即可得出该问题完整的线性规划模,表9.14 最优投资方案,投资机会,项目名称,第1年年初 第2年年初 第3年年初,A,X,11,=1,X,12,=1.2,X,13,=7.44,B,X,21,=5,C,X,32,=0,D,X,43,=2,9.6 线性规划的应用,8/8/2024,95,表9.14 最优投资方案 投资机会,3.人力资源分配问题,【例9.19】某百货商场售货员的需求经过统计分析如表9.16所示.为了保证售货员充分休息，售货员每周工作5天，休息2天，并要求休息的2天是连续的，问：应该如何安排售货员的作息时间，既满足工作需要，又使配备的售货员人数最少？,表9.16 售货人员需求统计表,时间,所需售货员人数,星期日,28,星期一,15,星期二,24,星期三,25,星期四,19,星期五,31,星期六,28,9.6 线性规划的应用,8/8/2024,96,3.人力资源分配问题表9.16 售货人员需求统计表时间所需,【解】设x,j,为星期j开始休息的人数（j=1,2,，分别对应星期一、二、三、四、五、六、日）.目标是要求售货员的总数最少.因为每个售货员都工作5天，休息2天，所以只要计算出连续休息2天的售货员数，也就计算出了售货员的总数.,这里可以把连续休息2天的售货员按照开始休息的时间分成7类，各类的人数分别为 x,j,（j=1,2,，），即有目标函数：,再按照每天所需售货员的人数写出约束条件.例如星期日需要28人，商场中的全体售货员中除了星期六和星期日开始休息的人外都应该上班，即有约束条件,9.6 线性规划的应用,8/8/2024,97,【解】设xj为星期j开始休息的人数（j=1,2,，,同理有,因x,j,（j=1,2,，）表示人数，故有,x,j,j=1,2,，），且为整数,9.6 线性规划的应用,综上得问题的线性规划模型为：,8/8/2024,98,同理有因xj（j=1,2,，）表示人数，故有9.6,9.6 线性规划的应用,计算结果：也就是说该商场至少需要售货员36人.他们的的休息安排为：,星期一 12人；星期三 11人；星期五 5人；星期日 8人.,8/8/2024,99,9.6 线性规划的应用计算结果：,一、对偶问题的提出,线性规划的,对偶原理,对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。,对偶思想举例,在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。,（1）周长一定，面积最大的矩形是正方形。,（2）面积一定，周长最短的矩形是正方形。,8/8/2024,100,一、对偶问题的提出 线性规划的对偶原理对偶是什么：,二、原问题和对偶问题的关系,1,、对称形式的对偶关系,（,1,）定义：若原问题是,8/8/2024,101,二、原问题和对偶问题的关系（1）定义：若原问题是 8/1/2,则定义其对偶问题为,这两个式子之间的变换关系称为“,对称形式的对偶关系,”,。,8/8/2024,102,则定义其对偶问题为 这两个式子之间的变换关系称为“,（,2,）对称形式的对偶关系的矩阵描述,（D）,（L）,（3）怎样从原始问题写出其对偶问题？,按照定义；,记忆法则：,“上、下”交换，“左、右”换位，,不等式变号，“极大”变“极小”,8/8/2024,103,（2）对称形式的对偶关系的矩阵描述（D）（L）（3）怎样,例 写出下面线性规划的对偶问题：,2,、非对称形式的对偶关系：,8/8/2024,104,例 写出下面线性规划的对偶问题：2、非对称形式的对偶关系,（1）原问题 对偶问题,（特点：对偶变量符号 不限，系数阵转置）,(,特点：等式约束,),8/8/2024,105,（1）原问题 对,（,2,）怎样写出非对称形式的对偶问题？,把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；,按照原始-对偶表直接写出,；,（,3,）原始,-,对偶表,8/8/2024,106,（2）怎样写出非对称形式的对偶问题？8/1/2023106,原问题（或对偶问题）,对偶问题（或原问题）,目标函数,MaxZ,目标函数,MinW,约束条件数：,m,个,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,=,”,对偶变量数：,m,个,第,i,个变量,0,第,i,个变量,0,第,i,个变量是自由变量,决策变量数：,n,个,第,j,个变量,0,第,j,个变量,0,第,j,个变量是自由变量,约束条件数：,n,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,=,”,8/8/2024,107,原问题（或对偶问题）对偶问题（或原问题）目标函数,练习：写出下面线性规划的对偶规划：,8/8/2024,108,练习：写出下面线性规划的对偶规划：8/1/2023108,下面的答案哪一个是正确的？为什麽？,（原问题是极小化问题，因此,应从原始对偶表的,右边,往,左边,查！,）,8/8/2024,109,下面的答案哪一个是正确的？为什麽？（原问题是极小化问题，因,