文档介绍：第九讲
线性规划及其应用
Linear Programming
8/2/2018
1
主要讲三节
引言
第一节线性规划模型的基本结构
第二节线性规划模型举例
第三节线性规划问题的求解
返回目录
8/2/2018
2
引言
线性规划在实际应用中包括下列四个步骤:
确定问题,明确目标和限制因素(约束条件);
建立线性规模型;
模型求解;
应用模型和数据进行分析,提出可供决策的方案。
返回目录
为什么要学习线性规划?
8/2/2018
3
第一节线性规划模型的基本结构
(1)变量(决策变量):规划中要确定的未知量,是用数量方式来表示的方案或措施,可由决策者决定和控制。
(2)目标函数:决策变量的函数,是决策者在一定的限制条件下希望得到的结果。
(3)约束条件:决策变量取值时受到的各种资源条件的限制,通常用等式或不等式来表达。
max(或min)z=c1x1+c2x2+…+ cnxn
a11x1+a12x2+…+a1nxn≤(或=,≥)b1
a21x1+a22x2+…+a2nxn≤(或=,≥)b2
…………………………………………
am1x1+am2x2+…+amnxn≤(或=,≥)bm
x1,x2,…,xn≥0
目标函数
约束条件
非负约束
返回目录
8/2/2018
4
例如某居住小区总投资≤680万元,。建筑密度要求≤25%,目标是在满足上述约束条件下,尽可能地得到最多的居住面积。其它有关资料如下表。
住宅类型
多层住宅(六层)
高层住宅(十层)
建筑面积
x1
x2
平面系数(k)
单方造价(元/m2)
132
220
投资约束
面密约束
非负约束
目标
约束条件
x1=29600m2
x2=13000m2
总面积为42000m2时利润最大。
返回本节目录
8/2/2018
5
线性规划模型建立的前提
1、目标函数和约束条件方程必须是线性函数
2、决策变量是连续分布的,即变量值是分数或小数
3、目标函数的单一性
4、线性规划模型是确定性的
5、决策变量的非负值
8/2/2018
6
第二节线性规划模型举例
一、运输分配问题
二、生产投资安排问题
三、设施配置问题
返回目录
8/2/2018
7
一、运输分配问题
两个混凝土工厂,生产能力分别为I1==。它们同时向三个工地供应,三个工地需求量分别为J1=、J2== 万立方米。
二个工厂分别到三个工地的运输距离为dij。两个工厂分别向各工地的供应量令其为xij。
现在的问题是求xij ,既满足各工地需要量的要求又保证各工厂有能力供应,同时使运输的费用(吨-公里)最小。
返回本节目录
8/2/2018
8
一、运输分配问题
假设xij为I工厂供应J工地的混凝土量。则
工厂i
工地j
生产量
(万立方米)
J1
J2
J3
I1
x11
x12
x13
d11=10
d12=14
d13=11
I2
x21
x22
x23
d21=16
d22=15
d23=19
需求量
(万立方米)
下一页
8/2/2018
9
运输分配问题的数学模型:
解得:
x11= x12=0 x13=
x21= x22= x23=0
最小运输量为:63吨公里。
上一页
8/2/2018
10