运筹学思想方法及应用 ch2 线性规划及其应用

2023/2/51第二章线性规划及其应用运筹学Operational

Research2023/2/52第二章线性规划及其应用线性规划（LinearProgramming）作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科.它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益.

因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法.线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段.2023/2/532.1线性规划是什么2.2建立线性规划模型的一般步骤2.3线性规划问题的图解法2.4线性规划问题解的性质2.5解线性规划问题的单纯形法2.6线性规划的应用2.7WinQSB软件应用第二章线性规划及其应用2023/2/542.1线性规划是什么2023/2/552.1线性规划是什么我们先通过几个实际问题来认识什么是线性规划.【例2.1】

某企业生产三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表2.1所示.

表2.1企业生产数据表1.利润最大化问题2023/2/562.1线性规划是什么试问：该企业怎样安排生产才会使每天的利润最大？解设该企业每天生产产品的数量分别为（单位：吨），则总利润的表达式为我们希望在现有资源条件下总利润最大.现有资源的限制为（原料甲的限制）

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

2023/2/572.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千元/日.

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

注本章的数学模型均可用软件求解，具体使用方法见本章的§2.7.

2.成本最小化问题【例2.2】

某钢铁厂熔炼一种新型不锈钢，需要4种合金为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表2.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料各多少吨，能够使成本最小？2.1线性规划是什么2023/2/5112.1线性规划是什么

表2.3生产某种不锈钢的相关数据表2023/2/5122.1线性规划是什么解设选用原料的量分别为（单位：吨）.由于追求的目标是成本最小，故有最小成本表达式：

以下分析约束条件.由于假设熔炼时质量没有损耗，熔炼该种不锈钢100吨，它由原料熔炼而成，故有等式约束

又因该不锈钢所需铬、锰和镍的最低质量分数是由4种合金对相应元素的质量分数构成，注意到要熔炼该种不锈钢100吨，于是得到铬、锰和镍的质量分数满足的不等式依次为2023/2/5132.1线性规划是什么此外，各种合金的加入量以整吨为单位，即有限制且为整数.综合上述讨论，我们得到该问题的数学模型为2023/2/5142.1线性规划是什么易求得此模型的解为.也就是说，选用原料依次为27，32，41，0吨时，达到最低成本957.1万元.例2.2的这类问题也称为混合配料问题.其一般描述是：把n种不同的原料配制成含有m种成分的一种产品，生产数量为.经测定这n种原料关于m种成分的质量分数（%）、单价以及这种产品所需m种成分的最低质量分数（%）如表2.4所示.假设产品配制时重量没有损耗，问：要生产数量为的这种产品，应选用原料各多少能够使成本最小？2023/2/5152.1线性规划是什么2023/2/5162.1线性规划是什么类似于例2.2，设选用原料的数量依次为，则得到此问题的数学模型为2023/2/5172.1线性规划是什么这类决策问题的应用领域同样是非常广泛的.再进一步抽象，就可以将其归纳为一类决策问题：当某个任务确定之后，如何统筹安排，尽量用最少的资金、人力、物力等资源去完成该项任务.3.运输问题【例2.3】某建材公司有三个水泥厂，四个销地，其产量、销量、运费见表2.5.2023/2/5182.1线性规划是什么如何制定调运方案，使总的运费或总货运量最小？

解设由水泥厂运到销地的货运量为，则得到问题的数学模型为2023/2/5192.1线性规划是什么其解为.最佳运输方案见表2.6.2023/2/5202.1线性规划是什么运输问题的一般描述：将个产地生产的一种产品运到个销地，表示产地的产量限制，表示销地的销量需求，表示单位产品从运到的运费.情况如表2.7所示.问题是：制定一个使总的运费或总货运量最小的调运方案.2023/2/5212.1线性规划是什么设由产地运到销地的货运量为，则得到此运输问题的数学模型为2023/2/5222.1线性规划是什么4.

合理下料问题【例2.4】

现有一批长度一定的钢管，由于生产的需要，要求截出若干不同规格的钢管.试问：要如何截取原材料，既能满足生产的需要，又使得使用的原材料钢管数量最少或废材最少？具体数据：原材料钢管长7.4m，截成2.9m,2.1m,1.5m各为1000根，2000根，1000根.

