第二章线性规划内容提要：线性规划的基本概念两变量线性规划的图解法线性规划的基本理论单纯形法线性规划应用举例
第二章 线 性 规 划 内容提要： 线性规划的基本理论 单纯形法 线性规划应用举例 两变量线性规划的图解法 线性规划的基本概念
第二章线性规划线性规划是运筹学中应用最广泛的方法之一。自从1947年G.B.Dantzig发明了求解线性规划的单纯形方法后，线性规划已被广泛地应用于解决经济管理和工业生产中遇到的实际问题。曾经有人进行过调查，在世界500家最大的企业中，有85%的企业使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用已为使用者节约了数以亿万
第二章 线性规划 线性规划是运筹学中应用最广泛的方法 之一。自从1947年G.B.Dantzig发明了求解线 性规划的单纯形方法后，线性规划已被广泛 地应用于解决经济管理和工业生产中遇到的 实际问题。曾经有人进行过调查，在世界500 家最大的企业中，有85％的企业使用过线性 规划解决经营管理中遇到的复杂问题。线性 规划的使用已为使用者节约了数以亿万
计的资金。线性规划实质上是解决稀缺资源在有竞争的使用方向中如何进行最优分配的问题。这类最优分配问题大部分是从经营管理中引出的，例如：产品的最优组合，生产排序，最优投资方案，人力资源分配等。在这类问题中，一个共性的问题是一些稀缺或有限的资源必须被分配到一些指定的生产活动中去，而这些资源的使用会伴随着费用或效益的发生。线性规划可
计的资金。 线性规划实质上是解决稀缺资源在有竞争的 使用方向中如何进行最优分配的问题。这类最 优分配问题大部分是从经营管理中引出的，例 如：产品的最优组合，生产排序，最优投资方 案，人力资源分配等。在这类问题中，一个共 性的问题是一些稀缺或有限的资源必须被分配 到一些指定的生产活动中去，而这些资源的使 用会伴随着费用或效益的发生。线性规划可
用于合理分配这些资源，并使付出的费用最小或获得的收益最大。在本章中我们将首先介绍什么是线性规划问题，线性规划问题的数学表达式，简单线性规划问题的图解法等线性规划的基本概念，然后介绍线性规划的基本理论和求解线性规划的单纯形方法。2.1线性规划的基本概念
用于合理分配这些资源，并使付出的费用最 小或获得的收益最大。 在本章中我们将首先介绍什么是线性规 划问题，线性规划问题的数学表达式，简单 线性规划问题的图解法等线性规划的基本概 念，然后介绍线性规划的基本理论和求解线 性规划的单纯形方法。 2.1 线性规划的基本概念
本小节介绍什么是线性规划问题，如何将实际问题转化为线性规划模型，线性规划问题的标准形式以及求解简单线性规划问题的图解法。2.1.1线性规划模型用线性规划方法解决实际问题的第一步是要将实际问题转化为线性规划模型。下面通过例子说明如何把具体问题转化为线性规划模型
本小节介绍什么是线性规划问题，如何 将实际问题转化为线性规划模型，线性规划 问题的标准形式以及求解简单线性规划问题 的图解法。 2.1.1 线性规划模型 用线性规划方法解决实际问题的第一步 是要将实际问题转化为线性规划模型。下面 通过例子说明如何把具体问题转化为线性规 划模型
线性规划模型举例一、纟例2.1生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价150元。椅子售价80元，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为180小时，油漆工工时为90小时。问该厂如何组织生产才能使每月的销售收入最大？
一、线性规划模型举例 例 2 . 1 生产计划问题 胜利家具厂生产桌子和椅子两种家具。桌子售 价150元。椅子售价80元，生产桌子和椅子需 要木工和油漆工两种工种。生产一个桌子需要 木工4小时，油漆工2小时。生产一个椅子需要 木工3小时，油漆工1小时。该厂每月可用木工 工时为180小时，油漆工工时为90小时。问该 厂如何组织生产才能使每月的销售收入最大?
解：将一个实际问题转化为线性规划模型有以下几个步骤：(1)确定决策变量：决策变量是模型要决定的未知量，也是模型最重要的参数。对简单的模型，如上例，决策变量是显而易见的。但对较复杂的问题，决策变量的定义就不那么简单了。在本例中，家具厂要确定柜子和桌子的生产数量，因此可定义：x,=生产桌子的数量，x=生产椅子的数量
解：将一个实际问题转化为线性规划模型有 以下几个步骤： (1) 确定决策变量：决策变量是模型要决定 的未知量，也是模型最重要的参数。对简单 的模型，如上例，决策变量是显而易见的。 但对较复杂的问题，决策变量的定义就不那 么简单了。在本例中，家具厂要确定柜子和 桌子的生产数量，因此可定义：x1 = 生产桌 子的数量，x2 = 生产椅子的数量
(2)确定目标函数：目标函数决定线性规划问题的优化方向，是线性规划模型的重要组成部分。很明显，家具厂的目标是使销售收入最大，更具体一点，是使两种产品售价与产量的乘积的总和最大，因此目标函数可写为：max z = 150x, + 80x,(3)确定约束方程：如果家具厂可以随意选择生产桌子和椅子的数量，他们的销售收入可以随意大。而这实际是不可能的，因为任何
(2) 确定目标函数：目标函数决定线性规划问 题的优化方向，是线性规划模型的重要组成 部分。很明显，家具厂的目标是使销售收入 最大，更具体一点，是使两种产品售价与产 量的乘积的总和最大，因此目标函数可写为： max z = 150x1 + 80x2 (3) 确定约束方程：如果家具厂可以随意选择 生产桌子和椅子的数量，他们的销售收入可 以随意大。而这实际是不可能的，因为任何
生产都会受到种种客观条件的限制。一个正确的模型应通过约束方程来反映这些客观条件。本例中的限制条件是每月可用的木工和油漆工的工时不能超过180和90小时。这两个条件可由以下方程表示：4x, + 3x2 ≤1802xi + x2 ≤ 90(4)变量取值限制：一般情况下，决策变量只取正值（非负值）。因此，模型中应有变
生产都会受到种种客观条件的限制。一个正 确的模型应通过约束方程来反映这些客观条 件。本例中的限制条件是每月可用的木工和 油漆工的工时不能超过180和90小时。这两 个条件可由以下方程表示： 4x1 + 3x2 180 2x1 + x2 90 (4) 变量取值限制：一般情况下，决策变量 只取正值（非负值）。因此，模型中应有变
量的非负约束。在本例中，非负约束为x,≥0,x,≥0。将以上几部分结合起来就得到反映家具厂经营活动的完整的数学模型：max z = 150x, + 80x2s.t.4x, + 3x2≤ 180(2.1)2xi + x2 ≤ 90X,X, ≥0
量的非负约束。在本例中，非负约束为x1 0， x2 0。 将以上几部分结合起来就得到反映家具厂经 营活动的完整的数学模型： max z = 150x1+ 80x2 s.t. 4x1 + 3x2 180 2x1 + x2 90 (2.1) x1 , x2 0