第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.

Slides:



Advertisements
Similar presentations
第三章 單形法 Simplex Method © 廖慶榮 作業研究 二版 p.2/45 章節大綱 1. 前言 2. 單形法的幾何意義 單形法的幾何意義 3. 單形法的代數說明 單形法的代數說明 4. 單形法的表形式 單形法的表形式 5. 特殊情況 特殊情況 6. 對於其他形式的調整 對於其他形式的調整.
Advertisements

台南市立後甲國中 訓導工作簡報 報告人:訓導主任 傅寶源 歡迎蒞臨指導. 訓導處是一個關懷學生生活問題、處理 學生生活事務的溫馨園地,舉凡生活常 規、安全防護、交通安全之教育,民主 法治、社團活動、訓育活動之訓練,衛 生習慣、飲食健康、預防疾病之培養, 體育活動,運動競賽、身心健康之鍛練, 均有專人專責為同學服務。
Chap 3 微分的應用. 第三章 3.1 區間上的極值 3.2 Rolle 定理和均值定理 3.3 函數的遞增遞減以及一階導數的判定 3.4 凹面性和二階導數判定 3.5 無限遠處的極限 3.6 曲線繪圖概要 3.7 最佳化的問題 3.8 牛頓法 3.9 微分.
楊學成 老師 Chapter 1 First-order Differential Equation.
工職數學 第四冊 第一章 導 數 1 - 1 函數的極限與連續 1 - 2 導數及其基本性質 1 - 3 微分公式 1 - 4 高階導函數.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
譯著:王銘正 製作:王銘正 馬惠茹 © 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
Chapter 1 人類的探究與科學 © 2010 Cengage Learning. All rights reserved.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
第 3 章 方程與圖像.
中二數學 第五章 : 二元一次方程 二元一次方程的圖像.
3-2 條件不等式 解一元 n 次不等式 二元一次不等式的圖解法 函數的極植.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
譯著:王銘正 製作:王銘正 馬惠茹 © 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
線性規劃實務應用 應用領域(例如): 決定每期最佳產品生產組合 多重期間的生產規劃 行銷管理(如選擇媒體) 財務管理(如選擇投資組合)
第十三章 以全球市場行銷策略談科技管理與創新-以三星電子全球布局為例
認識倍數(一) 設計者:建功國小 盧建宏.
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
二元一次不等式 課堂練習一:圖解 x
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
读秀学术搜索 读秀的图书搜索. 能够为我们解决一个 什么问题? 是什么东西? 读秀 1. 读秀知识库是以 170 万种中文图书、 6 亿页 全文资料为基础的超大型数据库。 2. 为读者提供深入到图书内容章节和全文的精 度检索,全面立体的多面检索,部分文献的 原文试读,以及参考咨询服务,是一个真正.
LINGO.
Linear Programming: Introduction and Duality
22 货币增长与通货膨胀 经济学原理 N. 格里高利·曼昆 第六版
Chapter 2 線性規劃.
譯著:王銘正 製作:王銘正 馬惠茹 © 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
Chapter 17 投資決策經濟分析.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
整數線性規劃 線性規劃中有一項假設,是決策變數是連續的,且不必為整數。如果某個問題符合線性規劃連續性等其他假設,但決策變數卻必須是整數,則成為『整數線性規劃(ILP)』。 7-1.
第6章 線性規劃:單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
簡捷法 簡捷法可用來找尋端點,並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解,再算出是否有其他解的目標函數值較此點為佳。
第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
Wavelet transform 指導教授:鄭仁亮 學生:曹雅婷.
第1章 緒論 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a.
第一章 直角坐標系 1-1 數系的發展.
網路遊戲版 幸福農場168號.
有效的運用組織資源 Linear Programming (Goal Programming)
第四章 線性規劃:敏感度分析與電腦報表解讀
第一章 直角坐標系 1-3 函數圖形.
決策的衝突與重結構   內容大綱  決策的本質與程序 賽局理論的觀察 多階規劃的觀察 結論與建議 2019/4/7 U.P. Wen.
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
赵 彤 运筹学模型与软件实践 Models and Software Practice of the Operations Research 赵 彤
Definition of Trace Function
可愛的鍬形蟲 五年四班2.
小學四年級數學科 8.最大公因數.
第八章補充 運輸模型.
線性規劃模式 Linear Programming Models
大綱:加減法的化簡 乘除法的化簡 去括號法則 蘇奕君 台灣數位學習科技股份有限公司
微積分網路教學課程 應用統計學系 周 章.
圓的定義 在平面上,與一定點等距的所有點所形成的圖形稱為圓。定點稱為圓心,圓心至圓上任意一點的距離稱為半徑,「圓」指的是曲線部分的圖形,故圓心並不在圓上.
Chapter 8 整數規劃與目標規劃.
105學年度 服務學習教育說明會 Service Learning.
6.6 線性規劃的單體法 單體法 (simplex method)
第一章 直 線 ‧1-3 二元一次方程式的圖形.
第三章 直線方程式與 二元一次不等式 3-1 直線的斜角與斜率 3-2 直線方程式的求法 3-3 二元一次方程式的圖形
第二章 三角函數 2-5 三角函數的圖形.
函數應用(二)與自定函數.
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
1-1 二元一次式運算.
第一章 直角坐標系 1-3 函數及其圖形.
線性規劃的其他演算法 Special Simplex Method
4-1 變數與函數 第4章 一次函數及其圖形.
第四章 線性規劃:敏感度分析與電腦報表解讀
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
以下是一元一次方程式的有________________________________。
7. 三角學的應用 正弦公式 餘弦公式 a2 = b2 + c2 - 2bc cos A b2 = a2 + c2 - 2ac cos B
Chapter 16 動態規劃.
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
Presentation transcript:

