建立线性规划模型.ppt

《建立线性规划模型.ppt》由会员分享，可在线阅读，更多相关《建立线性规划模型.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 优优 化化 建建 模模拍卖与投标问题拍卖与投标问题-例例6.3:艺术品拍卖问题艺术品拍卖问题招招标项标项目目类类型型12345招招标项标项目的数量目的数量12334投投标标价格价格投投标标人人192863投投标标人人267915投投标标人人378634投投标标人人454321假设每个投标人对每类艺术品最多只能购买假设每个投标人对每类艺术品最多只能购买1件件 每个投标人购买的艺术品的总数不能超过每个投标人购买的艺术品的总数不能超过3件件 问哪些艺术品能够卖出去？卖给谁？每类物品的清算价问哪些艺术品能够卖出去？卖给谁？每类物品的清算价应该是多少？应该是多少？优优 化化 建建 模模假设有一个中间商

2、希望最大化自己的例润假设有一个中间商希望最大化自己的例润 问题分析与假设问题分析与假设 设有N类物品需要拍卖，第j类物品的数量为Sj（j=1,2，,N）；有M个投标者，投标者i（i=1，2，,M）对第j类物品的投标价格为bij（假设非负）。投标者i对每类物品最多购买一件，且总件数不能超过ci。实际中可以通过对所有投标的报价进行排序来解决实际中可以通过对所有投标的报价进行排序来解决 优优 化化 建建 模模目标：目标：确定第j类物品的清算价格pj，它应当满足下列假设条件：成交的第j类物品的数量不超过Sj（j=1，2，,N）；对第j类物品的报价低于pj的投标人将不能获得第j类物品；如果成交的第 j

3、类物品的数量少于Sj（j=1，2，,N），可以认为pj=0（除非拍卖方另外指定一个最低的保护价）；对第j类物品的报价高于pj的投标人有权获得第j类物品，但如果他有权获得的物品超过3件，那么假设他总是希望使自己的满意度最大（满意度可以用他的报价与市场清算价之差来衡量）。优优 化化 建建 模模线性规划线性规划模型模型(LP)用0-1变量xij表示是否分配一件第j类物品给投标者i，即xij=1表示分配，而xij=0表示不分配。目标函数目标函数 虚拟的中间商的虚拟的中间商的总利润最大总利润最大,即即约束条件约束条件(1)每类物每类物品的数量限品的数量限制制(2)每个投标人所能分每个投标人所能分到的物品