解把所有可能的下料方式、按照各种下料方式从长7.4m的原料上得到的不同规格钢管的根数、残料长度，以及需要量列于表2.8中.例如，按照下料方式，可以得到2.9m钢管2根,1.5m钢管1根.问题转化为确定每种下料方式各用多少根7.4m的原料，可使被使用的原料根数最少.2023/2/5232.1线性规划是什么设分别为按照方式下料的原料根数，则得到问题的数学模型为2023/2/5242.1线性规划是什么其解为

根.即最佳下料方案为：方式：200根；方式：800根；方式：200根；其他方式为0根.2023/2/5252.1线性规划是什么下料问题的一般描述：已知有一批原材料，每根长度为L，由于生产的需要，要求截出规格分别为的零件根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例2.4的建模过程列出此一般问题的数学模型.总之，类似于例2.1—2.4的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的共同点，即每一个问题都用一组决策变量来表示某一方案，追求的目标可以用关于决策变量的线性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量的线性等式或不等式表示.

2023/2/5262.1线性规划是什么这类问题所构成的数学模型,称为线性规划模型.有时也直接将线性规划模型称为线性规划问题.针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案.2023/2/5272.1线性规划是什么本节学习要点1.通过实例，了解什么是线性规划，了解线性规划在管理中的几类应用例子2.线性规划数学模型的组成及其特征2023/2/5282.2建立线性规划模型的一般步骤2023/2/5292.2建立线性规划模型的一般步骤从§2.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步理解要解决的问题.搞清在什么条件下追求什么目标.第2步定义决策变量.每一个问题都用一组决策变量来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的.第3步确定约束条件.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.第4步列出目标函数.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.2023/2/5302.2建立线性规划模型的一般步骤对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.线性规划的一般形式可表示为：2023/2/5312.2建立线性规划模型的一般步骤其中称为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的为常数.当要求决策变量均为整数时，称（2.1）为纯整数线性规划问题；当要求决策变量均取0或1时，称（2.1）为整数线性规划问题.当要求决策变量既取实数又取整数时，称（2.1）为混合整数线性规划问题.我们把满足所有约束条件的解称为线性规划问题（2.1）的可行解.全体可行解的集合称为问题（2.1）的可行域,记为.使目标函数值最大（或最小）的可行解称为该线性2023/2/5322.2建立线性规划模型的一般步骤

规划问题的最优解，与此最优解相应的目标函数值称为最优目标函数值，简称最优值.因此，若记，求解线性规划问题（2.1），本质上就是寻找一点，使得均满足不等式【例2.5】

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

，（台时数限制）

，（原材料限制）

，（原材料限制）最后，根据实际问题所追求的目标，列出其线性函数表达式.由于问题的目标是工厂获利最大，假如产品都能销售，则总利润可表示为，最大利润记为2023/2/5352.2建立线性规划模型的一般步骤综上所述，就得到了描述该问题的线性规划模型：计算最优解为：元.即在现有资源条件下，该企业在计划期内生产的最优计划是：2023/2/5362.2建立线性规划模型的一般步骤计算最优解为：即在现有资源条件下，该企业在计划期内生产的最优计划是：产品甲生产100单位，产品乙生产200单位，可实现最大利润130000元.2023/2/5372.2建立线性规划模型的一般步骤

【例2.6】

某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？2023/2/5382.2建立线性规划模型的一般步骤解设为时段开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：2023/2/5392.2建立线性规划模型的一般步骤计算最优解为： 故该医院需雇用150名护士，最佳安排见表2.10所示.2023/2/5402.2建立线性规划模型的一般步骤本节学习要点线性规划的一般形式，可行解、最优解等概念线性规划问题建模过程：第1步理解要解决的问题.

第2步定义决策变量.

第3步确定约束条件.

第4步列出目标函数.

2023/2/5412.3线性规划问题的图解法2023/2/5422.3线性规划问题的图解法1.图解法

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

图解法的步骤可概括为：（1）在平面上建立直角坐标系；（2）图示约束条件，找出可行域（由于，可行域必位于第一象限）；

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

2023/2/5442.3线性规划问题的图解法

以下结合实例来具体说明.

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

