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

第9章线性规划方法及其应用1/4/20231第9章线性规划方法及其应用12/29/20221线性规划（LinearProgramming）作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益。因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。1/4/20232线性规划（LinearProgramming）作为运筹学的

1、康托洛维奇生产组织与计划中的数学方法,一本小册子，1939;2、康托洛维奇“最佳资源利用的经济计算”——1942完成、1959发表的著作；3、自1947年丹兹格（G.B.Dantzing）提出求解线性规划问题的一般方法--单纯形法之后，线性规划在理论上趋于成熟，应用日益广泛与深入；

随着电子计算机的发展和计算速度的不断提高，其适用的领域更加广泛，它已成为必不可少的重要手段之一。1/4/202331、康托洛维奇生产组织与计划中的数学方法,一

4、1975年库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获诺贝尔经济学奖；5、冯•诺伊曼和摩根斯坦1944年发表的

《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论。1/4/202344、1975年库伯曼斯(Koopmans)因线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。最优化/运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划的基础是线性变换。1/4/20235线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容1/4/20236数非线性规划整数规划动态规划学多目标规划双层规划组最优计数问9.1线性规划是什么9.2建立线性规划模型的一般步骤9.3线性规划问题的图解法9.4线性规划问题解的性质9.5解线性规划问题的单纯形法9.6线性规划的应用1/4/202379.1线性规划是什么12/29/202279.1线性规划是什么1/4/202389.1线性规划是什么12/29/202289.1线性规划是什么我们先通过几个实际问题来认识什么是线性规划.【例9.1】

某企业生产三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表9.1所示.表9.1企业生产数据表1.利润最大化问题1/4/202399.1线性规划是什么我们先通过几个实际问题来认识什么是线9.1线性规划是什么试问：该企业怎样安排生产才会使每天的利润最大？解设该企业每天生产产品的数量分别为（单位：吨），则总利润的表达式为我们希望在现有资源条件下总利润最大.现有资源的限制为（原料甲的限制）

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

1/4/2023109.1线性规划是什么试问：该企业怎样安排生产才会使每天的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千元/日.

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

注本章的数学模型均可用软件求解。

2.成本最小化问题【例9.2】某钢铁厂熔炼一种新型不锈钢，需要4种合金为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表9.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料各多少吨，能够使成本最小？9.1线性规划是什么1/4/202314模型中9.1线性规划是什么下料问题的一般描述：已知有一批原材料，每根长度为L，由于生产的需要，要求截出规格分别为的零件根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例9.4的建模过程列出此一般问题的数学模型.总之，类似例9.1、9.2的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的共同点，即每一个问题都用一组决策变量来表示某一方案，追求的目标可以用关于决策变量的线性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量的线性等式或不等式表示.

1/4/2023159.1线性规划是什么下料问题的一般描述：已知有一批原材料9.1线性规划是什么这类问题所构成的数学模型,称为线性规划模型.有时也直接将线性规划模型称为线性规划问题.针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案。1/4/2023169.1线性规划是什么这类问题所构成的数学模型,称为线性规9.2建立线性规划模型的一般步骤1/4/2023179.2建立线性规划模型的12/29/2022179.2建立线性规划模型的一般步骤从§9.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步理解要解决的问题.搞清在什么条件下追求什么目标.第2步定义决策变量.每一个问题都用一组决策变量来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的.第3步确定约束条件.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.第4步列出目标函数.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.1/4/2023189.2建立线性规划模型的一般步骤从§9.1节中对实际问题9.2建立线性规划模型的一般步骤对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.线性规划的一般形式可表示为：1/4/2023199.2建立线性规划模型的一般步骤对于一些比较复杂的线性规9.2建立线性规划模型的一般步骤其中称为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的为常数.当要求决策变量均为整数时，称（9.1）为纯整数线性规划问题；当要求决策变量均取0或1时，称（9.1）为整数线性规划问题.当要求决策变量既取实数又取整数时，称（9.1）为混合整数线性规划问题.我们把满足所有约束条件的解称为线性规划问题（9.1）的可行解.全体可行解的集合称为问题（9.1）的可行域,记为.使目标函数值最大（或最小）的可行解称为该线性1/4/2023209.2建立线性规划模型的一般步骤其中称9.2建立线性规划模型的一般步骤规划问题的最优解，与此最优解相应的目标函数值称为最优目标函数值，简称最优值.因此，若记，求解线性规划问题（9.1），本质上就是寻找一点，使得均满足不等式【例9.3】某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备（台时），A、B两种原材料的消耗以及资源的限制情况如表2.11所示.问：该工厂应分别生产多少甲产品和乙产品才能使工厂获利最大？1/4/2023219.2建立线性规划模型的一般步骤规划问题的最优解，与9.2建立线性规划模型的一般步骤解首先，确定决策变量.工厂目前要决策的是甲产品和乙产品的生产量，可以分别用变量来表示.由于它们表示产品产量，所以只取非负数.其次，根据问题的限制条件，列出表示约束条件的线性不等式：1/4/2023229.2建立线性规划模型的一般步骤解首先，确定决策变量9.2建立线性规划模型的一般步骤，（非负限制）

