線性規(guī)劃模型ppt課件.ppt

1 第1節(jié)線性規(guī)劃問題與模型 一 線性規(guī)劃模型從招聘總經(jīng)理談起 2 泰山工廠生產(chǎn)狀況 泰山工廠可以生產(chǎn)兩種產(chǎn)品出售 需要三種資源 已知各產(chǎn)品的利潤 各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表 目前生產(chǎn)現(xiàn)狀 不生產(chǎn)產(chǎn)品A 生產(chǎn)產(chǎn)品B每天30 獲利3600 3 招聘總經(jīng)理 約翰 我應(yīng)聘 在現(xiàn)有資源狀況下 我可以使利潤達到4280 方案是 生產(chǎn)A產(chǎn)品20 生產(chǎn)B產(chǎn)品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 4 怎么達到的 約翰使用了運籌學(xué)中的線性規(guī)劃模型問題 如何安排生產(chǎn)計劃 使得獲利最多 步驟 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 200原材料約束3X1 10X2 300非負性約束X1 0X2 0 5 線性規(guī)劃圖解法 由數(shù)學(xué)知識可知 y ax b是一條直線 同理 Z 70 x1 120 x2 x2 70 120 x1 Z 120也是一條直線 以Z為參數(shù)的一族等值線 9x1 4x2 360 x1 360 9 4 9x2是直線x1 360 9 4 9x2下方的半平面 所有半平面的交集稱之為可行域 可行域內(nèi)的任意一點 就是滿足所有約束條件的解 稱之為可行解 6 例1圖示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 7 最優(yōu)解 X1 20 x2 24對應(yīng)的生產(chǎn)方案 生產(chǎn)A產(chǎn)品20生產(chǎn)B產(chǎn)品24獲利 70 20 120 24 4280 8 約翰就任泰山工廠總經(jīng)理 9 二 線性規(guī)劃圖解法 例2 某工廠在計劃期內(nèi)要安排 兩種產(chǎn)品的生產(chǎn) 已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A B兩種原材料的消耗 資源的限制 如下表 問題 工廠應(yīng)分別生產(chǎn)多少單位 產(chǎn)品才能使工廠獲利最多 線性規(guī)劃模型 目標函數(shù) Maxz 50 x1 100 x2約束條件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 10 例1 目標函數(shù) Maxz 50 x1 100 x2約束條件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最優(yōu)解 x1 50 x2 250最優(yōu)目標值z 27500 圖解法 對于只有兩個決策變量的線性規(guī)劃問題 可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關(guān)概念 并求解 下面通過例1詳細講解其方法 11 線性規(guī)劃圖解法 續(xù) 1 分別取決策變量X1 X2為坐標向量建立直角坐標系 在直角坐標系里 圖上任意一點的坐標代表了決策變量的一組值 例1的每個約束條件都代表一個半平面 12 線性規(guī)劃圖解法 續(xù) 2 對每個不等式 約束條件 先取其等式在坐標系中作直線 然后確定不等式所決定的半平面 13 線性規(guī)劃圖解法 續(xù) 3 把五個圖合并成一個圖 取各約束條件的公共部分 如圖2 1所示 14 線性規(guī)劃圖解法 續(xù) 4 目標函數(shù)z 50 x1 100 x2 當z取某一固定值時得到一條直線 直線上的每一點都具有相同的目標函數(shù)值 稱之為 等值線 平行移動等值線 當移動到B點時 z在可行域內(nèi)實現(xiàn)了最大化 A B C D E是可行域的頂點 對有限個約束條件則其可行域的頂點也是有限的 15 線性規(guī)劃圖解法 續(xù) 重要結(jié)論 如果線性規(guī)劃有最優(yōu)解 則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解 無窮多個最優(yōu)解 若將例1中的目標函數(shù)變?yōu)閙axz 50 x1 50 x2 則線段BC上的所有點都代表了最優(yōu)解 無界解 即可行域的范圍延伸到無窮遠 目標函數(shù)值可以無窮大或無窮小 一般來說 這說明模型有錯 忽略了一些必要的約束條件 無可行解 若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1 3x2 1200 則可行域為空域 不存在滿足約束條件的解 當然也就不存在最優(yōu)解了 16 線性規(guī)劃圖解法 續(xù) 例2某公司由于生產(chǎn)需要 共需要A B兩種原料至少350噸 A B兩種材料有一定替代性 其中A原料至少購進125噸 但由于A B兩種原料的規(guī)格不同 各自所需的加工時間也是不同的 加工每噸A原料需要2個小時 加工每噸B原料需要1小時 而公司總共有600個加工小時 又知道每噸A原料的價格為2萬元 每噸B原料的價格為3萬元 試問在滿足生產(chǎn)需要的前提下 在公司加工能力的范圍內(nèi) 如何購買A B兩種原料 使得購進成本最低 17 線性規(guī)劃圖解法 續(xù) 解 目標函數(shù) Minf 2x1 3x2約束條件 s t x1 x2 350 x1 1252x1 x2 600 x1 x2 0采用圖解法 如下圖 得Q點坐標 250 100 為最優(yōu)解 18 三 線性規(guī)劃一般形式 企業(yè)管理的重點內(nèi)容之一就是在各種生產(chǎn)因素和產(chǎn)品的調(diào)配問題上 一方面 在一固定階段 企業(yè)管理者所能 投入 的生產(chǎn)因素 原料 人力 設(shè)備時間是由一定限量的 在一固定期間 任何一工廠的廠房 工場 機器 一切固定資本是不會變動的 再雄厚的資本 也還是有它的限度 再從流動資本來看 原料的來源和存量 各種技工的人數(shù)和時間 在一相當?shù)亩唐谥幸彩怯幸欢ǖ南薅?19 線性規(guī)劃一般形式 另一方面 企業(yè)管理者 投入 生產(chǎn)因素時 一定有一完整的目標 在商言商 企業(yè)管理者的目標當然是求最高的利潤和最低的成本 如何將受時間 空間 數(shù)量限制的 投入 生產(chǎn)因素調(diào)配 得當 達到最佳的境界而獲得最佳的 產(chǎn)出 量 因而獲得最大的收益 以上就是企業(yè)管理者須面對的一個問題的兩個方面 企業(yè)管理者不僅要知道如何調(diào)配手頭上有限的生產(chǎn)因素 同時要從不同的調(diào)配中 找出最佳的調(diào)配 來達到他的企業(yè)經(jīng)營目標 最低成本 最高利潤 20 線性規(guī)劃一般形式 事實上 用最低的代價去追求最高的收獲 原是一種理性的要求 因此在任何理性活動中 都有一求 最佳 問題的存在 21 例題3 配方問題 養(yǎng)海貍鼠飼料中營養(yǎng)要求 VA每天至少700克 VB每天至少30克 VC每天剛好200克 現(xiàn)有五種飼料 搭配使用 飼料成分如下表 22 例題3建模 設(shè)抓取飼料Ix1kg 飼料IIx2kg 飼料IIIx3kg 目標函數(shù) 最省錢minZ 2x1 7x2 4x3 9x4 5x5約束條件 3x2 2x2 x3 6x4 18x5 700營養(yǎng)要求 x1 0 5x2 0 2x3 2x4 0 5x5 300 5x1 x2 0 2x3 2x4 0 8x5 200用量要求 x1 50 x2 60 x3 50 x4 70 x5 40非負性要求 x1 0 x2 0 x3 0 x4 0 x5 0 23 例題4 人員安排問題 醫(yī)院護士24小時值班 每次值班8小時 不同時段需要的護士人數(shù)不等 據(jù)統(tǒng)計 24 例題4建模 目標函數(shù) minZ x1 x2 x3 x4 x5 x6約束條件 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30非負性約束 xj 0 j 1 2 6 25 歸納 線性規(guī)劃的一般模式 目標函數(shù) max min Z c1x1 c2x2 c3x3 cnxn約束條件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非負性約束 x1 0 x2 0 xn 0 26 四 線性規(guī)劃的標準型 一般形式目標函數(shù) Max Min z c1x1 c2x2 cnxn約束條件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0標準形式目標函數(shù) Maxz c1x1 c2x2 cnxn約束條件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0 27 線性規(guī)劃的標準型 可以看出 線性規(guī)劃的標準形式有如下四個特點 目標最大化 約束為等式 決策變量均非負 右端項非負 對于各種非標準形式的線性規(guī)劃問題 我們總可以通過以下變換 將其轉(zhuǎn)化為標準形式 28 線性規(guī)劃的標準型 1 極小化目標函數(shù)的問題 設(shè)目標函數(shù)為Minf c1x1 c2x2 cnxn 可以 令z f 則該極小化問題與下面的極大化問題有相同的最優(yōu)解 即Maxz c1x1 c2x2 cnxn但必須注意 盡管以上兩個問題的最優(yōu)解相同 但它們最優(yōu)解的目標函數(shù)值卻相差一個符號 即Minf Maxz 29 線性規(guī)劃的標準型 2 約束條件不是等式的問題 設(shè)約束條件為ai1x1 ai2x2 ainxn bi可以引進一個新的變量s 使它等于約束右邊與左邊之差s bi ai1x1 ai2x2 ainxn 顯然 s也具有非負約束 即s 0 這時新的約束條件成為ai1x1 ai2x2 ainxn s bi 30 線性規(guī)劃的標準型 當約束條件為ai1x1 ai2x2 ainxn bi時 類似地令s ai1x1 ai2x2 ainxn bi顯然 s也具有非負約束 即s 0 這時新的約束條件成為ai1x1 ai2x2 ainxn s bi 31 線性規(guī)劃的標準型 為了使約束由不等式成為等式而引進的變量s 當不等式為 小于等于 時稱為 松弛變量 當不等式為 大于等于 時稱為 剩余變量 如果原問題中有若干個非等式約束 則將其轉(zhuǎn)化為標準形式時 必須對各個約束引進不同的松弛變量 3 右端項有負值的問題 在標準形式中 要求右端項必須每一個分量非負 當某一個右端項系數(shù)為負時 如bi 0 則把該等式約束兩端同時乘以 1 得到 ai1x1 ai2x2 ainxn bi 32 線性規(guī)劃的標準型 例 將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0解 首先 將目標函數(shù)轉(zhuǎn)換成極大化 令z f 2x1 3x2 4x3其次考慮約束 有2個不等式約束 引進松弛變量x4 x5 0 第三個約束條件的右端值為負 在等式兩邊同時乘 1 33 線性規(guī)劃的標準型 通過以上變換 可以得到以下標準形式的線性規(guī)劃問題 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 變量無符號限制的問題 在標準形式中 必須每一個變量均有非負約束 當某一個變量xj沒有非負約束時 可以令xj xj xj 其中xj 0 xj 0即用兩個非負變量之差來表示一個無符號限制的變量 當然xj的符號取決于xj 和xj 的大小 34 五 計算機求解算法 單純形算法基本思想 從可行域中的一個基本可行解出發(fā) 判斷它是否已是最優(yōu)解 若不是 尋找下一個基本可行解 并使目標函數(shù)得到改進 如此迭代下去 直到找出最優(yōu)解或判定問題無界為止 從另一個角度說 就是從可行域的某一個極點出發(fā) 迭代到另一個極點 并使目標函數(shù)的值有所改善 直到找出有無最優(yōu)解時為止 35 求解線型規(guī)劃的算法單純形算法且聽下回分解 36 37 第三章運籌學(xué)優(yōu)化模型 大連海事大學(xué)劉巍 38 第2節(jié)線性規(guī)劃求解 單純性算法求解線性規(guī)劃的最常用算法 39 單純形算法 基本思想 從可行域中的一個基本可行解出發(fā) 判斷它是否已是最優(yōu)解 若不是 尋找下一個基本可行解 并使目標函數(shù)得到改進 如此迭代下去 直到找出最優(yōu)解或判定問題無界為止 從另一個角度說 就是從可行域的某一個極點出發(fā) 迭代到另一個極點 并使目標函數(shù)的值有所改善 直到找出有無最優(yōu)解時為止 40 單純形法 引例 41 解 1 確定初始可行解 B P3P4P5 I 令X1 X2 0 X 1 0 0 30 60 24 TZ 1 0 42 2 判定解是否最優(yōu) Z 0 40X1 50X2當X1從0 或X2從0 Z從0 X 1 不是最優(yōu)解 43 3 由一個基可行解 另一個基可行解 50 40選X2從0 X1 0 X2 min 30 2 60 2 24 2 12X2進基變量 X5出基變量 44 B2 P3P4P2 45 1 2 代入 式 令X1 X5 0X 2 0 12 6 36 0 TZ 2 600 46 2 判斷 40 0 X 2 不是 3 選X1從0 X5 0 X1 min 6 1 36 3 1 6X1進基 X3出基 47 B3 P1P4P2 令X3 X5 0X 3 6 12 0 18 0 TZ 3 840 48 2 15 0 X 3 不是 3 選X5從0 X3 0 X5 min 18 2 12 1 2 9X5進基 X4出基 49 B4 P1P5P2 令X3 X4 0X 4 15 15 2 0 0 9 TZ 4 975 50 0 0 0 X2 X1 51 兩個重要公式 52 當LP的數(shù)學(xué)模型為一般型時 兩個重要公式形如 53 B P1P2 Pm I 54 當Xj 0 j m 1 n 時 55 1 5 2單純形法原理 56 此時 B P1P2 Pm 對應(yīng)的基本可行解為 57 定理1 對解X 1 若檢驗數(shù) j j m 1 n 全部 0 則X 1 為最優(yōu)解 定理2 對X 1 若有某個非基變量Xm k m k 0且相應(yīng)的Pm k a1m k amm k T 0 則原問題無有限最優(yōu)解 58 定理2證明 X 2 b1 a1m k bm amm k 0 0 T AX 2 bX 2 0 Z Z0 m k 當 時Z 59 初始基B1 P3P4 X 1 0 0 10 15 TZ 1 0 60 選中X1從0 X2 0 求X1 X1 Z 61 換基迭代公式 1 決定換入變量 2 決定換出變量 bi aim kXm k 0 i 1 2 m 62 則Xr為換出變量 63 定理3 經(jīng)單純形法得到的 64 若否 因為P1 Pm線性無關(guān) 65 X 2 是基本解 且是可行解 66 單純形法基本步驟 1 定初始基 初始基本可行解 3 若有 k 0 Pk全 0 停 沒有有限最優(yōu)解 否則轉(zhuǎn) 4 2 對應(yīng)于非基變量檢驗數(shù) j全 0 若是 停 得到最優(yōu)解 若否 轉(zhuǎn) 3 67 定Xr為換出變量 arm k為主元 由最小 比值法求 68 轉(zhuǎn) 2 5 以arm k為中心 換基迭代 69 證明可用歸納法 略 X在邊界上 X在內(nèi)部 0 1 70 證明 設(shè)X 1 X k 為可行域頂點 若X 不是頂點 但maxZ CX X 定理2 可行域有界 最優(yōu)值必可在頂點得到 iX i i 1 0 i 1 CX iCX i iCX m CX m 設(shè)CX m Max CX i 1 i k 71 Z 2 Z 1 Cm k Zm k m k 0 72 1 5 3單純形表 73 74 本問題的最優(yōu)解X 15 15 2 0 0 9 TZ 975 75 幾點說明 1 例maxZ X1 2X2 76 77 78 X 1 2 3 Z 1 8 X 2 4 2 Z 2 8 無窮多解 79 80 81 判定定理1 基本可行解X 當全部 j 0時 X為最優(yōu)解 判定定理2 對可行基B 當某 k 0 且Pk a1k amk T 0 則原問題無有限最優(yōu)解 82 83 84 退化解 X 0 3 2 0 1 2 0 T Zmax 18 85 P1P2P3 P4P2P3 P4P5P3 P6P5P3 P6P7P3 P1P7P3 P1P2P3 86 4 例 87 88 89 本問題無界 90 1 5 4初始基本可行解的求法 一 大M法 判定無解條件 當進行到最優(yōu)表時 仍有人工變量在基中 且 0 則說明原問題無可行解 91 例1 92 93 94 95 96 97 解題過程 98 兩階段法原理 1 輔助問題的基本可行解X 0 為最優(yōu)解 對應(yīng)最小值 0則X 0 的前n個分量是原問題的基本可行解 99 證明 100 2 原問題有可行解時 輔助問題最優(yōu)值 0 101 maxZ X1 2X2 X1 X2 2 X1 X2 1X2 3X1X2 0 例2 102 第 1 階段 103 104 105 例3 106 第 1 階段 107 108 109 第1階段最優(yōu)基B min 1 0 110 1 arj全 0 式多余方程 2 arj有 0元 設(shè)為ars 0 以ars為主元 換基迭代 最后得到 111 例4 求 112 一 二 113 CBXB000005 205 40X21011 4 2 31 20 1 21y200000 3 21 1 40X12101 20101 6 第一階段 三 40 30X1X2X3X4CBXB 800 100X21011 4 2 3 4X42101 20 第二階段 114 的特殊情況 第1階段結(jié)束時 有人工變量在基中取0 但Xi系數(shù)全為0 此方程為多余方程 115 例5 求 116 一 二 117 118 40 30X1X2X3X4CBXB 800000X21010 2 3 3X300010 4X121000 第二階段 的特殊情況 可將人工變量換出 119 單純形法小結(jié) 1 標準型中有單位基 120 建模有問題 5 退化解問題 121 122 第三章運籌學(xué)優(yōu)化模型 大連海事大學(xué)劉巍 123 第3節(jié)對偶線性規(guī)劃與影子價格 一 對偶問題再談?wù)衅缚偨?jīng)理 124 泰山工廠生產(chǎn)狀況 泰山工廠可以生產(chǎn)兩種產(chǎn)品出售 需要三種資源 已知各產(chǎn)品的利潤 各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表 目前生產(chǎn)現(xiàn)狀 不生產(chǎn)產(chǎn)品A 生產(chǎn)產(chǎn)品B每天30 獲利3600 125 招聘總經(jīng)理 約翰 我應(yīng)聘 在現(xiàn)有資源狀況下 我可以使利潤達到4280 方案是 生產(chǎn)A產(chǎn)品20 生產(chǎn)B產(chǎn)品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 126 怎么達到的 約翰使用了運籌學(xué)中的線性規(guī)劃模型問題 如何安排生產(chǎn)計劃 使得獲利最多 步驟 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 200原材料約束3X1 10X2 300非負性約束X1 0X2 0 127 例1圖示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 128 X1 20 x2 24對應(yīng)的生產(chǎn)方案 生產(chǎn)A產(chǎn)品20生產(chǎn)B產(chǎn)品24獲利 70 20 120 24 4280 129 問題的最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4280變量最優(yōu)解相差值 x1200 x2240約束松弛 剩余變量對偶價格 18402013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1276360無上限2150200226 9233227 586300400 130 再談?wù)衅缚偨?jīng)理 約翰作為總經(jīng)理將泰山工廠經(jīng)營的很好了 湯姆來競爭了 競爭口號 不裁員 不減薪 不加班 提高利潤5 131 可能嗎 目前約翰的經(jīng)營已經(jīng)是資源的最佳利用了 湯姆還有什么絕招增加利潤呢 132 這個問題涉及到 1 線性規(guī)劃的對偶問題 2 影子價格概念 133 原來問題的最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4280變量最優(yōu)解相差值 x1200 x2240約束松弛 剩余變量對偶價格 18402013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1276360無上限2150200226 9233227 586300400 134 對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一 每一個線性規(guī)劃 LP 必然有與之相伴而生的另一個線性規(guī)劃問題 即任何一個求maxZ的LP都有一個求minZ的LP 其中的一個問題叫 原問題 記為 P 另一個稱為 對偶問題 記為 D 例 資源的合理利用問題已知資料如表所示 問應(yīng)如何安排生產(chǎn)計劃使得既能充分利用現(xiàn)有資源有使總利潤最大 對偶問題的提出 135 下面從另一個角度來討論這個問題 假定 該廠的決策者不是考慮自己生產(chǎn)甲 乙兩種產(chǎn)品 而是將廠里的現(xiàn)有資源用于接受外來加工任務(wù) 只收取加工費 試問該決策者應(yīng)制定怎樣的收費標準 合理的 136 分析問題 1 每種資源收回的費用不能低于自己生產(chǎn)時的可獲利潤 2 定價又不能太高 要使對方能夠接受 137 一般而言 W越大越好 但因需雙方滿意 故 為最好 該問題的數(shù)學(xué)模型為 138 模型對比 139 對稱形式 互為對偶 LP Maxz cTx DP Minf bTys t Ax bs t ATy cx 0y 0 Max Min 一般形式 若一個問題的某約束為等式 那么對應(yīng)的對偶問題的相應(yīng)變量無非負限制 反之 若一個問題的某變量無非負限制 那么對應(yīng)的對偶問題的相應(yīng)約束為等式 對偶定義 140 對偶問題 令y1 y1 y1 141 解 142 3 原問題第k個約束為等式 對偶問題第k個變量是自由變量 原問題第k個變量是自由變量 則對偶問題第k個約束為等式約束 143 對偶關(guān)系對應(yīng)表 144 例2 寫對偶規(guī)劃 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 145 maxW 6y1 9y2 4y3 y1 2y2 y3 42y1 5y3 23y2 2y3 3y1 0 y2 0 y3自由 146 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 或?qū)⒃瓎栴}變形為 147 maxW 6y1 9y2 4y3 y1 2y2 y3 4 2y1 5y3 23y2 2y3 3y1 y2 0 y3自由 對偶規(guī)劃 148 產(chǎn)品A B產(chǎn)量X1 X2 Z為利潤 例1 149 X 8 24 TZ 184 150 151 y 2 9 13 9 Z 184 152 觀察結(jié)論 一對對偶問題都有最優(yōu)解 且目標函數(shù)值相等 最優(yōu)表中有兩個問題的最優(yōu)解 153 1 7 2對偶問題解的性質(zhì) 154 定理1 弱對偶定理 155 推論2 P 有可行解 但無有限最優(yōu)解 則 D 無可行解 推論1 P D 都有可行解 則必都有最優(yōu)解 156 157 158 159 定理4 松緊定理 互補松弛性 原問題 160 對偶問題 161 162 163 164 165 例 min 5y1 y2 166 P 最優(yōu)解 0 9 0 4 64 9 167 168 169 解 D 為 170 將y1 y2 代入 知 為嚴格不等式 x2 x3 x4 0 x 1 0 0 0 1 TZ 5 171 小結(jié) 原問題與對偶問題的關(guān)系 互為對偶最優(yōu)解的存在性相同 目標函數(shù)值相等 解互為影子價格 172 影子價格在管理決策中的作用 173 原來問題的最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4280變量最優(yōu)解相差值 x1200 x2240約束松弛 剩余變量對偶價格 18402013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1276360無上限2150200226 9233227 586300400 174 4 影子價格可以告訴決策者 用多大的代價增加資源才是合算的 如 第二種資源增加1單位能使收益增加13 6 如果增加這種資源的代價大于13 6就不劃算了 3 影子價格可以告訴決策者 增加哪一種資源對增加經(jīng)濟效益最有利 如 本例中三種資源的價格為0 13 6 5 2 說明首先應(yīng)增加第二種資源 因為相比之下 它能使收益增加得更多 175 5 影子價格可以告訴決策者應(yīng)如何考慮新產(chǎn)品的價格 如 企業(yè)要生產(chǎn)一種新產(chǎn)品時 如果每件新產(chǎn)品耗用的這三種資源數(shù)量是1 2 3單位 則新產(chǎn)品的定價一定要大于才能增加公司的收益 如售價低于42 8的話 生產(chǎn)是不劃算的 176 湯姆的決策 設(shè)備資源的影子價格為0 不需要添加 人力資源的影子價格為13 6 而在市場上人力資源的價格是5 因此 招聘人力26人 原材料的影子價格為5 2 可是市場上這種材料價格是5 9 買入不上算 不增加 177 新的線型規(guī)劃模型 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 226原材料約束3X1 10X2 300非負性約束X1 0X2 0 178 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4633 6變量最優(yōu)解相差值 x130 40 x220 880約束松弛 剩余變量對偶價格 12 8802013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1357 12360無上限2150226226 9233297 517300452 179 新的生產(chǎn)計劃 生產(chǎn)A產(chǎn)品30 4生產(chǎn)B產(chǎn)品20 88獲利4633 6相比約翰的經(jīng)營增加純利潤353 6 130 223 提高5 2 180 熱烈祝賀湯姆競聘泰山工廠總經(jīng)理成功 181 問題 可不可以再進一步增加人力資源 從而能否用這種方式使利潤進一步提高 182 將人力資源增加到250人 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 250原材料約束3X1 10X2 300非負性約束X1 0X2 0 183 計算結(jié)果 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4646 11變量最優(yōu)解相差值 x130 7690 x220 7690約束松弛 剩余變量對偶價格 104 359223 07703010 256目標函數(shù)系數(shù)范圍 變量下限當前值上限 x13670270 x231 111120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 11203604322226 923250無上限3120300362 069 184 效益分析 利潤4646 11增加4646 11 5 50 4391 11相比人力資源為226時的利潤4391 11 4633 6 142 49 185 注意 將人力資源增加到227人時 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 227原材料約束3X1 10X2 300非負性約束X1 0X2 0 186 人力資源為227時最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4646 11變量最優(yōu)解相差值 x130 7690 x220 7690約束松弛 剩余變量對偶價格 104 3592 07703010 256目標函數(shù)系數(shù)范圍 變量下限當前值上限 x13670270 x231 111120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1120360360 242226 923227無上限3120300300 207 187 原來是這樣啊 此時人力資源的影子價格為0 再增加也不會帶來新的利潤 188 新的問題 靈敏度分析且聽下回分解 189 190 第三章運籌學(xué)優(yōu)化模型 大連海事大學(xué)劉巍 191 第3節(jié)對偶線性規(guī)劃與影子價格 續(xù) 靈敏度分析湯姆總經(jīng)理的失誤 192 泰山工廠生產(chǎn)狀況 泰山工廠可以生產(chǎn)兩種產(chǎn)品出售 需要三種資源 已知各產(chǎn)品的利潤 各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表 目前生產(chǎn)現(xiàn)狀 不生產(chǎn)產(chǎn)品A 生產(chǎn)產(chǎn)品B每天30 獲利3600 193 招聘總經(jīng)理 約翰 我應(yīng)聘 在現(xiàn)有資源狀況下 我可以使利潤達到4280 方案是 生產(chǎn)A產(chǎn)品20 生產(chǎn)B產(chǎn)品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 194 怎么達到的 約翰使用了運籌學(xué)中的線性規(guī)劃模型問題 如何安排生產(chǎn)計劃 使得獲利最多 步驟 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 200原材料約束3X1 10X2 300非負性約束X1 0X2 0 195 最優(yōu)解 X1 20 x2 24對應(yīng)的生產(chǎn)方案 生產(chǎn)A產(chǎn)品20生產(chǎn)B產(chǎn)品24獲利 70 20 120 24 4280 196 再談?wù)衅缚偨?jīng)理 約翰作為總經(jīng)理將泰山工廠經(jīng)營的很好了 湯姆來競爭了 競爭口號 不裁員 不減薪 不加班 提高利潤5 197 原來問題的最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4280變量最優(yōu)解相差值 x1200 x2240約束松弛 剩余變量對偶價格 18402013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1276360無上限2150200226 9233227 586300400 198 湯姆的決策 設(shè)備資源的影子價格為0 不需要添加 人力資源的影子價格為13 6 而在市場上人力資源的價格是5 因此 招聘人力26人 原材料的影子價格為5 2 可是市場上這種材料價格是5 9 買入不上算 不增加 199 新的線型規(guī)劃模型 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 226原材料約束3X1 10X2 300非負性約束X1 0X2 0 200 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4633 6變量最優(yōu)解相差值 x130 40 x220 880約束松弛 剩余變量對偶價格 12 8802013 6305 2目標函數(shù)系數(shù)范圍 變量下限當前值上限 x1367096x287 5120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1357 12360無上限2150226226 9233297 517300452 201 新的生產(chǎn)計劃 生產(chǎn)A產(chǎn)品30 4生產(chǎn)B產(chǎn)品20 88獲利4633 6相比約翰的經(jīng)營增加純利潤353 6 130 223 提高5 2 202 熱烈祝賀湯姆競聘泰山工廠總經(jīng)理成功 203 湯姆總經(jīng)理的失誤 在成績面前和贊譽聲中湯姆總經(jīng)理頭腦有些發(fā)熱 湯姆決定 再進一步增加人力資源 將人力資源達到250人 204 將人力資源增加到250人 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 250原材料約束3X1 10X2 300非負性約束X1 0X2 0 205 計算結(jié)果 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4646 11變量最優(yōu)解相差值 x130 7690 x220 7690約束松弛 剩余變量對偶價格 104 359223 07703010 256目標函數(shù)系數(shù)范圍 變量下限當前值上限 x13670270 x231 111120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 11203604322226 923250無上限3120300362 069 206 效益分析 利潤4646 11增加4646 11 5 50 4391 11相比人力資源為226時的利潤4391 11 4633 6 142 49 207 注意 將人力資源增加到227人時 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標函數(shù) maxZ 70X1 120X23 確定約束條件 設(shè)備約束9X1 4X2 360人力約束4X1 5X2 227原材料約束3X1 10X2 300非負性約束X1 0X2 0 208 人力資源為227時最優(yōu)解 最優(yōu)解如下 目標函數(shù)最優(yōu)值為 4646 11變量最優(yōu)解相差值 x130 7690 x220 7690約束松弛 剩余變量對偶價格 104 3592 07703010 256目標函數(shù)系數(shù)范圍 變量下限當前值上限 x13670270 x231 111120233 333常數(shù)項數(shù)范圍 約束下限當前值上限 1120360360 242226 923227無上限3120300300 207 209 原來是這樣啊 此時人力資源的影子價格為0 再增加也不會帶來新的利潤 210 新的問題 靈敏度分析 211 戴維來競爭了 戴維 男 25歲 大連海事大學(xué)管理科學(xué)與工程碩士研究生畢業(yè) 在校學(xué)習(xí)期間認真刻苦 善于思考 從不缺課 注 約翰 湯姆都是戴維的同班同學(xué) 但是約翰在學(xué)習(xí) 運籌與優(yōu)化模型 課時因故缺課 沒聽到影子價格一節(jié)內(nèi)容 而湯姆雖然聽了影子價格一節(jié)內(nèi)容 但是也因故在講 靈敏度分析 一節(jié)內(nèi)容時缺課了 212 2 3靈敏度分析進一步理解最優(yōu)單純形表中各元素的含義考慮問題Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0引入m個松弛變量后 通過計算得到最優(yōu)單純形表 應(yīng) 1 1能夠找到最優(yōu)基B的逆矩陣B 以及BN 檢驗數(shù)等 靈敏度分析 213 靈敏度分析 續(xù) 在生產(chǎn)計劃問題的一般形式中 A代表企業(yè)的技術(shù)狀況 b代表企業(yè)的資源狀況 而C代表企業(yè)產(chǎn)品的市場狀況 在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計劃和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定 在實際生產(chǎn)過程中 上述三類因素均是在不斷變化的 如果按照初始的狀況制訂了最佳的生產(chǎn)計劃 而在計劃實施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變 則決策者所關(guān)心的是目前所執(zhí)行的計劃還是不是最優(yōu) 如果不是應(yīng)該如何修訂原來的最優(yōu)計劃 更進一步 為了防止在各類狀況發(fā)生時 來不及隨時對其變化作出反應(yīng) 即所謂 計劃不如變化快 企業(yè)應(yīng)當預(yù)先了解 當各項因素變化時 應(yīng)當作出什么樣的反應(yīng) 214 靈敏度分析 續(xù) 當系數(shù)A b C發(fā)生改變時 目前最優(yōu)基是否還最優(yōu) 為保持目前最優(yōu)基還是最優(yōu) 系數(shù)A b C的允許變化范圍是什么 假設(shè)每次只有一種系數(shù)變化 目標系數(shù)C變化基變量系數(shù)發(fā)生變化 非基變量系數(shù)發(fā)生變化 右端常數(shù)b變化 增加一個變量 增加一個約束 技術(shù)系數(shù)A發(fā)生變化 215 靈敏度分析 續(xù) 若B是最優(yōu)基 則最優(yōu)表形式如下 216 靈敏度分析 續(xù) 最優(yōu)單純形表 B 1 BT 1cB I O 217 價值系數(shù)C發(fā)生變化 m考慮檢驗數(shù) j cj criarijj 1 2 ni 11 若ck是非基變量的系數(shù) 設(shè)ck變化為ck ck k ck ck criarik k ck只要 k 0 即 ck k 則最優(yōu)解不變 否則 將最優(yōu)單純形表中的檢驗數(shù) k用 k 取代 繼續(xù)單純形法的表格計算 例 MaxZ 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 靈敏度分析 續(xù) 218 例 最優(yōu)單純形表從表中看到 3 C3 C3 C2 a13 C1 a23 可得到 C3 9 5時 原最優(yōu)解不變 靈敏度分析 續(xù) 219 2 若cs是基變量的系數(shù) 設(shè)cs變化為cs cs 那么 j cj criarij cs cs asj j csasj 對所有非基變量i s只要對所有非基變量 j 0 即 j csasj 則最優(yōu)解不變 否則 將最優(yōu)單純形表中的檢驗數(shù) j用 j 取代 繼續(xù)單純形法的表格計算 Max j asj asj 0 cs Min j asj asj 0 例 MaxZ 2x1 3x2 0 x3 0 x4 0 x5S t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 靈敏度分析 續(xù) 220 例 下表為最優(yōu)單純形表 考慮基變量系數(shù)c2發(fā)生變化從表中看到 j Cj C1 a1j C5 a5j C2 C2 a2j j 3 4可得到 3 C2 1時 原最優(yōu)解不變 靈敏度分析 續(xù) 221 右端項b發(fā)生變化設(shè)分量br變化為br br 根據(jù)第1章的討論 最優(yōu)解的基變量xB B 1b 那么只要保持B 1 b b 0 則最優(yōu)基不變 即基變量保持 只有值的變化 否則 需要利用對偶單純形法繼續(xù)計算 對于問題 LP Maxz cTxs t Ax bx 0最優(yōu)單純形表中含有B 1 aij i 1 m j n 1 n m那么 新的xi B 1b i brairi 1 m 由此可得 最優(yōu)基不變的條件是Max bi air air 0 br Min bi air air 0 靈敏度分析 續(xù) 222 例 上例最優(yōu)單純形表如下 00 250 這里B 1 20 51 各列分別對應(yīng)b1 b2 b3的單一 0 5 0 1250 變化 因此 設(shè)b1增加4 則x1 x5 x2分別變?yōu)?4 0 4 4 4 2 4 4 0 2 0 5 4 4用對偶單純形法進一步求解 可得 x 4 3 2 0 0 Tf 17 靈敏度分析 續(xù) 223 增加一個變量增加變量xn 1則有相應(yīng)的pn 1 cn 1 那么 計算出B 1pn 1 n 1 cn 1 criarin 1填入最優(yōu)單純形表 若 n 1 0則最優(yōu)解不變 否則 進一步用單純形法求解 例 前例增加x6 p6 2 6 3 T c6 5 計算得到 靈敏度分析 續(xù) 用單純形法進一步求解 可得 x 1 1 5 0 0 0 2 Tf 16 5 224 增加一個約束增加約束一個之后 應(yīng)把最優(yōu)解帶入新的約束 若滿足則最優(yōu)解不變 否則填入最優(yōu)單純形表作為新的一行 引入1個新的非負變量 原約束若是小于等于形式可引入非負松弛變量 否則引入非負人工變量 并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)? 進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?例 前例增加3x1 2x2 15 原最優(yōu)解不滿足這個約束 于是 靈敏度分析 續(xù) 225 A中元素發(fā)生變化 只討論N中某一列變化情況 與增加變量xn 1的情況類似 假設(shè)pj變化 那么 重新計算出B 1pj j cj criarij填入最優(yōu)單純形表 若 j 0則最優(yōu)解不變 否則 進一步用單純形法求解 靈敏度分析 續(xù) 可得最優(yōu)解 x 3 2 0 8 0 0 2 4 Tf 15 2 226 靈敏度分析 續(xù) 靈敏度分析小結(jié) 1Ci發(fā)生變化2Bj發(fā)生變化3增加一個變量4增加一個約束5A中元素發(fā)生變化 返回目錄 227 228 第三章運籌學(xué)優(yōu)化模型 大連海事大學(xué)劉巍 229 第4節(jié)線性規(guī)劃應(yīng)用 學(xué)以致用 培養(yǎng)學(xué)生 用數(shù)學(xué)的意識是本節(jié)的重要目的學(xué)習(xí)線性規(guī)劃的有關(guān)知識其最終目的就是運用它們?nèi)ソ鉀Q一些生產(chǎn) 生活中問題 230 線性規(guī)劃的應(yīng)用 1人力資源分配的問題2生產(chǎn)計劃的問題3套裁下料問題4配料問題5投資問題 231 人力資源分配的問題 例1 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班 并連續(xù)工作八小時 問該公交線路怎樣安排司機和乘務(wù)人員 既能滿足工作需要 又配備最少司機和乘務(wù)人員 232 人力資源分配的問題 解 設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員數(shù) 這樣我們建立如下的數(shù)學(xué)模型 目標函數(shù) Minx1 x2 x3 x4 x5 x6約束條件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 233 人力資源分配的問題 例2 一家中型的百貨商場 它對售貨員的需求經(jīng)過統(tǒng)計分析如下表所示 為了保證售貨人員充分休息 售貨人員每周工作5天 休息兩天 并要求休息的兩天是連續(xù)的 問應(yīng)該如何安排售貨人員的作息 既滿足工作需要 又使配備的售貨人員的人數(shù)最少 234 人力資源分配的問題 解 設(shè)xi i 1 2 7 表示星期一至日開始休息的人數(shù) 這樣我們建立如下的數(shù)學(xué)模型 目標函數(shù) Minx1 x2 x3 x4 x5 x6 x7約束條件 s t x1 x2 x3 x4 x5 28x2 x3 x4 x5 x6 15x3 x4 x5 x6 x7 24x4 x5 x6 x7 x1 25x5 x6 x7 x1 x2 19x6 x7 x1 x2 x3 31x7 x1 x2 x3 x4 28x1 x2 x3 x4 x5 x6 x7 0 235 2生產(chǎn)計劃的問題 例3 某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題 該公司生產(chǎn)甲 乙 丙三種產(chǎn)品 都需要經(jīng)過鑄造 機加工和裝配三個車間 甲 乙兩種產(chǎn)品的鑄件可以外包協(xié)作 亦可以自行生產(chǎn) 但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量 數(shù)據(jù)如表 問 公司為了獲得最大利潤 甲 乙 丙三種產(chǎn)品各生產(chǎn)多少件 甲 乙兩種產(chǎn)品的鑄造中 由本公司鑄造和由外包協(xié)作各應(yīng)多少件 236 生產(chǎn)計劃的問題 解 設(shè)x1 x2 x3分別為三道工序都由本公司加工的甲 乙 丙三種產(chǎn)品的件數(shù) x4 x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲 乙兩種產(chǎn)品的件數(shù) 求xi的利潤 利潤 售價 各成本之和產(chǎn)品甲全部自制的利潤 23 3 2 3 15產(chǎn)品甲鑄造外協(xié) 其余自制的利潤 23 5 2 3 13產(chǎn)品乙全部自制的利潤 18 5 1 2 10產(chǎn)品乙鑄造外協(xié) 其余自制的利潤 18 6 1 2 9產(chǎn)品丙的利潤 16 4 3 2 7可得到xi i 1 2 3 4 5 的利潤分別為15 10 7 13 9元 237 生產(chǎn)計劃的問題 通過以上分析 可建立如下的數(shù)學(xué)模型 目標函數(shù) Max15x1 10 x2 7x3 13x4 9x5約束條件 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 238 生產(chǎn)計劃的問題 例4 永久機械廠生產(chǎn) 三種產(chǎn)品 均要經(jīng)過A B兩道工序加工 設(shè)有兩種規(guī)格的設(shè)備A1 A2能完成A工序 有三種規(guī)格的設(shè)備B1 B2 B3能完成B工序 可在A B的任何規(guī)格的設(shè)備上加工 可在任意規(guī)格的A設(shè)備上加工 但對B工序 只能在B1設(shè)備上加工 只能在A2與B2設(shè)備上加工 數(shù)據(jù)如表 問 為使該廠獲得最大利潤 應(yīng)如何制定產(chǎn)品加工方案 239 生產(chǎn)計劃的問題 解 設(shè)xijk表示第i種產(chǎn)品 在第j種工序上的第k種設(shè)備上加工的數(shù)量 建立如下的數(shù)學(xué)模型 s t 5x111 10 x211 6000 設(shè)備A1 7x112 9x212 12x312 10000 設(shè)備A2 6x121 8x221 4000 設(shè)備B1 4x122 11x322 7000 設(shè)備B2 7x123 4000 設(shè)備B3 x111 x112 x121 x122 x123 0 產(chǎn)品在A B工序加工的數(shù)量相等 x211 x212 x221 0 產(chǎn)品在A B工序加工的數(shù)量相等 x312 x322 0 產(chǎn)品在A B工序加工的數(shù)量相等 xijk 0 i 1 2 3 j 1 2 k 1 2 3 240 生產(chǎn)計劃的問題 目標函數(shù)為計算利潤最大化 利潤的計算公式為 利潤 銷售單價 原料單價 產(chǎn)品件數(shù) 之和 每臺時的設(shè)備費用 設(shè)備實際使用的總臺時數(shù) 之和 這樣得到目標函數(shù) Max 1 25 0 25 x111 x112 2 0 35 x221 2 80 0 5 x312 300 6000 5x111 10 x211 321 10000 7x112 9x212 1