2023/2/5452.3线性规划问题的图解法解先画出线性规划的可行域如图2.1阴影部分.再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点.

最后求解线性方程组

求解得到点的坐标，从而得到最优解，最大值2023/2/5462.3线性规划问题的图解法2023/2/5472.3线性规划问题的图解法【例2.8】用图解法求解线性规划问题解先画出线性规划的可行域，如图2.2阴影部分.

2023/2/5482.3线性规划问题的图解法2023/2/5492.3线性规划问题的图解法再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点B.最后求解线性方程组

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

例2.7与例2.8中求解得到的问题的最优解是惟一的，但对一般线性规划问题，求解结果还可能出现其他情况.2023/2/5502.3线性规划问题的图解法2.线性规划解的其他情况（1）多重最优解的情况

【例2.9】

若将例2.7中的目标函数变为，则代表目标函数的直线平移到最优位置后将和直线重合.此时，不仅顶点A，B都代表了最优解，而且线段上AB的所有点都代表了最优解.这个线性规划问题有无穷多最优解，这些最优解都对应着相同的最大值2023/2/5512.3线性规划问题的图解法（2）无界解的情况

【例2.10】

对下述线性规划问题用图解法求解结果如图2.3(a)所示.从图中可以看出，由于可行域是无界区域，当目标函数等值线沿箭头方向平行移动时，始终与该无界区域相交.此时，目标函数值无上界，因此无最优解，也称最优解无界.2023/2/5522.3线性规划问题的图解法（3）无可行解的情况

【例2.11】

对线性规划问题由图2.3(b)可以看出，同时满足所有约束条件的点不存在，即可行域为空集，也就是没有可行解，故不存在最优解.2023/2/5532.3线性规划问题的图解法2023/2/5542.3线性规划问题的图解法当根据实际问题建立的线性规划模型的求解结果出现（2）,（3）两种情况时，一般说明建模有错误.前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意.下面再给出一个求目标函数最小化的线性规划问题.【例2.12】

求解线性规划2023/2/5552.3线性规划问题的图解法解画出此线性规划问题的可行域，如图2.4中的阴影部分.目标函数，它在坐标平面上可表示为以f为参数，以-2/4为斜率的一组等值线.当等值线移动到B点时，目标函数在可行域中取最小值.B点的坐标可以从线性方程组中求出，为.这就是所求线性规划问题的最优解，且.2023/2/5562.3线性规划问题的图解法2023/2/5572.3线性规划问题的图解法本节学习要点1.通过图解法了解线性规划有几种解的形式2.作图的关键有三点

(1)可行解区域要画正确

(2)目标函数增加的方向不能画错

(3)目标函数的直线怎样平行移动2023/2/5582.4线性规划问题解的性质2023/2/5591.线性规划问题的标准形

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

于是，具有个约束条件和个决策变量的线性规划问题的标准形为：2.4线性规划问题解的性质2023/2/562

其中常数非负.一般可以通过以下方法，把非标准形线性规划问题化为标准形：（1）目标函数的标准化如果线性规划问题是求目标函数的最小值，即则令，得，这就同标准形的目标函数的形式一致了.但要注意，如果要求原问题的最优值，应取最优值的相反数.2.4线性规划问题解的性质2023/2/563（2）约束条件的标准化当约束条件为≤形式的不等式时，可在不等式左边加上一个非负的新变量（称为松弛变量），把不等号变为等号；当约束条件为≥形式的不等式时，可在不等式左边减去一个非负的新变量（称为剩余变量），把不等号变为等号.2.4线性规划问题解的性质2023/2/564（3）决策变量的标准化如果某一决策变量是一个符号不受限制的“自由变量”，可以引入两个非负的新变量和，并作变换，将决策变量标准化..2.4线性规划问题解的性质2023/2/565（4）约束常数的标准化如果有某约束常数为负数，可在等式（或不等式）两边同时乘以，把约束常数变为正数.2.4线性规划问题解的性质2023/2/566【例2.13】把下面的线性规划问题化为标准形：【解】此例只有约束条件不符合标准形，为此引入非负的松弛变量，并分别把它们加到第1个和第2个不等式的左边，即得标准形：注意，所加松弛变量表示没有被利用的资源，当然也没有利润，所以在目标函数中的系数应为零.2.4线性规划问题解的性质2023/2/5672.4线性规划问题解的性质【例2.14】将下面线性规划问题化为标准形【解】令，把求改为求；用替换，其中；在第1个约束不等式的左边加入松弛变量，在第2个约束不等式的左边减去剩余变量，这样即可得到该问题的标准形为2023/2/568，

