線性規(guī)劃概論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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