一般隐枚举法(2)(运筹学)汇总_第1页
一般隐枚举法(2)(运筹学)汇总_第2页
免费预览已结束，剩余11页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、一般隐枚举法(1)标准问题r min z = c()+ cx+.+ cnxn再內+绚 2 兀 2+ %叫汕假定:1)c0 (j=ln)2)e,c20Cj，-Cj(A)9%內+%2耳+ %二4石益取0或I（2）定义：子问题2有等式约束（2）定义：子问题C niin z = c0+ q十c3十c4x4十.十cnxn口4兀+舛”兀”二耳_绚|_门(B) 1,2,3x4兀取0或1令（A）的决策变量（Xi定(3)判定子问题已查明条件：(a)若( (0, 0,0)为问题可行解，则必为 此问题最优解。V 方1,bm均(b)若某约束条件中，正系数和小于常数项，则 此问题无解。( (C) )若已有某可行解，相应

2、目标函数值乙 (上界)若可断定，问题既使有解，z也z。则可停止，认为该问题已査明。例:min z = 2兀+ 3x2+ 8x34西+ x2+ 3X3 32X2+ 1兀“2 人取 0, 1步1： M常数项bpb2, b3= (-4, 3, 1)(a)各约束正系数和：5,&34,3,1(b)原问题未査明步2：1 Xi=l,x29x3未定min z = 2+ 3x2+ 8x35兀 3兀3 2bib22天2+花二b3(a)正系数和(5, 4, 3) 73x? 2兀3二1兀3取01C bi, b?, b3 ) =(7, 2, 1) 32X2+ 兀3 N 1兀2，兀3取0,1(为,厶2,厶3)=(

3、43,1)(a)(5,4,3) v(43,l)0+c. =3 -93 2兀3 2 _ 1兀3取0,1(5,厶2,/?3)=(-9,2,-1)(G)(0,3,1) A：(-9,2,-1)(b)3 +C2= 11 5(c)寸步6：1,2 min z =8X3步4：1(b)-3二- 43“ 3x3 1冷取0,1(也,/?2,方3)= (-4,3,1)(a)(),3,1)弋(4,3,1)(h)0 + 5 = 8 5(c) yj子问题k或kmin z= 5 +伽 + +c”&C%+16+1 十+呦,严|”二为hm(-)判定子问题的条件(是否査明)若(a)全部bi 0(/ =1丿和)，则Z = Z。，忑+i= =兀=。，为子问 题的最优解。已査明。(b)若有i,使EaiJ0(C)目前的最优解z = zo ,Zo+C“ zo则子问题解不会好于目前解。已査明。nS+1+1 + +（二）步骤：（1）定界。Z。（可行解必）;仙（3）子问题k未查明； 分为k,k+l,和乜订1若k,k+l满足（a）,得解门,目标Z1以Zi Zo。停，转k。若.k, k+1满足（B）或（C）,停，转去乩厂门;若k

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论