线性规划概论

1、第二章線性規劃概論1. 以圖解法求解以下問題：極大化 受限於Sol. 此LP的圖形如題解圖2.1所示，其最佳解為。088642642題解圖 2.1 2. 以圖解法求解以下問題：極小化 受限於 Sol. 此LP的圖形如題解圖2.2所示。由圖中可得最佳解為 。08108642642題解圖2.23. 考慮以下問題：極大化 受限於(a) 以圖解法求解此問題。(b) 若目標函數改為：極大化，則最佳解為何？Sol. (a) 此LP的圖形如題解圖2.3所示，其最佳解為。(b) 此LP的圖形如題解圖2.4所示，其最佳解為連接與兩點之線段上所有點，亦即，其中。08108642642128題解圖2.3 08108

2、64264212810題解圖2.4 4. 考慮以下問題：極大化 受限於若要使得最佳解為，則之值的範圍為何？Sol. 此LP的圖形如題解圖2.5所示。因此，的範圍可計算如下：04242題解圖2.5 5. 考慮以下問題：極大化 受限於(a) 以圖解法求解此問題。(b) 若目標函數改為極小化，則最佳解為何？Sol. (a) 此LP的圖形如題解圖2.6所示。因為可得到，所以此問題的解是無窮解。(b) 若目標函數改為極小化，則最佳解為。6. 以圖解法求解以下問題：極大化 受限於不受限, Sol. 此LP的圖形如題解圖2.7所示。由圖中可得最佳解為 。04242題解圖2.6 7. 以圖解法求解以下問題：極

3、大化 受限於Sol. 此問題的圖形如題解圖2.8所示。因為可行區域是空集合，所以此問題無可行解。642420題解圖2.7 0642642題解圖2.8 8. 以圖解法求解以下問題：極大化 受限於Sol. 此LP的圖形如題解圖2.9所示。由圖中可知可行區域僅為一條線段，最佳解為。088642642題解圖2.99. 將以下問題轉換為線性規劃模式：極大化 受限於Sol. 轉換後的LP模式如下：極大化 受限於10. 將以下問題轉換為線性規劃模式：極大化 受限於Sol. 轉換後的LP模式如下：極大化 受限於11. 將以下問題轉換為線性規劃模式：極大化 受限於Sol. 定義新的變數。因為有可能是正值，亦有可

4、能是負值，所以讓，其中。轉換後的LP模式如下：極大化 受限於 12. 某海鮮食品加工廠，每個月月初均要買進大批的魚貨，經過加工後，再賣到各批發市場。由於季節性問題，各種魚類每個月的進貨價格和賣出價格均有所差異。對於A種魚類，一年當中只有五個月可以捕獲，各月份的進貨價格與賣出價格如表2.5所示。魚貨買進後會先放進冷凍庫等待加工，加工完畢後可送至批發市場販賣，亦可再放回冷凍庫以後再賣。該加工廠在這五個月內，只加工此A種魚類，每個月可加工15噸（1噸1000公斤），而冷凍庫的容量最多可儲存30噸的魚貨。加工廠為安排加工其他魚種，所有A種魚貨將於七月底前全部賣出。欲使這五個月的收益最大，這家食品加工廠

5、每個月應分別買進與賣出多少魚貨？建立此問題的線性規劃模式。Sol. 月份買進的魚貨量（噸）月份賣出的魚貨量（噸）月份加工的魚貨量（噸）月份月底存貨（噸）此問題的LP模式如下：極大化表 2.5 月份買進價格（萬元噸）賣出價格（萬元噸）三月$60$100四月$55$95五月$40$85六月$55$105七月$50$100受限於13. 某工廠目前生產四項產品（A、B、C、D），然因產能受到限制，所以管理當局希望重新評估並分析這四項產品的最佳生產組合。根據資料顯示，目前主要的產能限制是其中的兩個瓶頸部門，其每月產能分別為320及240機器小時。各產品每生產一個批次所需的生產時間如表2.6所示，表中亦顯

6、示各產品每生產一個批次所能獲得的利潤。根據行銷部門所提供的資料，產品A至多只能售出40個批次的量，而產品C最少要提供30個批次的量。管理當局應如何決定這四項產品的最佳生產組合，以獲得最大的總利潤？建立此問題的線性規劃模式。表 2.6瓶頸部門生產一個批次所需小時數可用產能ABCD部門11331320部門22125240每批次的利潤Sol. 讓部門生產之批次數，則此問題的LP模式如下：極大化 受限於 14. 某公司有四個工廠（P1、P2、P3、P4）和三個配銷中心（D1、D2、D3）。各工廠每個月的產能（所能供給的數量）以及各配銷中心每個月的需求如表2.7所示。各工廠至各配銷中心的運送距離（單位為

7、公里）亦彙整於表中。例如，工廠P1至配銷中心D2的運送距離為50公里。假設運輸成本和距離完全成正比。該公司應如何決定各工廠配送至各配銷中心的數量，才能使得總運送成本最低？建立此問題的線性規劃模式。（此問題稱為運輸問題transportation problem，詳細內容請參見第七章）表2.7配銷中心工廠D1D2D3供給（噸）P1455065150P250705090P3504040160P460355570需求（噸）45180210Sol. 讓工廠配送至配銷中心之數量，則此問題的LP模式可表示如下：極小化受限於15. 某公司目前有四個職缺亟需用人，並有三位已決定錄用的新進人員。根據新進人員的專