2.4线性规划问题解的性质标准形原问题2023/2/569【定义2.1】如果集合K中任意两点s,t之间连线上所有的点都是集合K中的点，即对于任意的，都有，则称K为凸集.例如图2.5中（a）,（b）,（c）为凸集，而（d）,（e）不是凸集.

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

图2.5凸集与非凸集示例2.4线性规划问题解的性质2023/2/570【定义2.2

】如果凸集K中的点x不能成为任何线段的内点，即对任意，都不存在，使得，则称x

为K

的一个顶点.例如三角形、正方形、凸多边形、凸无界区域的顶点及圆周上的点，都是相应凸集的顶点.从图解法的例子中知道线性规划问题的可行域是一个凸集，且如果问题有最优值，都是在顶点上达到.这些性质推广到一般，就是下面几个重要定理.2.4线性规划问题解的性质2023/2/571【定理2.1

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

】若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到.2.4线性规划问题解的性质2023/2/5722.4线性规划问题解的性质本节学习要点1.将非标准形化为标准形的方法

2.线性规划问题解的性质（1）线性规划问题的可行域是一个凸集.

（2）若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到.2023/2/5732.5解线性规划问题的单纯形法

2023/2/574

单纯形法是求解线性规划的一种通用方法，1947年由美国数学家丹兹格（G.B.Dantzig）给出.下面结合§2.1中的利润最大化问题介绍单纯形法的基本内容.由§2.1中的例2.1提供的数学模型为:2.5解线性规划问题的单纯形法2023/2/575（1）先化为标准形.引入松弛变量得到标准形2.5解线性规划问题的单纯形法2023/2/576（2）再把目标函数改写成并把它加入到约束方程组中去，即得到方程组2.5解线性规划问题的单纯形法2023/2/577将此方程组的系数及常数项b列成一个数表，即.2.5解线性规划问题的单纯形法

称此表为初始单纯形表.表中的数字被分成了4部分，位于左下角的每个数字称为检验数.此时与

对应的检验数都是负数，因此，若不令

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

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

可知位于第2行、第3列的元素3为主元，标为,2.5解线性规划问题的单纯形法2023/2/579的第2行乘以1/3，得

再将矩阵的第2行乘以（2）加到第1行，第2行乘以7加到第3行，得

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

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

2023/2/584【解】引入松弛变量，化为标准形

2.5解线性规划问题的单纯形法【例2.15】

解线性规划问题

2023/2/5852.5解线性规划问题的单纯形法初始单纯形表为由于检验数1所在列无正数元素，故此问题无最优解.2023/2/586【注2】在上例的初始单纯形表中，由虚线隔开的左上部分，所在列的元素构成一个二阶单位矩阵我们称为基变量.

一般地，对含有n个变量、m个约束的线性规划问题，当把它化为标准形后，若恰有一个m阶单位矩阵，就可以用前面的单纯形法求出最优解（若最优解存在）；若基变量不足m个，则用改进单纯形法或对偶单纯形法求解.由于这两种方法用到较多的数学知识，这里不再介绍，但WinQSB软件中的线性规划程序已经包含了改进单纯形法和对偶单纯形法.2.5解线性规划问题的单纯形法2023/2/5872.5解线性规划问题的单纯形法本节学习要点1.判断基本可行解.有3种情形：①已是最优解，②是无界解，③不能确定.前2种情形计算结束，第3种情形需要继续迭代，先进基、后出基，用矩阵的初等行变换求下一个基本可行解，直到出现最优解或无界解为止.2.判定方法唯一最优解的判定：所有非基变量的检验数为正,则线规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解无界解的判断:

某个检验数小于0且该检验数所在列中所有元素小或等于0，则线性规划具有无界解2023/2/5882.6线性规划的应用2023/2/5892.6线性规划的应用

