優化方法運籌學ppt課件(已修改)

　

【正文】 第四章 最優化方法 (運籌學 ) ? 第一節 線性 (Linear Programing )規劃 ? 第二節 運輸問題和指派問題 ? 第三節 動態規劃 問題？ ? 怎樣才是最漂亮的最帥？ ? 金字塔、巴特農神殿、巴黎鐵塔等 ,在文藝復興時期也更有許多以黃金比例創造出來旳作品 ? 人從肚臍開始分 ,上半身到頭 ,下半身到腳 ,這個比例符合 1: 是最美旳。 ? 鼻子以及嘴巴旳寬度 = 1:。 ? 鼻子側面ㄑ字型 ,鼻梁旳長度以及鼻尖高度旳比 = 1:。 ? 從正面看來嘴巴長度以及嘴角到臉部輪廓邊旳長度比 = 1:。 ? 臉寬以及臉長各為眼睛長度旳 5 倍以及 8 倍 ,比 = 5:8。［也相近于 1:］ ? 歐洲的古代城堡為什么建成圓形？ 案例：生產計劃問題 ?例 1. 某工廠在計劃期內要安排 Ⅰ 、 Ⅱ 兩種產品的生產，已知生產單位產品所需的設備臺時及 A、 B兩種原材料的消耗、資源的限制，如下表： Ⅰ Ⅱ 資源限制 設備 1 1 300 臺時 原料 A 2 1 400 千克 原料 B 0 1 250 千克 單位產品獲利 50 元 100 元 ?問題：工廠應分別生產多少單位 Ⅰ 、 Ⅱ 產品才能使工廠獲利最多？ 第一節 線性規劃 ? 一、在管理中一些典型的線性規劃應用 ? 二、線性規劃的一般模型 ?三、 線性規劃問題的計算機求解（ Excel， lingo） 第一節 線性規劃 一、在管理中一些典型的線性規劃應用 ?合理利用線材問題：如何在保證生產的條件下，下料最少 ?配料問題：在原料供應量的限制下如何獲取最大利潤 ?投資問題：從投資項目中選取方案，使投資回報最大 ?產品生產計劃：合理利用人力、物力、財力等，使獲利最大 ?勞動力安排：用最少的勞動力來滿足工作的需要 ?運輸問題：如何制定調運方案，使總運費最小 小知識 ? 茅于軾擇優分配原理 ? 茅于軾通過引進帕累托最優理論和帕累托改進理論，提出他的擇優分配原理 ? 帕累托最優（ Pareto Optimality）是指資源分配的一種理想狀態：如果固有的一群人和可分配的資源，從一種分配狀態到另一種分配狀態的變化中，在沒有使任何人境況變壞的前提下，不會使任何一個人變得更好。帕累托改進（ Pareto improvement）是指資源分配的一種改進狀態：如果固有的一群人和可分配的資源，從一種分配狀態到另一種分配狀態的變化中，在沒有使任何人境況變壞的前提下，可以使其中至少一個人變得更好。帕累托改進是達到帕累托最優的路徑和方法。由于從帕累托改進到帕累托最優的核心精神是資源優化配置，而西方經濟學的本質是配置經濟學，“帕累托最優”、“帕累托改進”成了 100多年來西方經濟學的核心概念。 第一節 線性規劃 ? 二、線性規劃的一般模型 ? （一）線性規劃的組成： ? 目標函數 Max F 或 Min F ? 約束條件 . (subject to) 滿足于 ? 決策變量 用符號來表示可控制的因素 第一節 線性規劃 ?（二）建模過程 ，了解解題的目標和條件； （ x1 ， x2 ， ? ， xn ），每一組值表示一個方案； ，確定最大化或最小化目標； 題過程中必須遵循的約束條件 第一節 線性規劃 ?（三）線性規劃模型的一般形式 目標函數： Max （ Min） z = c1 x1 + c2 x2 + ? + xn 約束條件： . a11 x1 + a12 x2 + ? + a1n xn ≤ （ =, ≥ ） b1 a21 x1 + a22 x2 + ? + a2n xn ≤ （ =, ≥ ） b2 ?? ?? am1 x1 + am2 x2 + ? + amn xn ≤ （ =, ≥ ） bm x1 ，x2 ， ? ， xn ≥ 0 例題分析 1：生產計劃問題 ?例 1. 某工廠在計劃期內要安排 Ⅰ 、 Ⅱ 兩種產品的生產，已知生產單位產品所需的設備臺時及 A、 B兩種原材料的消耗、資源的限制，如下表： Ⅰ Ⅱ 資源限制 設備 1 1 300 臺時 原料 A 2 1 400 千克 原料 B 0 1 250 千克 單位產品獲利 50 元 100 元 問：工廠應分別生產多少單位 Ⅰ 、 Ⅱ 產品才能使工廠獲利最多？ 例題分析 1：生產計劃問題 ? 解：工廠應分別生產 Ⅰ 、 Ⅱ 產品 x x2單位，則所求的線性規劃模型為： ? Max z = 50 x1 + 100 x2 ? . x1 + x2 ≤ 300 ? 2 x1 + x2 ≤ 400 ? x2 ≤ 250 ? x1 , x2 ≥ 0 例題分析 2：食譜問題 ?例 1 已知某人每周所需的營養成分、所食用的食品及單位食品所含營養如下表所示： 營養成分 大米 白菜 雞蛋 豬肉 營養成分的需要量（周） 蛋白質 某維生素 某礦物質 a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 b1 b2 b3 單價（元） c1 c2 c3 c4 — 問這個人每周應食用大米、白菜、雞蛋和豬肉各多少，能使生活費用最省？ 例題分析 2：食譜問題 ? 解：設這個人每周應食用大米、白菜、雞蛋、豬肉各為 xx x x4，則所求的線性規劃模型為： ? minZ = c1x1+c2x2+c3x3+c4x4 ? . a11x1+a12x2 +a13x3+a14x4≥b 1 ? a21x1+a22x2+a23x3+a24x4 ≥b 2 ? a31x1+a32x2+a33x3+a34x4 ≥b 3 ? x1,x2,x3,x4 ≥0 小知識 ? 明尼蘇達大學建立食物營養價值評估數據庫，可對每天需要的營養與食物作最優化選擇 ? 作業：建立自己的小營養優化選擇 例題分析 3：人力資源分配問題 例 2．某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 班次 時間 所需人數 1 6 ： 00 —— 10 ： 00 60 2 10 ： 00 —— 14 ： 00 70 3 14 ： 00 —— 18 ： 00 60 4 18 ： 00 —— 22 ： 00 50 5 22 ： 00 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 設司機和乘務人員分別在各時間段一開始時上班，并連續工作 八小時 (注意每班次才 4小時 )，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員 ? 例題分析 3：人力資源分配問題 解：設 xi 表示從第 i班次開始上班的司機和乘務人員數(i=1,2,3,4,5,6),這樣我們建立如下的數學模型。 Min Z = x1 + x2 + x3 + x4 + x5 + x6 . x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 例題分析 4：合理下料問題 ? 例 4 假定現有一批某種型號的 圓鋼長 8米 ，需要裁取長 米的毛坯 100根、長 200根，問應該怎樣選擇下料方式才能既滿足需要，又使總的用料最省？ ? 解：各種可能的裁剪方案如下表所示： 型號 方案 1 方案 2 方案 3 方案 4 需要根數 3 2 1 0 0 2 4 6 100 200 余料 (米 ) — 例題分析 4：合理下料問題 ? 設 x1,x2,x3,x4 分別為上面 4種方案下料的原材料根數。這樣我們建立如下的數學模型。 ? Min f = x1 + x2 + x3 + x4 ? . 3x1 + 2x2 + x3 ≥ 100 ? 2x2 + 4x3 + 6x4 ≥ 200 ? x1,x2,x3,x4 ≥ 0 例題分析 5：投資問題 例 5 某部門現有資金 200萬元，今后五年內考慮給以下的項目投資。已知： 項目 A：從第一 年 到第五年每年年初都可投資，當年末能收回本利 110%； 項目 B：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規定每年最大投資額不能超過 30萬元； 項目 C：需在第三年年初投資，第五年末能收回本利 140%，但規