【正文】 ???????????????????njmixnjbxmiaxijmijijnjiij,2,1。設(shè) xij 為從產(chǎn)地 Ai運(yùn)往銷地 Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型： ? ?? ??minjijij xcz1 1m i n????????????????????njmixnjbxmiaxtsijjmiijnjiij,1。 線性規(guī)劃解的情況：有 唯一最優(yōu)解；有無窮多最優(yōu)解；無界解；無可行解 Page 34 建立線性規(guī)劃模型的過程可以分為四個步驟： (1)設(shè)立決策變量； (2)明確所有的約束條件并用決策變量的線性等式或不等式表示出來； (3)用決策變量的線性函數(shù)表示目標(biāo) ， 并確定是求極大（ Max） 還是極小 （ Min） ； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性 。 ? ? ijij bxa0??????iniinjijxbxxa 稱為松弛變量 ? ? ijij bxa0??????iniinjijxbxxa 稱為剩余變量 變量 的變換 可令 0?jxjj xx ??? 0??jxPage 32 線性規(guī)劃問題的數(shù)學(xué)模型 4. 線性規(guī)劃問題的解 ????????????????????????????????)3(,2,1,0)2(),2,1(.)1(m a x11njxmibxatsxcZjnjijijnjjj??線性規(guī)劃問題 求解線性規(guī)劃問題，就是從滿足約束條件 (2)、 (3)的方程組中找出一個解，使目標(biāo)函數(shù) (1)達(dá)到最大值。 (2) 約束條件都為等式方程，且右端常數(shù)項 bi都大于或等于零 (3) 決策變量 xj為非負(fù)。其中 ， “ Max” 是英文單詞 “ Maximize” 的縮寫 ，含義為 “ 最大化 ” ； “ .” 是 “ subject to”的縮寫 ， 表示 “ 滿足于 … ” 。 Chapter1 線性規(guī)劃 (Linear Programming) LP的數(shù)學(xué)模型 LP模型的應(yīng)用 本章主要內(nèi)容： Page 22 線性規(guī)劃問題的數(shù)學(xué)模型 1. 規(guī)劃問題 生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。約束條件一般用一個集合 D表示為： X∈D 。由于最優(yōu)化問題背景十分廣泛，涉及的知識不盡相同，學(xué)科分枝很多，因此這個學(xué)科名下到底包含哪些分枝，其說法也不一致。 ? 用到時間序列分析的至少 2個 。 綜合評價、機(jī)理分析等方法 。 賽題常用的計算軟件： Matlab, SPSS， EXCEL等 Page 7 參考網(wǎng)站 [1] 全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)： [2] 數(shù)學(xué)中國網(wǎng)站 [3] 中國數(shù)學(xué)建模網(wǎng)站： Page 8 從問題的解決方法上分析 涉及到的 數(shù)學(xué)建模方法 ： 幾何理論、組合概率、統(tǒng)計 (回歸 )分析 。 Page 4 拿到賽題后大家需要思考的問題 題目屬于哪種類型：連續(xù)的、離散的 需要解決什么問題 :最優(yōu)化方案、預(yù)測模型、最短路徑等等；將問題分解。你們的論文必須觀點(diǎn)鮮明、分析有據(jù)、結(jié)論明確。 ? 2. 賽題的開放性增大 :題意的開放性，思路的開放性，方法的開放性，結(jié)果的開放性。Page 1 賽題發(fā)展的特點(diǎn)： ? ： 賽題的解決依賴計算機(jī)，題目的數(shù)據(jù)較多，手工計算不能完成 。 計算機(jī)模擬和以算法形式給出最終結(jié)果 ,如 09B， 11B。數(shù)據(jù)的收集和分析是你們建模分析的基礎(chǔ)和重要組成部分。 ?： 國內(nèi)外的大事，社會的熱點(diǎn)，生活的焦點(diǎn)，近期發(fā)生和即將發(fā)生被關(guān)注的問題。 (1)流程圖 模型應(yīng)用 問題分析 模型假設(shè) 建立模型 模型求解 模型分析 模型檢驗 Page 6 解決問題涉及到的計算軟件分析 重要的是參賽選手具備編程計算、計算機(jī)仿真、模擬能力。 插值與擬合、灰色系統(tǒng)理論、神經(jīng)網(wǎng)絡(luò)、時間序列 。 ? 用到 圖論與網(wǎng)絡(luò)優(yōu)化 方法的問題有 6個； ?用到 層次分析 方法的問題有３個； Page 10 ?用到插值擬合的問題有 6個； ? 用灰色系統(tǒng)理論的 4個 。 Page 12 一、最優(yōu)化概念 所有類似的這種課題統(tǒng)稱為最優(yōu)化問題，研究解決這些問題的科學(xué)一般就總稱之為 最優(yōu)化理論和方法 另外也可用學(xué)術(shù)味更濃的名稱： “ 運(yùn)籌學(xué) ” 。通常，稱 F(X)為 “ 目標(biāo)函數(shù) ” ， X應(yīng)滿足的條件為 “ 約束條件 ” 。 （ 4）最優(yōu)解的驗證和實施。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？ 設(shè) 備 產(chǎn) 品 A B C D 利潤（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 臺 時 12 8 16 12 Page 24 線性規(guī)劃問題的數(shù)學(xué)模型 解：設(shè) x x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為： max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0 . 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 Page 25 這是一個典型的利潤最大化的生產(chǎn)計劃問題 。 怎樣辨別一個模型是線性規(guī)劃模型？ Page 27 線性規(guī)劃問題的數(shù)學(xué)模型 00 )( )( ( m i n ) m a x12211112121112211????????????????????nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz??????????????目標(biāo)函數(shù)： 約束條件： 3. 線性規(guī)劃數(shù)學(xué)模型的一般形式 )21(j 0 )21(i )( Z ( m i n )m a x 11nxmbxaxcjnjijijnjjj????????????????簡寫為： Page 28 線性規(guī)劃問題的數(shù)學(xué)模型 矩陣形式： ???????????mnmnaaaaA?????1111????????? 0 )( ( m i n ) m a xXBAXCXZ其中： ) ( 21 ncccC ?????????????nxxX ?1???????????mbbB ?1Page 29 線性規(guī)劃問題的數(shù)學(xué)模型 3. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 minjxbxatsxcZjnjijijnjjj,2,1,2,1,0.m a x11????????????????特點(diǎn)： (1) 目標(biāo)函數(shù)求最大值。 zz ????????? jj xczzm a x即 若存在取值無約束的變量 ,可令 其中： jx jjj xxx ?????0, ????jj xx 變量的變換 Page 31 線性規(guī)劃問題的數(shù)學(xué)模型 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 最優(yōu)解 ：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 Page 37 運(yùn)輸問題的數(shù)學(xué)模型 例 某公司從兩個產(chǎn)地 A A2將物品運(yùn)往三個銷地 B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？ B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷量 150 150 200 Page 38 運(yùn)輸問題的數(shù)學(xué)模型 解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量＝ 500 設(shè) xij 為從產(chǎn)地 Ai運(yùn)往銷地 Bj的運(yùn)輸量，得到下列運(yùn)輸量表： B1 B2 B3 產(chǎn)量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 銷量 150 150 200 Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 . x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 2； j = 3） Page 39 運(yùn)輸問題的數(shù)學(xué)模型 運(yùn)輸問題的一般形式：產(chǎn)銷平衡 A A … 、 Am 表示某物資的 m個產(chǎn)地； B B … 、 Bn 表示某物質(zhì)的 n個銷地； ai 表示產(chǎn)地 Ai的產(chǎn)量； bj 表示銷地 Bj 的銷量； cij 表示把物資從產(chǎn)地 Ai運(yùn)往銷地 Bj的單位運(yùn)價。 Page 41 運(yùn)輸問題的應(yīng)用 2. 產(chǎn)銷不平衡的運(yùn)輸問題 當(dāng)總產(chǎn)量與總銷量不相等時 ,稱為不平衡運(yùn)輸問題