运筹学1线性规划与单纯形法

运筹学1线性规划与单纯形法

第一章

线性规划及单纯形法

目 录1.1 线性规划问题及其数学模型

1.2 线性规划解的概念、性质及图解法1.3 单纯形法

1.4 初始可行基的求法-人工变量法1.5 线性规划问题的计算机求解

1.6 线性规划应用举例

运筹学1线性规划与单纯形法

本章重点:(1)掌握线性规划数学模型的基本特征和标准形式， 以及线性规划问题数学模型的建立方法，学会用 图解法求解简单的线性规划问题。 (2)理解线性规划问题的解的概念，了解线性规划的 基本理论。 (3)了解单纯形表的构成，熟练掌握运用单纯形法求 解线性规划问题。 (4)掌握人工变量法(包括大M法和两阶段法)的计 算步骤。管理科学与工程学院

运筹学1线性规划与单纯形法

所研究的主要问题有两类:一项已确定的任务,如何统筹安排,做到以 最少的人力,物力资源去完成该项任务? 已有一定数量的人力,物力资源,如何安排 使用它们,使完成的任务 (或创造的财富,利 润) 最多?

管理科学与工程学院

运筹学1线性规划与单纯形法

第一章

线性规划及单纯形法

线性规划是运筹学的一个重要的分支。早 在20世纪30年代末就有人从运输问题开始研究

它。自1947年美国人丹捷格(G . B . Dantzig)提出了求解线性规划问题的方法 —— 单纯形法

以后，线性规划从理论上日趋完整和成熟，在应用上也及为广泛。

运筹学1线性规划与单纯形法

线性规划实质上是解决稀缺资源如何进行最优分 配的问题，这类最优分配问题大部分是从经营管理中

引出的，例如：产品的最优组合，生产排序，最优投资方案，人力资源分配等。在这类问题中，一个共性

的问题是一些稀缺资源必须被分配到一些指定的生产活动中去，而这些资源的使用会伴随着费用或效益的 发生。线性规划可用于合理分配这些资源，并使付出

的费用最小或获得的收益最大。

运筹学1线性规划与单纯形法

在本章中我们将首先介绍什么是线性规

划问题，线性规划问题的数学表达式，简单线性规划问题的图解法等线性规划的基本概

念，然后介绍线性规划的基本理论和求解线性规划的单纯形方法。

运筹学1线性规划与单纯形法

1.1 线性规划问题及其数学模型 本小节介绍什么是线性规划问题， 如何将实际问题转化为线性规划模型， 线性规划问题的标准形式。

回本章目录管理科学与工程学院

运筹学1线性规划与单纯形法

用线性规划方法解决实际问题的第一步是要将实际问题转化为线性规划模型。下面

通过例子说明如何把具体问题转化为线性规划模型。

运筹学1线性规划与单纯形法

一、线性规划模型举例例 1 . 1 生产计划问题 家具厂生产桌子和椅子两种家具。桌子售 价150元。椅子售价80元，生产桌子和椅子需

要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要

木工3小时，油漆工1小时。该厂每月可用木工工时为180小时，油漆工

工时为90小时。问该 厂如何组织生产才能使每月的销售收入最大?

运筹学1线性规划与单纯形法

解：将一个实际问题转化为线性规划模型有以下几个步骤：(1) 确定决策变量：决策变量是模型要决定的未知量。在本例 中，家具厂要确定桌子和椅子的生产数量，因此可定义： x1 = 生产桌子的数量，x2 = 生产椅子的数量。

(2) 确定目标函数：目标函数决定线性规划问题的优化方向。很明显，家具厂的目标是使销售收入最大，更具体一点，是 使两种产品售价与产量的乘积的总和最大，因此目标函数可

写为：

max z = 150x1 + 80x2

运筹学1线性规划与单纯形法

(3) 确定约束方程：如果家具厂可以随意选择生产桌子和椅子的数量，他们的销售收入可以随意大。 而这实际是不可能的，因为任何生产都会受到种种 客观条件的限制。一个正确的模型应通过约束方程 来反映这些客观条件。本例中的限制条件是每月可

用的木工和油漆工的工时不能超过180和90小时。这两个条件可由以下方程表示： 4x1 + 3x2 180 2x1 + x2 90

运筹学1线性规划与单纯形法

(4) 变量取值限制：一般情况下，决策变量只取正值(非负值)。因此，模型中应有变量的非负约 束。在本例中，非负约束为x1 0,x2 0。 将以上几部分结合起来就得到反映家具厂经营活 动的完整的数学模型： max z = 150x1 + 80x2 s.t. 4x1 + 3x2 180 2x1 + x2 90 x1, x2 0

运筹学1线性规划与单纯形法

Max”是英文单词“Maximize”的缩写，含义 为“最大化”;“s.t.”是“subject to”的缩 写，表示“满足于……”。因此，上述模型 的含义是：在给定的条件限制下，求使得目

标函数Z达到最大的x1,x2 取值。

运筹学1线性规划与单纯形法

例 1. 2: 生产计划问题 某厂生产两种产品，需要三种资源，已知 各产品的利润、各资源的限量和各产品的资 源消耗系数如下表：劳动力 设备 原材料产品A 9 4 3 产品B 4 5 10 12管理科学与工程学院

资源限量 360 200 300

利润 元/kg 7

运筹学1线性规划与单纯形法

建模问题：如何安排生产计划， …… 此处隐藏：392字，全部文档内容请下载后查看。喜欢就下载吧 ……