整数规划应用案例分析 ppt课件.ppt

一、投资项目的选择
利用线性规划可以来完成资金预算决策，决定对 不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投资。
管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。
对每个是或否的决策：
1，是
引入决策变量x=
0，否
第四章 整数规划的应用
例1 投资问题
设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知
1)第i个时段里该公司可动用的资金是b i，
2)第j项投资计划所需要的资金是a ij ,
3)能够得到的利润是c ij。
问该公司如何选择投资计划，使m个时段内的总利润最大。
解：设x ij表示在第i个时段内对第j个投资计划的决策变量。
建立该投资问题的数学模型为：
表示第i个时段内选中第j个投资计划，
表示第i时段内未选中第j个投资计划。
项目
投资额(万元)
投资收益(万元)
1
210
150
2
300
210
3
100
60
4
130
80
5
260
180
该公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束：
1）在项目1、2和3中必须有一项被选中；
2）项目3和4只能选中一项；
3）项目5被选中的前提是项目1必须被选中。
如何在上述条件下，选择一个最好的投资方案，使收益最大。
投资项目的选择
例2. 华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：
1 选中项目i
0 未选中项目I
(i=1,…,5)
解：令
xi=
Max Z=150 x1 + 210x2 + 60x3 +80x4 + 180x5
.
210 x1 + 300x2 +100x3 +130x4 + 260x5  600
x1 + x2 + x3 >=1
x3 + x4  1
x5  x1
xi=1或0(i=1,…,5)
1,2,3必须有一项选中
3,4只能选中一项
5被选中前提是1选中
解得（1，0，0，1，1）
Max Z=410
即投资项目1、4、5，可以获得410万元。
二、分布系统设计-选址问题
在如今的全球经济中，许多公司正在全世界各个地方建立新工厂，为的是获得低劳动力成本等好处。
在为新工厂选址之前，需要分析和比较地点。每个可供选择的地点都涉及一个是或否的决策。
对每个是或否的决策：
1，是
引入决策变量 x=
0，否

在许多案例中，目标是地点的选择以使新建设施的总的成本最小化，且这新设施能满足生产的需要。
分布系统设计-选址问题
例3．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，各销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。
a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?
解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题：
Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23
+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
（其中前4项为固定投资额，后面的项为运输费用。）
. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制)
x21+ x22+ x23 ≤ 10 ( A2 厂的产量限制)