数学建模《运筹与统计组合优化》.docx

数学建模《运筹与统计组合优化》.docx

《数学建模《运筹与统计组合优化》.docx》由会员分享，可在线阅读，更多相关《数学建模《运筹与统计组合优化》.docx（71页珍藏版）》请在冰点文库上搜索。

数学建模《运筹与统计组合优化》

数学建模

浙江大学数学系谈之奕

tanzy@

运筹与统计

组合优化

组合优化

数学建模

•通常把从有限个可行解中找出使某个目标函数达到最优的解的优化问题称为组合优化

（CombinatorialOptimization）

•组合优化与组合学（Combinatorics）

同为研究离散对象的数学分支，但两

者侧重不同。

后者着重研究满足特定

性质对象的存在性，计数，构造等问

题，前者要求在众多可行解中按一定

标准选出最优解

Journalof

Combinatorial

Optimization

Discrete

Optimization

2

背包问题

数学建模

•背包问题（KnapsackProblem）

•一背包客准备参加自助游，想要

携带的物品很多，但随身背包的容量有限，因此希望通过综合考虑，使放入背包中的物品对旅行的帮助最大

n

•设物品数为，由于每个物品可

以选择放入或不放入，因此可行解数目不超过2n个

33

旅行售货商问题

数学建模

•旅行售货商问题（TravelingSalesmanProblem，

TSP）

•一推销商想在若干个城市中推销自己的产品。

计划从某个城市出发，经过每个城市恰好一次，最后回到出发的城市。

假设城市之间距离已知，推销商应如何选择环游路线，使他走的路程最短

1

2n

•每一条环游路线对应于的一个排列。

不同的排

（n

1）!

列数目共有个

4

环游美国的TSP

数学建模

美国48个州首府的TSP环游（上图的环游顺序与1954年论文相

美国49个城市的最优TSP环游

Dantzig,G.,Fulkerson,R.,Johnson,S.,

SolutionofaLarge-ScaleTraveling-Salesman

Problem,JournaloftheOperationsResearch

SocietyofAmerica,2,393-410

同，但不

再是最优

的，下图

为最优环

游）

5

VLSI设计中的TSP

数学建模

•441个焊点的印刷电路板

Applegate,D.L.,Bixby,R.E.,ChvátalV.,Cook,W.,EspinozaD.G.,Goycoolea,M.,Helsgaun,K.,CertificationofanoptimalTSPtourthrough85,900cities,OperationsResearchLetters,37,11-15,2009.

6

指派问题

数学建模

•指派问题（AssignmentProblem）

nn

•设有项任务需分配给位员工，每人完成其

ijcij中一项，员工完成任务所需时间为，如

何分配可使完成所有任务所用总时间最少

•不同的分配方案共有种

n!

7

枚举

数学建模

•组合优化问题通常

不能通过枚举所有

可行解并加以比较

来求解，其原因是

可行解的数目可能

是一很大的数，以

致于当前或相当长

的一段时间内人力

或计算机不能承受

201

按一千克小麦含

25000粒计算，

棋盘上的小麦总

计约为7400亿

吨，按目前的平

均产量计算，是

全世界一千多年

生产的全部小麦

63

2

9223372036

9.2210

18

854775808

舍罕王PK西萨·班·达依尔

8

函数量阶

数学建模

102040100函数

lgn

1秒1.30秒1.60秒2秒

n

4.34秒8.69秒17.37秒43.4秒

5

n

12小时16天514天138年

n

2

n!

444秒

18.2天

5.27天

151世纪

世纪

38世纪1.11038

.31038世纪1.11038

1

.710

20

世纪

1148

.2101148

世纪

n

n

138年

11.410190

.4101

16

世纪54世纪

世纪

.610

9

函数量阶

数学建模

快100倍快10000倍快1000000倍现在的计算机

lgn

NN2

N4N6

n

N100N10000N1000000N

5

n

N2.51N6.31N15.85N

n

2

N

N6.64N13.28N19.93

10

Top500

数学建模

http:

//www.top500.org

gigaFLOPS=

teraFLOPS=

10

9

10