线性规划在国内外很多部门的规划、管理、决策过程中有大量成功的应用，并收到了良好的效果.但是，应用线性规划来解决某一类实际问题时，由于问题的复杂性和情况的多变性，要真正建立一个反映实际问题的、能得出正确结论的理想模型，并不是一件容易的事情.它要求建模者具有丰富的经验、较强的创造力和比较熟练的技巧.本节通过一些被简化了的问题，介绍建立线性规划模型的基本思路和基本技巧.2023/2/5901.办学规模问题【例2.16】某人准备投资1200万元办一所中学，为了考虑社会效益和经济效益，对该地区教育市场进行调查，得出一组数据，如表2.12所示.表2.12市场调查表班级班级学生数配备教师数硬件建设费（万元）教师年薪（万元）初中502.0281.2高中402.5581.6根据物价部门的有关文件，初中是义务教育阶段，收费标准适当控制，预计除书费、办公费外，初中每个学生每年可收取600元，而高中每个学生每年可收取1500元.因生源和环境等条件限制，办学规模以20～30个（含20与30）班为宜.教师实行聘任制.初、高中的教育周期均为3年.请你合理地安排招生计划，使年利润最大.问：大约经过多少年可以收回全部投资？2.6线性规划的应用2023/2/591即.于是此问题的线性规划模型为解得最优解代入中得2.6线性规划的应用解设初中编制班数为x,高中编制班数为y,又设年利润为f,（单位：万元），那么2023/2/592故学校的最优规模和招生计划分别为最优规模：初中18个班，高中12个班；招生计划：第1年初中招生6个班约300人，高中招生4个班约160人.以后每年按此计划招生.

设经过n年可收回投资.第1年利润为第2年利润为

2×11.6=23.2(万元);以后每年的利润均为34.8万元.故依题意应有解得(年).即约经过36年可以收回全部投资.2.6线性规划的应用2023/2/5932.投资问题【例2.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年底，投资的本利之和最大？2.6线性规划的应用2023/2/594【解】这是一个连续投资问题.设决策变量xij为第j年投资到第i

个项目的资金(i=1,2,3,4,分别对应于项目A,B,C,D；分别对应于投资年份),见列表2.13.表2.13投资项目投资机会项目名称

第1年年初第2年年初第3年年初ABCD2.6线性规划的应用2023/2/595下面分析每年资金的使用情况并建立线性规划模型.第1年初，有A,B两个项目，企业只能提供6万元资金，故有:.项目B不得超过5万元，有

第2年初，有A,C两个投资项目.此时第1年初投资到项目A的资金已全部收回，本利和为

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

2.6线性规划的应用于是；；2023/2/5962.6线性规划的应用第3年初，第1年初投资到项目B的资金全部收回，本利和为

;第2年初投资于项目A的资金也全部收回，本利和为以上两笔资金可供该年继续投资.第3年内还有A,D两个项目的投资，可得，而且要求

第3年底，到期把所有本利和收回.所能收回的资金有第2年初投资到项目C的本利和，第3年初投资到项目A的本利和

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

;2023/2/597将上述目标函数和约束条件整理后即可得出该问题完整的线性规划模型:求解得到最优投资方案如表2.14所示，且在第3年底收回投资的本利和最大为11.528万元.2.6线性规划的应用2023/2/598表2.14最优投资方案

投资机会

项目名称

第1年年初第2年年初第3年年初AX11=1X12=1.2X13=7.44BX21=5CX32=0DX43=22.6线性规划的应用2023/2/599配套生产计划问题【例2.18】某公司面临一个是外包协作还是自行生产的问题.该公司生产甲、乙、丙3种产品，这3种产品都要经过铸造、机加工和装配3个车间.甲、乙两种产品的铸件可以外包协作，也可以自行生产，但产品丙必须本厂铸造才能保证质量.有关情况见表2.15.该公司中可利用的总工时为：铸造8000小时、机加工12000小时和装配10000小时.为使该公司获得最大利润，甲、乙、丙3种产品应各生产多少件？甲、乙两种产品由本公司铸造多少件？外包协作铸造多少件？2.6线性规划的应用2023/2/5100表2.15某公司工时与成本数据表