第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

第2章 線性規劃概要 2.1 簡單的極大化問題 2.2 圖解法 2.3 極點與最佳解 2.4 Par公司問題的電腦解 2.5 簡單的極小化問題 2.6 特殊案例 2.7 一般線性規劃的符號 第2章 線性規劃概要 第29頁

前言 線性規劃的典型應用實例: 1. 製造商想建立其生產排程與存貨政策,以滿足未來某段期間的銷售需求。理想的生產排程與存貨政策將能同時滿足客戶的需求,並使生產與存貨的成本極小化。 2. 財務分析師必須由眾多股票及債券商品中,擇定一投資組合,希望此投資組合能使投資報酬極大化。 第2章 線性規劃概要 第30頁

前言 線性規劃的典型應用實例: 3. 行銷經理想要由眾多的廣告媒體諸如廣播、電視、報紙、雜誌等,決定其廣告預算的最佳配置,以使得廣告的效用極大化。 4. 某公司在全美各地擁有若干座倉庫。針對若干客戶的需要,公司想要決定各個倉庫對每個客戶的送貨量,以使運輸成本極小化。 第2章 線性規劃概要 第30頁

前言 對所有的線性規劃問題而言,目標是使某個數量極大化或是極小化。 限制條件(constraints)使得目標的滿足只能到達某個程度,限制條件是每個線性規劃問題的共同特徵。 第2章 線性規劃概要 第31頁

2.1 簡單的極大化問題 為Par公司的問題建立數學模式,分別決定標準型及豪華型球袋的生產量,使得總利潤最大。 第2章 線性規劃概要 第32頁

問題的模式化 問題的模式化(problem formulation / modeling)是將問題由文字描述轉成數學描述的過程。 問題模式化的步驟 徹底瞭解問題 描述目標 描述每個限制條件 限制條件1 切割及染色所使用的工時必須小於或等於可用的切割及染色工時。 限制條件2 縫製所使用的工時必須小於或等於可用的縫製工時。 第2章 線性規劃概要 第32-33頁