，（台时数限制）

，（原材料限制）

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

【例9.4】某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？1/4/2023269.2建立线性规划模型的一般步骤【例9.4】某医院9.2建立线性规划模型的一般步骤解设为时段开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：1/4/2023279.2建立线性规划模型的一般步骤解设为时段开9.2建立线性规划模型的一般步骤计算最优解为： 故该医院需雇用150名护士，最佳安排见表9.10所示.1/4/2023289.2建立线性规划模型的一般步骤计算最优解为：9.2建立线性规划模型的一般步骤线性规划的一般形式，可行解、最优解等概念线性规划问题建模过程：第1步理解要解决的问题。第2步定义决策变量。第3步确定约束条件。

第4步列出目标函数。

1/4/2023299.2建立线性规划模型的一般步骤线性规划的一般形式，可行9.3线性规划问题的图解法1/4/2023309.3线性规划问题的图解法12/29/2022309.3线性规划问题的图解法1.图解法

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

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

1/4/202332图解法的步骤可概括为：12/29/2022329.3线性规划问题的图解法

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

1/4/2023339.3线性规划问题的图解法12/29/2022339.3线性规划问题的图解法解先画出线性规划的可行域如图9.1阴影部分.再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点.最后求解线性方程组

求解得到点的坐标，从而得到最优解，最大值1/4/2023349.3线性规划问题的图解法解先画出线性规划的可行域如9.3线性规划问题的图解法1/4/2023359.3线性规划问题的图解法12/29/2022359.3线性规划问题的图解法【例9.6】用图解法求解线性规划问题解先画出线性规划的可行域，如图9.2阴影部分.

1/4/2023369.3线性规划问题的图解法【例9.6】用图解法求解线性规9.3线性规划问题的图解法1/4/2023379.3线性规划问题的图解法12/29/2022379.3线性规划问题的图解法再画出目标函数等值线，朝着增大纵截距的方向平行移动等值线至点B.最后求解线性方程组

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

例9.5与例9.6中求解得到的问题的最优解是惟一的，但对一般线性规划问题，求解结果还可能出现其他情况.1/4/2023389.3线性规划问题的图解法再画出目标函数等值线，朝着增大9.3线性规划问题的图解法2.线性规划解的其他情况（1）多重最优解的情况

【例9.9】若将例9.5中的目标函数变为，则代表目标函数的直线平移到最优位置后将和直线重合.此时，不仅顶点A，B都代表了最优解，而且线段上AB的所有点都代表了最优解.这个线性规划问题有无穷多最优解，这些最优解都对应着相同的最大值1/4/2023399.3线性规划问题的图解法2.线性规划解的其他情况12MAX1/4/202340MAX12/29/2022409.3线性规划问题的图解法（2）无界解的情况（3）无可行解的情况1/4/2023419.3线性规划问题的图解法（2）无界解的情况（3）无可行9.3线性规划问题的图解法（2）无界解的情况

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