产品工时与成本甲乙丙每件铸造工时（小时）5107每件机加工工时（小时）648每件装配工时（小时）322自产铸件每件成（元）354外协铸件每件成（元）56—机加工每件成本（元）213装配每件成本（元）322每件产品售价（元）2318162.6线性规划的应用2023/2/5101【解】设x1,x2,x3分别为3道工序都由该公司加工的甲、乙、丙3种产品的件数，设

x4,x5,分别为由外协铸造再由该公司加工、装配的甲、乙两种产品的件数.每件产品的利润分别如下：每件产品甲全部自制的利润=23-(3+2+3)=15(元)；每件产品甲由外协铸造，其余自制的利润=23-(5+2+3)(元)；每件产品乙全部自制的利润=18-(5+1+2)=10(元)；每件产品乙由外协铸造，其余自制的利润18-(6+1+2)=9(元)；每件产品丙的利润=16-(4+3+2)=7(元).

2.6线性规划的应用2023/2/5102建立此问题的线性规划模型如下：（铸造工时约束）（机加工工时约束）

（装配工时约束）（非负约束）经计算得结果：

故最优计划为：产品甲生产1600件，全部由该公司铸造；产品乙生产600件，由外协铸造后再由该公司加工、装配；产品丙不生产.2.6线性规划的应用2023/2/51034.人力资源分配问题【例2.19】某百货商场售货员的需求经过统计分析如表2.16所示.为了保证售货员充分休息，售货员每周工作5天，休息2天，并要求休息的2天是连续的，问：应该如何安排售货员的作息时间，既满足工作需要，又使配备的售货员人数最少？表2.16售货人员需求统计表时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六282.6线性规划的应用2023/2/5104【解】

设xj为星期j开始休息的人数（j=1,2,…，７，分别对应星期一、二、三、四、五、六、日）.目标是要求售货员的总数最少.因为每个售货员都工作5天，休息2天，所以只要计算出连续休息2天的售货员数，也就计算出了售货员的总数.这里可以把连续休息2天的售货员按照开始休息的时间分成7类，各类的人数分别为xj

（j=1,2,…，７），即有目标函数：再按照每天所需售货员的人数写出约束条件.例如星期日需要28人，商场中的全体售货员中除了星期六和星期日开始休息的人外都应该上班，即有约束条件2.6线性规划的应用2023/2/5105同理有因xj

（j=1,2,…，７）表示人数，故有

xj

≥０j=1,2,…，７），且为整数2.6线性规划的应用综上得问题的线性规划模型为：2023/2/51062.6线性规划的应用计算结果：也就是说该商场至少需要售货员36人.他们的的休息安排为：星期一12人；星期三11人；星期五5人；星期日8人.2023/2/51075.应用案例【例2.20】刹车用的气泵年度生产计划.（1）问题描述某厂生产刹车用的气泵，产品类型有“东风1”、“东风2”、“东风3”、“东风4”、“东风5”、“东风6”及其配件，其中“东风4”、“东风5”、“东风6”3种型号是新产品.尚未大量生产.为了提高质量，改进性能，降低成本，厂里决定生产“东风4”250台，每台盈利30元；生产“东风5”7000台，每台盈利89元；生产“东风6”1000台，每台亏损7.5元.这3种型号产品的产量不作为最优生产计划的决策变量.由于“东风1”、“东风2”、“东风3”及配件为畅销产品，以这4种产品的产量作为决策变量.该厂各种产品的利润、生产条件等统计资料如表2.17～表2.20所示.2.6线性规划的应用2023/2/5108表2.17年计划产量、成本、利润统计表产品指标东风-1东风-2东风-3配件东风-4东风-5东风-6年计划产量（台）1100015000240001500025070001000销售收入（元/台）416.4201.6317082.84成本（元/台）314.49153.63133.0945.55利润（元/台）85.4533.7724.9931.5430897.5税金（元/台）16.4614.2311.925.75

表2.18年原材料、燃料、动力供应情况表（单位：吨）煤焦碳生铁钢材铝材铜材电（万度）柴油汽油6021074.12189.61369.149.1435.81245.5285542.6线性规划的应用2023/2/5109