問題的模式化 限制條件3 細部製作所使用的工時必須小於或等於可用的細部製作工時。 限制條件3 細部製作所使用的工時必須小於或等於可用的細部製作工時。 限制條件4 檢驗及包裝所使用的工時必須小於或等於可用的檢驗及包裝工時。 定義決策變數 S = 標準型球袋的數量 D = 豪華型球袋的數量    S及D就是決策變數(decision variables)  第2章 線性規劃概要 第34-35頁

問題的模式化 以決策變數來表示目標 10S + 9D 稱為目標函數 Max 10S + 9D 以決策變數表示限制條件 限制條件1: (2.1) 限制條件2: (2.2) 第2章 線性規劃概要 第2章 線性規劃概要 第33-34頁

問題的模式化 限制條件3: (2.3) 限制條件4: (2.4) 非負限制式(nonnegativity constraints) 第2章 線性規劃概要 第34頁

Par公司問題的數學敘述 (2.6) Par公司問題的數學模式是一種線性規劃模式(linear programming model or linear program)。 所有變數都是獨立項(沒有相乘項),且都是一次方的函數稱為線性函數(linear functions)。 第2章 線性規劃概要 第35頁

2.2 圖解法 只包含兩個決策變數的線性規劃問題可以用圖解法求解。 第2章 線性規劃概要 第35-36頁

2.2 圖解法 第2章 線性規劃概要 第37頁

2.2 圖解法 第2章 線性規劃概要 第38頁

2.2 圖解法 第2章 線性規劃概要 第39頁

2.2 圖解法 第2章 線性規劃概要 第40頁

2.2 圖解法 圖2.3 與圖2.4 的四張圖經過重疊之後,可以得到一張同時有四個限制式的圖,結果如圖2.5 所示。圖2.5 的陰影區域包含能同時滿足四個限制條件的所有解。因為能夠滿足所有限制式的解稱為可行解(feasible solutions),此陰影區域稱為可行解區域,或簡稱可行區域(feasible region)。任何位於可行區域之內或邊界上的點都稱為可行解點(feasible solution point)。 第2章 線性規劃概要 第38頁

2.2 圖解法 第2章 線性規劃概要 第40頁

2.2 圖解法 第2章 線性規劃概要 第41頁

2.2 圖解法 第2章 線性規劃概要 第42頁

2.2 圖解法 第2章 線性規劃概要 第43頁

2.2 圖解法 第2章 線性規劃概要 第45頁

2.2 圖解法 第2章 線性規劃概要 第46頁

極大化問題圖解法摘要 圖解法解極大化問題的步驟可以摘要如下: 畫出每個限制式的可行解的圖形。 找出同時滿足所有限制式的可行區域。 畫出某個目標值的目標函數線。 將目標函數線往目標值大的方向平移,一直到可行區域的邊緣為止。 目標函數線上具有最大目標值的可行解就是最佳解。 第2章 線性規劃概要 第46-47頁

寬鬆變數 將最佳解的值(S=540, D=252)代入每個限制式,得到以下的資訊。 在線性規劃中,任何一個限制式未用完的量都稱為此限制式的寬裕值。 寬裕值 第2章 線性規劃概要 第47頁

寬鬆變數 線性規劃問題的式子中加入寬鬆變數(slack variables)以代表寬裕值或未閒置產量。 加入S1、S2 、S3及S4四個寬鬆變數之後 第2章 線性規劃概要 第47頁

寬鬆變數 當線性規劃問題的限制式寫成等式的形式,稱為標準型(standard form)。 Par公司問題的標準型,最佳解(S=540, D=252)的寬鬆變數值為: 不影響可行區域及最佳解,此限制式稱為冗餘限制式(redundant constraint)。 第2章 線性規劃概要 第47-48頁

2.3 極點與最佳解 Par公司的標準型高爾夫球袋的單位利潤由10美元減為5美元,而豪華型球袋的單位利潤與其他限制條件則不變。修正過的目標函數: Max 5S + 9D 第2章 線性規劃概要 第48頁

