线性规划方法及其应用

第9章线性规划方法及其应用4/27/20241第9章线性规划方法及其应用线性规划（LinearProgramming）作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益。因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。4/27/20242第9章线性规划方法及其应用1、康托洛维奇生产组织与计划中的数学方法,一本小册子，1939;2、康托洛维奇“最佳资源利用的经济计算”——1942完成、1959发表的著作；3、自1947年丹兹格（G.B.Dantzing）提出求解线性规划问题的一般方法--单纯形法之后，线性规划在理论上趋于成熟，应用日益广泛与深入；

随着电子计算机的发展和计算速度的不断提高，其适用的领域更加广泛，它已成为必不可少的重要手段之一。4/27/20243第9章线性规划方法及其应用4、1975年库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获诺贝尔经济学奖；5、冯•诺伊曼和摩根斯坦1944年发表的

《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论。4/27/20244第9章线性规划方法及其应用线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。最优化/运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划的基础是线性变换。4/27/20245第9章线性规划方法及其应用数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容4/27/20246第9章线性规划方法及其应用9.1线性规划是什么9.2建立线性规划模型的一般步骤9.3线性规划问题的图解法9.4线性规划问题解的性质9.5解线性规划问题的单纯形法9.6线性规划的应用4/27/20247第9章线性规划方法及其应用9.1线性规划是什么4/27/20248第9章线性规划方法及其应用9.1线性规划是什么我们先通过几个实际问题来认识什么是线性规划.【例9.1】某企业生产三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表9.1所示.表9.1企业生产数据表1.利润最大化问题4/27/20249第9章线性规划方法及其应用9.1线性规划是什么试问：该企业怎样安排生产才会使每天的利润最大？解设该企业每天生产产品的数量分别为（单位：吨），则总利润的表达式为（原料甲的限制）

（原料乙的限制）此外，由于未知数（我们称之为决策变量）是计划产量，应有为非负的限制，即

4/27/202410第9章线性规划方法及其应用9.1线性规划是什么由此得到问题的数学模型为其中为英文“subjectto”的缩写，表示决策变量受它后面的条件约束.最优解为（具体解法后面介绍），代入总利润的表达式得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品不生产，生产25吨，生产25吨，可实现最大利润250千元/日.

其中为英文“subjectto”的缩写，表示决策变量受它后面的条件约束.最优解为（具体解法后面介绍），代入总利润的表达式得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品不生产，生产25吨，生产25吨，可实现最大利润250千元/日.

其中为英文“subjectto”的缩写，表示决策变量受它后面的条件约束.最优解为（具体解法后面介绍），代入总利润的表达式得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品不生产，生产25吨，生产25吨，可实现最大利润250千元/日.

其中为英文“subjectto”的缩写，表示决策变量受它后面的条件约束.最优解为（具体解法后面介绍），代入总利润的表达式得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品不生产，生产25吨，生产25吨，可实现最大利润250千元/日.

其中为英文“subjectto”的缩写，表示决策变量受它后面的条件约束.最优解为（具体解法后面介绍），代入总利润的表达式得对应的目标函数最大值为250.由此得到该企业在现有资源条件下，日生产的最优安排是：产品不生产，生产25吨，生产25吨，可实现最大利润250千元/日.

4/27/202411第9章线性规划方法及其应用9.1线性规划是什么类似于例9.1的这类问题称为最优生产计划问题.其一般描述是利用种资源组织生产种产品.以表示资源的限制，表示产品的单位利润，表示单位产品消耗资源的数量（代表该企业当前的技术水平），情况如表9.2所示.现在的问题是：如果该企业生产的这种产品都可以卖出，如何合理充分地利用现有的资源，给出一个使总利润达到最大的产品生产计划？4/27/202412第9章线性规划方法及其应用有了解决上述问题的经验，我们可以假设产品的计划产量分别为单位，则问题的数学模型为9.1线性规划是什么4/27/202413第9章线性规划方法及其应用模型中的都是实际问题给定的常数；未知量为决策变量.这类决策问题的应用领域非常广泛.

