引言組合優(yōu)化理論

引言組合優(yōu)化理論第1頁，共22頁，2023年，2月20日，星期六引言模型是研究和解決現(xiàn)代社會中復(fù)雜系統(tǒng)工程問題的重要工具和方法，模型方法的掌握和運用，不僅需要自然科學(xué)和社會科學(xué)方面的廣泛知識，而且需要豐富的實踐經(jīng)驗，以及綜合運用各種知識、經(jīng)驗、主體感悟和創(chuàng)造所形成的整體素質(zhì)和能力.常識！

模型和算法相結(jié)合，是運用計算機解決實際問題的強有力的現(xiàn)代應(yīng)用技術(shù)的重要組成部分，也是高級研究和技術(shù)人才素質(zhì)培養(yǎng)的重要一環(huán).數(shù)學(xué)建模競賽的重要內(nèi)容第2頁，共22頁，2023年，2月20日，星期六引言

在各種活動，如果要作一決策而備選方案不止一個，則自然希望所選方案是最優(yōu)（最佳）的（某種意義下如：最短、最省、最大etc.）.最優(yōu)化方法就是從眾多可能方案中選擇以達到最優(yōu)目標(biāo)的科學(xué).

通過數(shù)學(xué)方法在一個有限的可行解集合中尋找最優(yōu)解的問題——

組合優(yōu)化問題第3頁，共22頁，2023年，2月20日，星期六引言課程之簡介課程之要求數(shù)學(xué)之重要第4頁，共22頁，2023年，2月20日，星期六引言---數(shù)學(xué)之重要……數(shù)學(xué)使人周密……----FrancisBacon

數(shù)學(xué)處于人類智能的中心領(lǐng)域……數(shù)學(xué)方法滲透、支配著一切自然科學(xué)的理論分支……它已愈來愈成為衡量成就的主要標(biāo)志。

----VonNeumann第5頁，共22頁，2023年，2月20日，星期六引言---數(shù)學(xué)之重要

一門科學(xué)只有當(dāng)它達到能夠成功地運用數(shù)學(xué)時，才算真正發(fā)展了.----KarlMarxGalileo:

展現(xiàn)在我們眼前的宇宙像一本用數(shù)學(xué)語言寫成的大書，如不掌握數(shù)學(xué)符號語言，就像在黑暗的迷宮里游蕩，什么也認識不清.數(shù)學(xué)是一種語言，是一切科學(xué)的共同語言第6頁，共22頁，2023年，2月20日，星期六二十世紀(jì)最偉大的數(shù)學(xué)家----二十世紀(jì)最偉大的物理學(xué)家----D.HilbertA.EinsteinNobelPrizeFieldsMedal

Goback引言---數(shù)學(xué)之重要數(shù)學(xué)是一種技術(shù)，是高技術(shù)的本質(zhì)數(shù)學(xué)技術(shù)----數(shù)學(xué)方法與計算技術(shù)的結(jié)合形成的一種關(guān)鍵性的、可實現(xiàn)的技術(shù)第7頁，共22頁，2023年，2月20日，星期六引言---課程之簡介Example1婚姻問題

(matchingproblem)DEF女兒ABC追求者EDF327151042628得到分配矩陣：如何嫁娶，使獲得的禮品最多？7共有3!種可能第8頁，共22頁，2023年，2月20日，星期六引言---課程之簡介DEF貪婪（Greedy)解一般不會產(chǎn)生最差解；在某些模型中,貪婪算法能得到最優(yōu)解；3.可以使用窮舉法，但是以時間為代價貪婪解的結(jié)果：28+5+1=34最優(yōu)解的結(jié)果：

27+4+26=57Note：最差解的結(jié)果：3+10+7=20第9頁，共22頁，2023年，2月20日，星期六引言---課程之簡介Example2

旅行商問題（Traveling

Salesman

Problem）TSP

:有一位旅行售貨員，欲到城市v1，v2,…，vn

進行商品銷售，已知：的距離為

wij.(,).他從其中某個城市出發(fā)，需訪問每一個城市一次且僅一次（在歐氏距離下）而回到出發(fā)的城市.問應(yīng)如何計劃他的旅行路線，使他所走路線的總長度最短？共有（n-1)!種可能最優(yōu)Hamilton回路第10頁，共22頁，2023年，2月20日，星期六引言---課程之簡介組合優(yōu)化問題又稱離散優(yōu)化問題，是一類重要的優(yōu)化問題.

