第二章线性规划概要.pptVIP

第2章 線性規劃概要 第二章 線性規劃概要 第二章 線性規劃概要 2.1 一個簡單的極大化問題 2.2 圖解法 2.3 極點與最佳解 2.4 Par公司問題的電腦解 2.5 一個簡單的極小化問題 2.6 特殊案例 2.7 一般的線性規劃符號 對所有的線性規劃問題的目標在使某個數量極大化或是極小化。 限制條件(constraints)使得目標的滿足只能到達某個程度，限制條件是每個線性規劃問題的共同特徵。 一個簡單的極大化問題 為Par公司的問題建立一個數學模式，分別決定標準型及豪華型球袋的生產量，以使得總利潤為最大。 問題的模式化 問題的模式化(problem formulation or modeling)是將問題由文字描述轉成數學描述的過程。 問題模式化的步驟 徹底瞭解問題 描述目標 描述每一個限制條件 限制條件1　切染所使用的工時必須小於或等於可用的切染工時。 限制條件2　縫製所使用的工時必須小於或等於可用的縫製工時。 限制條件3　細部製作所使用的工時必須小於或等於可用的細部製作工時。 限制條件4　檢驗及包裝所使用的工時必須小於或等於可用的檢驗及包裝工時。 定義決策變數 S=標準型球袋的數量 D=豪華型球袋的數量　S及D就是決策變數(decision variables)　 以決策變數來表示目標 10S+9D稱為目標函數 Max　10S+9D 將限制條件以決策變數表示之 限制條件1： (切染耗用工時) ? (切染可用工時) 限制條件2： (縫製耗用工時) ? (縫製可用工時) 限制條件3： (細部製作耗用工時) ? (細部製作可用工時) 限制條件4： (檢驗及包裝耗用工時) ? (檢驗及包裝可用工時) 非負限制式(nonnegativity constraints) Par公司問題的數學模式 Par公司問題的數學模式是一種線性規劃模式(linear programming model or linear program)。 所有變數都是獨立項(沒有相乘項)，且皆為一次方的函數稱為線性函數(linear functions)。 圖解法 只包含二個決策變數的線性規劃問題可以用圖解法求解。 極大化問題圖解法摘要 圖解法解極大化問題的步驟可以摘要如下： 為每一個限制式找出可行解。 找出同時滿足所有限制式的可行區域。 畫出某個目標值的目標函數線。 將目標函數線往目標值大的方向平移，一直到可行區域的邊緣為止。 目標函數線上具有最大目標值的可行解就是最佳解。 寬鬆變數 將最佳解的值(S=540, D=252)代入每一個限制式得到以下的資料。 在線性規劃中，任何一個 ? 限制式未用完的量都稱為此限制式的寬裕值(slack)。 在線性規劃問題的式子中加入寬鬆變數(slack variables)以代表寬裕值 在加入S1, S2, S3及S4四個寬鬆變數之後 當線性規劃問題的限制式都寫成等式的形式時，稱為標準型(standard form)。 Par公司問題的標準型，最佳解(S=540, D=252)的寬鬆變數值為 不影響可行區域及最佳解，此限制式因此稱為冗餘限制式(redundant constraint)。 極點與最佳解 Par公司標準型高爾夫球袋單位利潤由10美元減少成5美元，單位利潤與其他限制條件則維持不變。修正過的目標函數 Max　5S+9D Par公司問題的電腦解 電腦輸出結果的解讀 一個簡單的極小化問題-MD化學 A=產品A的加侖數 B=產品B的加侖數 每加侖A的生產成本為2美元，B為3美元，欲使總生產成本最小化的目標函數可以寫成 Min　2A+3B A的產量至少必須為125加侖 1A ? 125 A與B的總產量必須至少350加侖 1A+1B ? 325 可用工時的上限為600小時 2A+1B ? 600 非負限制式(A, B ? 0) MD化學問題的線性規劃模式 極小化問題圖解法摘要 最小化的圖解法求解步驟摘要如下： 畫出每一個限制式的可行區域。 找出同時滿足所有限制式的可行區域。 畫出某個目標值的目標函數線。 將目標函數線往目標值小的方向平移，一直到可行區域的邊緣為止。 目標函數線上具有最小目標值的可行解就是最佳解。 剩餘變數 在線性規劃的術語中，超過 ? 限制式右手邊值的量稱為剩餘值。 例如，A的產量超過最低要求250-125=125加侖，此超過的產量稱為剩餘值(surplus)。 在 ? 的限制式中，在不等式的左手邊減去一個剩餘變數(surplus variable)可以將限制式轉成等式的形式。 在加入二個剩餘變數S1, S2於 ? 的限制式中，以及一個寬鬆變數S3於 ? 的限制式後，MD化學的線性規劃模式變成 MD化學問題的電