数据、模型与决策（原书第16版）课件 第2章、线性规划引论

数据、模型与决策,第16版第2章、线性规划引论章节内容2-1 一个简单的最大化问题2-2 图解法2-3 极点和最优解2-4 Par公司问题的计算机求解2-5 一个简单的最小化问题2-6 特例2-7 线性规划的通用符号

本章小结学习目标(1of2)完成本章后，你将能够：LO2.1 确定可以在线性规划中用作目标函数或约束条件的线性数学关系。LO2.2 为线性规划问题做出一张含目标函数和约束条件的图，并找出满足约束条件的解。LO2.3 从线性规划的图形表示中确定可行域和极值点。LO2.4 使用图解法求解线性规划问题并解释结果。LO2.5 从问题的文字描述中，公式化并解释线性规划模型的目标函数和约束条件。学习目标(2of2)LO2.6 在线性规划的解中识别紧的、非紧的和冗余约束，并找到与约束条件相关的松弛/剩余变量。LO2.7 写出线性规划模型的标准形式。LO2.8 在Excel中建立线性规划模型，并使用ExcelSolver求解。LO2.9 确定并解释线性规划的最优解的情况:唯一最优解，多重最优解，不可行解，无界解。引言线性规划是一种帮助管理者制定决策的解决问题的方法。线性规划涉及在问题的数学模型仅包含线性函数时选择行动方案。所有线性规划问题的目标是某一数量的最大化或最小化。所有线性规划问题都有约束，这些约束条件限制了目标函数的取值。2-1一个简单的最大化问题Par公司高尔夫球袋业务Par公司是一个生产高尔夫器材的小型制造商，公司决定进入中高价位的高尔夫球袋市场。分销商对新产品十分感兴趣，且同意买进Par公司未来3个月内生产的全部产品。生产的每个高尔夫袋都需要以下操作：切割和印染缝制成型检查和包装Par公司约束Par公司的生产还受各个部门生产时间的限制。经过对各个生产部门工作量的研究，生产主管估计未来3个月内每个部门可用的最大生产时间分别是：切割和印染630小时缝纫600小时成型708小时检查和包装135小时会计部门考虑了生产数据、相关变动成本以及产品价格之后，得出了标准球袋和高级球袋的单位产品利润分别为10美元和9美元。2-1Par公司问题的数学表述

2-1问题模型化问题模型化或称建模，是将语言文字描述转化为数学描述的过程。全面的了解问题。描述目标。描述约束条件定义决策变量用决策变量写出目标用决策变量写出约束条件最优解是满足所有约束条件的可行解，使得目标函数值在最大化时尽可能大（或在最小化时尽可能小）。当有两个变量时，可以使用图解法求解线性规划。2-2切割和印染约束线

2-2对应切割和印染约束的可行解用阴影区域表示满足切割和印染约束条件的解。满足所有约束条件的解，被称为可行解。图中的阴影区域被称为可行解的集合，简称可行域。2-2对应缝制、定型、检查和包装约束的可行解2-2图解法求解过程可行域

最优解