表2.19单位产品原材料、燃料、动力消耗统计表（单位：kg）产品消耗量资源东风-1东风-2东风-3配件东风-4东风-5东风-6煤15.198.41.48715焦碳17.1124.9516.714.6410.9214.03生铁34.8850.8634.0429.8422.2828.6钢材39.86.142.990.62.9212.76.26铝材0.0740.0070.0133.1850.01620.01460.016铜材0.1440.3620.370.03050.0040.012电（度）6337346353042柴油1.21.210.210.91.3汽油10.90.900.90.812.6线性规划的应用2023/2/5110表2.20各车间单位产品占用工时统计表（单位：分钟）产品

加工时间车间东风-1东风-2东风-3配件东风-4东风-5东风-6全年提供最大工时数金一281.5940.63129.0674请外单位加工1554.988419360金二69.378.2522.6812.8826.798.053572620金三60.5883.6576.3532.2254165872830金四90.73177.19167.7857832600铸工1140.5120.967.216.12134540锻工1460.736.5102856750铆焊43.569.642.914.15899068热处理31.477.7222.3453.7221982320组装173.5146.5146.58613550146121042002.6线性规划的应用2023/2/5111由表2.19可以计算出完成“东风4”、“东风5”和“东风6”生产任务所消耗的各种资源的数量.如消耗煤的量：（8250+77000+151000）kg=66000kg.再由表2.18知，(60200066000)kg=536000kg才是用于生产“东风1”、“东风2”、“东风3”及“配件”的煤的约束量，其余资源的约束量类推.它们的约束和总量见表2.21.表2.21原材料、燃料、动力的约束量和总量

约束量资源可用的量总量煤536000602000焦碳9799701074100生铁19975802189600钢材1343209.751369100铝材49017.7549140铜材35762.37535810电（度）21944502455200柴油7715085000汽油47175540002.6线性规划的应用2023/2/5112同样由表2.20可以计算出各车间可用于生产“东风-1”、“东风-2”、“东风-3”及配件的约束量，见表2.22.表2.22工时的约束量和总量（单位：分钟）约束量车间量总量金一82593808419360金二32876703572620金三54788305872830金四77976007832600铸工20680402134540锻工28467502856750铆焊58949685899068热处理19344201982320组装10874450121042002.6线性规划的应用2023/2/5113（2）建立数学模型根据以上资料，建立使该厂年总利润最大的数学模型.设产品“东风-1”、“东风-2”、“东风-3”及配件的产量依次为X1,X2,X3,X4.目标函数：约束条件组：煤的约束：焦炭的约束：生铁的约束：钢材的约束：铝材的约束：铜材的约束：2.6线性规划的应用2023/2/5114电力的约束:柴油的约束：汽油的约束：金一车间的工时约束：金二车间的工时约束:金三车间的工时约束：金四车间的工时约束：铸工车间的工时约束：锻工车间的工时约束：铆焊车间的工时约束：热处理车间的工时约束：组装车间的工时约束:非负约束：xj≥0(j=1,2,3,4),且为整数.2.6线性规划的应用2023/2/5115线性规划模型为

且为整数.2.6线性规划的应用2023/2/5116（3）用WinQSB软件求解：调用WinQSB中的“LinearandIntegerProgrem”子程序（该子程序使用的详细说明见本章§2.7），填写相应数据如图2.6之后，点击“OK”健得到表2.23.再填写线性规划模型中的数据如表2.24.图2.62.6线性规划的应用2023/2/5117表2.232.6线性规划的应用2023/2/5118表2.242.6线性规划的应用2023/2/5119（4）计算结果：计算结果见表2.25.2.6线性规划的应用2023/2/5120最优解为最优值为显然,计算结果不符合实际要求,因为气泵的台数应为整数.因此,我们应改用整数规划方法计算，数据操作如图2.7.点击“”健得到一表，在其上填写线性规划模型中的数据，见表2.26.特别注意最后一行与表2.24的区别.计算结果见表2.27.2.6线性规划的应用2023/2/51212.6线性规划的应用2023/2/51222.6线性规划的应用2023/2/51232.6线性规划的应用2023/2/51242.6线性规划的应用（5）结论：最优年生产计划为：生产“东风-1”22836台；生产“东风-2”18023台；生产配件14820台，而“东风-3”不宜生产.执行此计划，生产“东风-1”、“东风-2”及配件，年总利润为3027396元.由表2.17知，原计划的总利润为2519360元.最优年生产计划与原生产计划比较，在不增加任何投入的情况下，增加利润

