运筹学02-线性规划I

第2讲 线性规划I
2.1 2.2 2.3 2.4 线性规划问题的数学模型 线性规划的一般形式与标准形式 线性规划隐含的假定 线性规划的图解法
2.1 线性规划问题的数学模型
例2.1 生产方案问题
某家具厂生产桌子和椅子两种家具。每个桌子售价 50元， 每个椅子售价30元。生产一个桌子需要木工4小时，油漆 工 2小时；生产一个椅子需要木工3小时，油漆工1小时。 该家具厂每月可用木工工时为120小时，油漆工工时为50 小时。试问工厂应如何安排生产，才能使每月的销售收 入达到最大？
School of Business ECUST
约束条件：反映客观条件的限制
木工工时不能超过可用工时
4x 1 3x 2 120
油漆工工时不能超过可用工时
2x 1 x 2 50
非负约束：变量取值的限制
x 1 0, x 2 0
School of Business ECUST
x 1, x 2, x 3, x 4 0
School of Business ECUST
营养配餐问题的数学模型
min z 14x 1 6x 2 3x 3 2x 4 1000x 1 800x 2 900x 3 200x 4 3000 50x 1 60x 2 20x 3 10x 4 55 s .t . 400x 1 200x 2 300x 3 500x 4 800 x 1, x 2, x 3, x 4 0
School of Business ECUST
(2) 满足每天至少摄入55克蛋白质的营养要求
50x 1 60x 2 20x 3 10x 4 55
(3) 满足每天至少摄入800毫克钙的营养要求
400x 1 200x 2 300x 3 500x 4 800
非负约束：采购量不能为负值
x1 x2 C c1, c 2,..., cn ，X : x n
Pn
b
School of Business ECUST
矩阵式
a11 a12 .. a1n a 21 a 22 .. a 2n A P1, P2 ,.., Pn : : : : 系数矩阵 a a .. amn m1 m 2
家具厂生产方案问题的数学模型
设x1，x2分别表示该家具厂每月生产的桌子数和椅 子数，则其生产方案问题的数学模型可表示为
max z 50x 1 30x 2 4x 3x 120 2 1 s .t . 2x 1 x 2 50 x , x 0 1 2
s.t. —— subject to 表示 “受约束于...”
假定市场上可买到n种食品，含有m种营养成分，并且 每个单位第j种食品含有aij个单位第i种营养成分，第j种 食品的售价为cj ，另外，为达到营养平衡，每个人必须 保证每天至少摄取bi个单位的第i种营养成分。问在保证 起码的营养要求下，如何确定每天最经济的饮食方案？
School of Business ECUST
线性规划模型是求解这类问题的有效工具。
School of Business ECUST
家具厂生产方案问题数学模型的建立
决策变量：决策者要决定的未知量
每月生产桌子的数量 —— x1
每月生产椅子的数量 —— x2
目标函数：决策者的目标
每月的销售收入达到最大
max z 50x 1 30x 2
School of Business ECUST
例1.2 营养配餐问题
假定一个成年人每天至少需要从食物中摄取3000 大卡的热量、55克蛋白质和800毫克的钙。市场上 只有猪肉、鸡蛋、大米和白菜四种食品可供选择， 它们每公斤所含的热量和营养成分以及市场价格 见下表。请问如何选择才能在满足营养的前提下， 使购买食品的费用最小？
方案2：生产20个桌子，10个椅子，消耗木工110小 时，油漆工50小时，剩余木工10小时，每月销售收 入1300元；
方案3：生产15个桌子，20个椅子，消耗木工120小 时，油漆工50小时，用完全部工时，每月销售收入 1350元。
School of Business ECUST
对于简单的问题，凭经验和简单的计算进行比较， 或能找到最优方案。但当问题较为复杂时，如在上 例种该家具厂生产20种产品，消耗10种资源，则凭 经验和手工计算可能就很难寻找到最佳的生产方案 了！怎么办？
营养配餐问题建模
决策变量：
xj — 每天购入第 j种食品的公斤数
目标函数：每天的食品采购成本最小
min z 14x 1 6x 2 3x 3 2x 4
约束条件：满足每天的营养要求
(1) 满足每天至少3000大卡的热量要求
1000x 1 800x 2 900x 3 200x 4 3000
已知甲、乙两种原料的成本分别是每公斤 3元和2元，厂方希望总 单位成本（元） ３ ２ 成本达到最小，问如何配置该产品？
School of Business ECUST
习3. 捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物 资。已知各月份所需仓库面积列于下表1。仓库租借费用随合同期 而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每 月初都可办理，每份合同具体规定租用面积和期限。因此该厂可 根据需要，在任何一个月初办理租借合同。每次办理时可签一份 合同，也可签若干份租用面积和租用期限不同的合同。试确定该 公司签订租借合同的最优决策，目的是使所租借费用最少。
P1
P2