8、長、經驗和興趣，人事部門做出這三位新進人員任職各不同職缺的適合度指標（參見表2.8）；指標數值越大者，代表適合度越高。該公司應如何指派這三位新進人員至其中的三個職缺？建立此問題的線性規劃模式。（此問題稱為指派問題assignment problem，由於此問題的特殊結構，會使所得到的解必為整數解，因此可用線性規劃求解，詳細內容請參見第七章）表2.8 工作職缺人員J1J2J3J4S13932S294103S38645Sol. 讓員工指派至職缺之人數，則此問題的LP模式如下：極小化 受限於16. 某公司目前有萬的閒置資金，三年後才會需要使用。根據財務部門所提供的資料，現在有四個投資方案列入考慮。各

9、投資方案均已評估過風險，並給予0至3分的風險指標，數值越大代表風險越高。表2.9顯示各投資方案每年利息的百分比及風險指標。例如，方案2完全沒有風險（風險指標為零），每年年底可獲得投資金額3%的利息；方案4的風險最高（風險指標為2），投資後僅在第三年年底可獲得投資金額18%的利息。在以上的四個方案中，本金均於第三年年底全數歸還；當年底有回收的利息時，僅能於次年年初投資方案2（亦即，其餘方案必須於第一年年初投資）。該公司希望所投資金額的平均風險指標（僅本金部份）不要高於1。該公司於每年年初應分別投資多少金額在各投資方案上，才能於第三年年底獲致最多的利息收入？建立此問題的線性規劃模式。表2.9年底利

10、息（%）投資方案第一年第二年第三年風險指標106612333030741400182Sol. 定義變數如下：第年投資方案的金額此問題的LP模式如下：極小化受限於在此LP模式中，前三個限制式是資金平衡公式。限制式(4)是限制投資金額的平均風險指標不要高於1（僅本金部分），該式是由下式簡化而得17. 某服務業公司對於每天需要的員工人數有很大的波動，於一週期間每天所需要的人數如下表所示：星期一二三四五六日人力需求50404045608085除了專職人員外，公司亦可聘僱兼職人員。每兩位兼職人員的人力相當於一位專職人員，但每位兼職人員的薪資僅為專職的30%。然而，因為考慮專職人員對於工作的熟悉度，所以公

11、司希望每天上班的兼職人員人數最多不得超過專職人員人數的1/4。專職人員每週連續上班五天、休假兩天；兼職人員則沒有任何規定。在此情況下，欲使總人事成本最低，該公司至少應聘請多少位專職人員？每天上班的兼職人員時數又應是多少？Sol. 定義變數如下：星期開始第一天上班的專職人數（代表星期一，以此類推）星期上班的兼職人員時數此問題的LP模式如下：極小化 受限於18. 某公司專門製造合金，其中三種合金是由三種回收金屬冶煉而成。表2.10顯示三種合金應含回收金屬的成分（下限及上限百分比），以及每月可購得回收金屬的數量及價格。例如，合金A最少需20%、最多40%的回收金屬I。該公司每月應購買多少這三種回收金

12、屬作為此三種合金生產之用，才能獲得最大的淨利？建立此問題的線性規劃模式。表2.10回收金屬成分（%）合金價格（公斤）合金IIIIIIA(20,40)(40,65)(10,10)$650B(15,30)(50,60)(20,25)$500C(30,60)(40,60)(25,25)$830回收金屬數量（公斤）1008050回收金屬價格（公斤）$300$200$450Sol. 定義變數如下：每月回收金屬用於合金的數量（公斤）此問題的LP模式如下：極小化受限於以上功能限制式分為兩部分，第一部份包括限制式(1)(3)，其目的是限制每月可購得回收金屬的數量。第二部分包括所有其餘的功能限制式，其目的是限制

13、各合金中所含回收金屬的上下限。例如，對於的限制如下：以上兩式經轉換後即為限制式(4)及(5)。其餘限制式均可以同樣方式求得。19. 某客運公司擬重新規劃各班別駕駛員的人數。經過詳細分析，各時段所需班車數（即駕駛員人數）如表2.11所示。駕駛員上班時間分為早、中、下午、晚四個班別，其開始上班時間分別為6:00、12:00、14:00及16:00，均為連續上班8小時。該客運公司各班別應分別安排多少位駕駛員，才能以最少的人數滿足所需？表2.11時段所需人數06:0010:004010:0016:002216:0019:004219:0021:002821:0022:003522:0024:00182

14、4:0002:008Sol. 根據題目，我們可建立表如下：時段早班中班下午班晚班所需人數06:0010:004010:0012:002212:0014:002214:0016:002216:0018:004218:0019:004219:0020:002820:0021:002821:0022:003522:0024:001824:0002:008定義變數如下：安排早班的駕駛員人數安排中班的駕駛員人數安排下午班的駕駛員人數安排晚班的駕駛員人數此問題的LP模式如下：極小化 受限於 20. 因為已連續半年未下大雨，所以政府決定未來一年對於北部農地採取限水的措施。北部四戶相連農地的農家委請當地農會協

15、助規劃未來一年的農作物耕種。各戶農家的土地面積及未來一年每月可分配到的水量（依據各戶去年的用水量而定）如表2.12所示。目前大家考慮耕種三項農作物，各農作物對於水量的需求各有不同。為考慮市場情況，農會認為各項農作物的耕種面積應有其上限，並提供所建議的上限數字。表2.13提供各農作物的用水需求、耕種面積上限、每公頃的銷售價格及耕種成本等資料。此外，為公平起見，四戶農家各自的總耕種面積和土地面積的比例要求完全相等。農會應如何為農家決定各戶耕種各農作物的面積，才能獲得最大的利潤？建立此問題的線性規劃模式。表2.12 農家1農家2農家3農家4土地面積（公頃）108514分配水量（公頃公尺）1510920表2.1