2-2图解法求解最大化问题的步骤小结为每个约束条件画出可行解图形。确定出同时满足所有约束条件的解的可行域。画出目标函数线，表示在特定目标函数值下的决策变量值。沿目标函数值增长方向平移目标函数线，直到移动到可行域的边界。取得最大值的目标函数线上的可行解都是最优解。2-2松弛变量所有变量都是非负的，并且所有约束条件都是等式形式的线性规划被称为标准型。通过向“小于或等于”约束添加松弛变量，并通过从“大于或等于”约束中减去剩余变量来实现标准型。松弛和剩余变量代表约束的左侧和右侧之间的差异。松弛和剩余变量在目标函数中的系数等于0。在Par公司最优解中，缝制和检查与包装部门有120和18小时的未用时间。Max10S+9D++++s.t.+1D++++=630+++++=6001S+++++=708+++++=1352-2标准型的线性规划通常在制定线性规划问题时会添加松弛变量，以表示闲置或未用容量。未用容量不会对利润做出贡献；因此，松弛变量在目标函数中的系数为零。在添加了四个松弛变量（表示为S1、S2、S3和S4）之后，Par公司问题的数学模型变为:2-3极点与最优解可行区域的顶点被称为极点在寻找最优解时，不必评估所有可行解点线性规划问题的最优解可以在可行区域的极点找到。Par公司问题有5个可行区域的极点。Par公司问题的最优解位于极点③。2-4计算机求解现在对于有成千上万个变量和约束条件的问题，用计算机求解就成了常规、可行的方法。一些领先的商业软件包,包括CPLEX、Gurobi、LINGO、MOSEK和Excel求解器。也有免费的计算机软件包可用，包括Clp（COIN-OR线性规划）、基于R语言的lpSolve软件包和基于Python的PuLPlibrary软件包。下面我们将解释为Par公司问题提供的计算机输出结果:最优解提供了7668美元的利润我们有540个标准和252个高级袋作为最优生产量缝制和检查与包装部门分别有120和18小时的未用容量2-5M&D化学公司：一个简单的最小化问题M&D化学公司生产两种用于生产肥皂和清洗剂的原材料。

M&化学公司的管理层确定A和B的总产量至少要达到350加仑。.公司的一个主要客户订购的125加仑a产品必须首先得到满足。每加仑的处理时间:产品A需要2小时产品B需要1小时生产成本为产品A每加仑2美元，产品B每加仑3美元。公司最大可用工作时间是600小时。M&D的目标是以最低的总生产成本满足要求。在添加了非负约束(A,B≥0)之后，我们得到了M&D化学品问题的以下线性规划：Max2A+3Bs.t.1A≥630产品A的需求1A+1B≥600总产量2A+1B≥708处理时间A,B≥02-5M&D化学公司问题的可行域和最优解可行域

最优解2-5图解法求解最小化问题的步骤小结画出每个约束条件的可行解。确定满足所有约束条件的可行域。画出目标函数线，表示在特定目标函数值下的决策变量值。沿目标函数值减小方向平移目标函数线，直至移动到可行域的边界。目标函数线上具有最小值的可行解即为问题的最优解。2-5剩余变量

Max2A+3B+++s.t.1A−=1251A+1B−=3502A+1B+=600≥02-6特例：多重最优解

2-6特例：无可行解无可行解是指线性规划问题，不存在满足全部约束条件的解。在图形中无可行解是指可行域，并不存在。假设管理层确定公司必须至少生产500个标准球带和360个高级球带。生产出500个标准球袋和360个高级球袋所需的资源无可行解原因可能包括：表述错误管理者的过高期望约束条件过多的问题2-6特例：无界解

2-7线性规划的通用符号我们在Par公司问题中选择了决策变量S和D，在M&D化学品问题中选择了A和B，以便于记住这些决策变量在问题中代表的内容。.这种方法对于涉及少量决策变量的线性规划效果很好，但在处理涉及大量决策变量的问题时变得困难。在线性规划问题中，更加通用的符号是带有下标的x

在Par公司例子中，我们可以将决策变量定义为：

x1=标准球袋的数量

x2=高级球袋的数量

使用这种变量命名方法时的一个缺点是我们不能够轻松地识别出变量在数学模型中所代表的含义

如果模型中包含大量的决策变量，使用这种方法命名会相对比较容易。本章小结我们对如下两个线性规划问题进行了建模:Par行数学建模的过程中，我们给出了线性规划模型的一公司最大化问题和M&D化学公司的最小化问题。

对这两个问题，我们给出了图解法的求解过程，并将不同软件包的求解结果展示在表格中。线性规划模型是具有如下特点的数学模型。求解最大化或是最小化的线性目标函数。存在线性约束集合。满足非负约束的决策变量。松弛变量被用来将小于等于形式的约束条件转变为等于形