优化模型举例

1、2022-4-26数学建模方法2022-4-26建立数学模型的方法建立数学模型的方法层次分析法层次分析法最小二乘法最小二乘法差分法差分法定性理论法定性理论法优化法优化法变分法变分法回归分析法回归分析法机理分析法机理分析法统计分析法统计分析法聚类分析法聚类分析法主成分分析法主成分分析法马尔科夫预测法马尔科夫预测法系统分析法系统分析法模糊数学法模糊数学法灰色系统法灰色系统法2022-4-262022-4-26优化模型是中国大学生建模竞赛常见的类型，占很大的比重。92 年以来，优化模型有：94年A题：“逢山开路”设计最短路径。95年A题：“一个飞行管理问题”，线性规划 和非线性规划模型。96年A题：

2、“最优捕鱼策略”，以微分方程为 基础的优化模型。2022-4-2696年B题：“洗衣节水问题”，以用水量为目 标函数的优化模型。97年A题：“零件的参数设计”，随机优化模型。97年B题：“截断切割”，动态优化模型。98年A题：“投资的收益和风险”，双目标优 化模型。98年B题：“灾情巡视的最佳路线”，0-1线性 规划模型。2022-4-2699年A题：“自动化车床管理”，双参数规划模型。99年B题：“钻井布局”，非线性混合整数规划模型。00年B题：“钢管订购和运输”，二次规划模型。01年B题：“公交车调度”，双目标规划模型。02年A题：“车灯线光源的优化设计”，规划模型。2022-4-2603

