文档介绍：运筹帷幄之中
决胜千里之外
线性规划
Linear Programming
第一章线性规划及单纯形法
★线性规划问题
★线性规划模型
★线性规划的图解法
★可行域的性质
★线性规划的基本概念
★基础解、基础可行解
★单纯形表
§
●生产计划问题
●配料问题
●背包问题
●运输问题
●指派问题
●下料问题
1. 生产计划问题(Production Planning)
产品甲
产品乙
产品丙
产品丁
设备能力(小时)
设备A
2000
设备B
8000
设备C
5000
利润(元/件)
某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:
求使得总利润最大的生产计划。
产品甲
产品乙
产品丙
产品丁
设备能力(小时)
设备A
2000
设备B
8000
设备C
5000
利润(元/件)
设四种产品的产量分别为x1,x2,x3,x4,总利润为z,线性规划模型为:
max z=+++
. +++≤2000
+++≤8000
+++≤5000
x1, x2, x3, x4≥0
目标函数
约束条件
变量非负约束
这个问题的最优解为:x1=,x2=1500件,x3=0,x4=
最大利润为:z=。
2. 配料问题(Material Blending)
某工厂要用四种合金T1、T2、T3、T4为原料,经熔炼成为新的不锈钢G。这四种原料含铬(Cr)、锰(Mn)和镍(Ni)的含量(%),这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量(%)如下表:
T1
T2
T3
T4
G
Cr
Mn
Ni
单价(元/公斤)
115
97
82
76
要求配100公斤不锈钢G,并假定在配制过程中没有损耗。求使得总成本最低的配料方案。
T1
T2
T3
T4
G
Cr
Mn
Ni
单价(元/公斤)
115
97
82
76
min z=115x1+97x2+82x3+76x4
. +++≥320 Cr的含量下限约束
+++≥210 Mn的含量下限约束
+++≥430 Ni的含量下限约束
x1+x2+x3+x4=100 物料平衡约束
x1, x2, x3, x4≥0
设四种原料分别选取x1,x2,x3,x4公斤,总成本为z。
这个问题的最优解为:x1=, x2=, x3=,x4=0(公斤), 最低成本为z=。
3. 背包问题(Knapsack Problem)
一只背包最大装载重量为50公斤。现有三种物品,每种物品数量无限。每种物品每件的重量、价格如下表:
物品1
物品2
物品3
重量(公斤/件)
10
41
20
价值(元/件)
17
72
35
求背包中装入每种物品各多少件,使背包中物品总价值最高。
设三种物品的件数各为x1,x2,x3件,总价值为z。
max z=17x1+72x2+35x3
. 10x1+41x2+20x3≤50
x1,x2,x3≥0
x1,x2,x3为整数
这是一个整数规划问题(Integer Programming)。最优解为: x1=1,x2=0,x3=2件,最高价值z=87元。
物品1
物品2