文档介绍：第二章线性规划
线性规划(linear programming,简称LP)是运筹学的一个重要分支,研究得比较早,尤其自1947年丹捷格()提出了单纯形法之后,:一类是在现有的人、财、物等资源的条件下,研究如何合理地计划、安排,可使得某一目标达到最大,如产量、利润目标等;另一类是在任务确定后,如何计划、安排,使用最低限度的人、财等资源,去实现该任务,如使生产成本、,即都在一组约束条件下,去实现某一个目标的最优(最大或最小).线性规划研究的问题要求目标与约束条件函数均是线性的,,大量的问题是线性的,有的可以转化为线性的,《财富》杂志对全美500家大公司的调查,线性规划的应用名列前茅,有85%左右的公司频繁地使用线性规划.
线性规划问题及其数学模型
一、线性规划问题的数学模型
在生产实践和日常生活中,经常会遇到如何合理地使用有限资源(如资金、劳力、材料、机器、仪器设备、时间等),以获得最大效益的问题.
例2-1 某制药厂在计划期内要安排生产Ⅰ、Ⅱ两种药品,,每千克药品Ⅰ和Ⅱ在各台设备上所需要的加工台时数如表2-(1台设备工作1小时称为1台时)分别是12、8、Ⅰ可得利润200元,每生产1千克药品Ⅱ,才能使制药厂利润最大?
表2-1 两种药品每千克在各台设备上所需的加工台时数
药品
Ⅰ
2
1
4
0
Ⅱ
2
2
0
4
这是一个资源有限,但需利润最大的线性规划问题.
解设,分别表示在计划期内药品Ⅰ和Ⅱ的产量(千克),Ⅰ、Ⅱ两种药品的利润总额为(元).但是生产Ⅰ、Ⅱ两种药品在设备上的加工台时数必须满足;在设备上的加工台时数必须满足;在设备上的加工台时数必须满足;在设备上的加工台时数必须满足;生产Ⅰ、Ⅱ两种药品的数量应是非负的数,:
目标函数
约束条件
同样,在经济生活和生产活动中也遇到另一类问题,即为了达到一定的目标,应如何组织生产,或合理安排工艺流程,或调整产品的成分等,以使消耗(人力、设备台时、资金、原材料等)为最少.
例2-2 用3种原料配制某种食品,要求该食品中蛋白质、脂肪、糖、维生素的含量不低于15、20、25、,如下表2-,使所需成本最低?
表2-2 3种原料所含成分
营养成分
原料
食品中营养成分的最低需要量(单位)
蛋白质(单位/千克)
5
6
8
15
脂肪(单位/千克)
3
4
6
20
糖(单位/千克)
8
5
4
25
维生素(单位/千克)
10
12
8
30
原料单价(元/千克)
20
25
30
这个问题是在食品的营养要求得到满足的前提下,如何通过适当的原料配比,使食品的成本最低.
解设分别表示原料的用量(千克),表示食品的成本(元),则这一食品配制问题变为:
目标函数
约束条件
例2-3 某医院每天至少需要下列数量的护士(见表2-3).
表2-3 某医院每天至少需要的护士数
班次时间护士数
1 上午6时-上午10时 60
2 上午10时-下午2时 70
3 下午2时-下午6时 60
4 下午6时-晚10时 50
5 晚10时-凌晨2时 20
6 凌晨2时-上午6时 30
每班的护士在值班开始时向病房报到,:为满足每班所需要的护士数,医院最少应雇用多少护士?请列出线性规划问题的数学模型.
解设表示第1班次向病房报到的护士数;
表示第2班次向病房报到的护士数;
表示第3班次向病房报到的护士数;
表示第4班次向病房报到的护士数;
表示第5班次向病房报到的护士数;
表示第6班次向病房报到的护士数.
则有
目标函数
约束条件
且为整数
例2-4 ,,,;一次小手术,医生要花1小时,,,一次接生的收入为