【例9.11】对线性规划问题由图2.3(b)可以看出，同时满足所有约束条件的点不存在，即可行域为空集，也就是没有可行解，故不存在最优解.1/4/2023439.3线性规划问题的图解法（3）无可行解的情况由图2.39.3线性规划问题的图解法当根据实际问题建立的线性规划模型的求解结果出现（2）,（3）两种情况时，一般说明建模有错误.前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意.下面再给出一个求目标函数最小化的线性规划问题.【例9.12】求解线性规划1/4/2023449.3线性规划问题的图解法当根据实际问题建立的线性规划模9.3线性规划问题的图解法解画出此线性规划问题的可行域，如图中的阴影部分.目标函数，它在坐标平面上可表示为以f为参数，以-2/4为斜率的一组等值线.当等值线移动到B点时，目标函数在可行域中取最小值.B点的坐标可以从线性方程组中求出，为.这就是所求线性规划问题的最优解，且.1/4/2023459.3线性规划问题的图解法解画出此线性规划问题的可行9.3线性规划问题的图解法1/4/2023469.3线性规划问题的图解法12/29/2022469.3线性规划问题的图解法1.通过图解法了解线性规划有几种解的形式2.作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动1/4/2023479.3线性规划问题的图解法1.通过图解法了解线性规划有几9.4线性规划问题解的性质1/4/2023489.4线性规划问题解的性质12/29/2022481.线性规划问题的标准形

前面曾给出了线性规划问题的一般形式，可以看出，其中有的要求目标函数最大化，有的要求目标函数最小化；约束条件可以是“≤”或“≥”形式的不等式，也可以是等式；决策变量一般是非负约束，但也允许在范围内取值，即无约束。为了进一步研究和讨论，就需要把线性规划问题的一般形式化为统一的标准形式。9.4线性规划问题解的性质1/4/2023491.线性规划问题的标准形

前面曾给出了线性规划问题的一般形线性规划的一般形式可表示为：1/4/202350线性规划的一般形式可表示为：12/29/202250这里的标准形式有以下规定：（1）目标函数是求最大值；（2）所有约束条件均用等式表示；（3）所有决策变量均取非负数；（4）所有约束常数均为非负数.9.4线性规划问题解的性质1/4/202351这里的标准形式有以下规定：9.4线性规划问题解的性质1

于是，具有个约束条件和个决策变量的线性规划问题的标准形为：9.4线性规划问题解的性质1/4/202352于是，具有个约束条件和个决策变量的线性在约束条件

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

下，求一组未知变量（j

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

或其缩写形式为：1/4/202353在约束条件

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

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

9.4线性规划问题解的性质标准形原问题1/4/202360，9.4线性规划问题解的性质标准形原问题12/29/22.线性规划的解

可行解与最优解

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

1/4/2023612.线性规划的解12/29/202261基本解与基本可行解

在线性规划问题中，将约束方程组的m×n阶矩阵A写成由n个列向量组成的分块矩阵1/4/202362基本解与基本可行解12/29/202262如果B是A中的一个m阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称为基向量，与基向量相对应的向量为基变量，而其余的变量为非基变量。

1/4/202363如果B是A中的一个m阶的非奇异子阵，则称B为如果是方程组的解,则就是方程组的一个解，它称之为对应于基B的基本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。1/4/202364如果线性规划问题的以上几个解的关系，可用下图来描述：1/4/202365线性规划问题的以上几个解的关系，可用下图来描述：12/29/【定义9.1】如果集合K中任意两点s,t之间连线上所有的点都是集合K中的点，即对于任意的，都有，则称K为凸集.例如图9.5中（a）,（b）,（c）为凸集，而（d）,（e）不是凸集.

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

图9.5凸集与非凸集示例9.4线性规划问题解的性质1/4/202366【定义9.1】如果集合K中任意两点s,t之间连线上所有的【定理9.1

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

】若可行域非空有界，则线性规划问题的最优值一定可以在可行域的某个顶点上达到.9.4线性规划问题解的性质1/4/202367【定理9.1】线性规划问题的可行域是一个凸集.这两个定理【定义9.2

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

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

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

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