注本章的数学模型均可用软件求解。2.成本最小化问题【】某钢铁厂熔炼一种新型不锈钢，需要4种合金为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表9.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料各多少吨，能够使成本最小？9.1线性规划是什么4/27/202414第9章线性规划方法及其应用9.1线性规划是什么下料问题的一般描述：已知有一批原材料，每根长度为L，由于生产的需要，要求截出规格分别为的零件根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例9.4的建模过程列出此一般问题的数学模型.总之，类似例9.1、9.2的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的共同点，即每一个问题都用一组决策变量来表示某一方案，追求的目标可以用关于决策变量的线性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量的线性等式或不等式表示.4/27/202415第9章线性规划方法及其应用9.1线性规划是什么这类问题所构成的数学模型,称为线性规划模型.有时也直接将线性规划模型称为线性规划问题.针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案。4/27/202416第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤4/27/202417第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤从§9.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步理解要解决的问题.搞清在什么条件下追求什么目标.第2步定义决策变量.每一个问题都用一组决策变量来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的.第3步确定约束条件.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.第4步列出目标函数.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.4/27/202418第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.线性规划的一般形式可表示为：4/27/202419第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤其中称为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的为常数.当要求决策变量均为整数时，称（9.1）为纯整数线性规划问题；当要求决策变量均取0或1时，称（9.1）为整数线性规划问题.当要求决策变量既取实数又取整数时，称（9.1）为混合整数线性规划问题.我们把满足所有约束条件的解称为线性规划问题（9.1）的可行解.全体可行解的集合称为问题（9.1）的可行域,记为

.使目标函数值最大（或最小）的可行解称为该线性4/27/202420第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤规划问题的最优解，与此最优解相应的目标函数值称为最优目标函数值，简称最优值.因此，若记，求解线性规划问题（9.1），本质上就是寻找一点

，使得

均满足不等式【】某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备（台时），A、B两种原材料的消耗以及资源的限制情况如表2.11所示.问：该工厂应分别生产多少甲产品和乙产品才能使工厂获利最大？4/27/202421第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤解首先，确定决策变量.工厂目前要决策的是甲产品和乙产品的生产量，可以分别用变量来表示.由于它们表示产品产量，所以只取非负数.其次，根据问题的限制条件，列出表示约束条件的线性不等式：4/27/202422第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤，（非负限制）

，（台时数限制）

，（原材料限制）

，（原材料限制）最后，根据实际问题所追求的目标，列出其线性函数表达式.由于问题的目标是工厂获利最大，假如产品都能销售，则总利润可表示为，最大利润记为4/27/202423第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤综上所述，就得到了描述该问题的线性规划模型：4/27/202424第9章线性规划方法及其应用计算最优解为：即在现有资源条件下，该企业在计划期内生产的最优计划是：产品甲生产100单位，产品乙生产200单位，可实现最大利润130000元.9.2建立线性规划模型的一般步骤4/27/202425第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤【例9.4】某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？4/27/202426第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤解设为时段开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：4/27/202427第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤计算最优解为： 故该医院需雇用150名护士，最佳安排见表9.10所示.4/27/202428第9章线性规划方法及其应用9.2建立线性规划模型的一般步骤线性规划的一般形式，可行解、最优解等概念线性规划问题建模过程：第1步理解要解决的问题。第2步定义决策变量。第3步确定约束条件。

第4步列出目标函数。

4/27/202429第9章线性规划方法及其应用9.3线性规划问题的图解法4/27/202430第9章线性规划方法及其应用9.3线性规划问题的图解法1.图解法

对一个线性规划问题建立数学模型之后，就面临着如何求解的问题.这里先介绍含有两个决策变量的线性规划问题的图解法.它简单直观，有助于了解线性规划问题求解的基本原理.

4/27/202431第9章线性规划方法及其应用图解法的步骤可概括为：（1）在平面上建立直角坐标系；（2）图示约束条件，找出可行域（由于，可行域必位于第一象限）；（3）图示目标函数，即画出目标函数等值线；（4）对（或）问题朝着增大（或减少）纵截距的方向平行移动目标函数等值线，至与可行域的边界相切时为止.切点（即某个边界点）就是代表最优解的点；（5）寻找该点的坐标得到最优解.以下结合实例来具体说明.

4/27/202432第9章线性规划方法及其应用9.3线性规划问题的图解法

【例9.5】用图解法求解线性规划问题

4/27/202433第9章线性规划方法及其应用9.3线性规划问题的图解法解先画出线性规划的可行域如图9.1阴影部分.再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点.最后求解线性方程组