max min z CX
Pn x n ( , )b


a11x 1 a12x 2 a1n x n ( , )b1 P1x 1 P2x 2 s.t . X 0 a 21x 1 a 22x 2 a 2n x n ( , )b2 s .t . am 1x 1 a m 2x 2 a mn x n ( , )bm x j 0,( j 1, 2, , n )
线性规划模型的一般形式
一般的数学规划模型 线性规划模型
max min z f x 1, x 2 ,..., x n

g x , x ,..., x , b n 1 1 1 2 g2 x 1, x 2 ,..., x n , b2 s .t . ... g x , x ,..., x , b n m m 1 2
线性规划问题的一般特征：
(1) 有一组有待决策的变量(决策变量)，一般表示为 x1, x2, ..., xn，变量组的每一组取值对应于某一种决策 方案，根据实际问题，通常要求变量取非负值，即
x i 0, i 1, 2,
n
School of Business ECUST
(2) 每个问题中存在若干个约束条件，约束条件可用 决策变量的线性等式或线性不等式来表达。 (3) 每个问题中有一个目标函数，这个目标函数可表 示为决策变量的线性函数。要求这个目标函数在满 足约束条件下实现最大化或最小化




线性规划模型的一般形式
通常称 x1 , x2 ,
, xn 为决策变量，c1 , c2 ,
, cn 为系数, b1 , b2 , , bm 为资源限制系数。
School of Business ECUST
max m in z c1x 1 c2x 2 ... cn x n a11x 1 a12x 2 a 21x 1 a 22x 2 s .t . a x a x m2 2 m1 1 x j 0,( j a1n x n ( , )b1 a 2n x n ( , )b2 amn x n ( , )bm 1, 2, , n )
将约束条件及目标函数都是决策变量线性函数的数 学规划问题称为线性规划(LP, linear programming)
School of Business ECUST
线性规划模型的一般形式
某工厂生产n种产品，需消耗m种资源，每生产一单位 第j种产品消耗第i种资源的数量为aij, (i=1,…,m; j=1,…,n)，每生产一单位第j种产品(j=1,…,n)可获利cj, (j=1,…,n) ，该工厂第i种资源的拥有量为bi, (i=1,…,m )， 问如何安排生产可获利最大？





max min z c1x 1 c2x 2 ... cn x n a11x 1 a12x 2 a 21x 1 a 22x 2 s .t . a x a x m2 2 m1 1 x j 0,( j a1n x n ( , )b1 a 2n x n ( , )b2 amn x n ( , )bm 1, 2, , n )


可简写为：
max(min) z
c x
j 1 j
n
j
n aij x j ( , )bi s.t . j 1 xj 0
(i 1, 2,..., m ) ( j 1, 2,..., n )
School of Business ECUST
向量式
max m in z c1x 1 c2x 2 ... cn x n
School of Business ECUST
线性规划建模练习
习1. 某厂生产甲乙两种产品，生产工艺路线为：各自的零部件 分别在设备A、B加工，最后都需在设备C上装配。经测算得到 相关数据如表所示。已知甲、乙两种产品的市场售价分别为3 元和5元，问应如何制定生产计划，使总利润为最大。