4、的数量限制到的物品的数量限制 优优 化化 建建 模模MODEL:TITLE 拍卖与投标拍卖与投标;SETS:!S,C,B,X的含义就是上面建模时给出的定义的含义就是上面建模时给出的定义;AUCTION:S;BIDDER:C;LINK(BIDDER,AUCTION):B,X;ENDSETSDATA:!通过文本文件输入数据通过文本文件输入数据;AUCTION=FILE(AUCTION.TXT);BIDDER=FILE(AUCTION.TXT);S=FILE(AUCTION.TXT);C=FILE(AUCTION.TXT);B=FILE(AUCTION.TXT);ENDDATAMAX=SUM(LIN

5、K:B*X);!目标函数目标函数;FOR(AUCTION(J):!拍卖数量限制拍卖数量限制 AUC_LIM SUM(BIDDER(I):X(I,J)S(J);FOR(BIDDER(I):!投标数量限制投标数量限制;BID_LIM SUM(AUCTION(J):X(I,J)C(I);FOR(LINK:BIN(X);!0-1变量限制变量限制;ENDLINGO模型为模型为 优优 化化 建建 模模最优解为：投标人1得到艺术品1、3、4，投标人2、3都得到艺术品2、3、5，投标人4得到艺术品4、5.结果，第4、5类艺术品各剩下1件没有成交。如何才能确定清算价格呢？如何才能确定清算价格呢？约束“AUC_L

6、IM”是针对每类艺术品的数量限制的，对应的影子价格就是其清算价格：即5类艺术品的清算价格分别是5、5、3、0、0。第4、5类艺术品有剩余，所以清算价格为0 推广推广:大学生的选课问题大学生的选课问题 优优 化化 建建 模模交通流均衡问题例交通流均衡问题例6.4:公路网汽车分布公路网汽车分布居民区居民区工作区工作区BCDA每天上班时间有6千辆小汽车要从居民区A前往工作区D 道路道路ABACBCBDCD行行驶驶时间时间（分（分钟钟）流量流量 220521252202 流量流量 330531353303 流量流量 440541454405条道路上每辆汽车的平均行驶时间和汽车流量之间的关系见下表 这些

7、汽车将如何在每条道路上分布？优优 化化 建建 模模问题分析问题分析 交通流的规律交通流的规律:每辆汽车都将选择使自己每辆汽车都将选择使自己从从A到到D运行时间最少的路线运行时间最少的路线 必然的结果:无论走哪条路线从A到D，最终花费的时间应该是一样的，因为花费时间较长的那条线路上的部分汽车总会改变自己的路线，以缩短自己的行驶时间汽车在每条道路上的分布将达到均衡状态汽车在每条道路上的分布将达到均衡状态 决决策策变变量量共有20个决策变量Y(j)和X(i,j)，(i=2，3，4；j=AB，AC，BC，BD，CD）如如Y（AB）表示道路）表示道路AB上的总的流量，进一步分解成三部分：上的总的流量，进

8、一步分解成三部分：道路道路AB上的流量不超过上的流量不超过2时的流量，用时的流量，用X（2，AB）表示；）表示；AB上的流量超过上的流量超过2但不超过但不超过3时，超过时，超过2的流量部分用的流量部分用X（3，AB）表示；）表示；AB上的流量超过上的流量超过3但不超过但不超过4时，超过时，超过3的流量部分用的流量部分用X（4，AB）表示。）表示。线性线性规划规划模型模型(LP)优优 化化 建建 模模目标函数目标函数 约约束束条条件件总的堵塞总的堵塞时间最小时间最小 用T(i，j)表示流量X(i，j)对应的堵塞时间 并不是总并不是总堵塞时间堵塞时间 T(i，j)关于i是单调增加的，即不断增加的车

9、流只会使以前的堵塞加剧而不可能使以前的堵塞减缓。故关于决策变量X(i，j)而言，与希望优化的目标的单调性一致每条道路上的总流量每条道路上的总流量Y等于该道路上的分流量等于该道路上的分流量X的和的和道路交汇处道路交汇处A、B、C、D(称为节点称为节点)的流量守恒（即流入的流量守恒（即流入量等于流出量）量等于流出量）决策变量的上限限制，如决策变量的上限限制，如 X(2，AB)2，X(3，AB)1，X（4，AB）1等等 优优 化化 建建 模模LINGO模型如下：模型如下：MODEL:TITLE 交通流均衡交通流均衡;SETS:ROAD/AB,AC,BC,BD,CD/:Y;CAR/2,3,4/;LIN

10、K(CAR,ROAD):T,X;ENDSETSDATA:!行驶时间行驶时间;T=20,52,12,52,20 30,53,13,53,30 40,54,14,54,40;ENDDATAOBJ MIN=SUM(LINK:T*X);!目标函数目标函数;优优 化化 建建 模模!四个节点的流量守恒条件四个节点的流量守恒条件;NODE_A Y(INDEX(AB)+Y(INDEX(AC)=6;NODE_B Y(INDEX(AB)=Y(INDEX(BC)+Y(INDEX(BD);NODE_C Y(INDEX(AC)+Y(INDEX(BC)=Y(INDEX(CD);NODE_D Y(INDEX(BD)+Y(I

11、NDEX(CD)=6;!每条道路上的总流量每条道路上的总流量Y等于该道路上的分流量等于该道路上的分流量X的和的和;FOR(ROAD(I):ROAD_LIM SUM(CAR(J):X(J,I)=Y(I);!每条道路的分流量每条道路的分流量X的上下界设定的上下界设定;FOR(LINK(I,J)|I#EQ#1:BND(0,X(I,J),2);FOR(LINK(I,J)|I#GT#1:BND(0,X(I,J),1);END 优优 化化 建建 模模均衡时道路AB、AC、BC、BD、CD的流量分别是4、2、2、2、4（千辆车）。注意这时得到的目标函数452并不是真正的总运行和堵塞时间 真正运行时间是：每辆

12、车通过真正运行时间是：每辆车通过ABAB、ACAC、BCBC、BDBD、CDCD道道路分别需要路分别需要4040、5252、1212、5252、4040分钟，也就是三条路分钟，也就是三条路线线ABDABD、ACDACD、ABCDABCD上都需要上都需要9292分钟，所以这也说明交分钟，所以这也说明交通流确实达到了均衡。于是，均衡时真正的总运行时通流确实达到了均衡。于是，均衡时真正的总运行时间应该是间应该是6*92=5526*92=552（千辆车（千辆车*分钟）分钟）结果解释结果解释 优优 化化 建建 模模模型讨论模型讨论 均衡解并不一定是最优的流量分配方案，故上面的解并不是最优解。假设有一个权

13、威的机构来统筹安排，如何最优分配这些交通流，使所有汽车的总运行时间最小？计算新增的流量计算新增的流量X(i,j)，(i=2,3,4；j=AB,AC,BC,BD,CD）造成的实际堵塞时间。以道路）造成的实际堵塞时间。以道路AB为例：为例：当流量为当流量为2（千辆）时，每辆车的通过时间为（千辆）时，每辆车的通过时间为20分钟，所以总分钟，所以总通过时间是通过时间是40（千辆车（千辆车*分钟）分钟）当流量增加一个单位（当流量增加一个单位（1千辆）达到千辆）达到3（千辆）时，每辆车的通（千辆）时，每辆车的通过时间为过时间为30分钟，所以总通过时间是分钟，所以总通过时间是90（千辆车（千辆车*分钟）分钟

14、）当流量再增加一个单位达到当流量再增加一个单位达到4（千辆）时，每辆车的通过时间（千辆）时，每辆车的通过时间为为40分钟，所以总通过时间是分钟，所以总通过时间是160（千辆车（千辆车*分钟）分钟）优优 化化 建建 模模这样可以得到单位流量的增加导致总行驶时间的增量和汽车流量之间的关系，如下表 道路道路ABACBCBDCD总总行行驶时驶时间间的增量的增量（千（千辆车辆车 分分钟钟）流量流量 220521252202 流量流量 350551555503 01.5 x1+0.7 x2-y 0求解得到求解得到 ：应该投资：应该投资A A、B B股票各股票各50%50%，至少可以，至少可以增值增值10%

15、10%优优 化化 建建 模模求解得到求解得到 ：应该投资：应该投资A A股票股票54.5455%，B B 股票股票45.4545%，至少可以增值至少可以增值13.6364%.13.6364%.现在，假设有一条重要信息：如果情形1发生，股票B的增值将达到30%而不是表中给出的20%。那么，一般人的想法应该是增加对股票B的持有份额。果真如此吗？这个投资人如果将上面模型中的1.2改为1.3计算也就是说，应该减少对股票B的持有份额，增加对股票A的持有份额！这真是叫人大吃一惊！这相当于说：有人告诉你有某只股票涨幅要增加了，你赶紧说：那我马上把这只股票再卖点吧。之所以出现如此奇怪的现象，就是由于这个例子中

16、的目标的特殊性引起的 优优 化化 建建 模模3.市场营销问题市场营销问题 优优 化化 建建 模模含义含义:最近购买某种产品（用行表示）的顾客，最近购买某种产品（用行表示）的顾客，下次购买四种产品的机会（概率）下次购买四种产品的机会（概率）现有新产品现有新产品A和和已有的同类产品已有的同类产品B、C、D，市场调查如下表，市场调查如下表例例6.106.10：新产品的市场预测新产品的市场预测问题问题产产品品ABCDA0.750.10.050.1B0.40.20.10.3C0.10.20.40.3D0.20.20.30.3新产品新产品A未来的市场份额大概是多少？未来的市场份额大概是多少？优优 化化 建

17、建 模模问问题题分分析析模模型型建建立立 离散动态随机过程离散动态随机过程A未来的市场份额未来的市场份额产品编号记为产品编号记为 i（i=1，2，,N）转移概率矩阵的元转移概率矩阵的元素记为素记为Tij稳定状态下每种产品的概率稳定状态下每种产品的概率优化模型优化模型(无目标函数无目标函数)稳定状态下产品稳定状态下产品i的的市场份额记为市场份额记为pipi非负非负 A的市场份的市场份额是额是47.5%优优 化化 建建 模模效用函数效用函数-例例6.11:6.11:小汽车属性的效用函数小汽车属性的效用函数考虑某牌号小汽车的两种属性：价格和安全气囊。考虑某牌号小汽车的两种属性：价格和安全气囊。价格分

18、为价格分为12.9、9.9、7.9万元万元；安全气囊的配置为两；安全气囊的配置为两个、一个、没有。顾客对该产品的不同配置的偏好个、一个、没有。顾客对该产品的不同配置的偏好程度（效用）如下表所示程度（效用）如下表所示：价格（万元）价格（万元）12.99.97.9安全气囊安全气囊278913460125价格和安全气囊的效用函数如何？价格和安全气囊的效用函数如何？优优 化化 建建 模模模型建立模型建立 记价格选项分别为H(高)、M(中)、L(低)，对应的效用为pj（j=H，M，L）；安全气囊选项分别为0、1、2，对应的效用为qi（i=0，1，2）目的目的:求出求出pj 和和qi 假设价格和安全气囊的

19、效用是线性可加的，即当价格选项为j、安全气囊选项为i时，效用 c（i，j）=pj+qi 如何比较不同的估计的好坏呢？如何比较不同的估计的好坏呢？用最小二乘法确定pj和qi。也就是说，此时的目标为：其中，其中，c c0 0(i i，j j)是表中的数是表中的数据据(安全气囊选项为安全气囊选项为i i、价格、价格选项为选项为j j时具体产品的效用时具体产品的效用)优优 化化 建建 模模因为做效用分析的主要目的是将来用于把不同配置的具体产品的优劣次序排出来，所以另一种方法是希望c(i，j)和c0(i，j)保持同样的顺序：即对任意的(i，j)和(k，l),当c0(i，j)+1 c0(k，l)时，也尽量

20、有c(i，j)+1 c(k，l)(这里“+1”表示c(i，j)严格小于 c(k，l)，且至少相差1)。考虑目标考虑目标 求和只对满足c0(i，j)+1 c0(k，l)的(i，j)和(k，l)求和此时模型的最优值（误差和）为此时模型的最优值（误差和）为0，所以说明在这个，所以说明在这个效用函数下，虽然得到的产品权重（效用）与问题中效用函数下，虽然得到的产品权重（效用）与问题中给出的数据并完全相同，但产品的相对偏好顺序是完给出的数据并完全相同，但产品的相对偏好顺序是完全一致的。全一致的。优优 化化 建建 模模航班航班AHAH、HBHB、HCHC可搭乘旅客的最大数量分别为可搭乘旅客的最大数量分别为1

21、20120、100100、110110人人机票的销售策略机票的销售策略 例例6.126.12：机票分配问题：机票分配问题出出发发地地-目的地目的地头头等等舱舱需需求（人）求（人）头头等等舱舱价价格（元）格（元）经济舱经济舱需需求（人）求（人）经济舱经济舱价价格（元）格（元）AH331905690AB（经经H转转机）机）2424443193AC（经经H转转机）机）1226167199HB441406980HC1618617103每条航线上分别分配多少每条航线上分别分配多少头等舱和经济舱的机票？头等舱和经济舱的机票？问问题题目目标标使销售收入使销售收入最大化最大化 优优 化化 建建 模模5个起终点

22、航线个起终点航线AH、AB、AC、HB、HC，依次编号为依次编号为i（i=1，2，,5）模型建立模型建立 相应的头等舱需求记为相应的头等舱需求记为ai，价格记为，价格记为pi相应的经济舱需求记为相应的经济舱需求记为b bi i，价格记为，价格记为q qi i 三个航班三个航班AHAH、HBHB、HCHC的顾客容量分别是的顾客容量分别是c c1 1=120=120，c c2 2=100=100，c c3 3=110=110 决策决策变量变量xi（起终点航线（起终点航线i i上销售的头等舱机票数）上销售的头等舱机票数）yi（销售的经济舱机票数）（销售的经济舱机票数）优优 化化 建建 模模目标目标收入最大收入最大约束约束x1+x2+x3+y1+y2+y3 c1 x2+x4+y2+y4 c2 x3+x5+y3+y5 c3容容量量限限制制需需求求限限制制0 xi ai0 yi bi线性规划模型线性规划模型(LP)头等舱：头等舱：33、10、12、44、16经济舱：经济舱：0、0、65、46、17总销售收入：总销售收入：39344（元）（元）