上页 下页 返回
一般线性规划问题的标准形化
• min Z=CX 等价于 max Z’ = -CX • “” 约束：加入非负松驰变量
例： 目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8 4x1 16 4x2 12 x 1、 x 2 0
上页
下页
返回
一般线性规划问题的标准形化
上页 下页 返回
目标函数最大 线性规划问题的标准形式 • 标准形式为: 约束条件等式 决策变量非负
Max Z c1 x1 c2 x2 ... cn xn a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2 n xn b2 .......................................... a x a x ... a x b m2 2 mn n m m1 1 b1 , b2 ,...bm 0 x1 , x2 ,..., xn 0
上页
下页
返回
如何安排生产 使利润最甲
乙
上页
下页
返回
什么是线性规划？
在工业、农业、国防、建筑、交通运输、科研、商业 等各种活动中，常常要求对资源进行统一分配、全面规划 和合理调度，以便从各种可能安排方案中找出最优的计划 或设计，用以指导生产。在这类问题中，一方面有期望达 到最优要求的目标（例如希望产值最高或消耗最少），另 一方面又要受到一定条件的限制（例如人力、物力、财力 的限制），如何安排才能使成效最高，消耗既定资源取得 的收益最大，或达到既定收益所消耗的资源最少。这可以 借助线性规划（Linear Programming，LP）来解决。
上页 下页 返回
第一节
线性规划问题 及其数学模型
线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式
继续
返回
•问题的提出
• 引例: 生产计划问题
设备 原材料 A 原材料 B 利润
甲 1 4 0 2
乙 2 0 4 3
资源限量 8 台时 16kg 12kg
上页 下页 返回
经上述分析，可将该问题表示为：
max z＝7 x1十5 x2
3 x1十2 x2 ≤ 90 4 x1十6 x2 ≤ 200 7 x2 ≤ 210 x 1 ≥ 0 ，x 2 ≥ 0
这种数学表达方式，称为该问题的一种数学模型。
上页 下页 返回
例3：投资问题
某单位有一批资金用于四个工程项目的投资， 用于各工程项目时所得之净收益（投入资金的百 分比）如下表所示：
• 设xj为第j种天然饲料的使用量，则aij xj为第j 种天然饲料含有第i种营养成分的数量。则：
• 考虑到非负约束和目标要求，其数学模型为：
上页
下页
返回
线性规划三要素
线性规划(Linear Programming，LP)有：
• 一组有待决策的变量 （指模型中要求解的未知量） • 一个线性的目标函数 （指模型中要达到的目标的数学表达式） • 一组线性的约束条件 （指模型中的变量取值所需要满足的一切限制 条件）
x1
x2
上页
下页
返回
第2步 --定义目标函数
z ——利润
Max Z =
x1 +
x2
上页
下页
返回
第2步 --定义目标函数
Max Z = 2 x1 + 3 x2
上页
下页
返回
对我们有 何限制?
上页
下页
返回
第3步 --表示约束条件
x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0
• min Z=CX 等价于 max Z’ = -CX • “” 约束：加入非负松驰变量 例： max z 2 x1 3 x2 0 x3 0 x4 0 x5
8 x1 2 x2 x3 4 x x4 16 1 4 x2 x5 12 x1 , x2 , x3 , x4 , x5 0
上页 下页 返回
x1 x 2 X ... xn
– 用矩阵表示
max Z CX max Z CX A—系数矩阵 AX b C—价值向量 AX b b—资源向量 X 0 X 0
0 0 a11 .....a 1 n a ..... a 11 1n 0 0 (P , P2 ,..., P ) 0 .............. 1 3 .............. ( P1 , P2 ,..., Pn ) 0 ... A a ...... ... a mn m1 0 a ......a mn m1 0 资源向量 C - 价值向量X - 决策变量向量
上页
下页
返回
例2(书)
某厂生产甲乙两种产品，已知制成一吨产品 甲需用资源A 3吨，资源B 4m3；制成一吨产品乙 需用资源A 2吨，资源B 6m3，资源c 7个单位。 若一吨产品甲和乙的经济价值分别为7万元和5万 元，三种资源的限制量分别为90吨、200m3和210 个单位，试决定应生产这两种产品各多少吨才能 使创造的总经济价值最高?
第一章 线形规划
本章学习重点
线性规划是运筹学中比较成熟的一个分支 ，它具有成熟而有效的求解方法，可以借助于 计算机进行求解，在军事、经济等领域中具有 广泛的应用。学习本章，要掌握线性规划的数 学模型（建模以及把不同形式的线性规划问题 化为标准形式的方法）、求解方法。
上页 下页 返回
线性规划的地位与研究进程
上页 下页 返回
第三步：确定目标函数 max z=0.15x1+0.1x2+0.08x3+0.12x4 数学模型 max z = 0.15x1 + 0.1x2 + 0.08x3 + 0.12x4 x1 － x2 － x3 － x4 ≤ 0 x2 ＋ x3 － x4 ≥ 0 x1 ＋ x2 ＋ x3 ＋ x4 ＝ 1 xj ≥0，j＝1，2,…,4
• 作为一门科学的线性规划，最早可以追溯到 20 世 纪 30 年代末，前苏联数学家康德洛维奇等人关于 生产 组 织和 运 输 问题 研 究 所作 的 开 拓性 工 作 。 1947年，美国数学家G.B.Dantzig以及美国空军的 SCOOP研究小组提出了线性规划问题的一般性解法 即单纯形法,奠定了线性规划的理论基础。50年代 后，随着电子计算机的介入，线性规划的应用越 来越普遍，在生产、管理、军事等方面发挥着重 要的作用。 • 线性规划目前仍然还在发展，主要是：大型线性 规划问题，线性规划解法研究等。
上页 下页 返回
– 用向量表示
max Z CX n Pj x j b i 1 x 0 j 1,2,...n j 其中：
未知数 向量
C (c1 , c 2 ,...c n ) a1 j a2 j Pj ... amj b1 b 2 b ... bm
上页
下页
返回
线性规划模型的一般形式
Max(min) z c1 x1 c2 x2 ... cn xn a11 x1 a12 x2 ... a1n xn (, )b1 a x a x ... a x (, )b 21 1 22 2 2n n 2 ................................................... a x a x ... a x (, )b m2 2 mn n m m1 1 x1 , x2 ,..., xn (, )0
设备 原材料 A 原材料 B 利润 甲 1 4 0 2 乙 2 0 4 3 资源限量 8 台时 16kg 12kg
上页
下页
返回
该计划的数学模型
目标函数
约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x 1、 x 2 0
x1
x2
上页 下页 返回
工程项目
收益（％）
A 15
B 10
C 8
D 12
由于某种原因，决定用于项目A的投资不大于 其它各项投资之和；而用于项目B和C的投资不小 于项目D的投资。试确定使该单位收益最大的投 资分配方案。
上页
下页
返回
第一步：确定变量 x1、 x2 、 x3 、 x4 分别表示用于项目A、 B、C、D的投资百分数。 第二步：确定约束条件 x1－ x2 － x3 － x4≤0 x2 ＋ x3 － x4≥0 x1 ＋ x2 ＋ x3 ＋ x4 ＝1 xj ≥0，j＝1，2,…,4
•基本概念
决策变量（Decision variables ） 它是决策变量的函数 目标函数（Objective function） 约束条件（Constraint conditions ） 指决策变量取值时受到 可行域（Feasible region) 的各种资源条件的限制 ，通常表达为含决策变 最优解（Optimal solution) 量的等式或不等式。
上页 下页 返回
线性规划研究的内容
• 在现有的资源条件下，如何充分利用资 源，使任务或目标完成得最好（求极大 化问题）。
• 在给定目标下，如何以最少的资源消耗 ，实现这个目标（求极小化问题）。
上页
下页
返回
• 第1步 -确定决策变量
•设
x1 ——甲的产量 x 2 ——乙的产量
是问题中要确定的未知量， 表明规划中的用数量表示的 方案、措施，可由决策者决 定和控制。