【正文】 0 例題分析 3：人力資源分配問題 解：設 xi 表示從第 i班次開始上班的司機和乘務人員數(shù)(i=1,2,3,4,5,6),這樣我們建立如下的數(shù)學模型。 ??????????????????????????????0,,302050607060..m i n654321655443322116654321xxxxxxxxxxxxxxxxxxtsxxxxxxZ例題分析 4：合理下料問題 ? 例 4 假定現(xiàn)有一批某種型號的圓鋼長 8米，需要裁取長 米的毛坯 100根、長 200根，問應該怎樣選擇下料方式才能既滿足需要，又使總的用料最??？ ? 解：各種可能的裁剪方案如下表所示： 型號 方案 1 方案 2 方案 3 方案 4 需要根數(shù) 3 2 1 0 0 2 4 6 100 200 余料 (米 ) — 例題分析 4：合理下料問題 ?設 x1,x2,x3,x4 分別為上面 4種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。 ????????????????0,20224210023..m i n43214323214321xxxxxxxxxxtsxxxxZ例題分析 5：投資問題 例 5 某部門現(xiàn)有資金 200萬元，今后五年內(nèi)考慮給以下的項目投資。已知： 項目 A：從第一年到第五年每年年初都可投資，當年末能收回本利 110%； 項目 B：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規(guī)定每年最大投資額不能超過 30萬元； 項目 C：需在第三年年初投資，第五年末能收回本利 140%，但規(guī)定最大投資額不能超過 80萬元； 項目 D：需在第二年年初投資，第五年末能收回本利 155%，但規(guī)定最大投資額不能超過 100萬元。 問應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？ 例題分析 4：投資問題 ?解： 設 xij ( i = 1～ 5， j = 1～ 4)表示第 i 年初投資于 A(j=1)、 B(j=2)、 C(j=3)、 D(j=4)項目的金額。這樣我們建立如下的決策變量： ? 1 2 3 4 5 ? A x11 x21 x31 x41 x51 ? B x12 x22 x32 x42 ? C x33 ? D x24 例題分析 5：投資問題 ????????????????????????????????????????)4,3,2,1。5,4,3,2,1(0100080)4,3,2,1(30200.. a x2433232415122314241122133323111242221121124334251jixxxixxxxxxxxxxxxxxxxxxxtsxxxxZiji投資問題（作業(yè)） 某部門現(xiàn)有資金 100萬元，今后五年內(nèi)考慮給以下的項目投資。已知： 項目 A：五年內(nèi)每年初均可投資，且金額不限，投資期限 1年，年回報率 7%； 項目 B： 五年內(nèi)每年初均可投資，且金額不限，投資期限 2年，年回報率 10% （不計復利）； 項目 C： 五年內(nèi)每年初均可投資，且金額不限，投資期限 3年，年回報率 12%（不計復利） ； 項目 D：只在第一年初有一次投資機會，最大投資額 50萬元， 投資期限 4年，年回報率 20% （不計復利） ； 項目 E：在第二年和第四年初有一次投資機會，最大投資額 30萬元，投資期限 1年，年回報率 30% ； 項目 F：在第四年初有一次投資機會，金額不限，投資期限 2年，年回報率25% ； 假設當年投資金額及其收益均可用于下一年投資， 問公司如何投資才能使得第五年末收回的本利金額最大？ 合理下料問題（作業(yè)） 新華造紙廠接到三份訂購卷紙的訂單，其長和寬的要求如下表所示： 該廠生產(chǎn) 1米和 2米兩種標準寬度的卷紙。假定卷紙的長度無限制，即可以連接起來達到所需的長度，問如何切割才能使切割損失的面積最小？ 訂單號碼 寬（米） 長（米） 1 1000 2 3000 3 2022 產(chǎn)品配套問題（作業(yè)） 假定一個工廠的甲、乙、丙三個車間生產(chǎn)同一產(chǎn)品，每件產(chǎn)品包含 4個 A零件和 3個 B零件。這兩種零件由兩種不同的原材料制成，而這兩種原材料的現(xiàn)有數(shù)額分別是 100千克和 200千克。第個生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示： 問：這三個車間各應開多少班次才能使這種產(chǎn)品的配套數(shù)達到最大？ 車間 第班進料數(shù)（千克） 每班產(chǎn)量（個數(shù)） 第一種原料 第二種原料 A零件 B零件 甲 8 6 7 5 乙 5 9 6 9 丙 3 8 8 4 計劃生產(chǎn)問題（作業(yè)） 某化工廠要用三種原料混合配置三種不同規(guī)格的產(chǎn)品，各產(chǎn)品的規(guī)格單價如下表所示： 問：如何安排生產(chǎn)利潤最大？ 產(chǎn)品 規(guī)格 單價（元 /公斤） 甲 原料 A不少于 50%，原料 B不超過 25% 50 乙 原料 A不少于 25%，原料 B不超過 50% 35 丙 不限 25 原料 日最大供應量（公斤） 單價（元 /公斤） A 100 65 B 100 25 C 60 35 基本概念： 凸集 —— 設 K是 n維歐氏空間的一個點集 ， 若任意兩點 X（ 1） ∈ K， X（ 2） ∈ K的連線上的一切點： αX（ 1） +（ 1α） X（ 2） ∈ K （ 0α1） ， 則稱 K為 凸集 。 五 、 線性規(guī)劃解的性質 凸組合 設 X（ 1） ,X（ 2） , … ,X（ k） 是 n維歐氏空間中的 K個點 ,若存在 k個數(shù) μ1, μ2 , … ,μk ,滿足0≤μi≤1, i=1,2, … ,k；且 ， 則稱 X=μ1X（ 1） +μ2X（ 2） +… +μkX(k)為 X（ 1） , ， X（ 2） ， … ， X（ k） 的 凸組合 。 頂點 設 K是凸集 ， X?K；若 X不能用 X（ 1） ? K， X（ 2） ? K 的線性組合表示 ， 即 X≠αX（ 1） +（ 1α） X（ 2） （ 0α1） 則稱 X為 K的一個 頂點 （也稱極點或角點） ???kii11?線性規(guī)劃問題解的性質定理 ： 定理 11 線性規(guī)劃問題的可行解集 （ 即可行域 ） 是凸集 。 ?????????? ??? ??nj jjj xbxPXD 1 0, 定理 12 線性規(guī)劃幾何理論基本定理 若 ， 則 X是 D的一個頂點的充分必要條件是 X為線性規(guī) 劃的基本可行解 。 ?????????? ??? ??nj jjjxbxPXD10, 定理 13 若可行域非空有界 ， 則線性規(guī)劃問題的目標函數(shù)一定可以在可行域的頂點上達到最優(yōu)值 。 定理 14 若目標函數(shù)在 k個點處達到最優(yōu)值（ k≥2） ,則在這些頂點的凸組合上也達到最優(yōu)值 。 上述 4個定理的一些有意義的啟示： ? LP的可行域一定是凸集 ， 但是凸集不一定成為 LP的可行域 ， 而非凸集一定不會是 LP的可行域 。 ?線性規(guī)劃的基本可行解和可行域的頂點是一一對應的 ? 在可行域中尋找 LP的最優(yōu)解可以轉化為只在可行域的頂點中找 ， 從而把一個無限的問題轉化為一個有限的問題 。 ? 若已知一個 LP有兩個或兩個以上最優(yōu)解 ， 那麼就一定有無窮多個最優(yōu)解 。 六、 LP問題的各種解 1. 可行解 ：滿足約束條件和非負條件的決策變量的一組取值 。 2. 可行解集 ：所有可行解的集合 。 3. 可行域 ： LP問題可行解集構成 n維空間的區(qū)域 ， 可以表示為： }0,|{ ??? XbAXXD :使目標函數(shù)達到最優(yōu)值的可行解 。 ：最優(yōu)解對應目標函數(shù)的取值 。 LP問題 :求出問題的最優(yōu)解和最優(yōu)值 。 ：設 A是約束方程組 m n的系數(shù)矩陣 ， A的秩 R(A)＝ m， B是 A中 m m階非奇異子式, 即 |B|≠0, 則稱 B是 LP問題的一個基 。 :B=[P1,P2,…,P m],稱 Pj(j=1,2, …,m)為基向量 , 與 Pj對應的變量 xj (j=1,2, …,m) 稱為基變量 , 其余的 xm+1 , …,x n為 非基變量 。 :令非基變量等于 0，從 AX＝ b中解出的基變量所得的解稱為 LP關于基 B的基本解。 可行解與基本解的區(qū)別？ 基本解 設 AX=b是含 n個決策變量、 m個約束條件的 LP的約束方程組，若 B是 LP問題的一個基，若令不與 B的列相應的 nm個分量（非基變量）都等于零，所得方程組的解 X=[x1,x2,…,x m,0, …,0] T稱為 方程組AX=b關于基 B的一個基本解 ， 簡稱 為 LP的基本解 。 （對應的基為可行基）：滿足非負條件的基本解。 非零分量個數(shù)小于 m（至少有一個基變量取值為 0）。 該基對應的基本可行解為 LP的最優(yōu)解。 n 基本解的個數(shù) ≤ Cm 基本可行解的非零分量均為正分量 個數(shù)不超過 m 結論 （對應的基為最優(yōu)基）：使目標函數(shù)達到最優(yōu)值的基本可行解。 最優(yōu)解 基本最優(yōu)解 1． 圖解法 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程 。 求解的思路是：先將約束條件加以圖解 ，求得滿足約束條件和非負條件的解的集合（ 即可行域 ） ， 然后結合目標函數(shù)的要求從可行域中找出最優(yōu)解 。 第二節(jié) 線性規(guī)劃問題的解法 實施圖解法，以求出 最優(yōu) 生產(chǎn)計劃（ 最優(yōu)解 ） , 給出 最優(yōu)值。 例： ??????????????0,12416482