12

时间公司计算机浮点数运算次数提高倍数1993.6（首届）TMCCM559.70GFlops

1998.6（11届）IntelASCI-Red1338.00GFlops22.42003.6（21届）NECNECVector35860.00GFlops600.72008.6（31届）IBMBladeCenter1026.0TFlops171862010.11（36届）国防科大天河一号2566.0TFlops42981

2012.12（40届）CrayTitan17590.0TFlops294640

11

匈牙利算法

数学建模

•1955年，Kuhn给出了指派问

题时间复杂性为4的算

O（n）

法。

该算法建立在两位匈牙利数学家DenesKönig和JenőEgerváry的工作基础之上，Kuhn将其命名为匈牙利算法

•匈牙利算法没有也不可能枚

举所有可行解，其时间复杂

性远小于可行解数目。

但对

背包、TSP等问题，目前还

没有找到有类似性质的算法

Kuhn,H.W.,TheHungarianMethodfor

theAssignmentProblem,2,83–97,1955

HaroldW.KuhnAwardSelectthebest

paperrepresentingthejournalfromamong

allpaperspublishedinthejournalsinceits

foundingin1954andnametheawardafter

thefirstrecipient

12

运筹与统计

计算复杂性

计算复杂性

数学建模

•计算复杂性（computationalcomplexity）理论可将组合优化问题按难度分类，从而

为进一步研究指明方向

•计算复杂性理论建立在名为

图灵机（Turingmachine）

的理论计算模型之上。

该模

型由Turing于1936年提出，

它能模拟目前所有的合理计

算模型

Turing,A.,Oncomputable

numbers,withan

AlanTuring

英国计算机学家

applicationtothe

Entscheidungsproblem,（1912-1954）

ProceedingsoftheLondon

MathematicalSociety,S2-42,

230–265

14

图灵机

数学建模

B111B11BB1B

B11B111BBB

15

规模

数学建模

•描述某问题一实例所需的计算机存储单元数称为该实例的规模（size）

•在计算机中，常用二进制表示整数，因此存储大小为n的整数所需字节数（连同表示整数结

尾的空格）为logn2

2

nn

2

logc22nlogc

•指派问题实例规模为，

2ij2iji,j1i,j1

也可简记为，两者可用多项式相互

nc

logmax

2ij

i,j

限制

16

时间复杂性

数学建模

•用算法执行过程中所需的加法、比较、赋值等基

本运算次数表示算法所用的时间

•算法的时间复杂性（timecomplexity）是关于实

nf（n）

例规模的一个函数，它表示用该算法求解所有规模为n的实例中所需基本运算次数最多的

那个实例的基本运算次数

fp（）

（n）O（p（n））

•若一算法的时间复杂性，这里

为一多项式，则称它为多项式时间算法。

不能这样限制时间复杂性函数的算法称为指数时间算法

17

有效算法

数学建模

•结合关于函数增长速度的比较，和算法的实际运行效果，通常将多项式时间算法称为有效算法（efficientalgorithm）

——Edmonds,J.Paths,trees,andflowers.CanadianJournalofMathematics,17,449–467,1965

18

P类

数学建模

•若一问题已找到多项式时间算法，该问题属于多项式时间可解问题类（polynomialsolvableproblemclass），记为P。

证明一问题属于P类只需设计出求解该问题的多项式时间算法

•指派问题即为P类中的问题；判断一个整数是否为素数也属于P类

Agrawal,M.,Kayal,N.,Saxena,N.,PRIMESisinP.AnnalsofMathematics,160,2,781-793,2004

19

NP类

数学建模•所谓非确定性算法在多项式时间内求解某问题，是指它能

•猜想出该实例的一个可行解，其规模不超过实例规模的多项式函数

•在实例规模的多项式时间内验证猜想是否正确

•非确定性算法多项式时间可解问题全体组成的集合称为非确定性算法多项式时间可解问题类（nondeterministicpolynomialsolvableproblemclass），记为NP。

NP类中的问题称为NP问题

•非确定性算法在现实生活中并不存在，只是为研究而定义的一种理论算

法