3027396元2519360元=508036元.2023/2/5125【例2.21】年度配矿计划优化决策（1）问题的描述：某大型冶金矿山公司共有14个出矿点，年产量及各矿点矿石的平均品位（含铁量的百分比）见表2.28.按照炼铁生产要求，在矿石产出后，需按要求指定的品位值TFe进行不同品位矿石的混合配料，然后进入烧结工序.最后，将小球状的烧结球团矿送入高炉进行高温炼铁，生产出生铁.该公司要求：将这14个出矿点的矿石进行混合配矿.依据生产设备及生产工艺要求，混合矿石的平均品位TFe规定为45％.问：应如何配矿才能获得最佳效益？2.6线性规划的应用2023/2/5126表2.28年产量及各矿点矿石的平均品位（含铁量的百分比）矿点出矿量（万吨）平均品位（％）17037.162751.2531740.0042347.005342.0069.549.967151.41815.448.3492.749.08107.640.221113.552.71122.756.92131.240.72147.250.202.6线性规划的应用2023/2/51272.6线性规划的应用2023/2/5128③目标函数：此题目要求“效益最佳”有一定的模糊性，由于配矿后的混合矿石将作为后面工序的原料而产生利润，故在初始阶段，可将目标函数选作配矿总量的最大化.通过以上分析，我们得到问题的线性规划模型2.6线性规划的应用2023/2/5129

2.6线性规划的应用（3）计算结果及分析①计算结果利用单纯形法可得出该线性规划问题的最优解为

最优值为万吨.

2023/2/51302.6线性规划的应用②分析与讨论计算结果是否可被该公司接受？回答是否定的.因为：在最优解中，除第1个采矿点有富裕外，其余13个采矿点的出矿量全部参与了配矿.

而矿点1在配矿以后尚有富余量（70－31.121）万吨＝38.879万吨，但矿点1的矿石品位仅为37.16%，属贫矿.该公司花费了大量人力、物力、财力后，在矿点1生产的贫矿中却有近39万吨矿石被闲置，而且在大量积压的同时，还会对环境造成破坏，作为该公司的负责人或公司决策者是难以接受这样的生产方案的.2023/2/5131

解决此问题的思路：经过分析后可知，在矿石品位TFe及出矿量都不可变更的情况下，只能把注意力集中在混合矿石的品位TFe要求上.不难看出，降低TFe的值，可以使更多的低品位矿石参与配矿.但TFe的值可以降低吗？在降低TFe的值使更多的贫矿入选的同时会产生什么影响？经调查，以及向实际操作人员、工程技术人员、管理人员学习、咨询，拟定了三个TFe的新值：44％，43％，42％.2.6线性规划的应用2023/2/5132

.③变动参数之后再计算，结果如下表2.29所示.矿点品位（%）出矿量（吨）TFe=45％TFe=44％TFe=43％TFe=42％最优解剩余最优解剩余最优解剩余最优解剩余137.167031.12138.87951.871825770707070340.0017170170170170447.0023230230230230542.00330303030649.969.59.509.509.509.50751.41110101010848.3415.415.4015.4015.4015.40949.082.72.702.702.702.701040.22

7.6

7.60

7.60

7.60

7.601152.7113.513.5013.5013.50013.51256.922.72.702.7002.702.71340.721.21.201.201.201.201450.207.27.207.204.532.670.776.43合计141.92138.879162.6718.13175.435.37158.1722.632.6线性规划的应用2023/2/5133(4)综合评判及结论：①TFe值取45％和44％的两个方案，均不能解决贫矿石大量积压的问题，且造成对环境的破坏，故不予以考虑.②TFe值取43％和42％的两个方案，可使贫矿石全部入选，配矿总量均在150万吨以上，且剩余的矿石皆为超过50％的富矿，可以用于生产高附加值的产品精矿粉，大大提高经济效益.因而，这两个方案对资源的利用比较合理.③经测算，按TFe值取42％的方案配矿，其混合矿