在信息的采集、傳遞、加工過程中這類問題與日俱增，越來越受到運籌學(xué)、應(yīng)用數(shù)學(xué)、計算機科學(xué)及管理科學(xué)等諸多學(xué)科的高度重視.

組合優(yōu)化是近幾十年發(fā)展起來的一門新興的交叉學(xué)科分支.

在計算機科學(xué)、計算生物學(xué)、物流和供應(yīng)鏈管理等新興領(lǐng)域有大量的應(yīng)用。

第11頁，共22頁，2023年，2月20日，星期六引言---課程之簡介組合優(yōu)化就其研究的問題和所形成的學(xué)科連貫性不能與數(shù)學(xué)、力學(xué)、電工學(xué)等學(xué)科相比.后者是從研究自然科學(xué)的基本問題而逐漸深入的、前后連貫的完整學(xué)科，有嚴(yán)密的理論體系和系統(tǒng)的研究方法.組合優(yōu)化問題多為專題研究系統(tǒng)最優(yōu)問題，以不同模型為對象，具有趣味性、應(yīng)用性.

大多數(shù)模型以獨立的理論基礎(chǔ)和解題方法出現(xiàn)，技巧性較強.第12頁，共22頁，2023年，2月20日，星期六引言---課程之簡介組合優(yōu)化問題最優(yōu)解的存在和有正確的算法（窮舉法etc.）是沒問題的.問題解決了嗎？沒有！時間

設(shè)有n個城市（有向圖）的TSP,則有（n-1）！種可能方案.以計算機1秒可以完成24個城市所有路徑枚舉為單位，則城市數(shù)2425

262728

29

30

31計算時間1s24s10min4.3h4.9d

136.5d10.8y

325y因此，對不同的問題（甚至同一問題解的不同表示）必須研究是否有有效算法、如何設(shè)計算法、分析算法的有效性等等.

問題的模型與應(yīng)用算法的設(shè)計與分析

第13頁，共22頁，2023年，2月20日，星期六引言---課程之簡介內(nèi)容：

課程內(nèi)容包括線性規(guī)劃、對偶線性規(guī)劃、運輸問題、整數(shù)規(guī)劃、指派問題、背包問題、裝箱問題、排序問題、網(wǎng)絡(luò)規(guī)劃等.參考書目：1、《數(shù)學(xué)規(guī)劃與組合優(yōu)化》姚恩瑜等2、《運籌學(xué)及其應(yīng)用》胡覺亮等Goback第14頁，共22頁，2023年，2月20日，星期六引言---課程之要求會做人會做事怎樣做為什么這樣做不這樣做可以嗎

How?Why?Otherways?4、提高數(shù)學(xué)素養(yǎng)1、增強優(yōu)化意識

2、掌握常用的優(yōu)化模型

3、掌握求解這些模型的思想和方法(算法)比方法更重要未來的文盲不再是目不識丁的人，而是那些沒有學(xué)會怎樣學(xué)習(xí)的人

AlvinToffler第15頁，共22頁，2023年，2月20日，星期六引言---課程之要求英國商船配置高射炮的評價步行時間狗的位置重力加速度問題Ramsey數(shù)第16頁，共22頁，2023年，2月20日，星期六homeRailwaystation提前30分鐘下班提前10分鐘到家問：步行了幾分鐘單程提前5分鐘結(jié)論：步行25分鐘Goback步行時間第17頁，共22頁，2023年，2月20日，星期六速度：女主人3km/h男主人5km/h狗7km/h

一對夫婦及一只小狗同時從家里出發(fā)，沿相同道路步行，小狗不停地往返在男女主人之間，已知他們的速度，問：1小時后狗在男女主人之間什么位置？結(jié)論：狗可以在男女主人之間的任何位置。分析：運用極限理論中的兩邊夾定理。狗的位置Goback第18頁，共22頁，2023年，2月20日，星期六引言---課程之要求重力加速度問題AristotleHeavyLight快慢GalileoHeavyLight快？慢？Goback第19頁，共22頁，2023年，2月20日，星期六引言---課程之要求Ramsey數(shù)鴿洞（抽屜）原理：把100只鴿子關(guān)進99個洞里面，則其中必有一個洞內(nèi)至少關(guān)有2只鴿子?！瘛瘛瘛瘛瘛裾J識：不認識：

在世界任何地方找六個人，則其中必有三個人相互認識或相互不認識。第20頁，共22頁，2023年，2月20