【正文】 ? 弱對偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對偶問題任意可行解的目標(biāo)函數(shù)值 (鞍型圖 ) ? 無界性：原問題無界，對偶問題無可行解 ? 對偶定理：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。 設(shè)第月正常生產(chǎn) xj件，加班生產(chǎn)件 yj，存儲 zj件。已知產(chǎn)品價格和原料價格，求利潤最大的配方。否則轉(zhuǎn)下步 ? 根據(jù) max {σj } = σK 原則確定 XK 進基變量；根據(jù) θ規(guī)則 ： θ = min {b’i / a’ik a’ik 0} = b’L/ a’Lk 確定 XL為出基變量 ? 以 a’Lk 為樞軸元素進行迭代，回到第二步 OR1 44 ? ：檢驗數(shù)的判別由所有 σj ≤0 即為最優(yōu)，變?yōu)樗?σj ≥ 0則為最優(yōu)。令 XK≠0 ，其余非基變量保持為零。 ? 退化的基可行解 ： 若某個基變量取值為零，則稱之為退化的基可行解。設(shè)A=B+N ， B是 A中 m?m階非奇異子矩陣，則稱B是 LP的一個 基 ，即： B是 A中 m個線性無關(guān)向量組。 基解：約束條件的交點稱為基解（直觀） 基可行解：基解當(dāng)中的可行解。 OR1 21 例 1圖示 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 ≤ 360 4x1+5x2 ≤200 3x1+10x2 ≤300 A B C D E F G H I Z=70x1+120x2 OR1 22 概念 ? 概念： 可行解：滿足所有約束條件的解。不同時段需要的護士人數(shù)不等。 OR1 13 LP的數(shù)學(xué)模型 例題 1— 生產(chǎn)計劃問題 ? 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表： 產(chǎn)品 A 產(chǎn)品 B 資源限量 勞動力 設(shè) 備 原材料 9 4 3 4 5 10 360 200 300 利潤 元 /kg 70 120 OR1 14 例題 1建模 ? 問題：如何安排生產(chǎn)計劃，使得獲利最多？ ? 步驟： 確定決策變量：設(shè)生產(chǎn) A產(chǎn)品 x1kg,B產(chǎn)品 x2kg 確定目標(biāo)函數(shù)： maxZ=70X1+120X2 確定約束條件：人力約束 9X1+4X2≤360 設(shè)備約束 4X1+5X2 ≤200 原材料約束 3X1+10X2 ≤300 非負(fù)性約束 X1≥0 X2≥0 OR1 15 例題 2—— 配方問題 ? 養(yǎng)海貍鼠 飼料中營養(yǎng)要求： VA每天至少 700克， VB每天至少 30克， VC每天剛好 200克。 V=F（ xi,yj,uk) G(xi,yj,uk)≥0 OR1 9 ? 規(guī)劃論：線性規(guī)劃、非線性規(guī)劃 |、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃 ? 圖論與網(wǎng)絡(luò) ? 存儲論 ? 排隊論 ? 決策論 ? 對策論 ? 計算機仿真 OR1 10 ? 確定問題 ? 搜集數(shù)據(jù)建立模型 ? 檢驗?zāi)Ｐ? ? 求解模型 ? 結(jié)果分析 ? 結(jié)果實施 OR1 11 ? 計算機為運籌學(xué)提供解題工具。 OR1 8 ? 模型：真實事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。 OR1 7 ? 例：店主進貨 ? 兩者都是常用的決策方法 ? 定性是基礎(chǔ)，定量是工具，定量為定性服務(wù)。OR1 1 OPERATIONS RESEARCH 運籌學(xué) Ⅰ —— 怎樣把事情做到最好 郝英奇 OR1 2 第一章 緒論 ? Operations 漢語翻譯 工作、操作、行動、手術(shù)、運算 Operations Research 日本 —— 運用學(xué) 港臺 —— 作業(yè)研究 中國大陸 —— 運籌學(xué) Operational Research原來名稱，意為軍事行動研究 —— 歷史淵源 OR1 3 緒論 ? 運籌學(xué)的歷史 早期運籌思想：田忌賽馬 丁渭修宮 沈括運糧 Erlang 1917 排隊論 Harris 1920 存儲論 Levinson 1930 零售貿(mào)易 康脫洛維奇 1939 LP OR1 4 緒論 ? 軍事運籌學(xué)階段 德軍空襲 防空系統(tǒng) Blackett 運輸船編隊 空襲逃避 深水炸彈 轟炸機編隊 OR1 5 緒論 ? 管理運籌學(xué)階段 戰(zhàn)后人員三分 :軍隊、大學(xué)、企業(yè) 大學(xué)：課程、專業(yè)、碩士、博士 企業(yè)：美國鋼鐵聯(lián)合公司 英國國家煤炭局 運籌學(xué)在中國： 50年代中期引入 華羅庚推廣 優(yōu)選法、統(tǒng)籌法 中國郵遞員問題、運輸問題 OR1 6 ?應(yīng)用學(xué)科 ?Morseamp。 ?中國定義：運籌學(xué)是應(yīng)用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。但定量不可替代定性。 ? 數(shù)學(xué)模型：用符號或數(shù)學(xué)工具描述現(xiàn)實系統(tǒng)。 LP有一組有待決策的變量， 一個線性的目標(biāo)函數(shù)， 一組線性的約束條件 。飼料 III x3kg…… ? 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5 ? 約束條件： 3x2+2x2+x3+6x4+18x5 ≥700 營養(yǎng)要求： x1+++2x4+ ≥30