/ Z6 a: H( I# U7 K' }: T 3 ~# r% X" d8 Z9 N5 l' O. f§2 整数规划 : M4 J- E/ \4 h( M2 P4 G! Q8 G; @4 y6 m1 g$ F. L
2.1 定义 0 R, M# x) V! z规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适- g9 z* z7 W5 }% i7 z G2 L
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。, m0 G5 V7 \$ @# B0 N9 R! I. e3 O
2.2 整数规划的分类 ' D Z! z3 \9 P0 @如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类: 9 s1 `5 D. u* e3 A' L- a: s1 ^: K. l1 变量全限制为整数时,称纯(完全)整数规划。 / [# K6 T6 Y0 ~: c. [' m& n6 Q2 变量部分限制为整数的,称混合整数规划。 $ O' ]+ }( |' f4 b6 g7 z A) X; C2.3 整数规划特点* k) [) J7 l, [: ?
(i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况: , P, W6 ~/ {& O1 }% J①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。 + u. f/ ?" V$ ^1 K* ^②整数规划无可行解。 - @4 F( P8 G! y4 R8 J2 G% L . J6 \, H! C0 W③有可行解(当然就存在最优解),但最优解值变差。 ! d% t1 Y4 \. E: ~3 g: H& A m" P$ \% }* z, N3 l: W(ii) 整数规划最优解不能按照实数最优解简单取整而获得。& f* t: n- u+ \' c& B) N: J1 v
2.4 求解方法分类: 7 t" Q! g2 j/ A8 \" ]9 q/ I1 a(i)分枝定界法—可求纯或混合整数线性规划。0 Q% t+ L+ R: F z* j4 g" }
(ii)割平面法—可求纯或混合整数线性规划。 9 z0 L/ w; }# N$ A4 F+ E(iii)隐枚举法—求解“0-1”整数规划: & y4 } c$ a$ d2 _) J3 S0 ?①过滤隐枚举法;6 I+ Q2 G3 q3 V) D7 O
②分枝隐枚举法。8 e j$ m6 } ~3 Q D+ T* y) M
(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。! ^3 P4 i! a! d
(v)蒙特卡洛法—求解各种类型规划。- D' g' K, q" n' a7 G
" } ~( B+ p1 v2 Y" q, P0 s
- k( ~; n4 m. ^ ( C( P& c3 Z$ j. b0 f§3 非线性规划 % H3 \% i6 Q# X# m( b! O" m+ K; u5 r- n' m6 M
如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不象线性规划有 6 t: a5 U* a6 h" k8 ]0 J单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一般算法,各个方法都有自己特定的适用范围。% N9 P. u6 {' t# m) ?
; ^3 N6 z$ n; s. m& ]: C3.1 线性规划与非线性规划的区别7 J% v& z- H4 q# Q1 W& w% \$ q) J
如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任# r3 V# `3 T" s( {- s
意一点达到。 ; u$ Z0 z* ]2 z' H5 i y3.2 非线性规划的 Matlab 解法 c8 H& R$ g: j% b. j% HMatlab 中非线性规划的数学模型写成以下形式 6 O. Z/ ~5 n9 \, @, y7 a) i- M/ X* L4 `
其中f(x)是标量函数, Beq,Aeq,B,A 是相应维数的矩阵和向量, Ceq(x),C(x) 是非线性向量函数。2 O& c% h; o2 n& n
Matlab 中的命令是 8 E( t: V# A$ k% R8 G+ K5 v0 }X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)) ?& [/ l% y1 g- @+ |3 @
它的返回值是向量 x ,其中 FUN 是用 M 文件定义的函数f(x);X0 是 x 的初始值;A,B,Aeq,Beq 定义了线性约束 Beq= X *Aeq , A*x≤ B,如果没有线性约束,则A=[],B=[],Aeq=[],Beq=[];LB 和 UB 是变量 x 的下界和上界,如果上界和下界没有约束,则 LB=[],UB=[],如果 x 无下界,则 LB 的各分量都为-inf,如果 x 无上界,则 UB的各分量都为 inf;NONLCON 是用 M 文件定义的非线性向量函数Ceq(x),C(x) ;OPTIONS定义了优化参数,可以使用 Matlab 缺省的参数设置。! @& w. @- N6 i
" v% H# w/ k' V/ E9 O( u: f
3.3 相应问题 / ~" u7 J+ @. Z! I ) `+ m7 D& Z$ Q, E; q' e" g无约束问题(一维搜索方法、二次插值法、无约束极值问题的解法)、约束极值问题(二次规划、罚函数法)、飞行管理问题) _9 F: C! f1 l; j8 k
1 r; b& O! Y) r
, ~+ K: ?5 @2 o* o ) ` J c, r+ l§4 动态规划(搞ACM的较熟)8 }" ~: | C, h
/ @- M; L2 Z; ~) i, j- k N动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。 ; b) b, B/ [( B1 s % G# C( v: @4 ~& M虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。 z# X B: Q7 S5 ]* _; Y: O) b' z" E* v
2 w3 y0 d2 c1 N _0 i. E/ Y + y2 {$ N% J {4 S& y' D§5 与网络模型及方法(搞ACM的较熟)2 E) g8 V$ e1 k2 T/ N6 ~- V