1/4/202374将此方程组的系数及常数项b列成一个数表，即.9.5解线性（3）在负检验数中选绝对值最大的负数（即7），在对应的列中，将该列中的正数分别去除对应的常数项，选择比值最小者所对应的元素为主元（称为最小比值原则）.在这里然后用矩阵的初等行变换，将主元化为1，把同列的其他元素化为0.这一过程如下：将矩阵

可知位于第2行、第3列的元素3为主元，标为,9.5解线性规划问题的单纯形法1/4/202375（3）在负检验数中选绝对值最大的负数（即7），在对应的列中的第2行乘以1/3，得

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

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

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

1/4/2023809.5解线性规划问题的单纯形法所以最优解及最优值分别为【【解】引入松弛变量，化为标准形

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

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

某个检验数大于0且该检验数所在列中所有元素小或等于，则线性规划具有无界解。1/4/2023849.5解线性规划问题的单纯形法1.判断基本可行解.有3种9.6线性规划的应用1/4/2023859.6线性规划的应用12/29/2022859.6线性规划的应用

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

2×11.6=23.2(万元);以后每年的利润均为34.8万元.故依题意应有解得(年).即约经过36年可以收回全部投资.9.6线性规划的应用1/4/202389故学校的最优规模和招生计划分别为设经过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线性规划的应用1/4/2023902.投资问题9.6线性规划的应用12/29/20229【解】这是一个连续投资问题.设决策变量xij为第j年投资到第i个项目的资金(i=1,2,3,4,分别对应于项目A,B,C,D；分别对应于投资年份),见列表9.13.表9.13投资项目投资机会项目名称第1年年初第2年年初第3年年初ABCD9.6线性规划的应用1/4/202391【解】这是一个连续投资问题.设决策变量xij为第j年投资下面分析每年资金的使用情况并建立线性规划模型.第1年初，有A,B两个项目，企业只能提供6万元资金，故有:.项目B不得超过5万元，有

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

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

9.6线性规划的应用于是；；1/4/202392下面分析每年资金的使用情况并建立线性规划模型..项目B不得超9.6线性规划的应用第3年初，第1年初投资到项目B的资金全部收回，本利和为;第2年初投资于项目A的资金也全部收回，本利和为以上两笔资金可供该年继续投资.第3年内还有A,D两个项目的投资，可得，而且要求

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

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

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

项目名称第1年年初第2年年初第3年年初AX11=1X12=1.2X13=7.44BX21=5CX32=0DX43=29.6线性规划的应用1/4/202395表9.14最优投资方案投资机会3.人力资源分配问题【例9.19】某百货商场售货员的需求经过统计分析如表9.16所示.为了保证售货员充分休息，售货员每周工作5天，休息2天，并要求休息的2天是连续的，问：应该如何安排售货员的作息时间，既满足工作需要，又使配备的售货员人数最少？表9.16售货人员需求统计表时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六289.6线性规划的应用1/4/2023963.人力资源分配问题表9.16售货人员需求统计表时间所需【解】设xj为星期j开始休息的人数（j=1,2,…，７，分别对应星期一、二、三、四、五、六、日）.目标是要求售货员的总数最少.因为每个售货员都工作5天，休息2天，所以只要计算出连续休息2天的售货员数，也就计算出了售货员的总数.这里可以把连续休息2天的售货员按照开始休息的时间分成7类，各类的人数分别为xj（j=1,2,…，７），即有目标函数：再按照每天所需售货员的人数写出约束条件.例如星期日需要28人，商场中的全体售货员中除了星期六和星期日开始休息的人外都应该上班，即有约束条件9.6线性规划的应用1/4/202397【解】设xj为星期j开始休息的人数（j=1,2,…，７，同理有因xj（j=1,2,…，７）表示人数，故有xj≥０j=1,2,…，７），且为整数9.6线性规划的应用综上得问题的线性规划模型为：1/4/202398同理有因xj（j=1,2,…，７）表示人数，故有9.69.6线性规划的应用计算结果：也就是说该商场至少需要售货员36人.他们的的休息安排为：星期一12人；星期三11人；星期五5人；星期日8人.1/4/2023999.6线性规划的应用计算结果：一、对偶问题的提出