3、年B题：“露天矿生产的车辆安排”，非线性规划模型。04年B题：“电力市场的输电阻塞管理”，双目 标线性规划模型。05年B题：“DVDDVD在现租赁在现租赁”，0-1规划模型。06年A题：“出版社的资源优化配置出版社的资源优化配置”，线性规划模型。2022-4-26（一）优化模型的数学描述（一）优化模型的数学描述下的最大值或最小值，其中下的最大值或最小值，其中.,.,)(mihi210 x.,.,),)()(piggii2100 xx设计变量（决策变量）设计变量（决策变量）目标函数目标函数),.,(nxxxx321x将一个优化问题用数学式子来描述，即求函数将一个优化问题用数学式子来描述，即求函数

4、)(xfu 在约束条件在约束条件和和x)(xf x 可行域可行域2022-4-26.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(max)min(ortosubjectts .“受约束于”之意2022-4-26（二）优化模型的分类（二）优化模型的分类1.1.根据是否存在约束条件根据是否存在约束条件 有约束问题和无约束问题。有约束问题和无约束问题。2.2.根据设计变量的性质根据设计变量的性质 静态问题和动态问题。静态问题和动态问题。3.3.根据目标函数和约束条件表达式的性质根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标

5、规划等。线性规划，非线性规划，二次规划，多目标规划等。2022-4-26（1）非线性规划）非线性规划目标函数和约束条件中，至少有一个非线性函数。目标函数和约束条件中，至少有一个非线性函数。.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(min2022-4-26.,.,.,.,.minnixnibxatsxcuinkikikniii2102111（2）线性规划（）线性规划（LP） 目标函数和所有的约束条件都是设计目标函数和所有的约束条件都是设计变量的线性函数。变量的线性函数。2022-4-26（3）二次规划问题）二次规划问题目标函数为二次函数，约

6、束条件为线性约束目标函数为二次函数，约束条件为线性约束.,.,.,.,.)(min,nixnibxatsxxbxcxfuinjijijnjijiijniii21021211112022-4-265. 根据变量具有确定值还是随机值根据变量具有确定值还是随机值 确定规划和随机规划。确定规划和随机规划。4. 4. 根据设计变量的允许值根据设计变量的允许值整数规划（整数规划（0-1规划）和实数规划。规划）和实数规划。2022-4-26（三）建立优化模型的一般步骤（三）建立优化模型的一般步骤1.确定设计变量和目标变量；确定设计变量和目标变量；2.确定目标函数的表达式；确定目标函数的表达式；3.寻找约束条

7、件。寻找约束条件。2022-4-26最优捕食策略最优捕食策略运输问题运输问题点菜问题点菜问题旅行商问题旅行商问题（四）线性规划模型举例（四）线性规划模型举例2022-4-26实例实例1 最优捕食者策略最优捕食者策略 假设存在一种捕食者，穴居假设存在一种捕食者，穴居A处，在处，在B和和C处有两个食物处有两个食物源源X、Y。捕食者从巢穴。捕食者从巢穴A到区域到区域B和和C带回一单位的食物所需带回一单位的食物所需的时间估计为的时间估计为2分钟和分钟和3分钟。捕食者在区域分钟。捕食者在区域B平均花平均花2分钟捕分钟捕获一单位食物获一单位食物X，而在区域，而在区域C只花只花1分钟就捕获一单位食物分钟就捕

8、获一单位食物Y。一单位一单位X所产生的热量估计为所产生的热量估计为25焦耳，一单位焦耳，一单位Y所产生的热量所产生的热量估计为估计为30焦耳。假设捕食者每天不可超过焦耳。假设捕食者每天不可超过120分钟用于从巢穴分钟用于从巢穴到食物区来回行走，同时每天不可能花到食物区来回行走，同时每天不可能花80分钟以上搜寻食物。分钟以上搜寻食物。估计捕食者每天能获得的最大热量值是多少？估计捕食者每天能获得的最大热量值是多少？2022-4-26一单位实物一单位实物 行走时间行走时间( (分钟分钟) ) 捕获时间捕获时间( (分钟分钟) ) 热量热量( (焦耳焦耳) )X2225Y3130 假设捕食者每天能得到

9、 x 单位的食物 X 和 y 单位的食物 Y ，则每天获得的热量值为.,.max00802120323025yxyxyxtsyxu2022-4-26xyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳焦耳图解法图解法2022-4-26编制Matlab程序：f=-25,-30;Aeq=;Beq=;A=2,3;2,1;B=120;80;xm=0;0;xM=Inf;Inf;ff=optimset;ff.Tolx=1e-15;ff.TolFun=1e-20;TolCon=1e-20;x,f_opt,key,c=linprog(

10、f,A,B,Aeq,Beq,xm,xM,0;0,ff)2022-4-26设有某物资从设有某物资从m个发点个发点A1,A2,Am输送到输送到n个收点个收点B1,B2,Bn，其中每个发点发出量分别为其中每个发点发出量分别为 每个收点输入量分别每个收点输入量分别为为 ，并且满足，并且满足从发点从发点A到收点到收点B的距离（或单位运费）是已知的，设的距离（或单位运费）是已知的，设为为 。一个调运方案主要由一组从发。一个调运方案主要由一组从发点点 到收点到收点 的输送量的输送量 来描述。来描述。问题：问题：寻求一个调运方案，使总运输费用达到最小。寻求一个调运方案，使总运输费用达到最小。maaa,.,21

11、nbbb,.,21minijjiba1),.,.,(njmicij2121iAjBijx实例实例2运输问题运输问题2022-4-26B1 B2 . BnA1A2Ama1a2am b1 b2 . bn.X11 X12 . X1nX21 X22 . X2nXm1 Xm2 . Xmn收点收点发点发点2022-4-26总的费用总的费用njjjnnjxCxCxCxCBA11111121211111.njjjnnjxCxCxCxCBA12222222221212.minjijijxCf11A1A1的总费用的总费用A2A2的总费用的总费用2022-4-26s.t.njmixnjbxmiaxijmijijnj

12、iij,.,.,.,.,.,.,21210212111minjijijxCf11min数学模型数学模型求解：单纯形方法。2022-4-26实例实例3 点菜问题点菜问题 我们在餐馆中点菜，我们在餐馆中点菜， 需要包含需要包含某些营养成份，但同时又希望总价某些营养成份，但同时又希望总价格最低。下表是这个餐馆的部分菜格最低。下表是这个餐馆的部分菜单，请你提供合理的选菜方案。单，请你提供合理的选菜方案。序号序号菜单菜单价格价格(元元 ) 蛋白质蛋白质 淀粉淀粉维生素维生素矿物质矿物质1菜肉蛋卷菜肉蛋卷1810112炒猪肝炒猪肝21.501013色拉色拉12.500104红烧排骨红烧排骨2310005咖

13、喱土豆咖喱土豆10.501006清汤全鸡清汤全鸡3210012022-4-26建模建模设设xi 表示点序号为表示点序号为i 的菜，则的菜，则目标函数：目标函数：约束条件：约束条件：1 0,1111. .6216213152641orxxxxxxxxxxxxxts654321325 .10235 .125 .2118minxxxxxxz2022-4-26注：注：0-10-1规划问题规划问题可用可用MatlabMatlab求解（薛定宇求解（薛定宇PP189PP189），对于简单问题亦可使用穷举法。），对于简单问题亦可使用穷举法。下面用下面用Matlab软件，求得结果：软件，求得结果：f=18,21

14、.5,12.5,23.0,10.5,32.0;Aeq=;Beq=;A=-1 0 0 -1 0 -1;0 -1 0 0 -1 0;-1 0 -1 0 0 0;-1 -1 0 0 0 -1;B=-1;-1;-1;-1;x=bintprog(f,A,B,)x = 1 0 0 0 1 0; fopt=28.52022-4-26进一步考虑进一步考虑如果至少点四个不同的菜，结果又如何？如果至少点四个不同的菜，结果又如何？1 0,41111. .6216543216213152641orxxxxxxxxxxxxxxxxxxxts654321325 .10235 .125 .2118minxxxxxxz202

15、2-4-26利用利用matlab 软件，得软件，得f=18,21.5,12.5,23.0,10.5,32.0;Aeq=;Beq=;A=-1 0 0 -1 0 -1;0 -1 0 0 -1 0;-1 0 -1 0 0 0;-1 -1 0 0 0 -1;-1 -1 -1 -1 -1 -1;B=-1;-1;-1;-1;-4;x=bintprog(f,A,B,)x = 1 1 1 0 1 0Fopt=62.52022-4-26点菜点菜价格（元）价格（元）点菜点菜价格（元）价格（元）1,2,3,6844,5,3,267.54,2,1,694.54,5,3,6784,5,1,2736,5,1,2824,5

16、,1,683.56,5,3,1734,5,3,1646,5,3,276.51,2,3,562.5也可利用穷举法，得也可利用穷举法，得2022-4-26实例实例4 旅行商问题旅行商问题(Travelling Saleman Problem）TSP 某商人由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。2022-4-26建模建模TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,n问题就转化为：,21niii21,n,nkkk,iid01)(其中 为城市 到 的距离，最

17、小。)(1kk,iidki1ki010nii求一个 的排序 使得2022-4-26TSP的数学规划形式：的数学规划形式：ijjiijxdmin 1or 0)1(111 ts00ijijjinjijniijxjn,ii,jnnxuuxx.表示进入且仅进入城表示进入且仅进入城 j 一次一次;表示离开且仅离开城表示离开且仅离开城 i 一次一次;保证连通性。保证连通性。其中其中 表示若该旅行商在访问城表示若该旅行商在访问城 i i 后接着访问城后接着访问城 j j ，则令，则令 ，否则令，否则令),(0 ni,jxij1 ijx0 ijx（P）2022-4-26定理：0-1规划问题(P) 即为旅行商问

18、题。证明：证明：将 n+1个城市看作顶点，可以作为一个完全图（即任意两点均有边相连图），1,2,n的每一排序对应于图中一个由0点出发经每一顶点一次最后回到0点的图。现在只需证明 是 (P) 的可行解的充分必要条件 对应的边组成完全图中的一个圈。ijx1 ijx2022-4-26(P) 的可行解必构成完全图中的若干回路（由约束条件中的前两个得知）。假设不然，设城 构成不过0的回路由第三个条件得：kiii,2111)-k,1,2,1(tnnuunnuuiiiiktt11上式两边相加得 ，矛盾。1 nn现证明这些回路必经过0，从而只能是唯一的回路，即完全图中的一个圈（Hamilton圈）。2022-

19、4-26反之，对每一由城 0 出发过每城一次回到城 0的圈均可找到一组 ，使得条件3成立。事实上， 可如下取之。 iuiu现令 ，若城 i 为第 k 个访问的城市，则令 ，于是，当 时， ， 从而 成立，证毕。00ukui1 itx1tiuu1nnuuti2022-4-26模型求解模型求解1 穷举法穷举法21,n,的不同排序有 个，当n稍大!n时，很难找出最佳答案。这是个NP-完全问题。2 近似算法近似算法 贪婪算法贪婪算法西德曾对一个有西德曾对一个有318318个点的问题找到了最优方案。个点的问题找到了最优方案。3 利用数学软件利用数学软件2022-4-26 一个送报员从送报中心出发一个送报

20、员从送报中心出发到五个小区送报，最后要回到送到五个小区送报，最后要回到送报中心。送报中心到各小区的距报中心。送报中心到各小区的距离及各小区间的距离均已知（见离及各小区间的距离均已知（见表表1），问送报员应按怎样的线路），问送报员应按怎样的线路行驶较好？（距离单位为千米）行驶较好？（距离单位为千米）送报线路安排送报线路安排2022-4-26表表1 1 送报中心及各小区间的距离送报中心及各小区间的距离01234500745861703109142430591035105014948991407561410970起起终终2022-4-260123450074586170310914243059103

21、5105014948991407561410970贪婪算法贪婪算法送报中心及五个小区分别用送报中心及五个小区分别用0 0，1 1，2 2，3 3，4 4，5 5来记。来记。算法的中心思想：算法的中心思想：每次寻找最小距离每次寻找最小距离 。起起终终2022-4-2601234500745861703109142430591035105014948991407561410970起起终终2132022-4-2601234500745861703109142430591035105014948991407561410970起起终终021433052022-4-26021433050123450074

22、5861703109142430591035105014948991407561410970起起终终4572022-4-260214330501234500745861703109142430591035105014948991407561410970起起终终4572022-4-260214330501234500745861703109142430591035105014948991407561410970起起终终457992022-4-2601234500745861703109142430591035105014948991407561410970起起终终0214530439795总距离

23、：37千米。2022-4-26应用例子应用例子 某类工件在加工时需在一些指定的位置上钻孔。钻头从初始位置出发，到各处钻孔，最后回到初始位置，以便继续对下一工件加工。问应如何安排钻孔的次序，使钻头在加工过程中移动的总距离最小。2022-4-26报童的诀窍报童的诀窍2022-4-261.确定设计变量和目标变量确定设计变量和目标变量2.确定目标函数的表达式确定目标函数的表达式l每天的总收入为目标变量每天的总收入为目标变量l每天购进报纸的份数为设计变量每天购进报纸的份数为设计变量3.寻找约束条件寻找约束条件l寻找设计变量与目标变量之间的关系寻找设计变量与目标变量之间的关系l设计变量所受的限制设计变量所

24、受的限制2022-4-26若每天购进若每天购进 0 份，份， 则则收入为收入为 0。若每天购进若每天购进 1 份，份，售出，则售出，则收入为收入为 a- -b。退回，则退回，则收入为收入为 ( (b-c)。若每天购进若每天购进 2 份，份，售出售出1份，则份，则收入为收入为 a-b (b-c) 。退回，则退回，则收入为收入为 2( (b- -c)。售出售出2份，则份，则收入为收入为 2(a-b) 。收入还与每天的需求量有关，而需求量是随机变量收入还与每天的需求量有关，而需求量是随机变量则收入也是随机变量，通常用均值，即期望表示。则收入也是随机变量，通常用均值，即期望表示。2022-4-26数学

25、期望数学期望离散型随机变量离散型随机变量 X 的概率分布为的概率分布为), 2 , 1()(nipxXPii则随机变量则随机变量 X 的数学期望值为的数学期望值为), 2 , 1()(nipxXEii连续型随机变量连续型随机变量 X 的概率密度函数为的概率密度函数为)(xf则随机变量则随机变量 X 的数学期望值为的数学期望值为dxxxfXE)()(期望值反映了随机变量取值的期望值反映了随机变量取值的“平均平均”意义！意义！2022-4-261 设每天购进设每天购进 n 份，份，日平均收入为日平均收入为 G(n)3 每天需求量为每天需求量为 r 的概率的概率 f(r), r=0,1,22 售出一

26、份赚售出一份赚 a- -b；退回一份赔；退回一份赔 b- -c2022-4-26nr nr nrnrrnfbarfrncbrbanG01)()()()()()(求求 n 使使 G(n) 最大最大每天的收入函数记为每天的收入函数记为U(n)，则，则rnnbarnrncbrbarnU )()()(),(收入函数的期望值为收入函数的期望值为rbar)(赚售出)(rncbrn赔退回nban)( 赚售出2022-4-26nndrrnpbadrrprncbrbanG0)()()()()()(将r视为连续变量概率密度）()()(rprfdndGnndrrpbadrrpcb0)()()()(ndrrpbann

27、pba)()()()(ndrrpcbnnpba0)()()()(2022-4-260dndGcbbadrrpdrrpnn)()(0dndGnndrrpbadrrpcb0)()()()(使报童日平均收入达到最大的购进量使报童日平均收入达到最大的购进量n应满足上式。应满足上式。因为cabadrrpn0)( 10drrp 10drrpdrrpnn2022-4-26售完的售完的概率概率cbbadrrpdrrpnn)()(0因为当购进n份报纸时， drrpPn01是需求量r不超过n的概率 drrpPn2是需求量 超过rn的概率售不完的售不完的概率概率上式意义为：购进的份数上式意义为：购进的份数n之比，恰

28、好等于卖出一份赚的钱之比，恰好等于卖出一份赚的钱ba与退回一份赔的钱与退回一份赔的钱cb之比。之比。应该使卖不完与卖完应该使卖不完与卖完的概率的概率2022-4-26根据需求量的概率密度 rp的图形可以确定购进量n在图中用21,PP分别表示曲线下的两块面积，则cbbaPP21 rpO n r1P2Pcbbadrrpdrrpnn)()(0当报童与报社签订的合同使报童每份赚钱与赔钱之比越大当报童与报社签订的合同使报童每份赚钱与赔钱之比越大时，报童购进的份数就应该越多。时，报童购进的份数就应该越多。结论2022-4-26注意注意l求解技巧：求解技巧：连续化连续化l建模方法：建模方法：从特殊到到一般从

29、特殊到到一般归纳抽象归纳抽象1998年年B题题 灾情巡视路线灾情巡视路线单旅行商到多旅行商单旅行商到多旅行商1999年年B题题 钻井布局钻井布局网格的平行移动到旋转运动网格的平行移动到旋转运动2000年年B题题 钢管的订购与运输钢管的订购与运输线形到树形线形到树形2000年年C题题 飞越北极飞越北极球形到椭球形球形到椭球形人口模型，战争模型人口模型，战争模型l随机变量的目标函数：随机变量的目标函数：期望值期望值航空公司的超额订票模型航空公司的超额订票模型2022-4-26l社会热点问题社会热点问题 2022-4-26经济发经济发展问题展问题2022-4-26环保问题环保问题2022-4-26新

30、一轮全国性房价上涨已经开始，土地也随之成了抢新一轮全国性房价上涨已经开始，土地也随之成了抢手货。令地产商为难的是，拿不到地，很可能会被淘手货。令地产商为难的是，拿不到地，很可能会被淘汰出局，但多拿了地，又意味着要承担诸多风险。汰出局，但多拿了地，又意味着要承担诸多风险。 房价问题房价问题2022-4-26 股票问题股票问题 依照机构乐观的分析，依照机构乐观的分析，2007年股票市场整体机年股票市场整体机会大于风险，但股指整体在高位运行，市场预期震会大于风险，但股指整体在高位运行，市场预期震荡幅度加大。荡幅度加大。 2022-4-26煤煤矿矿管管理理问问题题2022-4-26高校本科评估就是一场

31、闹剧高校高校本科评估就是一场闹剧高校 高校高校本科本科评估评估问题问题 2022-4-26中国石油价格将走向何方中国石油价格将走向何方? 石石油油价价格格问问题题2022-4-26洞洞庭庭湖湖鼠鼠患患问问题题20亿田鼠洞庭亿田鼠洞庭“跑马圈地跑马圈地 ”2022-4-26某服务部一周中的每天需要不同数目的雇员： 周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人。现规定应聘者需连续工作五天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。课后作业课后作业1 服务员的聘用问题服务员的聘用问题2022-4-26优化问题优化问题决策变量：决策变

32、量：周一到周日每天聘请的人数，记为目标函数目标函数：聘用总人数约束条件：约束条件：每天需要的人数，由于每人连续工作5天，所以周一的雇员应是周四到周一聘用的，按照需要至少有50人，于是7654321xxxxxxxz5076541xxxxx7654321,xxxxxxx2022-4-26整数 0,90908050505050. .72176543654325432174321763217652176541xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxts7654321minxxxxxxxz优化模型优化模型2022-4-26求解模型求解模型用 LINDO 求解 美国芝加

33、哥大学的 linus Schrage 教授于1980年前后开发的一套专门用于求解优化问题的软件包。包括 4 种主要产品：LINDO，LINGO，LINDO API，WathsBest!LINDO：linear Interactive and Discrete Optimizer.交互式的线性和离散优化求解器交互式的线性和离散优化求解器LINDGO：linear Interactive and General Optimizer.交互式的线性和通用优化求解器交互式的线性和通用优化求解器用以求解线性规划（用以求解线性规划（LPLP）和二次规划（）和二次规划（ QP QP ）问题）问题用以求解非线性

34、规划问题用以求解非线性规划问题2022-4-26用 LINDO 求解TITLE 服务员聘用问题的LINDO模型MIN x1+x2+x3+x4+x5+x6+x7SUBJECT TOMON) x1+ +x4+x5+x6+x7=50TUE) x1+x2+ +x5+x6+x7=50WED) x1+x2+x3+ +x6+x7=50THU) x1+x2+x3+x4+ +x7=50FRI) x1+x2+x3+x4+x5 =80SAT) x2+x3+x4+x5+x6 =90SUN) x3+x4+x5+x6+x7=90ENDGIN 7General Integer求解模型求解模型2022-4-26结果输出结果输

35、出主要结果OBJECTIVE FUNCTION VALUE1) 94.00000VARIABLE VALUE x1 0.000000 x2 4.000000 x3 40.000000 x4 2.000000 x5 34.000000 x6 10.000000 x7 4.000000至少聘用服务员至少聘用服务员9494人，周一到周人，周一到周日分别聘用人数为日分别聘用人数为（0 0，4 4，4040，2 2，3434，1010，4 4）2022-4-26 一家制造计算机的公司计划生产两种产品：两种计算机使用相同的微机处理芯片，但一种使用27英寸的显示器，而另一种使用31英寸的显示器。除了400000美元的固定费用外，每台27英寸显示器的计算机花费1950美元，而31 英寸的需要花费2250美元。制造商建议每台27英寸显示器的计算机零售价格为3390美元，而31 英寸的计算机零售价格为3990美元。课后作业课后作业2 制造问题制造问题2022-4-26 销售人员估计，在销售这些计算机的市场上，一种类型的计算机每多卖出一台，零售价格就下降0.1美元。此外，一种类型的计算机的销售也会影响另一种类型的销售：每销售一