防灾科技学院
12
1.2 线性规划问题的数学模型
三个组成要素： 1.决策变量:是决策者为实现规划目标采取的 方案、措施，是问题中要确定的未知量。 2.目标函数:指问题要达到的目的要求，表 示为决策变量的函数。 3.约束条件:指决策变量取值时受到的各种可 用资源的限制，表示为含决策变量的等式或 不等式。
2018/11/20 15
线性规划模型的简写形式(求和符号)
max (min) Z n aij x j ( ) bi j 1 x 0 j
c x
j 1 j
n
j
(i 1 2 (j 1 2
m) n)
一般线性规划(LP)问题模型向量形式
max (min) z CX p j x j ( ) b s.t. X 0
表示某一方案，这组决策变量的值代表一个具体方案。一般 这些变量的取值是非负且连续的；

都有关于各种资源和资源使用情况的技术数据，创造新价值 的数据；
a ; c b 1 , m ; j 1 , n ) i j j;( ii

存在可以量化的约束条件，这些约束条件可以用一组线性等 式或线性不等式来表示; 都有一个达到某一目标的要求，可用决策变量的线性函数 (称为目标函数)来表示。按问题的要求不同，要求目标函数 实现最大化或最小化。
m in z 1 4 x 6 x 3 x 2 x 1 2 3 4 1 0 0 0 x 8 0 0 x 9 0 0 x 2 0 0 x 3 0 0 0 1 2 3 4 5 0 x 6 0 x 2 0 x 1 0 x 5 5 1 2 3 4 st .. 0 0 x 2 0 0 x 3 0 0 x 5 0 0 x 8 0 0 1 2 3 4 4 xj 0(j1 ,...,4 )
2018/11/20 13
线性规划的数学模型由三个要素构成
决策变量 目标函数 约束条件 Decision variables Objective function Constraints
怎样辨别一个模型是线性规划模型？ 其特征是： （1）问题的目标函数是多个决策变量的线性函数，通 常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不等 式或等式。
m a x z 2 x1 3 x 2 2 x1 2 x 2 1 2 4 x 16 s. t . 1 5 x2 15 x1 , x 2 0
例2
线性规划模型的特点

决策变量：向量X=(x1… xn)T 决策人要考虑 和控制的因素，非负 约束条件：关于X的线性等式或不等式 目标函数：Z=ƒ(x1 … xn) 为关于X 的线性函数， 求Z极大或极小
各种食物的营养成分表
序号 食品名称
热 量 蛋白质
（千卡） （克）
价格 （毫克） (元/kg） 钙
x
1
1 2 3 4
猪肉 鸡蛋 大米 白菜
1000 800 900 200
3000
50 60 20 10
55
400 200 300 500
800
14 6 3 2
x
2
x3 x
4
每天需要
解：设 xj 为第 j 种食品每天的购入量，则配餐 问题的线性规划模型为：
一般线性规划问题的数学模型：
目标函数： m （或 m ax ） z c in x c x c x 1 1 2 2 n n 约束条件： a （ 或 ,） b a 1 1x 1 a 1 2x 2 1 nx n 1 a （ 或 ,） b 2 1x 1 a 2 2x 2 2nx n 2 a st .. a x a x a x （ 或 ,） b m 1 1 m 2 2 m n n m , xn 0 1, x 2, x
第1章 运筹学基础及应用-第六 版
第一章 线性规划及单纯形法
(Linear Programming & Simplex Method)
§1 一般线性规划问题的数学模型 §2 图解法 §3 单纯形法原理 §4 单纯形法的计算步骤 §5 单纯形法的进一步讨论 §6 数据包络分析(DEA) §7 应用举例
2018/11/20
3
§1 一般线性规划问题的数学模型 1.1 引例
例1、生产计划问题 Ⅰ Ⅱ 设备能力（小时）
设备A
设备B 设备C 利润（元）
2
4 0 2
2
0 5 3
12
16 15
问：Ⅰ，Ⅱ两种产品各加工多少单位, 可获最大利润?
2018/11/20 4
解:设产品Ⅰ, Ⅱ产量分别为变量x1 ， x2 max Z= 2x1 +3x2 2x1+2x2 12
2018/11/20
2
例2(教材第9页)生产计划问题
常山机器加工厂，利用A、B、C三种不同设备加 工生产Ⅰ、Ⅱ两种产品。按工艺要求，每生产一 个单位的Ⅰ产品，需要占用三种设备2、4、0小 时；每生产一个单位的Ⅱ产品，需要占用三种设 备2、0、5小时。已知三种设备加工能力分别为 12、16、15小时。且每生产一个单位的Ⅰ产品 可获取2单位的利润；每生产一个单位的Ⅱ产品 可获取2单位的利润。问应当如何安排加工，可 使获取的总利润最大？
s.t.
4x1 x1，x注意模型特点
2018/11/20
防灾科技学院
5
附例 营养配餐问题
假定一个成年人每天需要从食物中获得 3000千卡的热量、55克蛋白质和800毫克的 钙。如果市场上只有四种食品可供选择， 它们每千克所含的热量和营养成分和市场 价格见下表。问如何选择才能在满足营养 的前提下使购买食品的费用最小？


2018/11/20
10
LP问题一般可整理为：
决策变量及各类系数之间的对应关系
决策变量 资源
活
1 2 m
x1 a1 1 a 21 a m1 c1
x2 a1 2 a 22 am 2 c2
防灾科技学院
xn a1 n a2n amn cn
b1 b2 bm
动
价值系数
11
上述模型的共同特征：

x , x , x 1 2 n 每一个线性规划问题都用一组决策变量