线性规划的对偶原理对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。对偶思想举例在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。（1）周长一定，面积最大的矩形是正方形。（2）面积一定，周长最短的矩形是正方形。1/4/2023100一、对偶问题的提出线性规划的对偶原理对偶是什么：二、原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是

1/4/2023101二、原问题和对偶问题的关系（1）定义：若原问题是12/29则定义其对偶问题为

这两个式子之间的变换关系称为“对称形式的对偶关系”。

1/4/2023102则定义其对偶问题为这两个式子之间的变换关系称为“（2）对称形式的对偶关系的矩阵描述（D）（L）

（3）怎样从原始问题写出其对偶问题？

按照定义；记忆法则：“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”1/4/2023103（2）对称形式的对偶关系的矩阵描述（D）（L）（3）怎样例写出下面线性规划的对偶问题：

2、非对称形式的对偶关系：1/4/2023104例写出下面线性规划的对偶问题：2、非对称形式的对偶关系（1）原问题对偶问题（特点：对偶变量符号不限，系数阵转置）(特点：等式约束)1/4/2023105（1）原问题对（2）怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原始-对偶表直接写出；（3）原始-对偶表1/4/2023106（2）怎样写出非对称形式的对偶问题？12/29/202210

原问题（或对偶问题）

对偶问题（或原问题）

目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”

对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量

约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”

1/4/2023107原问题（或对偶问题）对偶问题（或原问题）目标函数练习：写出下面线性规划的对偶规划：1/4/2023108练习：写出下面线性规划的对偶规划：12/29/2022108下面的答案哪一个是正确的？为什麽？

（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）√

×

1/4/2023109下面的答案哪一个是正确的？为什麽？（原问题是极小化问题，因第9章线性规划方法及其应用1/4/2023110第9章线性规划方法及其应用12/29/20221线性规划（LinearProgramming）作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益。因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。1/4/2023111线性规划（LinearProgramming）作为运筹学的

1、康托洛维奇生产组织与计划中的数学方法,一本小册子，1939;2、康托洛维奇“最佳资源利用的经济计算”——1942完成、1959发表的著作；3、自1947年丹兹格（G.B.Dantzing）提出求解线性规划问题的一般方法--单纯形法之后，线性规划在理论上趋于成熟，应用日益广泛与深入；

随着电子计算机的发展和计算速度的不断提高，其适用的领域更加广泛，它已成为必不可少的重要手段之一。1/4/20231121、康托洛维奇生产组织与计划中的数学方法,一

4、1975年库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获诺贝尔经济学奖；5、冯•诺伊曼和摩根斯坦1944年发表的

《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论。1/4/20231134、1975年库伯曼斯(Koopmans)因线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。最优化/运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划的基础是线性变换。1/4/2023114线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容1/4/2023115数非线性规划整数规划动态规划学多目标规划双层规划组最优计数问9.1线性规划是什么9.2建立线性规划模型的一般步骤9.3线性规划问题的图解法9.4线性规划问题解的性质9.5解线性规划问题的单纯形法9.6线性规划的应用1/4/20231169.1线性规划是什么12/29/202279.1线性规划是什么1/4/20231179.1线性规划是什么12/29/202289.1线性规划是什么我们先通过几个实际问题来认识什么是线性规划.【例9.1】

某企业生产三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表9.1所示.表9.1企业生产数据表1.利润最大化问题1/4/20231189.1线性规划是什么我们先通过几个实际问题来认识什么是线9.1线性规划是什么试问：该企业怎样安排生产才会使每天的利润最大？解设该企业每天生产产品的数量分别为（单位：吨），则总利润的表达式为我们希望在现有资源条件下总利润最大.现有资源的限制为（原料甲的限制）

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

1/4/20231199.1线性规划是什么试问：该企业怎样安排生产才会使每天的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千元/日.

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

注本章的数学模型均可用软件求解。

