運籌學lpilppt課件(編輯修改稿)

　

【文章內容簡介】 ） 1 6 240 （小時） 利 潤（萬元） 1 3 設： x 1 ， x 2 表示產品 I 和 I I 的計劃產量。 數學模型為?????????????????2,102406180221002..m a x21212121jxxxxxxxtsxxfj 其解的最優基對應的單純形表為（見表 1 .56 ） B x 1 x 2 x 3 x 4 x 5 b 1 1 0 3/ 2 0 1/ 2 30 4 0 0 2/ 5 1 1/ 2 50 2 0 1 1/ 4 0 1/ 4 35 C 0 0 3/ 4 0 1/ 4 135 靈敏度分析（ 1） 一、 約束條件右邊常數 b 的靈敏度分析 二、 目標函數變量系數 c 的靈敏度分析 ( 1) 非基變量系數的靈敏度分析 ( 2) 基變量系數的靈敏度分析 靈敏度分析（ 2） 單位產品 產品 消耗工時 工序 A B C 有效工時 （小時） 零件加工（小時 / 件） 1. 0 1. 2 1. 4 4800 電 鍍（小時 / 件） 0. 5 0. 6 0. 6 1800 裝 配（小時 / 件） 0. 7 0. 7 0. 8 2400 利 潤（元 / 件） 12 15 8 解：設 x1, x2, x3 設分別表示產品 A , B , C 一周的計劃生產件數。 ?????????????????????3,2,10..81512m a x321321321321jxxxxxxxxxxtsxxxfj且為整數 靈敏度分析（ 3） x B x 1 x 2 x 3 x 4 x 5 x 6 b x 4 0 0 1/ 5 1 2 0 1200 x 2 5/ 6 1 1 0 5/ 3 0 3000 x 6 7/ 60 0 1/ 10 0 7/ 6 1 300 c 1/ 2 0 7 0 25 0 45000 目標規劃（ 1） 例 某企業計劃生產甲、乙兩種產品，這些產品分別要在 A 、 B 、 C 、 D 四種不同的設備上工。各產品占用資源數據，資源擁有數及產品利潤（見表 1. 54 ）。問如何安排生產，使獲得的總利潤最大？ 單位產品 占用設備臺時 產品甲 產品乙 設備工作 臺 時 設備 A 2 2 12 設備 B 1 2 8 設備 C 4 0 16 設備 D 0 4 12 利潤（百元 / 個） 2 3 m a x. .,f x xs tx xx xxxx x? ?? ?? ?????????????2 32 2 122 84 164 1201 21 21 2121 2它的解為 x1 * = 4 , x2* =2 ；最大目標函數值： f * = 14 從市場信息反饋可知，對甲、乙兩種產品需要量的比例大致是 1∶ 1； 計劃期內的設備能力有一點機動的余地。如設備 B必要時可以加班，當然不希望加班； 設備 A既要充分利用，又盡可能不加班； 企業決策者認識到不考慮附加條件，才使利潤指標達到 14。所以這是一個偏高的指標，決定降低為 12 目標規劃（ 2） ? 偏差變量 d+ ——正偏差 d ——負偏差 ? 目標約束與系統約束 系統約束 ——不可松動的嚴格約束 目標約束 ——可以松動的約束 ? 目標優先級與權系數 優先級 ——P P P3…… 權系數 ——系數大小表示同一優先級中目標的重要程度 第二章 運輸問題 單位運費 （百元 / 噸） A 地 B 地 供應量 甲城 1 2 40 噸 乙城 10 3 60 噸 需求量 30 噸 70 噸 甲 乙 A B 1 2 10 3 1 30 + 2 10 + 3 60 = 230（百元） 甲 乙 A B 1 2 5 10 1 30 + 2 10 + 10 60 = 650（百元） 2 40 + 5 30 + 10 30 = 530（百元） 第一節 運輸問題及其特征（ 2） B 1 B 2 …… B n 供應量 x 11 x 12 x 1n A 1 c 11 c 12 …… c 1n a 1 x 21 x 22 x 2n A 2 c 21 c 22 …… c 2n a 2 … … … …… … … x m1 x m2 x mn A m c m1 c m2 …… c mn a m 需求量 b1 b 2 …… b n 這樣很容易建立運輸問題的數學模型為： ???????????????????? ???? ?njmixnjbxmiaxtsxcfijnjjijmiiijminjijij. . . . . .,2,1,. . . . . .,2,1,0). . . . . .,2,1(), . . . . . .2,1(..m i n111 1 一、運輸問題 第一節 運輸問題及其特征（ 2） 二、運輸問題的特征 ? 特征 1：運輸問題一定有可行解； ? 特征 2：運輸問題一定有最優解； ? 特征 3： 運輸問題每一組基對應 m+n1個基變量； ? 特征 4：運輸問題的 m+n1個基變量不構成閉回路； ? 特征 5：任意一個非基變量和 m+n1個基變量組成的變量集合中必定存在一條并且只存在唯一一條 閉回路 ； ? 特征 6：如果運輸問題中的供應量和需求量都是整數，則任一基本解中各變量的取值也都是整數 ?????????????????????????11111. .. .. .. .. .11111. .. .. ..11. .. .. .. ..1. .. .. ..111. .. .. ..11???A 約束方程的系數矩陣： 閉回路 B 1 B 2 B 3 B 4 B 5 供應量 A 1 a 1 A 2 x 22 x 24 a 2 A 3 x 32 x 34 a 3 A 4 a 4 需求量 b 1 b 2 b 3 b 4 b 5 B 1 B 2 B 3 B 4 B 5 供應量 A 1 x 11 x 12 a 1 A 2 x 22 x 24 a 2 A 3 x 3 1 x 34 a 3 A 4 a 4 需求量 b 1 b 2 b 3 b 4 b 5 B 1 B 2 B 3 B 4 B 5 供應量 A 1 a 1 A 2 x 2 3 x 24 a 2 A 3 x 31 x 34 a 3 A 4 x 41 x 43 a 4 需求量 b 1 b 2 b 3 b 4 b 5 第二節 運輸問題的表上作業法 第一步：編制初始調運方案，也就是尋找第一個基本可行解； ? 求解初始調運方案的方法有很多種，像 西北角法 、 最小元素法 、伏格爾法等都是非常有效的。本書主要介紹最常用的前兩種方法。 第二步：求出相對應的檢驗數； ? 求檢驗數的方法也不止一種，本書主要介紹 位勢法 和 閉回路法 。 第三步：檢驗調運方案是否是最優方案； 如果已經是最優，則算法結束，問題已經解決； 如果還不是最優，則進入第四步； 第四步：調整非最優的調運方案，獲得更好的調運方案，也就是進行換基迭代； ? 改進調運方案，一般采用 閉回路調整法 。 西北角法 單位運費 （千元 / 噸） 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫存量 （噸） 倉庫 A 1 2 9 10 7 9 倉庫 A 2 1 3 4 2 5 倉庫 A 3 8 4 2 5 7 需求量（噸） 3 8 4 6 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫存量 （噸） 倉庫 A 1 ○ 3 ○ 6 9 倉庫 A 2 ○ 2 ○ 3 5 倉庫 A 3 ○ 1 ○ 6 7 需求量（噸） 3 8 4 6 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 C 1= 2 3 + 9 6 + 3 2 + 4 3 + 2 1 + 5 6 = 110 最小元素法 單位運費 （千元 / 噸） 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫存量 （噸） 倉庫 A 1 2 9 10 7 9 倉庫 A 2 1 3 4 2 5 倉庫 A 3 8 4 2 5 7 需求量（噸） 3 8 4 6 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫存量 （噸） 倉庫 A 1 ○ 5 ○ 4 9 倉庫 A 2 ○ 3 ○ 2 5 倉庫 A 3 ○ 3 ○ 4