求解得到点的坐标，从而得到最优解，最大值4/27/202434第9章线性规划方法及其应用9.3线性规划问题的图解法4/27/202435第9章线性规划方法及其应用9.3线性规划问题的图解法【例9.6】用图解法求解线性规划问题解先画出线性规划的可行域，如图9.2阴影部分.

4/27/202436第9章线性规划方法及其应用9.3线性规划问题的图解法4/27/202437第9章线性规划方法及其应用9.3线性规划问题的图解法

得到解出点B的坐标，从而得到最优解，最大值

例9.5与例9.6中求解得到的问题的最优解是惟一的，但对一般线性规划问题，求解结果还可能出现其他情况.4/27/202438第9章线性规划方法及其应用9.3线性规划问题的图解法2.线性规划解的其他情况（1）多重最优解的情况

【例9.9】，则代表目标函数的直线平移到最优位置后将和直线重合.此时，不仅顶点A，B都代表了最优解，而且线段上AB的所有点都代表了最优解.这个线性规划问题有无穷多最优解，这些最优解都对应着相同的最大值4/27/202439第9章线性规划方法及其应用MAX4/27/202440第9章线性规划方法及其应用9.3线性规划问题的图解法（2）无界解的情况（3）无可行解的情况4/27/202441第9章线性规划方法及其应用9.3线性规划问题的图解法（2）无界解的情况

