上页上页下页下页返回返回第第 一一 章章 线线 形形 规规 划划本章学习重点本章学习重点线性规划是运筹学中比较成熟的一个分支线性规划是运筹学中比较成熟的一个分支 ，它具有成熟而有效的求解方法，可以借助于，它具有成熟而有效的求解方法，可以借助于 计算机进行求解，在军事、经济等领域中具有计算机进行求解，在军事、经济等领域中具有 广泛的应用。学习本章，要掌握线性规划的广泛的应用。学习本章，要掌握线性规划的数数 学模型学模型（建模以及把不同形式的线性规划问题（建模以及把不同形式的线性规划问题 化为标准形式的方法）、化为标准形式的方法）、求解方法求解方法。上页上页下页下页返回返回线性规划的地位与研究进程线性规划的地位与研究进程 作为一门科学的线性规划，最早可以追溯到作为一门科学的线性规划，最早可以追溯到2020世世 纪纪3030年代末，前苏联数学家康德洛维奇等人关于年代末，前苏联数学家康德洛维奇等人关于 生产组织和运输问题研究所作的开拓性工作。生产组织和运输问题研究所作的开拓性工作。 19471947年，美国数学家年，美国数学家G.B.DantzigG.B.Dantzig以及美国空军的以及美国空军的 SCOOPSCOOP研究小组提出了线性规划问题的一般性解法研究小组提出了线性规划问题的一般性解法 即即单纯形法单纯形法, ,奠定了线性规划的理论基础。奠定了线性规划的理论基础。5050年代年代 后，随着电子计算机的介入，线性规划的应用越后，随着电子计算机的介入，线性规划的应用越 来越普遍，在生产、管理、军事等方面发挥着重来越普遍，在生产、管理、军事等方面发挥着重 要的作用。要的作用。 线性规划目前仍然还在发展，主要是：大型线性线性规划目前仍然还在发展，主要是：大型线性 规划问题，线性规划解法研究等。规划问题，线性规划解法研究等。vv 线性规划问题的提出线性规划问题的提出 vv 线性规划的基本概念线性规划的基本概念 vv 线性规划的数学模型线性规划的数学模型 vv 线性规划问题的标准形式线性规划问题的标准形式继续继续返回返回第一节第一节 线性规划问题线性规划问题及其数学模型及其数学模型上页上页下页下页返回返回 问题的提出问题的提出 引例引例: : 生产计划问题生产计划问题上页上页下页下页返回返回产品 甲产品 乙如何安排生产如何安排生产 使利润最大使利润最大 ？上页上页下页下页返回返回什么是线性规划？什么是线性规划？在工业、农业、国防、建筑、交通运输、科研、商业在工业、农业、国防、建筑、交通运输、科研、商业 等各种活动中，常常要求对资源进行统一分配、全面规划等各种活动中，常常要求对资源进行统一分配、全面规划 和合理调度，以便从各种可能安排方案中找出最优的计划和合理调度，以便从各种可能安排方案中找出最优的计划 或设计，用以指导生产。在这类问题中，一方面有期望达或设计，用以指导生产。在这类问题中，一方面有期望达 到最优要求的目标（例如希望产值最高或消耗最少），另到最优要求的目标（例如希望产值最高或消耗最少），另 一方面又要受到一定条件的限制（例如人力、物力、财力一方面又要受到一定条件的限制（例如人力、物力、财力 的限制），如何安排才能使成效最高，消耗既定资源取得的限制），如何安排才能使成效最高，消耗既定资源取得 的收益最大，或达到既定收益所消耗的资源最少。这可以的收益最大，或达到既定收益所消耗的资源最少。这可以 借助借助线性规划（线性规划（Linear ProgrammingLinear Programming，LPLP）来解决。来解决。上页上页下页下页返回返回线性规划研究的内容线性规划研究的内容 在现有的资源条件下，如何充分利用资在现有的资源条件下，如何充分利用资 源，使任务或目标完成得最好（求极大源，使任务或目标完成得最好（求极大 化问题）。化问题）。 在给定目标下，如何以最少的资源消耗在给定目标下，如何以最少的资源消耗 ，实现这个目标（求极小化问题）。，实现这个目标（求极小化问题）。上页上页下页下页返回返回是问题中要确定的未知量，是问题中要确定的未知量， 表明规划中的用数量表示的表明规划中的用数量表示的 方案、措施，可由决策者决方案、措施，可由决策者决 定和控制。定和控制。 第第1 1步步- -确定决策变量确定决策变量 设设 甲的产量甲的产量 乙的产量乙的产量上页上页下页下页返回返回Max Max Z Z = = x x1 1+ + x x2 2决策变量决策变量第第2 2步步 - -定义目标函数定义目标函数 利润利润上页上页下页下页返回返回Max Max Z Z = 2 = 2 x x1 1+ 3 + 3 x x2 2系数系数第第2 2步步 - -定义目标函数定义目标函数上页上页下页下页返回返回对我们有对我们有 何限制何限制? ?上页上页下页下页返回返回第第3 3步步 - -表示约束条件表示约束条件x x1 1+ 2 + 2 x x2 2 8 8 4 4 x x1 1 16 164 4 x x2 2 12 12x x1 1、 x x2 2 0 0上页上页下页下页返回返回该计划的数学模型该计划的数学模型目标函数目标函数 Max Max Z Z = 2 = 2x x1 1+ 3 + 3x x2 2约束条件约束条件 x x1 1+ 2 + 2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12x x1 1、 x x2 2 0 0x x1 1 x x2 2上页上页下页下页返回返回 决策变量（决策变量（Decision variablesDecision variables） 目标函数（目标函数（Objective functionObjective function） 约束条件（约束条件（Constraint conditionsConstraint conditions） 可行域（可行域（Feasible region)Feasible region) 最优解（最优解（Optimal solution)Optimal solution) 基本概念基本概念问题中要确定的未知量，表问题中要确定的未知量，表 明规划中的用数量表示的方明规划中的用数量表示的方 案、措施，可由决策者决定案、措施，可由决策者决定 和控制。和控制。它是决策变量的函数它是决策变量的函数指决策变量取值时受到的指决策变量取值时受到的 各种资源条件的限制，通各种资源条件的限制，通 常表达为含决策变量的等常表达为含决策变量的等 式或不等式。式或不等式。满足约束条件的决满足约束条件的决 策变量的取值范围策变量的取值范围可行域中使目标可行域中使目标 函数达到最优的函数达到最优的 决策变量的值决策变量的值上页上页下页下页返回返回线性规划问题的共同特征线性规划问题的共同特征 一组决策变量一组决策变量X X表示一个方案表示一个方案, ,一般一般X X大大 于等于零。于等于零。 约束条件是线性等式或不等式。约束条件是线性等式或不等式。 目标函数是线性的。目标函数是线性的。 求目标函数最大求目标函数最大 化或最小化化或最小化上页上页下页下页返回返回例例2(2(书书) )某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品 甲需用资源甲需用资源A 3A 3吨，资源吨，资源B 4mB 4m3 3；制成一吨产品乙；制成一吨产品乙 需用资源需用资源A 2A 2吨，资源吨，资源B 6mB 6m3 3，资源，资源c 7c 7个单位。个单位。 若一吨产品甲和乙的经济价值分别为若一吨产品甲和乙的经济价值分别为7 7万元和万元和5 5万万 元，三种资源的限制量分别为元，三种资源的限制量分别为9090吨、吨、200m200m3 3和和210210 个单位，试决定应生产这两种产品各多少吨才能个单位，试决定应生产这两种产品各多少吨才能 使创造的总经济价值最高使创造的总经济价值最高? ?上页上页下页下页返回返回建模步骤：建模步骤： 第一步：确定决策变量第一步：确定决策变量x x1 1：生产产品甲的数量（吨）：生产产品甲的数量（吨）x x2 2：生产产品乙的数量（吨）：生产产品乙的数量（吨）上述变量为由决策者决定的未知量，称上述变量为由决策者决定的未知量，称 为为决策变量决策变量。上页上页下页下页返回返回 第二步：确定目标函数第二步：确定目标函数以以 Z Z 表示生产甲和乙两种产品各为表示生产甲和乙两种产品各为x x1 1和和x x2 2（吨）时产生的经济价值，总经济价值（吨）时产生的经济价值，总经济价值 最高的目标可表示为：最高的目标可表示为：max zmax z7 x7 x1 1十十5 x5 x2 2这就是该问题的这就是该问题的目标函数目标函数。 上页上页下页下页返回返回 第三步：确定约束条件第三步：确定约束条件本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各 个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关 系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到约束约束 条件条件。 资源资源A A限制：限制：3 x3 x1 1十十2 x2 x2 2 90 90 资源资源B B限制；限制；4 x4 x1 1十十6 x6 x2 2 200 200 资源资源C C限制：限制： 7 x7 x2 2 210210此外，产量此外，产量x x1 1和和x x2 2不能为负，只能取正值不能为负，只能取正值 非负条件：非负条件： x x1 1 0 0， x x2 2 0 0 上页上页下页下页返回返回经上述分析，可将该问题表示为：经上述分析，可将该问题表示为：max zmax z7 x7 x1 1十十5 x5 x2 23 x 3 x1 1十十2 x2 x2 2 90 904 x 4 x1 1十十6 x6 x2 2 200 2007 x 7 x2 2 210210x x1 1 0 0，x x2 2 0 0这种数学表达方式，称为该问题的一种数学模型。这种数学表达方式，称为该问题的一种数学模型。上页上页下页下页返回返回例例3 3：投资问题：投资问题某单位有一批资金用于四个工程项目的投资，某单位有一批资金用于四个工程项目的投资， 用于各工程项目时所得之净收益（投入资金的百用于各工程项目时所得之净收益（投入资金的百 分比）如下表所示：分比）如下表所示：由于某种原因，由于某种原因，决定用于项目决定用于项目A A的投资不大于的投资不大于 其它各项投资之和；而用于项目其它各项投资之和；而用于项目B B和和C C的投资不小的投资不小 于项目于项目D D的投资。的投资。试确定使该单位收益最大的投资试确定使该单位收益最大的投资 分配方案。分配方案。工程项目工程项目A AB BC CD D收益（）收益（）151510108 81212上页上页下页下页返回返回第一步：确定变量第一步：确定变量