•NP类更严格的定义需借助非确定性图灵机

•NP类的提法仅限于输出仅为“是”、“否”两种的判定问题（decisionproblem），但优化问题都有一个与之复杂性等价的判定问题

20

P=NP猜想

数学建模

•P类中的问题是多项式时间

可求解问题，而NP类中的

问题仅是多项式时间可验证

MillenniumPrizeProblems

P

NP

问题。

因此

P

•是否有NP成立是数学和

理论计算机科学中一个重要

课题

P

NP

•尽管猜想是未决问

P

NP

题，但是普遍相信成

立。

在此假设下可进一步研

究NP类内部的结构

http:

//www.claymath.org/

21

NP-完全问题

数学建模

•NP类中最“难”的问题子集称为NP－完全类，记为NP-C。

NP-C类中的问题称为NP－完全问题（NP-completeproblem）

•若NP-C类中有一个问题有多项式时间算法，则NP类

中所有问题都有多项式时间算法

P=NP=NP-C

P

NP-C

NP

PNP（PNP-CNP）PNP

22

P，NP，与NP－完全

数学建模

וNP类是没有多项式时间算法的问题组成的集合

•P问题也属于NP类，它们都有多项式时间算法

•NP类并未包含所有问题，没有多项式时间算法的问题并不都属于NP类

P

NP

•仅是猜想，若，NP类中所有问题均有多

PNP项式时间算法

וNP类中的问题是最难的问题

•混淆NP类和NP-C类的概念

•NP-C类仅是NP类中最难的问题，在NP类之外可能存在着更“难”的问题

23

可满足性问题

数学建模

•1971年，Cook证明了可满足性问题（Satisfiability,SAT）是NP－完全的

•设为取值或的Boolean变

xx01量，1,给定,Bnoolean函数

mn

f（x,,x）axb（1x）,

1nijjijj

其中，是否存在变量的一种

i1j1

赋值ab，使得

0,1

ijij

fxx

xx0

（,,）1

00

jj1n

StephenArthurCook

（1939－）

美国计算机学家

1982年图灵奖得主

24

NP－完全问题

数学建模

•1973年，Levin独立地证明了若干搜索问题是NP－完全的

1956年Gödel致vonNeumann信，信中对若干数理逻辑问题算法和复杂性的讨论被认为是计算复杂性研究的开端

LeonidAnatolievich

Levin

（1948－）

KurtFriedrichGödel

（1906－1978）

奥地利哲学家、数学

苏联计算机学家家

25

归约

数学建模

•运用归约（reduction）技术可以建立起两个组合优化问题之间的某种联系，进而由前一个问题的NP－完全性证明后一个问题也是NP－完全的

•1972年，Karp证明了21个重要组合优化问题的NP－完全性。

这些问题

与实际优化问题的形式更为接近，因

而利用它们归约证明其它优化问题的

NP－完全性更为便捷

RichardManning

Karp

（1935－）

美国计算机学家

1985年图灵奖得主

26

NP－完全问题

数学建模

SAT•1978年，计算复杂

性领域奠基性著作

《Computersand3SATIntractability》出版，书中选定7个

三维匹配顶点覆盖

组合优化问题作为

基本NP－完全问

题，并给出了它们Hamiltion圈团

划分

NP－完全性的详

细证明Garey,M.R.,Johnson,D.S.,Computersand

Intractability:

AGuidetotheTheoryofNP-Completeness,Freeman,1978

27

划分问题

数学建模

•划分问题（partition）

A

•给定一正整数集{a1,a,,an}，问是否存在子

2

A

AA/

1,A1A

集，使得A，，且满足

1AO

222

1

n

aaa

iij

2

aA1aA2j1

ii

•整数规划是NP－完全问题

n1n

axa,x{0,1}

•整数规划是否有可行解与划分问题实

jjjj

2

j1j1

例答案为“是”等价

28

子集和问题

数学建模

•子集和问题（SubsetSum）

{a1,a,,an}B

AA

•给定正整数集和数，问是否存在子集，

21

aB

使得

iaA

i1

1n

•取B，a子集和问题与划分问题等价子集和是NP－完全问题

