《线性规划几何方法》由会员分享，可在线阅读，更多相关《线性规划几何方法（80页珍藏版）》请在金锄头文库上搜索。
1、第 3 章線性規劃：幾何方法23.1 二變數線性不等式系統之繪圖 線性不等式之繪圖Tan/管理數學 第3章 第140頁3線性不等式之繪圖Tan/管理數學 第3章 第141頁4線性不等式之繪圖Tan/管理數學 第3章 第141頁線性不等式的繪圖程序1. 將式子中的不等號改成等號之後得一線方程式，將該 線繪於xy平面上。若遇嚴格不等式，則以虛線表示圖 形不包含該線；否則以實線表示。 2. 在直線分割出來的任一半面中選一測試點(如有可能最好選原點)，將其點座標代入不等式左側。 3. 若測試點的座標滿足不等式，其所在的半面即為所求 半面；否則，另一個半面才是我們要的。在選好的半 面塗上陰影。5例題 1
2、l找出2x+3y 6的解。解： 我們先將的符號改成=，得到2x + 3y = 6的方程式， 用實線將線繪於xy平面上，如圖3。接著以原點為測 試點，代入不等式左側2(0) + 3(0)，由於所得的0不 可能大於6，即原點的座標無法滿足不等式，因此， 不含原點的另一半面才是2x + 3y 6 的解所成的集合 。Tan/管理數學 第3章 第142頁6例題 1（續）Tan/管理數學 第3章 第142頁7例題 2l繪出x 2y 0的圖形。解： 我們先畫出x 2y = 0的線，見圖4。由於原點落在直 線上，因此不能當測試點，任選另一點如(1, 2) 為測 試點，檢驗的結果1 2(2) 的值為3，無法滿足
3、不等 式，因此，不含測試點(1, 2)的另一半面才是x 2y 0的解所成的集合。Tan/管理數學 第3章 第142頁8例題 2（續）Tan/管理數學 第3章 第142頁9線性不等式系統的圖形l線性不等式系統(systems of linear inequalities)的解 所成的集合是指滿足所有不等式的(x, y) 點所成的集 合，我們也稱之為解集合(solution set)。欲求得線性 不等式系統的圖形解，可將每個不等式的圖形解獨 立繪出，之後找出共同交集的區域。Tan/管理數學 第3章 第143頁10例題 3l繪出下列不等式系統的解集合：解： 我們針對每個不等式先求出解所在的半面，並用
4、箭 頭標示半面的位置，如圖5。兩個半面的交集即陰影 區域，此區域構成系統的解集合，區域中的任一點 必滿足系統中的任一不等式。Tan/管理數學 第3章 第143頁11例題 3（續）Tan/管理數學 第3章 第143頁解（續）：其中P點座標是由下列線性方程組解得：12例題 4l繪出下列不等式系統的解集合：解： 前面兩個不等式代表解必定在第一象限。我們針對後面兩個 不等式先求出解所在的半面，並用箭頭標示半面的位置，如 圖6。兩個半面交集於第一象限的區域，如陰影所示，即為線 性不等式系統的解集合。Tan/管理數學 第3章 第143-144頁13例題 4（續）Tan/管理數學 第3章 第144頁解（續）
5、：其中P點座標是由x + y 6 = 0與2x + y 8 = 0的線性 方程組解得。14線性不等式系統的圖形Tan/管理數學 第3章 第144頁解集合的有界與無界若我們可以畫個大圓把線性不等式系統的解集合包起來， 則此解集合是有界的(bounded)；否則，即是無界的 (unbounded) 。15例題 5l繪出下列的不等式系統的解：解： 後面兩個不等式代表解必定在第一象限。我們針對前面兩個 不等式先求出解所在的半面，並用箭頭標示半面的位置，如 圖7。兩個半面交集於第一象限的區域，如陰影所示，即為線 性不等式系統的解集合，可以看出此解集合是無界的。Tan/管理數學 第3章 第144-145頁
6、16例題 5（續）Tan/管理數學 第3章 第145頁173.2 線性規劃問題Tan/管理數學 第3章 第149頁線性規劃問題一個線性規劃問題(linear programming problem) 具有一 個尋求極大化(maximization)或極小化(minimization)的線 性目標函數，且其隸屬的限制條件均以線性的等式或不 等式來呈現。或說線性規劃問題是在線性不等式的解集合裡尋求極大 值或極小值的問題。18例題 1 生產規劃l永新公司想要生產甲、乙兩款紀念品。l一個甲紀念品的利潤是1元；乙紀念品是1.20元。l製造一個甲紀念品時，需使用機器一2分鐘、機器二1分鐘 ；製造一個乙紀念
7、品時，需使用機器一1分鐘、機器二3分 鐘。l已知機器一可使用的總時數是3 小時，機器二為5 小時。試問永新公司每款紀念品應生產多少個才能使利潤 最大？將此線性規劃問題公式化但不必求解(我們將 於第3.3 節的例題1中求解)。Tan/管理數學 第3章 第149頁19例題 1 生產規劃（續）解： 根據題意，我們先整理出下表：令x, y分別為甲、乙兩款紀念品的生產量，則總利潤( 單位：元) 為 P = x + 1.2yTan/管理數學 第3章 第150頁20例題 1 生產規劃（續）解（續）： P即是欲求極大化的目標函數。此外，在x, y的產量 分配下，機器一將需2x + y分鐘，而這時間不能超過 機
8、器一可使用的時間，即180 分鐘，由此列出第一條 不等式： 2x + y 180 同樣地，機器二將需x+3y分鐘，而這時間不能超過 機器二可使用的時間，即300分鐘，由此列出了第二 條不等式： x+ 3y 300Tan/管理數學 第3章 第150頁21例題 1 生產規劃（續）解（續）： 生產量x, y不得為負，因此需加上不等式如下：故總結此問題係在下列幾個不等式的條件限制下，尋求目標 函數P = x + 1.2y的極大化：Tan/管理數學 第3章 第150頁22例題 2 營養問題l一營養學家建議一位欠缺鐵質與維他命B的病人，應攝取 至少2,400 毫克的鐵質、2,100毫克的維他命B1與1,5
9、00毫 克的維他命B2一段時間。現考慮採用A, B兩個牌子的維 他命丸。l維他命丸A每顆含40 毫克的鐵質、10 毫克的維他命B1與5 毫克的維他命B2；l維他命丸B每顆含10 毫克的鐵質，以及各15毫克的維他命 B1與B2。l已知維他命丸A 每顆要6 元，維他命丸B 每顆是8 元。請問營養學家應建議病人兩個牌子的維他命丸各吃多少 顆，才能滿足最低攝取量且花費最低？將此線性規劃問 題公式化但不必求解(我們將於第3.3 節例題2 中求解)。Tan/管理數學 第3章 第151頁23例題 2 營養問題（續）解： 我們將兩種維他命丸的資訊整理於下表：令x, y分別為維他命丸A與B所需服用的顆數，則維他
10、命丸的 花費成本為 C = 6x + 8y 此即欲求極小化的目標函數。Tan/管理數學 第3章 第151頁24例題 2 營養問題（續）解（續）： 服用x顆維他命丸A與y顆維他命丸B將獲取40x + 10y 毫克的鐵質，為達到最低攝取量2400毫克的要求， 我們得到第一條不等式：同樣地，為達到維他命B1與B2的最低攝取量的要求 ，我們列出另外兩條不等式如下：Tan/管理數學 第3章 第151頁25例題 2 營養問題（續）解（續）： 故總結此問題係在下列幾個不等式的條件限制下， 尋求目標函數C = 6x + 8y的極小化：Tan/管理數學 第3章 第151-152頁26例題 3 倉庫問題l雅音公司
11、在二個不同的廠(廠與廠)生產F型喇叭系統。廠 的月產能是400組而廠是600組。l目前打算運送這些喇叭系統到公司三家做為配銷中心的倉庫。l根據各倉庫的訂單情形，A, B, C三家倉庫每月最低的需求量分 別是200, 300與400 組。l一組喇叭從廠運送到A, B, C 三家倉庫的運輸成本分別為20, 8 與10元；從廠運送到A, B, C三家倉庫的運輸成本分別為12, 22 與18 元。l試問雅音公司該如何訂定運輸計畫，才能滿足三家配銷中心 的訂單需求，並使運輸成本最低？將此線性規劃問題公式化 但不必求解(我們將於第4.2 節的例題5 中求解)。Tan/管理數學 第3章 第152頁27Tan
12、/管理數學 第3章 第152頁例題 3 倉庫問題（續）解（續）： 我們先將工廠與倉庫間的單位運輸成本資訊整理於 下表：28例題 3 倉庫問題（續）解（續）： 令x1表示喇叭產品從廠運到倉庫A 的數量， x2表示 從廠運到倉庫B 的數量，並以此類推，詳見下表 ：Tan/管理數學 第3章 第152頁29例題 3 倉庫問題（續）解（續）： 由表3 與表4 可知從廠運到倉庫A 的運輸成本為20 x1 ，運到倉庫B 的運輸成本為8 x2，並以此類推。因 此，運輸的總成本為此外，基於廠與廠在產能上的限制，故有以下 兩個不等式：Tan/管理數學 第3章 第152頁30例題 3 倉庫問題（續）解（續）： 而為
13、滿足三家倉庫的最低需求量限制，分別列出三 個不等式：Tan/管理數學 第3章 第152頁31例題 3 倉庫問題（續）解（續）： 綜合起來，我們得到以下的線性規劃問題：Tan/管理數學 第3章 第152頁323.3 線性規劃問題的圖形解Tan/管理數學 第3章 第157頁圖解法33圖解法Tan/管理數學 第3章 第158頁定理1：線性規劃若一線性規劃問題有解，其解必然發生在可行集合S的頂 點或角落點(corner point) 上。若目標函數P在兩個相鄰的 頂點上都達到最佳值，則連接這兩相鄰頂點之線段上的 任一點均為最佳解，亦即此線性規劃問題有無限多個解 。34圖解法Tan/管理數學 第3章 第
14、159頁定理2：解的存在與否假設一線性規劃問題的可行集合為S，目標函數為P = ax + by。 a. 若S為有界，則P在S上可找到最大值及最小值。 b. 若定義S的限制式包括x 0及y 0，當a與b均是非負的數，且知S為無界時，則P在S上可找到最小值。 c. 若S是空集合，則此線性規劃問題無解，亦即無最大值也無最小值。35圖解法Tan/管理數學 第3章 第159頁角落法1. 畫出可行集合。 2. 找出可行集合上所有角落點(或頂點)的座標。 3. 算出各角落點的目標函數值。 4. 找出使目標函數值最大(或最小)的角落點。若此角落 點是唯一的，則代表這是唯一的解。若目標函數於兩 個相鄰的角落點上
15、都得到最大值(或最小值)，則此線 性規劃問題有無限多個解，而連接這兩相鄰角落點之 線段上的任一點均為最佳解。36例題 1 利潤極大化l在第3.2節的例題1中，我們已將線性規劃問題公式化，其結 果如下：本節則利用角落法求解。解： 我們首先繪出可行集合S，見圖10。Tan/管理數學 第3章 第159頁37例題 1 利潤極大化（續）解（續）：Tan/管理數學 第3章 第160頁38例題 1 利潤極大化（續）解（續）： 在S上的角落點有A (0, 0) , B (90, 0) , C (48, 84)與D (0, 100)。將各角落點座標及其目標函數值列表整理於Tan/管理數學 第3章 第160頁39
16、例題 1 利潤極大化（續）解（續）： 從表上的值可比較出來，最大的目標函數值發生在C (48, 84) 的角落點，其值為148.8。因此，永新公司應 生產甲款的紀念品48 個，乙款的紀念品84 個，如此 可以得到最大利潤148.8 元。Tan/管理數學 第3章 第160頁40例題 2 營養問題l在第3.2 節的例題2中，我們已將線性規劃問題公式 化，其結果如下：本節則利用角落法求解。Tan/管理數學 第3章 第160頁41例題 2 營養問題（續）解： 我們首先繪出可行集合S，見圖11。Tan/管理數學 第3章 第161頁42例題 2 營養問題（續）解（續）： 在S上的角落點有A (0, 240), B (30, 120), C (120, 60)與 D (300, 0)。將各角落點座標及其目標函數值列表整 理於下：Tan/管理數學 第3章 第161頁43例題 2 營養
