34指派问题(经典运筹学)-课件PPT（精）.ppt

一、决策问题与0-1变量件事是否做第决策变量ixi??????ix10做第i件事不做第i件事ni,,2,1??n件事中必须做k件并只做k件事kxxxn??????21n件事中最多做k件事kxxxn??????21n件事中至少做k件事nxxx?????21k?做第i件事的充要条件是做第j件事jixx??做第i件事的充要条件是不做第j件事jixx???1只在做了第i件事前提下才考虑是否做第j件事ijxx??该公司只有600万资金可用于投资,由于技术上的原因,投资受到以下约束: 1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案,使投资收益最大例1(投资问题)华美公司有5个项目被列入投资计划,每个项目的投资额和期望的投资收益见下表:180260580130460100321030021502101投资收益(万元)投资额(万元)项目)5,,2,1??ixi为决策变量(解:设????ix10投资第i个项目不投资第i个项目Z表示投资效益投资项目模型:543211808060210150maxxxxxxZ?????????????????xxxxx1321???xxx143??xx15xx?5,,2,11,0???ixi例2(布点问题)某城市共有6个区,每个区都可以建消防站。市政府希望设置的消防站最少,但必须满足在城市任何地区发生火火警时,消防车要在15分钟内赶到现场。据实地测定,各区之间消防车行驶的时间见右表。014252110206140152717275251501232284212712024163101732240102202728161001654321地区请为该市制定一个最节省的计划解:??????01ix在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2, …,6布点问题模型:654321minxxxxxxZ??????6,,2,11,0???ixi?????????xx1621???xxx143??xx1543???xxx1652???xxx最优解x2=1, x4=1最优值Z=2二、过滤隐枚举法(适合于变量个数较少的0-1规划)???????????????????????10,,:求xxxxxxxxxxxxxtsxxxZ过滤条件约束条件(1)(2)(3)(4)Z值(x1 x2 x3)(0 0 0)(0 0 1)(0 1 0)(1 0 0)(1 0 1)(1 1 0)(0 1 1)(1 1 1)√√√√0Z≥0枚举法:检验可行解:32次运算-25√√√√Z≥5318×366111321????Zxxx最优值,,最优解:运算次数:21计算目标函数值:8次√√√√三、指派问题与匈牙利法设有n个工作,要由n个人来承担,每个工作只能由一个人承担,且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 … j … n12…i…n指派问题模型:???jiijijxcZmin???????????????i=1,2, …,n121??????njijjjxxxx??j=1,2, …,nnjnixij,,2,1;,,2,11,0?????解:第i个人做第j 人件事Z表示总费用i=1,2, …,n; j=1,2, …,n第i个人不做第j 人件事??????????????????????????21212222211112111、指派问题的数学模型???jiijijxcZminnnnnnnnnnnnnxcxcxcxcxcxcxcxcxc?????????????????2211222222212**********?????????????121??????njijjjxxxx??i=1,2, …,nj=1,2, …,n当n=4时,有16变量,8个约束方程????????????????????????????????????11121222212112111??????????????????nninnnninixxxxxxxxxxxx???????例:现有4份工作,4个人应聘,由于各人技术专长不同,他们承担各项工作所需费用如下表所示,且规定每人只能做一项工作,每一项工作只能由一人承担,试求使总费用最小的