2.3 極點與最佳解 限制式沒有改變,所以可行區域沒變。 利潤線已經換成新的目標函數。 以線性規劃的術語,稱這些頂點為可行區的極點(extreme points)。 可以在可行區域的極點,找到線性規劃問題的最佳解。 第2章 線性規劃概要 第48-49頁

2.3 極點與最佳解 第2章 線性規劃概要 第49頁

2.4 Par公司問題的電腦解 最佳解 寬裕值 第2章 線性規劃概要 第51頁

2.5 一個簡單的極小化問題─M&D化學 A=產品A的加侖數 B=產品B的加侖數 Min 2A+3B A的產量至少必須為125加侖 1A 125 A與B的總產量必須至少350加侖 1A+1B  325 可用工時的上限為600小時 2A+1B  600 第2章 線性規劃概要 第52頁

2.5 一個簡單的極小化問題─M&D化學 非負限制式(A, B  0) M&D化學問題的線性規劃模式 第2章 線性規劃概要 第52頁

2.5 一個簡單的極小化問題─M&D化學 將目標函數線向左下 方移動,直到可行區 域的邊緣。 第2章 線性規劃概要 第53頁

2.5 一個簡單的極小化問題─M&D化學 第2章 線性規劃概要 第53頁

極小化問題圖解法摘要 最小化的圖解法求解步驟摘要如下: 畫出每個限制式的可行解的圖形。 找出同時滿足所有限制式的可行區域。 畫出某個目標值的目標函數線。 將目標函數線往目標值小的方向平移,一直到可行區域的邊緣為止。 目標函數線上具有最小目標值的可行解就是最佳解。 第2章 線性規劃概要 第54頁

剩餘變數 在線性規劃的術語中,超過限制式右側值的量稱為剩餘值。 A產品的產量超過最低要求250-125=125加侖,此超過的產量稱為剩餘值(surplus)。 在的限制式中,在不等式的左手邊減去一個剩餘變數(surplus variable)可以將限制式轉成等式的形式。 第2章 線性規劃概要 第54頁

剩餘變數 在加入兩個剩餘變數S1、S2於的限制式,以及一個寬鬆變數S3於的限制式之後,M&D化學的線性規劃模式變成: 第2章 線性規劃概要 第54頁

M&D化學問題的電腦解 第2章 線性規劃概要 第56頁

多重最佳解 由圖解法可知,在可行區域的極點可找到最佳解。現在讓我們看一個特例:最佳解的目標函數線與某個關鍵限制式在可行區域的邊緣發生重疊。此種現象將導致所謂的多重最佳解(alternative optimal solutions);也就是同時存在許多組解可以提供最佳目標函數值。 第2章 線性規劃概要 第57頁

多重最佳解 在此線段上皆為最佳解 第2章 線性規劃概要 第57頁

無可行解 無可行解(infeasibility):沒有一個解可以同時滿足所有的限制式,包括非負限制式。 第2章 線性規劃概要 第58頁

無可行解 第2章 線性規劃概要 第59頁

無限解 如果一個極大化問題的解可以無限大,或者一個極小化問題的解可以無限小,而不會違反任何的限制條件,此問題具有無限解(unbounded)。 第2章 線性規劃概要 第59、61頁

2.7 一般線性規劃的符號 經常使用於線性規劃,更具普遍性的符號表示法, 是將 x 加上下標的數字表示決策變數。例如, Par公司的問題,我們可以將決策變數定義成: x1 = 標準型球袋的數量 x2 = 標準型球袋的數量 使用一般符號的缺點是:不再能輕易地得知決策 變數所代表的意義。 優點是描述一個具有很多決策變數的問題時會變得比較容易。 第2章 線性規劃概要 第60-61頁

2.7 一般線性規劃的符號 第2章 線性規劃概要 第62頁