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

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

模型和算法相結合，是運用計算機解決實際問題的強有力的現代應用技術的重要組成部分，也是高級研究和技術人才素質培養(yǎng)的重要一環(huán).數學建模競賽的重要內容第2頁，課件共22頁，創(chuàng)作于2023年2月引言

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

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

組合優(yōu)化問題第3頁，課件共22頁，創(chuàng)作于2023年2月引言課程之簡介課程之要求數學之重要第4頁，課件共22頁，創(chuàng)作于2023年2月引言---數學之重要……數學使人周密……----FrancisBacon

數學處于人類智能的中心領域……數學方法滲透、支配著一切自然科學的理論分支……它已愈來愈成為衡量成就的主要標志。

----VonNeumann第5頁，課件共22頁，創(chuàng)作于2023年2月引言---數學之重要

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

展現在我們眼前的宇宙像一本用數學語言寫成的大書，如不掌握數學符號語言，就像在黑暗的迷宮里游蕩，什么也認識不清.數學是一種語言，是一切科學的共同語言第6頁，課件共22頁，創(chuàng)作于2023年2月二十世紀最偉大的數學家----二十世紀最偉大的物理學家----D.HilbertA.EinsteinNobelPrizeFieldsMedal

Goback引言---數學之重要數學是一種技術，是高技術的本質數學技術----數學方法與計算技術的結合形成的一種關鍵性的、可實現的技術第7頁，課件共22頁，創(chuàng)作于2023年2月引言---課程之簡介Example1婚姻問題

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

27+4+26=57Note：最差解的結果：3+10+7=20第9頁，課件共22頁，創(chuàng)作于2023年2月引言---課程之簡介Example2

旅行商問題（Traveling

Salesman

Problem）TSP

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

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

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

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

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

在計算機科學、計算生物學、物流和供應鏈管理等新興領域有大量的應用。

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

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

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

262728

29

30

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

136.5d10.8y

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

問題的模型與應用算法的設計與分析

第13頁，課件共22頁，創(chuàng)作于2023年2月引言---課程之簡介內容：

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

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

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

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

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

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

在世界任何地方找六個人，則其中必有三個人相互認識或相互不認識。第20頁，課件共22頁，創(chuàng)作