j

2

j1

•子集和问题的优化形式

•求子集，使得且尽可能大

aBa

AA

ii1

aAaA

i1i1

jajB

•若背包问题物品的价值与大小均为，容量为，则该背包问

题实例与子集和问题的优化形式等价背包是NP－完全问题

29

Compendium

数学建模

http:

//www.nada.kth.se/~viggo/problemlist/compendium.html

30

P，NP，与NP－完全

数学建模

31

运筹与统计

组合优化问题的研究方法

研究方法

数学建模

组合优化新问题

设计多项式时间复杂性未决问题证明为NP–完全算法（P问题）

进一步改进研究特殊在指数时间在多项式时间

算法性能可解性内求最优解内求近似解

33

研究方法

数学建模

在指数时间内求最优解在多项式时间内求近似解

整

数

规

划

法

分

枝

定

界

法

动

法

态

规

划

贪婪

思想

近似算法启发式算法

线性规

划松弛

索法

局部搜

Meta-

heuri-

stic

34

整数规划

数学建模

•组合优化问题一般可建立整数规划

•整数规划求解也是NP－完全的，但可借助整数规划的算法或软件求解一些具体实例，也可利用数学规划理论研究问题性质或设计算法

•分枝定界法

•除运用整数规划的分枝定界法求解组合优化问题所建立的整数规划外，也可根据问题组合结构设计相应的分枝定界策略

背包问题和TSP问题的分枝定界策略

35

指派问题

数学建模

•定义决策变量

x

ij

1,

0,

员工i被分配完成工作j

其他

nn

该规划形式上是整数规划，但由于系数矩阵是全

mincx

ijiji1j1

可以证明其松弛线性规划的最优解必为整数解

n

s.t.x1,j1,,n

ij

每项工作由一位员工完成i1

n

x1,i1,,n

每位员工完成一项工作ij

j1

x0或1，i,j1,,n

0x1

ijij

3636

TSP问题数学建模nn

指派问题？

•城市i与城市j之间

mincx

ijij

的距离为c

i1j1

ijn

s.t.x1,i1,,n

•决策变量

ijj1

1推销员离开

离开城市i后到达另一个城市

城市i后到

n

x

x1,j1,,n

达城市jij

ij

0其他

i1

j从一个城市来到城市

i,j1，2，,n

x0,1,i,j1,,n

ij

37

TSP问题

数学建模

1

2

35

4

x13x35x52x24x411,

3

n

1

2

x1,i1,,n

ij

j1

n

x1,j1,,n

ij

5

i1

4

xxxxx

1224411,35531,

x0,i,j

为其它组合

ij

x0,i,j

为其它组合,

ij

•TSP环游路线不能含有子环游

38

TSP问题

数学建模

（1iik）

i

•若含有子环游，则

2

x

1

ixxkkxk

iiii

iii

122311

S||

{1iik

i,,,}

xS•记，则

ij2

iSjS

•若要求不含有子环游，则

，

xSnO

||1S{1,2,,},S/ij

iSjS

2n2

•该组约束个数为，增加该组约束后整数规划

求解十分困难

39

TSP问题

数学建模

（1）2,,2,3,,

nxuunijn•约束

ijij

（）

i

1iik

•若含有子环游，则必有一子环游不经过城市1

2

x

1i

•若该子环游仅含一个城市，则

ii

（1）12矛盾

nxuunn

iiii

ii

x1

•若该子环游至少含有两个城市，记，，

k11

ii

jj1

（n1）xuun1uu,j1,2,,k

iiiiii

jj1jj1jj1

k

（n1）xuuk（n1）k（n2）

矛盾iiii

jj1jj1

j1

40

TSP问题

数学建模

nxuunijn

•约束

（1）2,,2,3,,

ijij

•对任意可行环游，选定城市1为起点，若城市i是环游

uk

2un中的第k个经过的城市，取，

ii

xnxuuuun

0

（1）2•若，则

ijijijij

xuu•若，则，ijij

11

（1）2

nxuun

ijij

（n1）2n1

•该组约束仅有个，需增加个