2.成本最小化问题【例9.2】某钢铁厂熔炼一种新型不锈钢，需要4种合金为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表9.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料各多少吨，能够使成本最小？9.1线性规划是什么1/4/2023123模型中9.1线性规划是什么下料问题的一般描述：已知有一批原材料，每根长度为L，由于生产的需要，要求截出规格分别为的零件根.问：如何截取使得总用料最省？即要求制定一个既能满足生产的需要，又使得使用的原材料数量最少的下料方案.同样可以仿照例9.4的建模过程列出此一般问题的数学模型.总之，类似例9.1、9.2的实际问题很多，而且形式多种多样.通过这些问题，我们可以看到上述各种问题的共同点，即每一个问题都用一组决策变量来表示某一方案，追求的目标可以用关于决策变量的线性函数刻画，或是最大化或是最小化，而要达到目标的条件又都有一定的限制，每个限制条件均可由关于决策变量的线性等式或不等式表示.

1/4/20231249.1线性规划是什么下料问题的一般描述：已知有一批原材料9.1线性规划是什么这类问题所构成的数学模型,称为线性规划模型.有时也直接将线性规划模型称为线性规划问题.针对这类模型,可以用根据数学理论设计的计算机软件，如软件求解，得出实际问题需要的答案。1/4/20231259.1线性规划是什么这类问题所构成的数学模型,称为线性规9.2建立线性规划模型的一般步骤1/4/20231269.2建立线性规划模型的12/29/2022179.2建立线性规划模型的一般步骤从§9.1节中对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步理解要解决的问题.搞清在什么条件下追求什么目标.第2步定义决策变量.每一个问题都用一组决策变量来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的.第3步确定约束条件.用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件.第4步列出目标函数.按实际问题的不同，用决策变量的线性函数最大化或最小化形式写出所要追求的目标，称之为目标函数.1/4/20231279.2建立线性规划模型的一般步骤从§9.1节中对实际问题9.2建立线性规划模型的一般步骤对于一些比较复杂的线性规划问题，为了便于建立其数学模型，常需要把反映问题的背景数据资料用表格形式归类综合，以揭示各个量之间的内在联系.线性规划的一般形式可表示为：1/4/20231289.2建立线性规划模型的一般步骤对于一些比较复杂的线性规9.2建立线性规划模型的一般步骤其中称为目标函数，为决策变量，为约束常数，后面的式子为约束条件.这里的为常数.当要求决策变量均为整数时，称（9.1）为纯整数线性规划问题；当要求决策变量均取0或1时，称（9.1）为整数线性规划问题.当要求决策变量既取实数又取整数时，称（9.1）为混合整数线性规划问题.我们把满足所有约束条件的解称为线性规划问题（9.1）的可行解.全体可行解的集合称为问题（9.1）的可行域,记为.使目标函数值最大（或最小）的可行解称为该线性1/4/20231299.2建立线性规划模型的一般步骤其中称9.2建立线性规划模型的一般步骤规划问题的最优解，与此最优解相应的目标函数值称为最优目标函数值，简称最优值.因此，若记，求解线性规划问题（9.1），本质上就是寻找一点，使得均满足不等式【例9.3】某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备（台时），A、B两种原材料的消耗以及资源的限制情况如表2.11所示.问：该工厂应分别生产多少甲产品和乙产品才能使工厂获利最大？1/4/20231309.2建立线性规划模型的一般步骤规划问题的最优解，与9.2建立线性规划模型的一般步骤解首先，确定决策变量.工厂目前要决策的是甲产品和乙产品的生产量，可以分别用变量来表示.由于它们表示产品产量，所以只取非负数.其次，根据问题的限制条件，列出表示约束条件的线性不等式：1/4/20231319.2建立线性规划模型的一般步骤解首先，确定决策变量9.2建立线性规划模型的一般步骤，（非负限制）

，（台时数限制）

，（原材料限制）

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

【例9.4】某医院护士24小时值班，每次值班8小时.不同时段需要的护士人数不等.据统计，各时段所需护士的最少人数如表2.9所示.如何安排才能做到安排最少的护士就能满足工作的需要？1/4/20231359.2建立线性规划模型的一般步骤【例9.4】某医院9.2建立线性规划模型的一般步骤解设为时段开始上班的人数，.目标是要求护士的总数最少.因为每个护士都工作8小时，即连续工作2个时段后休息，所以问题的线性规划模型为：1/4/20231369.2建立线性规划模型的一般步骤解设为时段开9.2建立线性规划模型的一般步骤计算最优