生活中的預測與決策.ppt

生活中的預測與決策,任課教師：薛 煥 斌 E-mail: QQ:51054616,預測和決策的意義,“凡事預則立，不預則廢.”這表明預測的重要性。事實上只有以預測為依據(jù)的決策，才是有遠見卓識的決策。下面是幾個有關的例子： 1. 美國克萊斯勒汽車公司，在20世紀70年代石油危機的沖擊中深受其害，1979年9個月內損失7億多美元；與此相反，日本豐田汽車公司，卻在此次經(jīng)濟浪潮中發(fā)展壯大。究其原因是市場預見與經(jīng)營決策的差異。 2. 第二次世界大戰(zhàn)期間，盟軍基于對氣候的可靠預測，抓住暴風雨的空隙，于1944年6月6日執(zhí)行諾曼底登陸計劃，獲得大捷；而希特勒由于對氣候作了錯誤的判斷，損失慘重，大敗而終。 3. 1980年，我國有兩艘遠洋輪，同時從太子港返航。其中一艘船對航線分析預測不當，決策失誤，一路上臺風侵襲耗時29天；另一艘船預測與決策妥當，返航時間縮短為16天。,第一章 灰預測與灰決策概論,一、灰色系統(tǒng)理論產(chǎn)生的科學背景 現(xiàn)代科學技術在高度分化的基礎上高度綜合的大趨勢，導致了具有方法論意義的系統(tǒng)科學學科群出現(xiàn)。系統(tǒng)科學揭示了事物之間更為深刻、更具有本質性的內在聯(lián)系，大大促進了科學技術的整體化進程；許多科學領域中長期難以解決的復雜問題隨著系統(tǒng)科學的出現(xiàn)迎刃而解；人們對自然界和客觀事物演化規(guī)律的認識也由于系統(tǒng)科學的出現(xiàn)逐步深化。,灰色系統(tǒng)理論(簡稱灰理論或灰論，Grey Theory)，是在1982年由中國學者鄧聚龍教授創(chuàng)立的，灰理論是一種研究少數(shù)據(jù)、貧信息不確定性問題的新方法。它以“部分信息已知，部分信息未知”的“小樣本”，“貧信息”不確定性系統(tǒng)為研究對象，主要通過對“部分”已知信息的生成、開發(fā)，提取有價值的信息，實現(xiàn)對系統(tǒng)運行行為、演化規(guī)律的正確描述和有效監(jiān)控?；疑到y(tǒng)模型對實驗數(shù)據(jù)沒有什么特殊的要求和限制，因此應用領域十分寬廣。,二、灰色系統(tǒng)的基本原理 在灰色系統(tǒng)理論創(chuàng)立和發(fā)展過程中，鄧聚龍教授發(fā)現(xiàn)并提煉出灰色系統(tǒng)的基本原理。這些基本原理具有十分深刻的哲學內涵。 （1）差異信息原理“差異”是信息，凡 信息必有差異； （2）解的非唯一性原理信息不完全、不確定的解是非唯一的； （3）最少信息原理灰色系統(tǒng)理論的特點是充分開發(fā)利用已占有的“最少信息”；,（4）認知根據(jù)原理信息是認知的根據(jù)； （5）最新信息優(yōu)先原理新信息對認知的作用大于老信息； （6）灰性不滅原理“信息不完全”（灰）是絕對的。 三、灰色系統(tǒng)理論的主要內容 灰色系統(tǒng)理論進過20多年的發(fā)展，現(xiàn)已基本建立起一門新興學科的結構體系。其基本內容包括以灰色代數(shù)系統(tǒng)、灰色方程、灰色矩陣等為基礎的理論體系，以灰色序列生成為基礎的方法體系，以灰色關聯(lián)空間為依托的分析體系，以灰色模型（GM）為核心的模型體系，以系統(tǒng)分析、評估、建模、預測、決策、控制、優(yōu)化為主體的技術體系。 我們這門課只要學習的是：灰數(shù)、建模、預測、決策,(4)連續(xù)灰數(shù)與離散灰數(shù) 在某一區(qū)間內取有限個值或可數(shù)個值的灰數(shù)稱為離散灰數(shù)，取值連續(xù)地充滿某一區(qū)間的灰數(shù)稱為連續(xù)灰數(shù)。 (5)黑數(shù)與白數(shù) 當 時，即當 的上、下皆為無窮時，稱 為黑數(shù)； 當 且 時，稱 為白數(shù)。 為了討論方便，我們將黑數(shù)與白數(shù)看成特殊的灰數(shù)。,(6)本征灰數(shù)與非本征灰數(shù) 本征灰數(shù)是指不能或暫時還不能找到一個白數(shù)作為其“代表”的灰數(shù)，比如一般的事前預測值、宇宙的總能量、準確到秒或微秒的“年齡”等都是本征灰數(shù)。 非本征灰數(shù)是指憑先驗信息或某種手段，可以找到一個白數(shù)作為其“代表”的灰數(shù)。我們稱此白數(shù)為相應灰數(shù)的白化值，記為 ，并用 表示以a為白化值的灰數(shù)。如估計某人的托?？荚嚦煽兛赡茉?00分左右，可將600作為該考生托?？荚嚦煽?的白化數(shù)，記為,第二章 問題分析,一、決策與我們的關系： “事事有決策、時時要決策” （一）決策的風險 是決策就會有風險，不同的決策需要承擔的風險完全不一樣。,（二）如何規(guī)避決策風險 第一，如何降低因決策失誤造成的風險 第二，怎樣增強承受風險的能力 如何才能有效地降低決策失誤造成的風險？如何增強我們承受風險的能力呢？ 要想有效地降低決策失誤風險和增強抵抗風險的能力，就必須建立一個決策模型，使用分析的工具。,（三）正確決策的關鍵 正確決策的關鍵是： 對問題的正確判斷。你能不能正確地判斷問題？要清楚地知道自己到底想要什么。 對環(huán)境的客觀評估。你到底處于什么樣的環(huán)境之中？你對這個環(huán)境的了解到底有多少？,對資源的有效評價。你要想解決問題，要想做出一個決策，你手上有什么資源？ 對困難的理性分析。這里面強調的一個詞就是“理性”，而不是感性。 對風險的充分準備。我們對一個決策所可能產(chǎn)生的風險要有充分的準備，準備得充分與否直接決定決策的成敗。,決策的支持體系三要素： 要有相關的數(shù)據(jù) 要掌握一種推理的方法 推理要符合邏輯 二、中華傳統(tǒng)文化與決策思維模式 （一）中華傳統(tǒng)文化對決策的影響 要“高深莫測”，還要“大智若愚” 即使內心“五內如焚”，但外表還要“不動聲色”,逢事要“自己明白”，但不能“說透”； 說話要“面面俱到”，并“留有余地”； 做人要“圓滑”、“世故”、“中庸” 因此，我們的傳統(tǒng)文化是以模糊為最高境界的，而模糊的最高境界則是一個“悟” （二）傳統(tǒng)決策思維模式,三、決策價值觀的差異 注重“過程”的決策觀，盡量把問題放在決策的前面； 注重“結果”的決策觀，總習慣于把問題放在決策的前面；,四、決策的模型及分析工具 （一）可使用的模型 可使用的模型包括一些簡單的方法還有一些比較復雜的模型。比如：柱狀圖、樹形圖、扇形圖、曲線圖等分析工具；和SWOT分析法、麥肯錫7S模型、EVA分析法等模型。 （二）需建立的模型 關注關鍵結果領域進行因果分析,柏拉圖法 柏拉圖法又稱排列圖法或主次因素分析圖法，由19世紀意大利學者柏拉圖在分析意大利社會財富分布狀況時首先提出。他在研究中發(fā)現(xiàn)，少數(shù)人占有社會上的大量財富，而絕大多數(shù)人處于貧困狀況，即發(fā)現(xiàn)了“關鍵的少數(shù)和次要的多數(shù)”的關系。 魚骨圖分析法 魚骨圖分析法是一種因果分析方式，指明問題發(fā)生的區(qū)域，并找出該區(qū)域的因素,利用魚骨圖結構來分析問題，可以辨識并列出與任一資源相關的潛在問題，并排列優(yōu)先級。換而言之，該分析法是一種層層剝繭、透過現(xiàn)象看本質的分析方法。 （三）靠個人的模型 以人的感覺、直覺、靠人對問題的判斷，靠人的經(jīng)驗和悟性去進行決策。,五、分析和解決問題的邏輯思維 邏輯有時也指邏輯學，其實就是研究主觀思維的客觀形式及其規(guī)律的科學。,第三章 序列算子與灰色序列生成,事實上，研究系統(tǒng)的行為特征，得到的數(shù)據(jù)往往是一串確定的白數(shù)，我們把它看成是某個隨機過程的一條軌道或實現(xiàn)，或是看成灰色過程的白化值，這并沒有本質上的區(qū)別。如何通過系統(tǒng)行為特征數(shù)據(jù)研究其發(fā)展規(guī)律，不同的方法思路也不一樣。 隨機過程是以先驗概率為出發(fā)點，研究數(shù)據(jù)的統(tǒng)計規(guī)律。這種方法是建立在大量數(shù)據(jù)的基礎上的。但有的時候，即使有了大量的數(shù)據(jù)也未必一定能找到統(tǒng)計規(guī)律。因為概論論或隨機過程中研究的典型分布十分有限，對于非典型的分布過程（如,平穩(wěn)過程、高斯過程、馬爾可夫過程或白噪聲過程等以外的分布過程), 往往難以處理。 灰色系統(tǒng)是通過對原始數(shù)據(jù)的挖掘、整理來尋求其變化規(guī)律的，這是一種就數(shù)據(jù)尋找數(shù)據(jù)的現(xiàn)實規(guī)律的途徑，我們稱為灰色序列生成?；疑到y(tǒng)理論認為，盡管客觀系統(tǒng)表象復雜，數(shù)據(jù)離亂，但它總是有整體功能，因此必然蘊含某種內在規(guī)律。關鍵在于如何選擇適當?shù)姆绞饺ネ诰蛩屠盟?。一切灰色序列都能通過某種生成弱化其隨機性，顯現(xiàn)其規(guī)律。 例如，已知原始數(shù)據(jù)數(shù)列X(0)=1,2,1.5,3 它沒有明顯的規(guī)律性。如何使其顯現(xiàn)出規(guī)律呢？,一、沖擊擾動系統(tǒng)與序列算子 沖擊擾動系統(tǒng)預測是一個歷來令預測專家棘手的問題。對于沖擊擾動系統(tǒng)預測，模型選擇理論也將失去其應有的功效。因為問題的癥結不在模型的優(yōu)劣，而是由于系統(tǒng)行為數(shù)據(jù)因系統(tǒng)本身受到某種沖擊波的干擾而失真。這時，系統(tǒng)行為數(shù)據(jù)已不能正確地反映系統(tǒng)的真實變化規(guī)律。,第四章 一個有效的問題 分析與決策模型,狀況評估,案例模擬X公司的一次部門經(jīng)理會議 X公司的起重機銷售額下降，成本不斷增加，為此公司總裁召集各個部門經(jīng)理開會，要求大家找到問題并采取行動。 生產(chǎn)部門認為是采購和運輸問題。具體說來就是采購的零配件質量不好，而且在運輸上又經(jīng)常中斷，使得他們的生產(chǎn)時斷時續(xù)，十分不穩(wěn)定。,市場部門認為是經(jīng)濟形勢的影響?？傮w來說，他們認為這沒什么大不了，主要是整體經(jīng)濟形勢下滑，造成整個行業(yè)出現(xiàn)了問題，而不是公司內部的問題。 銷售部認為對競爭對手不了解。他們認為競爭對手越來越強大，而公司對此熟視無睹，沒有對策，甚至根本不知道競爭對手在干什么。 開發(fā)部認為是技術優(yōu)勢不明顯。主要是因為公司部給錢，研發(fā)經(jīng)費減少，結果很多技術問題都解決不了。,因此，我們需要一個系統(tǒng)的程序來幫助解決難題，它就是狀況評估法。 什么是“難題”“難題”就是那些需要關注，并且采取行動解決的事件。而且難題不僅指困難，也需要涉及事件改進的可能。 狀況評估法的作用： 找出難題并且分解和控制問題； 體統(tǒng)分析資料后排出輕重緩急； 解決難題的計劃和采取的方法。,一、查明具體的難題 1、列出難題 想要查明具體的原因是什么、首先要做的就是列出一些問題。一般來說，我們可以提出下面一些常見的問題： 到底發(fā)生了什么偏差？ 應實施什么樣的計劃？ 應該做出怎么的決定？ 預計將來有什么變化？ 會存在什么樣的機會？,事實上，我們提出問題的最終目的，就是要列明存在的各種難題，這樣才能在后面的步驟中做到有的放矢。 通過上面的示例，我們就可以列出X公司的難題一覽表,2、澄清難題的方法做出有效提問 列出問題之后還需要進一步澄清問題，把一些復雜的問題分解成簡單的、一目了然的和具體的難點，讓原本籠統(tǒng)的、復雜的難題變得具體和現(xiàn)實。 如何來澄清難題呢？ 提問 你的實際意思是指？ 你具體講的問題是？,是否還有其他問題？ 你有什么具體證據(jù)？ 什么偏差造成問題？ X公司難題的澄清 籠統(tǒng)的難題：生成成本在不斷增加。 具體的難題：成本增加具體原因是什么？ 提供證據(jù)：某些原材料成本上升并多變。,3、問題的分解 X公司的問題分解： 液壓件的成本增加了20%； 公司產(chǎn)品在最近只中了3個標； 必須重新部署產(chǎn)品的競爭策略； 特種鋼材價格在不斷上升； 在少占用資金的前提下提高庫存量。,案例 某位女生遇到了以下幾個問題： 第一，男朋友經(jīng)常不陪她一起吃飯。 第二，男朋友對她態(tài)度不好。 第三，晚上經(jīng)常有人找他出去。 在查明具體難題這個環(huán)節(jié)里，我們要做到： 第一，列出難題； 第二，通過有效提問的方式澄清難題。,二、把握難題的輕重緩急,1、制定緩急程度的標準 一般來說，我們對問題的緩急程度很難達成共識，往往是仁者見仁、智者見智。所以，為了讓我們能對問題輕重緩急程度作出有效的判斷，就要設法找到一種合適的方法。 制定標準： 必須易于掌握和使用； 又有很明顯的靈活性； 基于問題的各個方面。,2、嚴重性、緊急性和發(fā)展性 衡量問題緩急程度的標準：問題分類 第一類，嚴重性；第二類，緊急性； 第三類，發(fā)展性,3、問題級別評估并得出結論,4、問題的變化與解決 我們做好了問題的級別評估，接下來還要防止問題發(fā)生變化。這是因為： 難題越臨近到最后期限，越會增加它的緊急性； 如果一旦出現(xiàn)新的難題，問題的緩急程度就需要重新做出判斷。,三、解決問題的計劃與步驟 當我們知道了存在什么問題、明確了問題的輕重緩急，也就知道了哪件事情是第一重要的，哪件次之。接下來就需要按照它們的輕重緩急去解決問題，那就需要知道解決問題的計劃和步驟是什么。 （一）第一輪提問 是否需要知道偏差的原因？ 是否需要去做出一個選擇？ 是否需要采取行動或計劃？,是否需要進一步澄清問題？ 實際和預計之間有沒有偏差？ 這種偏差的原因是明確的，還是不明確？ 我們采取行動之前，需不需要做出進一步分析？ （二）進一步提出問題 能不能確定我們需要采取行動？ 能不能確定我們需要實施的計劃？ 其他方面的改變會不會影響我的計劃？,（三）潛在問題分析 【案例】行軍問題 問題分析還是決策分析,重點提示：如果能下結論，我們就要做決策分析；如果不能下結論，那就要進一步做問題分析。,四、準備采取行動 在前面的內容中，我們講述了再狀況評估中，不但要知道問題，要澄清問題，要分析問題的緊急性、嚴重性、和發(fā)展性，我們還需要再對它做出一個評估，明確這些問題中的哪些是我們需要做進一步的問題分析，哪些需要做決策分析。 （一）計劃的內容 我們到底需要做什么？ 我們什么時候做？ 誰來參與做？,（二）計劃行動的程序 計劃行動的程序主要包含： 收集信息 分析 創(chuàng)造性（如何解決問題） 承諾 批準 執(zhí)行 培訓 獎勵激勵,【案例】,小結,問題分析,識別可能的原因,評估可能的原因,描述面臨的問題,確認真正的原因,解決問題的三大常見誤區(qū),1.妄下結論 第一，信息不夠，卻認為自己已經(jīng)把握 問題； 第二，只用支持自己觀點的信息來論證 自己的結論； 第三，故意忽略和自己的假設不相符的 信息，甚至去攻擊和否定它們。 2.錯誤的定義問題 第一，信息過多，我們看到很多信息 視乎都跟問題有關 ；,第二，我們沒有辦法去分辨哪些信息是 真正重要的； 第三，面對復雜的信息，我們很難判斷 這些信息到底有沒有利用價值。 3.盲目行動 第一，因為時間、事件的緊迫，往往會 同時采取多種行動； 第二，總是希望僥幸碰到解決問題的方 法； 第三，沒有核查、確認行動是否對解決 問題真正有利，馬上就采取行動,第四，即使偶爾問題得到了解決，也往 往不知道怎么解決的。,決策分析,評估選擇方案,評估決策風險,明確決策目的,作出最終決策,【案例】她該嫁給誰 某女孩有四個男朋友可以選擇，第一個叫李酷斃；第二個叫張帥呆；第三個叫羅老實；第四個叫王大款。因為她一個人不能同時嫁給四個人，所以只能去挑選其中的一個。 決策目標的分類： 1、必須要求目標； 2、愿望要求目標；,必須目標的判斷 第一，年齡20歲到50歲； 第二，有固定的工作和收入； 第三，一年之內可以和她結婚。 愿望目標評估 第一，英俊瀟灑； 第二，有樓有車； 第三，收入豐厚； 第四，存款大把； 第五，嫁過去要當家作主； 第六，財產(chǎn)共享。,評估風險 【案例】生產(chǎn)手機的公司，要在銷售旺季到來前向市場推出新型手機K。公司給出50萬的投資資金并下達任務銷售額要比去年同期提升兩個百分點。,應變措施,找出可能原因,采取預防措施,識別潛在問題,計劃應變措施,第五章 灰色關聯(lián)分析,數(shù)理統(tǒng)計中的回歸分析、方差分析、主成分分析等都是用來進行系統(tǒng)分析的方法。這些方法都有下來不足之處： （1）要求有大量數(shù)據(jù)，數(shù)據(jù)少量就難以找出統(tǒng) 計規(guī)律； （2）要求原本服從某個典型的概率分布，要求 各因素數(shù)據(jù)與系統(tǒng)特征數(shù)據(jù)之間呈線性關系 且各因素之間彼此無關。這種要求往往難以 滿足。 （3）計算量大，一般靠計算機幫助。 （4）可能出現(xiàn)量化結果與定性分析結果不符的 現(xiàn)象，導致系統(tǒng)的關系和規(guī)律遭到歪曲和顛 倒。,灰色關聯(lián)因素和關聯(lián)算子集,進行系統(tǒng)分析，選準體統(tǒng)行為特征的映射量后，還需進一步明確影響系統(tǒng)主行為的有效因素。如要作量化研究分析，則需對系統(tǒng)行為特征映射量和各有效因素進行恰當處理，通過算子作用，使之化為數(shù)量級大體相近的無量綱數(shù)據(jù)，并將負相關因素轉化為正相關因素。,命題5.1 初值化算子、均值化算子和區(qū)間化算子皆可使系統(tǒng)行為序列無量綱化，且在數(shù)量上歸一。 一般地，初值化算子、均值化算子和區(qū)間化算子不宜混合、重疊作用，在進行系統(tǒng)因素分析時，可根據(jù)實際情況選用其中一個。,命題5.2 任意行為序列的區(qū)間值像有逆化像,按照定理5.1定義的算式可得灰色關聯(lián)度的計算步驟如下：,例 某市工業(yè)、農業(yè)、運輸業(yè)、商業(yè)各部門的行為數(shù)據(jù)如下： 工業(yè)： X1=(x1(1), x1(2), x1(3), x1(4) =(45.8, 43.4, 42.3, 41.9) 農業(yè)： X2=(x2(1), x2(2), x2(3), x2(4) =(39.1, 41.6, 43.9, 44.9) 運輸業(yè)：X3=(x3(1), x3(2), x3(3), x3(4) =(3.4, 3.3, 3.5, 3.5) 商業(yè)： X4=(x4(1), x4(2), x4(3), x4(4) =(6.7, 6.8, 5.4, 4.7) 分別以X1 ，X2為系統(tǒng)特征序列，計算灰色關聯(lián)度,案例: 根據(jù)某地區(qū)10年農民人均收入年純收入的資料，和該地區(qū)相應年份的銷售額資料，預測該地區(qū)市場銷售額。觀察期資料見表1,根據(jù)表1中x與y觀察期十年資料繪制散點圖 散點圖表明，x與y存在相關關系，且散點基本集中在一條直線上，說明相關程度較高，農民年人均純收入（x）與銷售額（y）表現(xiàn)較高程度的直線正相關?？梢圆捎靡辉€性相關回歸分析預測模型,2. 應用最小平方法求回歸方程中的參數(shù)，建立預測模型 求參數(shù)a、b的標準方程為： ynabx xyaxbx2 解得方程為：,求解a、b值： 則回歸方程為： 99.1210.1x,99.121,0.1,灰色預測模型GM(1,1)模型,第六章 圖與網(wǎng)絡模型,1736年瑞士科學家歐拉發(fā)表了關于圖論方面的第一篇科學論文，解決了著名的哥尼斯堡七座橋問題。即一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。如圖1所示。,歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。,第六章 圖與網(wǎng)絡模型,1 圖與網(wǎng)絡的基本概念 2 最短路問題 3 最小生成樹問題 4 最大流問題 5 最小費用最大流問題,1 圖與網(wǎng)絡的基本概念 圖論中圖是由點和邊構成，可以反映一些對象之間的關系。 例如：在一個人群中，對相互認識這個關系我們可以用圖來表示，圖6-1就是一個表示這種關系的圖。,當然圖論不僅僅是要描述對象之間關系，還要研究特定關系之間的內在規(guī)律，一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的，如對趙等七人的相互認識關系我們也可以用圖6-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。,如果我們把上面例子中的“相互認識”關系改為“認識” 的關系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖6-3就是一個反映這七人“認識”關系的圖。相互認識用兩條反向的弧表示。,無向圖： 由點和邊構成的圖，記作G=（V，E）。 有向圖： 由點和弧構成的圖，記作D=（V，A）。 連通圖： 對無向圖G，若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖。 回路： 若路的第一個點和最后一個點相同，則該路為回路。 賦權圖： 對一個無向圖G的每一條邊(vi, vj)，相應地有一個數(shù)wij，則稱圖G為賦權圖，wij 稱為邊(vi, vj)上的權。 網(wǎng)絡： 在賦權的有向圖D中指定一點，稱為發(fā)點，指定另一點稱為收點，其它點稱為中間點，并把D中的每一條弧的賦權數(shù)稱為弧的容量，D就稱為網(wǎng)絡。,思考：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽，下表中打的是個運動員報名參加比賽的項目，問六個項目的比賽順序應如何安排？做到每名運動員都不連續(xù)地參加兩項比賽。,A,B,C,D,E,F,分析：點表示項目，邊表示兩個項目有同一名運動員參加,目的：在圖中找出點序列，使得依次排列的兩個點不相鄰，就找到了每名運動員不連續(xù)參加兩項比賽的安排方案,A、C、B、F、E、D,2 最短路問題 最短路問題：對一個賦權的有向圖D中的指定的兩個點Vs和Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權數(shù)的總和被稱為從Vs到Vt的距離。,最短路問題引例,下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費用?，F(xiàn)在某人要從v1出發(fā)，通過這個交通網(wǎng)到v8去，求使總費用最小的旅行路線。,從v1到v8： P1=（v1，v2，v5，v8） 費用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 費用 3+2+10+2+4=21 P3= ,最短路問題中，不考慮有向環(huán)、并行弧。,幾個概念,路：設p是D中一個首尾相連的弧的集合，如果vs是它的第一條弧的始點，vt是它的最后一條弧的終點，則稱它是以點vs為始點，以點vt為終點的一條路。 路長：路p中所有弧的權值的和稱為路p的長，記為,設圖D=（V，A）是一有向網(wǎng)絡,設P是以點vs為始點，以點vt為終點的所有路的集合， 如果 ,且 ，則稱p0是以點vs 為始點，以點vt為終點的最短路。而稱其路長為點 vi到點vj的距離，記為 。,最短路及一點到另一點的距離,最短路問題是重要的最優(yōu)化問題之一，可以直接應用于解 決生產(chǎn)實際的許多問題:管道鋪設、線路安排、廠區(qū)布局等。 而且經(jīng)常被作為一個基本工具來解決其他的優(yōu)化問題。,最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,求解最短路問題的Dijkstra算法,條件：當所有 wij 0 時，用來求給定點vs到任一 個點vj 最短路的公認的最好方法。,事實：如果P是D中從vs到vj的最短路，vi是P中的一 基解 個點，那么，從vs沿P到vi的路是從vs到vi的最基解 短路。,Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標號為主要特征，又稱為標號法。,v5,最短路的子路是最短路,Dijkstra算法基本思想,從始點vs出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。執(zhí)行過程中，與每個點對應，記錄下一個數(shù)(稱為這個點的標號),1.標號 P（固定標號或永久性標號） 從始點vs到該標號點vj的最短路權P (vj) 。 2.標號 T（臨時性標號） 從始點vs到該標號點vj的最短路權上界T (vj) 。,j ,P (vj),j, T (vj),該方法的每一步就是去修改T標號，并且把某一個具T標號的點 改變?yōu)榫哂蠵標號的點，從而使D中具P標號的頂點數(shù)多一個， 至多經(jīng)過n-1步，就可以求出始點vs到各點的最短路。,前點標號j 表示始點vs到vj的最短路上vj的前一點。,Dijkstra算法步驟：,第二步：考慮滿足條件 的所有點； vi具有P 標號;vj具有T 標號; 修改vj的T標號為 ， 并將結果仍記為T(vj),第一步：始點標上固定標號 ,其余各點標臨時性標號 T(vj)=, j1;,第三步：若網(wǎng)絡圖中已無T標號點，停止計算。 否則, 令 ，s為T標號點集, 然后將 的T 標號改成P 標號 ，轉入第二步。,v1,6,圖上標號法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,v1,1,v1,1,永久標號,永久標號,臨時標號,v1出發(fā)到v8去，使總費用最小的旅行路線,v1,6,圖上標號法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,0,0,v1,1,v4,11,v1,3,永久標號,臨時標號,v1出發(fā)到v8去，使總費用最小的旅行路線,0,0,M, ,v1,1,M, ,M,M, ,1,3,圖上標號法,v4,11,v1,3,v1,6,v3,5,v3,5,永久標號,臨時標號,v1出發(fā)到v8去，使總費用最小的旅行路線,0,0,M, ,v4,11,v1,1,M, ,M, ,M, ,v1,3,圖上標號法,v3,5,v2, 6,v2, 6,永久標號,臨時標號,v1出發(fā)到v8去，使總費用最小的旅行路線,0,0,M, ,v4,11,v1,1,M, ,M, ,v1,3,v5,12,v5,9,v5,9,圖上標號法,v3,5,v2, 6,永久標號,臨時標號,v5,10,v1出發(fā)到v8去，使總費用最小的旅行路線,0,0,v5,10,v1,1,M, ,v5, 12,v1,3,v5,9,v5, 12,v3,5,v2, 6,圖上標號法,永久標號,臨時標號,v5,10,v1出發(fā)到v8去，使總費用最小的旅行路線,0,0,v5,10,v1,1,M, ,v1,3,v5, 12,v3,5,v2, 6,圖上標號法,v5,9,永久標號,臨時標號,標號結束 反向追蹤,v1出發(fā)到v8去，使總費用最小的旅行路線,Dijkstra算法步驟：,第二步：考慮滿足條件 的所有點； vi具有P 標號;vj具有T 標號; 修改vj的T標號為 ， 并將結果仍記為T(vj),第一步：始點標上固定標號 ,其余各點標臨時性標號 T(vj)=, j1;,第三步：若網(wǎng)絡圖中已無T標號點，停止計算。 否則, 令 ，s為T標號點集, 然后將 的T 標號改成P 標號 ，轉入第二步。,例1 求下圖中v1到v6的最短路 采用Dijkstra算法，可解得最短路徑為 v1v3v4v6,無向網(wǎng)絡:,負權弧時。,無向網(wǎng)絡中，最短路最短鏈。,多個點對之間最短路？,Dijkstra算法失效,Dijkstra算法注意的問題,逐步逼近算法,路矩陣算法,5,7,2,7,4,6,1,2,6,3,2,0,2,6,5,7,7,10,v3,v1,v2,v4,v5,v6,v7,練習：求如下無向網(wǎng)絡中v1到v7的最短鏈,Dijkstra算法求最短鏈,最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,逐次逼近算法思想,該公式表明， P(1)1j中的第j個分量等于P(0)1j的分量與基本表(權矩陣)中的第j列相應元素路長的最小值，它相當于在v1與vj之間插入一個轉接點(v1,v2,vn中的任一個，含點v1與vj)后所有可能路中的最短路的路長；每迭代一次，就相當與增加一個轉接點，而P(k)1j中的每一個分量則隨著k的增加而呈不增的趨勢！,用于計算帶有負權弧指定點v1到其余各點的最短路,逐次逼近算法基本步驟,例 計算從點v1到所有其它頂點的最短路,解：初始條件為,以后按照公式 進行迭代。,直到得到 ，迭代停止。,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下標追蹤路徑,空格為無窮大,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下標追蹤路徑,空格為無窮大,已知有7個村子，相互間道路的距離如下圖示。擬合建一所小學，已知A處有小學生30人，B處40人，C處25人，D處20人，E處50人，F(xiàn)處60人， G處60人,問小學應建在哪一個村子，使學生上學最方便（原則所有人走的總路程最短；盡可能公平。）。,最短路問題算例1(選址問題),最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,最短路問題求解方法,Dijkstra算法 逐步逼近算法 路矩陣算法,某些問題需要求網(wǎng)絡上任意兩點間的最短路。當然，它也可以用標號算法依次改變始點的辦法來計算，但是比較麻煩。 這里介紹Floyd在1962年提出的路矩陣法，它可直接求出網(wǎng)絡中任意兩點間的最短路。,Floyd算法(路矩陣法)思想,考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網(wǎng)絡D0，記,wij為?。?vi，vj）的權。,在D0中加入v1及D中與vi，vj，v1相關聯(lián)的弧，得D1，D1中vi到vj的最短路記為 ,則一定有,Floyd算法(路矩陣法)思想,再在D1中加入v2及D中與vi，vj，v1， v2相關聯(lián)的弧，得D2，D2中vi到vj的最短路長記為 ，則有,Floyd算法(路矩陣法)思想,Floyd算法(路矩陣法)步驟,設有有向網(wǎng)絡D=（V，A），其權矩陣為A=(aij)nn，,如下構造路矩陣序列：,則n階路矩陣D(n)中的元素d(n)ij就是vi到vj的最短路的路長。,令權矩陣A為初始路矩陣D（0），即令D（0）=A,2. 依次計算K階路矩陣D（K）=（d(k)ij）nn, k=1,2,n，,這里,路矩陣序列的含義,K階路矩陣D（K） 其中的元素表示相應兩點間可能以點v1、v2、vk為 轉接點的所有路中路長最短的路的路長。,D（0） 其中的任一元素表示相應兩點間無轉接點時最短路路長。,一階路矩陣D（1） 其中的元素表示相應兩點間可能以點v1為轉接點的所有路中路長最短的路的路長；,為使計算程序化，轉接點按頂點下標的順序依次加入,n階路矩陣D(n) 其中的元素d(n)ij就是vi到vj的可能以點v1、v2、vn為轉接點的所有路中路長最短的路的路長。既是vi到vj的最短路的路長。,例 求如下交通網(wǎng)絡中各對點間最短路路長。,該圖的權矩陣為：,Floyd算法(路矩陣法)算例,例 求如下交通網(wǎng)絡中各對點間最短路路長。,Floyd算法(路矩陣法)算例,利用公式,發(fā)現(xiàn)第一行，第一列元素不變,利用公式,發(fā)現(xiàn)第二行，第二列元素不變,利用公式,發(fā)現(xiàn)第三行，第三列元素不變,利用公式,發(fā)現(xiàn)第四行，第四列元素不變,D(5)中的元素給出相應兩點間 的最短路，其下標給出最短路 個頂點下標,比如：,6254,已知有7個村子，相互間道路的距離如下圖示。擬合建一所小學，已知A處有小學生30人，B處40人，C處25人，D處20人，E處50人，F(xiàn)處60人， G處60人,問小學應建在哪一個村子，使學生上學最方便（原則所有人走的總路程最短；盡可能公平。）。,最短路問題算例1(選址問題),最短路問題算例1(選址問題),最短路問題算例1(選址問題),A處30人，B處40人，C處25人，D處20人，E處50人，F(xiàn)處60人， G處60人.,0 200 50 140 350 360 600,150 0 175 40 250 240 480,60 280 0 120 250 240 480,210 80 150 0 150 120 360,210 200 125 60 0 60 180,180 160 100 40 50 0 240,300 320 200 120 250 240 0,1700 1335 1430 1070 835 770 1330,A B C D E F G,A B C D E F G,某工廠使用一臺設備，每年年初工廠都要作出決定：如果繼續(xù)使用舊的，要付維修費；如果買新的，要付購置費。試制定一個五年更新計劃，使工廠總支出最少？,若該設備在各年的購置費、不同役齡的殘值及維修費如下表：,最短路問題算例2(設備更新問題),最短路問題算例2(設備更新問題),?。╲i，vj）的權: 表示第i年初購買的設備一直使用到第j年年初所需支付的總費用，即第i年初的購置費加上第一年、第二年、第（j-i）年的維修費，再減去（j-i）年役齡殘值。,解：為將該問題化為最短路問題，用點vi表示第i年初購買一臺新設備，并虛設點v6表示第五年年底。,?。╲i，vj）：表示第i年初購買的設備一直使用到第j年年初（即第j-1年年底）；,這樣一來，設備更新問題可歸結為如下基本表中的求v1到v6的最短路問題。,用逐次逼近法較為簡便,答：第一年初購買一臺新設備一直用到第三年年初處理，再購買一臺新設備一直用到第五年底可使支付的總費用最少。,7個村莊要在他們之間架設電話線，要求任何兩個村莊都可以互相通電話(允許中轉)，并且電話線根數(shù)最少？,引例,村莊1,村莊4,村莊3,村莊6,村莊2,村莊5,村莊7,分析：用七個點代表村莊，如果在某兩個村莊之間架設電話線，則相應的在兩點之間連一條邊，這樣電話線網(wǎng)就可以用一個圖來表示，并且滿足如下要求：,連通圖 圖中有圈的話，從圈中任去掉一條邊，余下的圖仍連通,樹,村莊1,村莊4,村莊3,村莊6,村莊2,村莊5,村莊7,如果G=（V，E）是一個無圈的連通圖，則稱G為樹。,樹中必存在次為1的點（懸掛點） 樹中任兩點必有一條鏈且僅有一條鏈； 在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈； 反之，去掉樹的任一條邊，樹就成為不連通圖； n個頂點的樹有（n-1）條邊。,樹是無圈連通圖中邊數(shù)最多的，也是最脆弱的連通圖！,圖的部分樹（支撐樹）,如果圖G=（V，E）的部分圖G=（V，E）是樹， 則稱G是G的部分樹（或支撐樹）。,村莊1,村莊4,村莊3,村莊6,村莊2,村莊5,村莊7,部分樹上各樹枝上權值的和稱為它的長度，其中長度最短的部分樹，稱其為該圖的最小部分樹（最小支撐樹）。,點保留 邊可去 仍是樹 不唯一,思考：如何鋪設電話線，使得電話線長度最少？,最小部分樹的求法,定理：圖中任一個點i，若j是與相鄰點中距離最近的， 則邊i,j一定必含在該圖的最小部分樹內。,推論：把圖的所有點分成 和 兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內。,避圈法,破圈法,2,2,7,5,4,1,4,3,5,1,7,5,求解最小生成樹的避圈算法,S,A,B,C,D,E,S,T,2,2,1,3,1,5,求解最小生成樹的破圈算法,算法的步驟： 1、在給定的賦權的連通圖上任找一個圈。 2、在所找的圈中去掉一個權數(shù)最大的邊（如果有兩條或兩條以上的邊都是權數(shù)最大的邊，則任意去掉其中一條）。 3、如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第1步。,第七章 風險決策的期望值準則及其應用,一、風險型決策分析 風險型決策分析是在狀態(tài)概率已知的條件下進行的，一旦各自然狀態(tài)的概率經(jīng)過預測或估算被確定下來，在此基礎上的決策分析所得到的最滿意方案就具有一定的穩(wěn)定性。,第一節(jié) 風險決策的期望值準則及其應用,風險型決策一般包含以下條件： （1）存在著決策者希望達到的目標（如收益最大或損失最?。?； （2）存在著兩個或兩個以上的方案可供選擇； （3）存在著兩個或兩個以上不以決策者主觀意志為轉移的自然狀態(tài)（如不同的天氣對市場的影響）；,第一節(jié) 風險決策的期望值準則及其應用,（4）可以計算出不同方案在不同自然狀態(tài)下的損益值； （5）在可能出現(xiàn)的不同自然狀態(tài)中，決策者不能肯定未來將出現(xiàn)哪種狀態(tài)，但能確定每種狀態(tài)出現(xiàn)的概率。,第一節(jié) 風險決策的期望值準則及其應用,二、風險型決策分析的期望值準則 （一）期望損益決策的基本原理 一個決策變量d的期望值，就是它在不同自然狀態(tài)下的損益值乘上相對應的發(fā)生概率之和。 式中 E(di)變量di的期望值； dij變量di在自然狀態(tài)j下的損益值； p（ j ）自然狀態(tài)j發(fā)生的概率。,第一節(jié) 風險決策的期望值準則及其應用,決策變量的期望值包括三類：收益期望值；損失期望值；機會期望值。 把每個方案的期望值求出來加以比較選優(yōu)的方法，即為期望值決策準則。 （二）案例分析 例3-1 某化工廠為擴大生產(chǎn)能力，擬定了三種擴建方案以供決策：大型擴建；中型擴建；小型擴建。如果大型擴建，遇產(chǎn)品銷路好，可獲利200萬元，銷路差則虧損60萬元；如果中型擴建，遇產(chǎn)品銷路好，可獲利150萬元，銷路差可獲利20萬元；如果小型擴建，產(chǎn)品銷路好，可獲利100萬元，銷路差可獲利60萬元。根據(jù)歷史資料，未來產(chǎn)品銷路好的概率為0.7，銷路差的概率為0.3，試做出最佳擴建方案決策。其決策表如表3-1。,第一節(jié) 風險決策的期望值準則及其應用,表3-1 某化工廠擴建問題決策 單位：萬元,第一節(jié) 風險決策的期望值準則及其應用,應用期望收益決策準則進行決策分析，其步驟是： （1）計算各方案的期望收益值： 大型擴建：E(d1)=0.72000.3(-60)=122（萬元） 中型擴建：E(d2)=0.71500.320=111（萬元） 小型擴建：E(d1)=0.71000.360=88（萬元） （2）選擇決策方案。根據(jù)計算結果，大型擴建方案獲利期望值是122萬，中型擴建方案獲利期望值是111萬元、小型擴建方案獲利期望值是88萬元。因此，選擇大型擴建方案是最優(yōu)方案。,第一節(jié) 風險決策的期望值準則及其應用,例3-2 某冷飲廠擬定今年夏天(七、八兩月)某種冷飲的日計劃產(chǎn)量。該種冷飲每箱成本為100元，售價為200元，每箱銷售后可獲利100元。如果當天銷售不出去，過剩一箱就要由于冷藏費及其它原因而虧損60元。通過統(tǒng)計分析和市場預測，確認當年市場銷售情況如表3-2所示。 表3-2 冷飲日銷售量概率表,第一節(jié) 風險決策的期望值準則及其應用,問：該廠今年夏天每日生產(chǎn)量應定為多少才能使利潤最大? 解：,第一節(jié) 風險決策的期望值準則及其應用,三、期望損益決策法中的幾個問題 （一）期望損益值相同方案的選擇 在一項決策中，如果期望收益值最大（或期望損失值最?。┑姆桨覆恢挂粋€時，就要選取離差最小的方案為最優(yōu)方案。 按決策技術定義的離差為：,第一節(jié) 風險決策的期望值準則及其應用,例3-3 設有一個四種狀態(tài)、三個方案的決策問題。各狀態(tài)發(fā)生的概率及每一方案在各個狀態(tài)下收益值如表3-4所示。 表3-4 收益值表,值,益,率,第一節(jié) 風險決策的期望值準則及其應用,E(d1)=300.1+100.2+450.3+200.4=26.5 E(d2)=150.1+250.2+250.3+350.4=28 E(d3)=330.1+210.2+350.3+250.4=28 E(d2)= E(d3) E(d1) 2= E(d2)-min15,25,25,35=13 3= E(d3)-min33,21,35,25=7 因2 3,故應選方案d3為最優(yōu)方案。,第一節(jié) 風險決策的期望值準則及其應用,（二）風險型決策中完整情報的價值 如果知道狀態(tài)j發(fā)生，則選擇狀態(tài)j下對應的最優(yōu)方案。記 ，Ep是完整情報的最大利潤。顯然， EpmaxE(di)=E(d)。 故完整情報的價值為Ev=Ep - E(d), 表示了花錢搞情報所能得到的最大的期望利潤。決策時，所花人力、物力去獲得完整情報的費用不超過Ev ，則獲取完整情報的工作是合算的，否則得不償失。,第一節(jié) 風險決策的期望值準則及其應用,例3-4 計算例3-2的完整情報的價值 。根據(jù)已提供的資料，計算具有完整情報下各方案的最大利潤