【正文】 xZ＝ 10x1＋ 18x2 （ 1） 5x1＋ 2x2 ＋ x3＝ 170 2x1＋ 3x2＋ x4＝ 100 （ 2） x1＋ 5x2＋ x5＝ 150 xj≥0 （ j＝ 1， 2， 3， 4， 5） σ2＝ 18－ －（ 0 0＋ 0 0－ 18 1）＝ 0 10＝ 100－（ 30 3） 7/5＝ 2－（ 1/5 3） x3 x4 0 0 x2 100/2 C j→ 10 18 0 0 0C B X B b x 1 x 2 x 3 x 4 x 5θ170 5 2 1 0 0100 2 3 0 1 0150 1 5 0 0 1x3 x5 x4 0 0 0 σ 10 18 0 0 0 170/2 150/3 1 0 0 18 1/5 0 0 1/5 30 10 7/5 0 1 110 23/5 1 － 3/5 0 － 2/5 σ 32/5 0 0 0 － 18/5 550/23 50/7 150 x3 x1 x2 0 10 18 1 50/7 0 0 5/7 － 3/7 540/7 0 0 1 － 23/7 11/7 200/7 0 1 0 － 1/7 2/7 X*=(50/7, 200/7, 540/7, 0, 0)T Z*=4100/7 σ 0 0 0 － 32/7 － 6/7 例 某房地產(chǎn)公司欲開發(fā)一七通一平空地 ， 總面積 2500m2。 ?線性規(guī)劃問題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一個(gè)頂點(diǎn) (極點(diǎn) )。 解 : (1)首先將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型 引入松弛變量 x3和 x4 ????????????????0,2402615053.243214321432121xxxxxxxxxxxxtsxxZM a x(2) 求基本解 由上式得 ?????????10260153A ?????????2415b可能的基陣 ?????????10260153A?????????265312B ?????????061313B ?????????160314B?????????021523B ?????????120524B ?????????100134B? ? 612121234!24!2!424 ??????????C 由于所有 |B|≠ 0，所以有 6個(gè)基陣和6個(gè)基本解。 基本解的數(shù)目不超過 個(gè)。 定義 在基本解中，若該基本解滿足非負(fù)約束，即 ，則稱此基本解為 基本可行解 ，簡(jiǎn)稱 基可行解 ；對(duì)應(yīng)的基 B稱為 可行基 。 X1 =159? X2 =+? (0? ? ? 1) 例 Max Z=2X1+ 4X2 2X1+X2 ?8 2X1+X2 ? 2 X1 , X2 ?0 Z=0 8 2 4 6 X2 4 0 X1 2X1+X2 ? 2 2X1+X2 ?8 X1 ?0 X2?0 可行域 無界 無有限最優(yōu)解 無有限最優(yōu)解 可行域 無上界 例 Max Z=3X1+2X2 X1 X2 ?1 X1 , X2 ?0 無可行域 無可行解 1 X2 1 X1 0 X2 ?0 X1 ?0 X1 X2 ?1 直觀結(jié)論 ? 線性規(guī)劃問題的解有四種情況 ? 唯一最優(yōu)解 ? 無窮多最優(yōu)解 ? 無有限最優(yōu)解 ? 無可行解 ? 若線性規(guī)劃問題有解，則可行域是一個(gè)凸多邊形（或凸多面體）； ? 若線性規(guī)劃問題有最優(yōu)解，則 ? 唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)； ? 無窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊； 3 單純形法 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 線性規(guī)劃問題的基本解 單純形法的基本思想 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 ? ?? ?? ?? ?????????????????????????????????0,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZM i nM ax??????目標(biāo)函數(shù) 約束條件 (1) 線性規(guī)劃模型一般形式 價(jià)值系數(shù) 決策變量 技術(shù)系數(shù) 右端常數(shù) ? ????????????????????????????0,b,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZM axm21nmnmnmmnnnnnn???????0,.21221122222121112121112211(2) 線性規(guī)劃模型標(biāo)準(zhǔn)形式 ??????0.XbAXtsCXZM ax? ?ncccC ?21????????????????mnmmnnaaaaaaaaaA???????212222111211???????????????nxxxX?21價(jià)值向量 決策向量 系數(shù)矩陣 ???????????????mbbbb?21右端向量 (3) 線性規(guī)劃模型矩陣形式 對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式 : (4) 一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化 ?目標(biāo)函數(shù) ?目標(biāo)函數(shù)為極小化 ?約束條件 ?分兩種情況：大于、小于 ?決策變量 ?可能存在小于零的情況 線性規(guī)劃問題的基本解 ? ?? ?? ?????????302.1XbAXtsCXZM a x(1) 解的基本概念 定義 在線性規(guī)劃問題中，約束方程組 (2)的系數(shù)矩陣 A(假定 )的任意一個(gè) 階的非奇異 (可逆 )的子方陣 B(即 )，稱為線性規(guī)劃問題的一個(gè) 基陣 或 基 。 (2)、求最優(yōu)解 0 20 30 10 10 20 30 D A B C 最優(yōu)解 Z=1200 最優(yōu)解： BC線段 最優(yōu)解： BC線段 B點(diǎn)： X(1)=(6,12) C點(diǎn)： X(2)=(15,) X=?X(1)+(1?)X(2) (0 ? ? ? 1) Max Z=1200 X1 6 15 X2 12 X= = ? +(1? ) X1 =6? +(1 ? ) 定義 2：滿足 (1)的可行解稱為線性規(guī)劃問題的 最優(yōu)解 。 ? 約束條件：可用線性等式或不等式表示 . 具備以上三個(gè)要素的問題就稱為 線性規(guī)劃問題 。 例、合理下料問題 設(shè)按第 i種方案下料的原材料為 xi根 ????????????????????????????????????????8,7,6,5,4,3,2,1100432030100002302010000002..87654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZM i ni為大于零的整數(shù)，組合方案 1 2 3 4 5 6 7 8 2 1 1 1 0 0 0 0 0 2 1 0 3 2 1 0 1 0 1 3 0 2 3 4 合 計(jì) 料 長(zhǎng) 料 頭 例、運(yùn)輸問題 工 廠 1 2 3 庫(kù)存 倉(cāng) 1 2 1 3 50 2 2 2 4 30 庫(kù) 3 3 4 2 10 需求 40 15 35 運(yùn)輸 單價(jià) 求： 運(yùn)輸費(fèi)用最小的運(yùn)輸方案 。根據(jù)題意 max Z＝ 36x1＋ 20x2 5 x1＋ x2≤28 3 x1＋ 2x2≤28 2 x1＋ x2≤12 x1＋ 2x2≤10 x1 、 x2 ≥0 鋼筋架子 100個(gè)，每個(gè)需用 各 1，原料長(zhǎng) 求：如何下料，使得殘余料頭最少。線性規(guī)劃及其對(duì)偶問題 1 線性規(guī)劃問題及其數(shù)學(xué)模型 2 線性規(guī)劃問題的圖解法 3 單純形法 4 對(duì)偶問題 5 EXCEL求解線性規(guī)劃 6 靈敏度分析 1 線性規(guī)劃問題及其數(shù)學(xué)模型 (1) 線性規(guī)劃問題 例、生產(chǎn)組織與計(jì)劃問題 A, B 各生產(chǎn)多少 , 可獲最大利潤(rùn) ? 可用資源 煤 勞動(dòng)力 倉(cāng)庫(kù) A B 1 2 3 2 0 2 單位利潤(rùn) 40 50 30 60 24 解 : 設(shè)產(chǎn)品 A, B產(chǎn)量分別為變量 x1， x2 可以建立如下的數(shù)學(xué)模型： Max Z= 40x1 +50x2 x1 + 2x2 ? 30 3x1 + 2x2 ? 60 2x2 ? 24 x1， x2 ? 0 目標(biāo)函數(shù) 約束條件 可用資源 煤 勞動(dòng)力 倉(cāng)庫(kù) A B 1 2 3 2 0 2 單位利潤(rùn) 40 50 30 60 24 例 某建筑設(shè)計(jì)院設(shè)計(jì)每萬(wàn)ｍ２辦公建筑和工業(yè)廠房需要的建筑師、結(jié)構(gòu)工程師、設(shè)備工程師和電氣工程師的平均人數(shù)列在表。問該院應(yīng)如何安排設(shè)計(jì)任務(wù)，才能使設(shè)計(jì)費(fèi)收入最大 ? 專業(yè) 建筑物 建筑 結(jié)構(gòu) 設(shè)備 電器 設(shè)計(jì)費(fèi)收入（萬(wàn)元 /萬(wàn) ｍ２ ） 辦公建筑 5 3 2 1 36 工業(yè)廠房 1 2 1 2 20 全院現(xiàn)有專業(yè)人數(shù) 28 26 12 10 解 設(shè)辦公建筑和工業(yè)廠房各承攬ｘ １ 、ｘ ２ 萬(wàn)ｍ２。 解：首先列出各種可能的下料方案； 計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度； 確定