【例9.10】对下述线性规划问题用图解法求解结果如图2.3(a)所示.从图中可以看出，由于可行域是无界区域，当目标函数等值线沿箭头方向平行移动时，始终与该无界区域相交.此时，目标函数值无上界，因此无最优解，也称最优解无界.4/27/202442第9章线性规划方法及其应用9.3线性规划问题的图解法（3）无可行解的情况【例9.11】对线性规划问题由图2.3(b)可以看出，同时满足所有约束条件的点不存在，即可行域为空集，也就是没有可行解，故不存在最优解.4/27/202443第9章线性规划方法及其应用9.3线性规划问题的图解法当根据实际问题建立的线性规划模型的求解结果出现（2）,（3）两种情况时，一般说明建模有错误.前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意.下面再给出一个求目标函数最小化的线性规划问题.【例9.12】求解线性规划4/27/202444第9章线性规划方法及其应用9.3线性规划问题的图解法中求出，为.这就是所求线性规划问题的最优解，且.4/27/202445第9章线性规划方法及其应用9.3线性规划问题的图解法4/27/202446第9章线性规划方法及其应用9.3线性规划问题的图解法(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动4/27/202447第9章线性规划方法及其应用9.4线性规划问题解的性质4/27/202448第9章线性规划方法及其应用1.线性规划问题的标准形

前面曾给出了线性规划问题的一般形式，可以看出，其中有的要求目标函数最大化，有的要求目标函数最小化；约束条件可以是“≤”或“≥”形式的不等式，也可以是等式；决策变量一般是非负约束，但也允许在范围内取值，即无约束。为了进一步研究和讨论，就需要把线性规划问题的一般形式化为统一的标准形式。9.4线性规划问题解的性质4/27/202449第9章线性规划方法及其应用线性规划的一般形式可表示为：4/27/202450第9章线性规划方法及其应用这里的标准形式有以下规定：（1）目标函数是求最大值；（2）所有约束条件均用等式表示；（3）所有决策变量均取非负数；（4）所有约束常数均为非负数.9.4线性规划问题解的性质4/27/202451第9章线性规划方法及其应用

于是，具有个约束条件和个决策变量的线性规划问题的标准形为：9.4线性规划问题解的性质4/27/202452第9章线性规划方法及其应用在约束条件

≥0（j=1，2，…，n）

下，求一组未知变量（j

=1，2，…，n）的值，使得。常记为如下更为紧凑的形式

或其缩写形式为：4/27/202453第9章线性规划方法及其应用

其中b和C为已知非负常数，A为已知常数矩阵，且rank(A)=m。一般可以通过以下方法，把非标准形线性规划问题化为标准形：（1）目标函数的标准化如果线性规划问题是求目标函数的最小值，即则令，得，这就同标准形的目标函数的形式一致了.但要注意，如果要求原问题的最优值，应取最优值的相反数.9.4线性规划问题解的性质4/27/202454第9章线性规划方法及其应用（2）约束条件的标准化当约束条件为≤形式的不等式时，可在不等式左边加上一个非负的新变量（称为松弛变量(slackvariables)

），把不等号变为等号；当约束条件为≥形式的不等式时，可在不等式左边减去一个非负的新变量（称为剩余变量），把不等号变为等号.9.4线性规划问题解的性质4/27/202455第9章线性规划方法及其应用（3）决策变量的标准化如果某一决策变量是一个符号不受限制的“自由变量”，可以引入两个非负的新变量和，并作变换，将决策变量标准化。9.4线性规划问题解的性质4/27/202456第9章线性规划方法及其应用（4）约束常数的标准化如果有某约束常数为负数，可在等式（或不等式）两边同时乘以，把约束常数变为正数.9.4线性规划问题解的性质4/27/202457第9章线性规划方法及其应用【例9.13】把下面的线性规划问题化为标准形：【解】此例只有约束条件不符合标准形，为此引入非负的松弛变量，并分别把它们加到第1个和第2个不等式的左边，即得标准形：注意，所加松弛变量表示没有被利用的资源，当然也没有利润，所以在目标函数中的系数应为零.9.4线性规划问题解的性质4/27/202458第9章线性规划方法及其应用9.4线性规划问题解的性质【例9.14】将下面线性规划问题化为标准形【解】令，把求改为求；用替换，其中；在第1个约束不等式的左边加入松弛变量，在第2个约束不等式的左边减去剩余变量，这样即可得到该问题的标准形为4/27/202459第9章线性规划方法及其应用，

9.4线性规划问题解的性质标准形原问题4/27/202460第9章线性规划方法及其应用

可行解与最优解

满足约束条件（即满足线性约束和非负约束）的一组变量为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。

4/27/202461第9章线性规划方法及其应用基本解与基本可行解

在线性规划问题中，将约束方程组的m×n阶矩阵A写成由n个列向量组成的分块矩阵4/27/202462第9章线性规划方法及其应用如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称为基向量，与基向量相对应的向量为基变量，而其余的变量为非基变量。

4/27/202463第9章线性规划方法及其应用如果是方程组的解,则就是方程组的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。4/27/202464第9章线性规划方法及其应用线性规划问题的以上几个解的关系，可用下图来描述：4/27/202465第9章线性规划方法及其应用【】如果集合K中任意两点s,t之间连线上所有的点都是集合K中的点，即对于任意的，都有，则称K为凸集.例如图9.5中（a）,（b）,（c）为凸集，而（d）,（e）不是凸集.

3.线性规划问题解的基本性质(a)(b)(c)(d)(e)

图9.5凸集与非凸集示例9.4线性规划问题解的性质4/27/202466第9章线性规划方法及其应用【

】线性规划问题的可行域

是一个凸集.这两个定理我们不给予数学证明.结合图解法，我们可以清晰地了解到线性规划问题解的有关性质.定理9.1说明：联结线性规划问题任意两个可行解的线段上的点（坐标）仍是可行解.定理9.2则告诉我们：如果一个线性规划问题有最优解，则一定可以从可行域的有限个顶点中找到.【

】若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到.9.4线性规划问题解的性质4/27/202467第9章线性规划方法及其应用【

】如果凸集K中的点x不能成为任何线段的内点，即对任意，都不存在，使得，则称x为K的一个顶点.例如三角形、正方形、凸多边形、凸无界区域的顶点及圆周上的点，都是相应凸集的顶点.从图解法的例子中知道线性规划问题的可行域是一个凸集，且如果问题有最优值，都是在顶点上达到.这些性质推广到一般，就是下面几个重要定理.9.4线性规划问题解的性质4/27/202468第9章线性规划方法及其应用9.4线性规划问题解的性质1.将非标准形化为标准形的方法（1）线性规划问题的可行域

是一个凸集。（2）若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到。4/27/202469第9章线性规划方法及其应用9.5解线性规划问题的单纯形法4/27/202470第9章线性规划方法及其应用数学模型为:9.5解线性规划问题的单纯形法4/27/202471第9章线性规划方法及其应用（1）先化为标准形.引入松弛变量得到标准形9.5解线性规划问题的单纯形法4/27/202472第9章线性规划方法及其应用（2）再把目标函数改写成并把它加入到约束方程组中去，即得到方程组9.5解线性规划问题的单纯形法4/27/202473第9章线性规划方法及其应用将此方程组的系数及常数项b列成一个数表，即.9.5解线性规划问题的单纯形法

称此表为初始单纯形表.表中的数字被分成了4部分，位于左下角的每个数字称为检验数.此时与对应的检验数都是负数，因此，若不令

，只要有一个是正数，则它与负数相乘后仍是负数，移项到右边，函数值就会增大，为此转到下一步.

4/27/202474第9章线性规划方法及其应用（3）在负检验数中选绝对值最大的负数（即

7），在对应的列中，将该列中的正数分别去除对应的常数项，选择比值最小者所对应的元素为主元（称为最小比值原则）.在这里然后用矩阵的初等行变换，将主元化为1，把同列的其他元素化为0.这一过程如下：将矩阵

可知位于第2行、第3列的元素3为主元，标为,9.5解线性规划问题的单纯形法4/27/202475第9章线性规划方法及其应用的第2行乘以1/3，得

再将矩阵的第2行乘以（

2）加到第1行，第2行乘以7加到第3行，得

此时的目标函数值已经由原来的0增加到700/3.由于检验数中仍有负数，按照最小比值原则，可知位于第1行、第2列的元素4/3为主元.同样用矩阵的初等行变换，将主元化为1，把同列的其他元素化为0，

9.5解线性规划问题的单纯形法4/27/202476第9章线性规划方法及其应用过程如下：将矩阵A的第1行乘以3/4，得最优单纯形表.易知最优解为最优值为250.从而原线性规划问题的最优解为对应的目标函数最优值为250.9.5解线性规划问题的单纯形法再将矩阵的第2行乘以（

2）加到第1行，第2行乘以7加到第3行，得4/27/202477第9章线性规划方法及其应用上述求解线性规划问题的方法称为单纯形法.单纯形法步骤如下：第1步，将线性规划化成标准形；第2步，写出初始单纯形表；第3步，对检验数进行检验.若检验数均为非负数，则得到最优单纯形表.若有负数，则在检验数绝对值最大的负数所对应的列中，按最小比值原则选主元，用初等行变换化主元为1，主元所在列其余元素化为0，得到一张新单纯形表.再检验该表是否为最优单纯形表，若不是，重复上述过程，直到得出最优单纯形表.第4步，从最优单纯形表直接写出最优解和最优值.9.5解线性规划问题的单纯形法4/27/202478第9章线性规划方法及其应用从上例求解过程看到，单纯形表中所对应的列始终不变，故在实际计算中可省去不写.上例的求解过程本质上是矩阵的初等行变换过程，我们可以把此例的单纯形法求解过程简化为9.5解线性规划问题的单纯形法4/27/202479第9章线性规划方法及其应用9.5解线性规划问题的单纯形法所以最优解及最优值分别为【注1】若在计算过程中，单纯形表出现某检验数为负，但其所在的列无正元素的情况，则可以证明该问题无最优解.

4/27/202480第9章线性规划方法及其应用【解】引入松弛变量，化为标准形

9.5解线性规划问题的单纯形法【例9.15】解线性规划问题

4/27/202481第9章线性规划方法及其应用初始单纯形表为由于检验数

1所在列无正数元素，故此问题无最优解.9.5解线性规划问题的单纯形法4/27/202482第9章线性规划方法及其应用【注2】在上例的初始单纯形表中，由虚线隔开的左上部分，所在列的元素构成一个二阶单位矩阵我们称为基变量.一般地，对含有n个变量、m个约束的线性规划问题，当把它化为标准形后，若恰有一个m阶单位矩阵，就可以用前面的单纯形法求出最优解（若最优解存在）；若基变量不足m个，则用改进单纯形法或对偶单纯形法求解.由于这两种方法用到较多的数学知识，这里不再介绍，但WinQSB软件中的线性规划程序已经包含了改进单纯形法和对偶单纯形法.9.5解线性规划问题的单纯形法4/27/202483第9章线性规划方法及其应用9.5解线性规划问题的单纯形法1.判断基本可行解.有3种情形：①已是最优解，②是无界解，③不能确定.前2种情形计算结束，第3种情形需要继续迭代，先进基后出基，初等变换求下一个基本可行解，直到出现最优解或无界解为止。唯一最优解的判定：所有非基变量的检验数非零,则线规划具有唯一最优解。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:某个检验数大于0且该检验数所在列中所有元素小或等于，则线性规划具有无界解。4/27/202484第9章线性规划方法及其应用9.6线性规划的应用4/27/202485第9章线性规划方法及其应用9.6线性规划的应用

线性规划在国内外很多部门的规划、管理、决策过程中有大量成功的应用，并收到了良好的效果.但是，应用线性规划来解决某一类实际问题时，由于问题的复杂性和情况的多变性，要真正建立一个反映实际问题的、能得出正确结论的理想模型，并不是一件容易的事情.它要求建模者具有丰富的经验、较强的创造力和比较熟练的技巧.本节通过一些被简化了的问题，介绍建立线性规划模型的基本思路和基本技巧.4/27/202486第9章线性规划方法及其应用【例9.16】某人准备投资1200万元办一所中学，为了考虑社会效益和经济效益，对该地区教育市场进行调查，得出一组数据，如表所示.表9.12市场调查表9.6线性规划的应用班级班级学生数配备教师数硬件建设费（万元）教师年薪（万元）初中502.0281.2高中402.5581.6根据物价部门的有关文件，初中是义务教育阶段，收费标准适当控制，预计除书费、办公费外，初中每个学生每年可收取600元，而高中每个学生每年可收取1500元.因生源和环境等条件限制，办学规模以20～30个（含20与30）班为宜.教师实行聘任制.初、高中的教育周期均为3年.请你合理地安排招生计划，使年利润最大.问：大约经过多少年可以收回全部投资？4/27/202487第9章线性规划方法及其应用解设初中编制班数为x,高中编制班数为y,又设年利润为f,（单位：万元），那么即.于是此问题的线性规划模型为解得最优解代入中得9.6线性规划的应用4/27/202488第9章线性规划方法及其应用故学校的最优规模和招生计划分别为最优规模：初中18个班，高中12个班；招生计划：第1年初中招生6个班约300人，高中招生4个班约160人.以后每年按此计划招生.设经过n年可收回投资.第1年利润为第2年利润为(万元);解得(年).即约经过36年可以收回全部投资.9.6线性规划的应用4/27/202489第9章线性规划方法及其应用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线性规划的应用4/27/202490第9章线性规划方法及其应用xij为第j年投资到第i个项目的资金(i=1,2,3,4,分别对应于项目A,B,C,D；分别对应于投资年份),见列表9.13.表9.13投资项目投资机会项目名称第1年年初第2年年初第3年年初ABCD9.6线性规划的应用4/27/202491第9章线性规划方法及其应用下面分析每年资金的使用情况并建立线性规划模型.第1年初，有A,B两个项目，企业只能提供6万元资金，故有:.项目B不得超过5万元，有

第2年初，有A,CA的资金已全部收回，本利和为

.这些资金可用于第2年的投资，，而且要求

9.6线性规划的应用于是；；4/27/202492第9章线性规划方法及其应用9.6线性规划的应用第3年初，第1年初投资到项目B的资金全部收回，本利和为;第2年初投资于项目A的资金也全部收回，本利和为A,D两个项目的投资，可得，而且要求

第3年底初投资到项目C的本利和，第3年初投资到项目A的本利和

及投资到项目D的本利和，则第3年底获得的本利和为

;4/27/202493第9章线性规划方法及其应用将上述目标函数和约束条件整理后即可得出该问题完整的线性规划模型:求解得到最优投资方案如表9.14所示，且在第3年底收回投资的本利和最大为11.528万元.9.6线性规划的应用4/27/202494第9章线性规划方法及其应用表9.14最优投资方案投资机会

项目名称第1年年初第2年年初第3年年初AX11=1X12=1.2X13=7.44BX21=5CX32=0DX43=29.6线性规划的应用4/27/202495第9章线性规划方法及其应用【例9.19】某百货商场售货员的需求经过统计分析如表9.16所示.为了保证售货员充分休息，售货员每周工作5天，休息2天，并要求休息的2天是连续的，问：应该如何安排售