管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法課件

1、管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法主講教師:馬越峰管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法第二章 線性規(guī)劃與單純形法n2.1線性規(guī)劃問(wèn)題與數(shù)學(xué)模型n2.2圖解法n2.3線性規(guī)劃的應(yīng)用n2.4單純形法基本原理及計(jì)算步驟n2.5單純形法的進(jìn)一步討論n2.6線性規(guī)劃的對(duì)偶問(wèn)題管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2.1 線形規(guī)劃線形規(guī)劃(Linear Programming)問(wèn)題及問(wèn)題及其數(shù)學(xué)模型其數(shù)學(xué)模型【引例引例】某工廠在計(jì)劃期內(nèi)要安排甲乙兩種產(chǎn)品的生某工廠在計(jì)劃期內(nèi)要安排甲乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)

2、時(shí)及A A、B B兩種兩種原材料的消耗，以及資源的限制如下表所示：原材料的消耗，以及資源的限制如下表所示：甲甲乙乙資源限制資源限制設(shè)備設(shè)備1 11 1300300臺(tái)時(shí)臺(tái)時(shí)原料原料A A2 21 1400400千克千克原料原料B B0 01 1250250千克千克單件利潤(rùn)單件利潤(rùn)5050（元（元/ /件）件）100100（元（元/ /件）件）問(wèn)問(wèn):工廠應(yīng)分別生產(chǎn)多少個(gè)產(chǎn)品甲、乙才能使工廠獲利最多？工廠應(yīng)分別生產(chǎn)多少個(gè)產(chǎn)品甲、乙才能使工廠獲利最多？管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)生產(chǎn)甲產(chǎn)品x1個(gè)，生產(chǎn)乙產(chǎn)品x2個(gè)目標(biāo)函數(shù)目標(biāo)函數(shù) max Z= 50 x1+100 x2 約束條件x1+x2 30

3、0 2x1+x2 400 x2 250 x10,x2 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 線性規(guī)劃模型線性規(guī)劃模型n1.適用條件：適用條件：n（1）優(yōu)化條件）優(yōu)化條件:問(wèn)題目標(biāo)最大化、最小化的要求；問(wèn)題目標(biāo)最大化、最小化的要求；n（2）約束條件）約束條件:問(wèn)題目標(biāo)受一系列條件的限制；問(wèn)題目標(biāo)受一系列條件的限制；n（3）選擇條件）選擇條件:實(shí)現(xiàn)目標(biāo)存在多種備選方案；實(shí)現(xiàn)目標(biāo)存在多種備選方案；n（4）非負(fù)條件的選擇）非負(fù)條件的選擇:根據(jù)問(wèn)題的實(shí)際意義決定是否非負(fù)。根據(jù)問(wèn)題的實(shí)際意義決定是否非負(fù)。n2. 構(gòu)建線性規(guī)劃模型的步驟構(gòu)建線性規(guī)劃模型的步驟n（1）科學(xué)選擇決策變量）科學(xué)選擇決策變量n（2）

4、明確目標(biāo)要求）明確目標(biāo)要求n（3）根據(jù)實(shí)際問(wèn)題的背景材料，找出所有的約束條件）根據(jù)實(shí)際問(wèn)題的背景材料，找出所有的約束條件n（4）確定是否增加決策變量的非負(fù)條件）確定是否增加決策變量的非負(fù)條件 管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法線性規(guī)劃模型表示形式線性規(guī)劃模型表示形式1 122()nnMax Min Zc xc xc x11 11221121 1222221 12212(. .(,0nnnnmmmnnmna xa xa xba xa xa xbsta xa xa xbx xx 或 ，）或 ，）或 ，）(1,2, )jxjn決策變量；決策變量；(1,2, )jcjn目標(biāo)函數(shù)系數(shù)、價(jià)值系數(shù)或費(fèi)用系數(shù)

5、；目標(biāo)函數(shù)系數(shù)、價(jià)值系數(shù)或費(fèi)用系數(shù)；(1,2, )ib im右端項(xiàng)或資源常數(shù)；右端項(xiàng)或資源常數(shù)；(1,2, ;1,2, )ija im jn 稱為約束系數(shù)或技術(shù)系數(shù)。稱為約束系數(shù)或技術(shù)系數(shù)。（1）一般形式：）一般形式：管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法（2）集合形式：）集合形式：12nxxXx111212122212nnmmmnaaaaaaAaaa1()njjjMax Min Zc x1(1,2,). .0(1,2, )nijjijja xb imstxjn 或，）1()njjjMax Min Zc x1(. .0(1,2, )njjjjp xbstxjn 或，）12mbbbb12,(1,2,

6、 )jjjmjaapjna（3）向量形式：）向量形式：()Max Min ZCX(. .0AXbstX 或，）（4）矩陣形式：）矩陣形式：12( ,)nCc cc管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法127065MaxZxx121212127321045200. .241800,0 xxxxstxxxx【例】【例】 將線性規(guī)劃模型一般表達(dá)式化為將線性規(guī)劃模型一般表達(dá)式化為矩陣形式。矩陣形式。111221223132734524aaAaaaa12( ,)TXx x12( ,)(70,65)Cc c123210200180bbbb12(70,65)xMaxZx.0AXbstX解解:1273210452

7、0024180 xxMaxZCX設(shè)設(shè):管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法例例1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 275002圖圖 解解 法法 對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。 下面通過(guò)例1詳細(xì)講解其方法：管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法步驟： (1)分別取決策變量X1 , X2 為坐標(biāo)向量

8、建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X20X2=0 x2x1X10X1=0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。100100 x2250 x2=250200300200300

9、x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法（4）目標(biāo)函數(shù)z=50 x1+100 x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形

10、法解的幾種可能結(jié)果解的幾種可能結(jié)果唯一最優(yōu)解解唯一最優(yōu)解解無(wú)窮多個(gè)最優(yōu)解無(wú)窮多個(gè)最優(yōu)解無(wú)界解無(wú)界解( (可行域無(wú)界，常為模型遺漏了某些可行域無(wú)界，常為模型遺漏了某些必要的約束條件必要的約束條件) ) 無(wú)可行解（可行域?yàn)榭占?，約束條件自相矛無(wú)可行解（可行域?yàn)榭占?，約束條件自相矛盾盾, ,資源滿足不了人們的需求）資源滿足不了人們的需求）可行解：滿足可行解：滿足LP問(wèn)題所有約束條件的解問(wèn)題所有約束條件的解最優(yōu)解：滿足目標(biāo)要求的可行解最優(yōu)解：滿足目標(biāo)要求的可行解管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法四種結(jié)局四種結(jié)局:x1x2唯一最優(yōu)解x2x1無(wú)窮多最優(yōu)解x1x2無(wú)界解x2x1無(wú)可行解管理運(yùn)籌學(xué)第2章線性規(guī)

11、劃與單純形法無(wú)界解ox ,xxxxxxxzmax2121121242管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 無(wú)可行解：可行域?yàn)榭占?5121x.x增加的約束條件管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式1 122nnMaxZc xc xc x11 11221121 1222221 12212. .,0nnnnmmmnnmna xa xa xba xa xa xbsta xa xa xbx xx線性規(guī)劃標(biāo)準(zhǔn)模型的一般表達(dá)式線性規(guī)劃標(biāo)準(zhǔn)模型的一般表達(dá)式： 非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化方法非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)化方法： 1.目標(biāo)函數(shù)目標(biāo)函數(shù)1njjjMinZc xZZ 令 11()nnjjjjjjM

12、axZc xc x 2.約束條件為不等式約束條件為不等式:1 122iiinnia xa xa xb引進(jìn)松馳變量引進(jìn)松馳變量xs:1 122iiinnsia xa xa xxb1 122iiinnia xa xa xb引進(jìn)剩余變量引進(jìn)剩余變量xs:1 122iiinnsia xa xa xxb4.決策變量為自由變量決策變量為自由變量:jxuv令0,0uv 5.約束右端項(xiàng)為負(fù)約束右端項(xiàng)為負(fù):1 122iiinnia xa xa xb兩端乘兩端乘-1:03.約束條件為不等式約束條件為不等式:管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法n引入松馳變量（含義是資源的剩余量） 【引例】中引入 s1， s2， s3

13、 模型化為 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 約束條件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 對(duì)于最優(yōu)解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 說(shuō)明：生產(chǎn)50單位產(chǎn)品和250單位產(chǎn)品將消耗完所有可能的設(shè)備臺(tái)時(shí)數(shù)及原料B，但對(duì)原料A則還剩余50千克。管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 12335MinZxxx121231231239234. .3260,0,xxxx

14、xstxxxxxx 無(wú)約束【例】將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)式【例】將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)式解解:13(1)0,xx1132313,0 xy xyyyy 令無(wú)約束無(wú)約束122335MinZyxyy 121223122392334. .326,0ijyxyxyystyxyyx y 1223(2)()35MinZMaxZyxyy 1223(3)326yxyy 1223326yxyy(4)在第一、第三約束左端加上松弛變量在第一、第三約束左端加上松弛變量x4,x60 ，在第二約束左端減去剩余變量，在第二約束左端減去剩余變量x50 1223()35MaxZyxyy124122351223612234569

15、2334. .326,0yxxyxyyxstyxyyxy xyy x x x管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法習(xí)題習(xí)題n1.用圖解法求解下列LP問(wèn)題（1）minZ= 6x1+4x2 (2)maxZ= 3x1-2x2 2x1+x2 1 x1+x2 1 3x1+4x2 3 2x1+2x2 4 x1，x2 0 x1，x2 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2 、對(duì)下面LP問(wèn)題(1)用圖解法求解(2)寫出此問(wèn)題的標(biāo)準(zhǔn)形式(3)求剩余變量的值 minZ=11x1+8x2 s.t. 10 x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x2 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法圖解

16、法的靈敏度分析圖解法的靈敏度分析n1、目標(biāo)函數(shù)中的系數(shù)Ci的靈敏度分析分析Ci在什么范圍內(nèi)變化，原最優(yōu)解不變?cè)顑?yōu)解不變 C1=50 C2=100管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法EADCBF管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 直線BC 的斜截式為：x x2 2= -x= -x1 1 +300 +300 斜率為-1 直線BF 的斜截式為：x2= 0 x1 +250 斜率為0 目標(biāo)函數(shù)Z=c1x1+c2x2的斜截式為： x = -c1/c2x1 +z/c2 斜率為-c1/c2 所以,當(dāng)-1 -c /c0時(shí)，頂點(diǎn)B仍然是最優(yōu)解 假設(shè)c2 不變,則有-1 -c1/100 0，解之得0 c1100，管

17、理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法練習(xí)：計(jì)算計(jì)算C 在什么范圍內(nèi)變化時(shí)頂在什么范圍內(nèi)變化時(shí)頂 點(diǎn)點(diǎn)B 仍然是最優(yōu)解仍然是最優(yōu)解管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2、約束條件右邊約束條件右邊b系數(shù)的靈敏度分析系數(shù)的靈敏度分析 b b變化時(shí)通常引起可行域的變化從而引起最優(yōu)解的變化。變化時(shí)通常引起可行域的變化從而引起最優(yōu)解的變化。設(shè)例設(shè)例1 1中的設(shè)備臺(tái)時(shí)增加了中的設(shè)備臺(tái)時(shí)增加了1010個(gè)臺(tái)時(shí)數(shù)個(gè)臺(tái)時(shí)數(shù), ,則約束變?yōu)椋簞t約束變?yōu)椋簒 x1 1+x+x2 2310 310 代入求得新的最優(yōu)解為代入求得新的最優(yōu)解為x x1 1=60,x=60,x2 2=250 =250 Z=50 Z=5060+1006

18、0+100250=28000250=28000比原來(lái)最大的利潤(rùn)比原來(lái)最大的利潤(rùn)2750027500增加了增加了500500元元, ,可知每增加一個(gè)臺(tái)時(shí)可知每增加一個(gè)臺(tái)時(shí)的設(shè)備可多獲利潤(rùn)的設(shè)備可多獲利潤(rùn)500/10=50500/10=50元元 在約束條件右邊常量每增加一個(gè)單位而使最在約束條件右邊常量每增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)得到改進(jìn)的量稱為這個(gè)約束條件的優(yōu)目標(biāo)函數(shù)得到改進(jìn)的量稱為這個(gè)約束條件的對(duì)偶價(jià)格對(duì)偶價(jià)格管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 練習(xí)：練習(xí)：將原料將原料A A增加增加1010千克計(jì)算最優(yōu)解和最優(yōu)值千克計(jì)算最優(yōu)解和最優(yōu)值某一約束條件的對(duì)偶價(jià)格僅僅在某一某一約束條件的對(duì)偶價(jià)格僅僅在

19、某一范圍內(nèi)有效范圍內(nèi)有效總結(jié)當(dāng)約束條件右邊常數(shù)增加一個(gè)單位時(shí)：當(dāng)約束條件右邊常數(shù)增加一個(gè)單位時(shí)：(1)(1)如果對(duì)偶價(jià)格大于零如果對(duì)偶價(jià)格大于零, ,則最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)則最優(yōu)目標(biāo)函數(shù)值得到改進(jìn), ,即求最大值時(shí)變得更大即求最大值時(shí)變得更大; ;求最小值時(shí)變得更小求最小值時(shí)變得更小(2)(2)如果對(duì)偶價(jià)格小于零如果對(duì)偶價(jià)格小于零, ,則最優(yōu)目標(biāo)函數(shù)值變壞則最優(yōu)目標(biāo)函數(shù)值變壞, ,即即求最大值時(shí)變得小了求最大值時(shí)變得小了; ;求最小值時(shí)變得大了求最小值時(shí)變得大了(3)(3)如果對(duì)偶價(jià)格等于零如果對(duì)偶價(jià)格等于零, ,則最優(yōu)目標(biāo)函數(shù)值不變則最優(yōu)目標(biāo)函數(shù)值不變管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法練習(xí)

20、練習(xí):某公司目前正生產(chǎn)甲乙兩種產(chǎn)品公司目前正生產(chǎn)甲乙兩種產(chǎn)品,產(chǎn)量分別為產(chǎn)量分別為 30個(gè)和個(gè)和120個(gè)個(gè),公司經(jīng)理希望了解是否通過(guò)改變公司經(jīng)理希望了解是否通過(guò)改變 這兩種產(chǎn)品的數(shù)量而提高公司的利潤(rùn)這兩種產(chǎn)品的數(shù)量而提高公司的利潤(rùn).公司制造公司制造 每個(gè)產(chǎn)品所需的加工工時(shí)和各個(gè)車間的加工能每個(gè)產(chǎn)品所需的加工工時(shí)和各個(gè)車間的加工能 力如下表力如下表:車間車間產(chǎn)品甲產(chǎn)品甲產(chǎn)品乙產(chǎn)品乙車間能力車間能力(每天加工工時(shí)數(shù)每天加工工時(shí)數(shù))12030020354032244041.21.5300利潤(rùn)利潤(rùn)/每個(gè)產(chǎn)品每個(gè)產(chǎn)品(元元)500400管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法(1)假設(shè)生產(chǎn)的全部產(chǎn)品都能銷售出

21、去假設(shè)生產(chǎn)的全部產(chǎn)品都能銷售出去,用圖解法確定用圖解法確定 最優(yōu)產(chǎn)品組合最優(yōu)產(chǎn)品組合(2)在上面求得的最優(yōu)產(chǎn)品組合中在上面求得的最優(yōu)產(chǎn)品組合中,那些車間的能力還那些車間的能力還 有剩余有剩余,剩余多少剩余多少?是剩余變量還是松弛變量是剩余變量還是松弛變量?(3)各車間的能力分別增加一個(gè)加工工時(shí)數(shù)給公司帶各車間的能力分別增加一個(gè)加工工時(shí)數(shù)給公司帶 來(lái)多少額外的利潤(rùn)來(lái)多少額外的利潤(rùn).(4)當(dāng)產(chǎn)品甲的利潤(rùn)不變時(shí)當(dāng)產(chǎn)品甲的利潤(rùn)不變時(shí),產(chǎn)品乙的利潤(rùn)在什么范圍產(chǎn)品乙的利潤(rùn)在什么范圍 內(nèi)變化時(shí)此最優(yōu)解不變內(nèi)變化時(shí)此最優(yōu)解不變?當(dāng)產(chǎn)品乙的利潤(rùn)不變時(shí)當(dāng)產(chǎn)品乙的利潤(rùn)不變時(shí), 產(chǎn)品甲的利潤(rùn)在什么范圍內(nèi)變化時(shí)最優(yōu)解不

22、變產(chǎn)品甲的利潤(rùn)在什么范圍內(nèi)變化時(shí)最優(yōu)解不變.(5)當(dāng)產(chǎn)品甲的利潤(rùn)從當(dāng)產(chǎn)品甲的利潤(rùn)從500降為降為450元元,而產(chǎn)品乙的利潤(rùn)而產(chǎn)品乙的利潤(rùn) 從從400元增加為元增加為430元時(shí)元時(shí),原來(lái)產(chǎn)品組合是否依然是原來(lái)產(chǎn)品組合是否依然是 最優(yōu)產(chǎn)品組合最優(yōu)產(chǎn)品組合.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2.3 LP的應(yīng)用的應(yīng)用n一.人力資源分配問(wèn)題人力資源分配問(wèn)題n例例1.某晝夜服務(wù)的公交線路每天各時(shí)間段所需司某晝夜服務(wù)的公交線路每天各時(shí)間段所需司機(jī)和乘務(wù)人員數(shù)如下：機(jī)和乘務(wù)人

23、員數(shù)如下： 班次 時(shí)間 所需人數(shù) 1 6：00-10：0060 2 10：00 -14：0070 3 14：00 -18：0060 4 18：00 -22：0050 5 22：00-2：0020 6 2：00-6：0030管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)段一開(kāi)始時(shí)上班設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)段一開(kāi)始時(shí)上班,并連續(xù)工作并連續(xù)工作8小時(shí)小時(shí),問(wèn)該公交線路怎樣安排人員問(wèn)該公交線路怎樣安排人員,既能滿足工作需要又配備最少司機(jī)和乘務(wù)人員。既能滿足工作需要又配備最少司機(jī)和乘務(wù)人員。管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)xi表示第i班次開(kāi)始上班的人員s.t.minZ= X1 +

24、X2 + X3 + X4+X5 + X6 X1+X6 60 X1+X2 70 X2+X3 60 X3+X4 50 X4+X5 20 X5+X630 X1,X2,X3,X4,X5,X6 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法最優(yōu)解最優(yōu)解 ： x =50 x =20 x =50 x =0 x =20 x =10 最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值 Z=150管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法【練習(xí)練習(xí)】某中型百貨商場(chǎng)對(duì)售貨人員的需求統(tǒng)計(jì)如下表某中型百貨商場(chǎng)對(duì)售貨人員的需求統(tǒng)計(jì)如下表,并規(guī)定售貨員每周工作并規(guī)定售貨員每周工作5天且連續(xù)休息天且連續(xù)休息2天，問(wèn)如何安排天，問(wèn)如何安排 人員的作息既滿足工作需要又

25、使配備人員最少？人員的作息既滿足工作需要又使配備人員最少？ 時(shí)間所需售貨員人數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六28管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法解：設(shè)解：設(shè)x x1 1為星期一開(kāi)始休息的人數(shù)為星期一開(kāi)始休息的人數(shù), ,x x2 2為星期二開(kāi)為星期二開(kāi)始休息的人數(shù)始休息的人數(shù), , x x7 7為星期日開(kāi)始休息的人數(shù)為星期日開(kāi)始休息的人數(shù)目標(biāo)函數(shù)目標(biāo)函數(shù):minZ=x1+x2+x3+x4+x5+x6+x7x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7 + x125x5+x6+x7 + x

26、1+x219x6+x7 + x1+x2+x3 31 x7 +x1+x2+x3+x428 xi 0 管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法最優(yōu)解最優(yōu)解： x1 =12 x2 =0 x3 =11 x4 =5 x5 =0 x6 =8 x7 =0 目標(biāo)函數(shù)最小值為目標(biāo)函數(shù)最小值為：36管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法二二 生產(chǎn)計(jì)劃問(wèn)題生產(chǎn)計(jì)劃問(wèn)題例例2、某公司生產(chǎn)甲，乙，丙三種產(chǎn)品，這某公司生產(chǎn)甲，乙，丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過(guò)鑄造，機(jī)加工和裝配三個(gè)三種產(chǎn)品都要經(jīng)過(guò)鑄造，機(jī)加工和裝配三個(gè)車間。甲乙兩種產(chǎn)品的鑄件可以外包協(xié)作也車間。甲乙兩種產(chǎn)品的鑄件可以外包協(xié)作也可自行生產(chǎn)，但丙產(chǎn)品必須本廠鑄造才能保

27、可自行生產(chǎn)，但丙產(chǎn)品必須本廠鑄造才能保證質(zhì)量。有關(guān)情況見(jiàn)下表；公司中可利用的證質(zhì)量。有關(guān)情況見(jiàn)下表；公司中可利用的總工時(shí)為鑄造總工時(shí)為鑄造8000小時(shí)機(jī)加工小時(shí)機(jī)加工12000小時(shí)和小時(shí)和裝配裝配10000小時(shí)。公司為了獲得最大利潤(rùn)，小時(shí)。公司為了獲得最大利潤(rùn)，甲，乙，丙三種產(chǎn)品各生產(chǎn)多少件，甲乙兩甲，乙，丙三種產(chǎn)品各生產(chǎn)多少件，甲乙兩種產(chǎn)品的鑄造應(yīng)多少由本公司完成？多少由種產(chǎn)品的鑄造應(yīng)多少由本公司完成？多少由外包協(xié)作？外包協(xié)作？管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法工時(shí)與成本工時(shí)與成本甲甲乙乙丙丙每件鑄造工時(shí)每件鑄造工時(shí)510 7每件機(jī)加工工時(shí)每件機(jī)加工工時(shí)648每件裝配工時(shí)每件裝配工時(shí)322自

28、產(chǎn)鑄件每件成本自產(chǎn)鑄件每件成本354外協(xié)鑄件每件成本外協(xié)鑄件每件成本56機(jī)加工每件成本機(jī)加工每件成本213裝配每件成本裝配每件成本322每件產(chǎn)品售價(jià)每件產(chǎn)品售價(jià)231816管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法解：解：設(shè)設(shè)x1，x2，x3分別為三道工序都由本公司加工的分別為三道工序都由本公司加工的 甲，乙，丙三種產(chǎn)品的件數(shù)，設(shè)甲，乙，丙三種產(chǎn)品的件數(shù)，設(shè)x4，x5分別為由外分別為由外 協(xié)鑄造再由本公司機(jī)加工和裝配的甲乙兩種產(chǎn)品的協(xié)鑄造再由本公司機(jī)加工和裝配的甲乙兩種產(chǎn)品的 件數(shù)。件數(shù)。計(jì)算每件產(chǎn)品的利潤(rùn)分別如下：計(jì)算每件產(chǎn)品的利潤(rùn)分別如下：產(chǎn)品甲全部自制的利潤(rùn)產(chǎn)品甲全部自制的利潤(rùn) =23-（3+2

29、+3）=15產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)=23-（5+2+3）=13產(chǎn)品乙全部自制的利潤(rùn)產(chǎn)品乙全部自制的利潤(rùn) =18-（5+1+2）=10產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)=18-（6+1+2）=9產(chǎn)品丙的利潤(rùn)產(chǎn)品丙的利潤(rùn) =16-（4+3+2）=7管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法目標(biāo)函數(shù)目標(biāo)函數(shù)：max Z= 15X1 +10X2+ 7X3 +13 X4+9X5 5X1 + 10X2 + 7X3 80006 X1 + 4X2 + 8X3 +6 X4+4X5 12000 3X1 + 2X2 +2 X3 + 3X4+2X5 10000X

30、1 ,X2 , X3,X4,X5 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法三三 套裁下料問(wèn)題n例例3、某工廠要做、某工廠要做100套鋼架，每套用套鋼架，每套用29m、21m和和15m的原鋼各一根。已知原料每根的原鋼各一根。已知原料每根長(zhǎng)長(zhǎng)74m，問(wèn)應(yīng)如何下料，可使所用原料最省。，問(wèn)應(yīng)如何下料，可使所用原料最省。管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 下料 方案長(zhǎng)度291201021002211531203合計(jì)7473727166余料001020308管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)按各方案下料的原材料根數(shù)分別為設(shè)按各方案下料的原材料根數(shù)分別為X1 ， X2 ，X3 ， X4，X5 。 目標(biāo)函數(shù)：目

31、標(biāo)函數(shù)：min Z= X1 + X2 + X3 + X4+X5 約束條件：約束條件： X1 +2X2 + X4100 2 X3 + 2X4 +X5 100 3X1 + X2 + 2X3 +3X5 100 X1 ， X2 ，X3 ，X4，X5 0最優(yōu)解X1 =30 X2 =10 X3 =0 X4=50 X5 =0 Z=90管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法四四 、投資問(wèn)題、投資問(wèn)題例例4、某部門現(xiàn)有資金、某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮以下的萬(wàn)元，今后五年內(nèi)考慮以下的項(xiàng)目投資，已知項(xiàng)目項(xiàng)目投資，已知項(xiàng)目A：第一年到第五年年初都可投資，：第一年到第五年年初都可投資，當(dāng)年末能收回本利當(dāng)年末能

32、收回本利110%。已知項(xiàng)目。已知項(xiàng)目B：第一年到第四：第一年到第四年年初都可投資，次年末能收回本利年年初都可投資，次年末能收回本利125%，但規(guī)定每，但規(guī)定每年最大投資額不能超過(guò)年最大投資額不能超過(guò)30萬(wàn)元。項(xiàng)目萬(wàn)元。項(xiàng)目C：第三年初需要：第三年初需要投資，到第五年末能回收本利投資，到第五年末能回收本利140%，但規(guī)定最大投資，但規(guī)定最大投資額不超過(guò)額不超過(guò)80萬(wàn)元。項(xiàng)目萬(wàn)元。項(xiàng)目D：第二年初需要投資，到第五：第二年初需要投資，到第五年末能回收本利年末能回收本利155%，但規(guī)定最大投資額不超過(guò)，但規(guī)定最大投資額不超過(guò)100萬(wàn)萬(wàn)元。元。問(wèn)：應(yīng)如何確定這些項(xiàng)目的每年投資，使得第五年：應(yīng)如何確定這些

33、項(xiàng)目的每年投資，使得第五年末擁有資金的本利和金額最大？末擁有資金的本利和金額最大？管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法這是一個(gè)連續(xù)投資的問(wèn)題，設(shè)：這是一個(gè)連續(xù)投資的問(wèn)題，設(shè)：X i j=第第i年初投資年初投資j項(xiàng)項(xiàng)目的金額，見(jiàn)表：目的金額，見(jiàn)表： 年份年份項(xiàng)目項(xiàng)目12345AX 1AX 2AX 3AX 4AX 5ABX 1BX 2BX 3BX 4BCX 3CDX 2D管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法目標(biāo)函數(shù)：目標(biāo)函數(shù)： maxz=11X 5A125 X 4B 140X 3C155 X 2D X 1A X 1B=200， X 2A X 2B X 2D = 11X 1A ， X 3A X 3B X

34、 3C = 11 X 2A 125X 1B ， X 4A X 4B = 11 X 3A 125 X 2B ， X 5A = 11X 4A 125 X 3B ， X i B 30 （i= 1，2，3，4） ， X 3C 80 ， X 2D 100 ， X i j0 ，管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法五、配料問(wèn)題 例例5 5：某工廠要用三種原料1、2、3混合調(diào)配出三種 不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)： 該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？產(chǎn)品名稱規(guī)格要求單價(jià)（元/kg）甲原材料1不少于50%，原材料2不超過(guò)25%50乙原材料1不少于25%，原材料2不超過(guò)50%35丙不限25原材料名稱

35、每天最多供應(yīng)量單價(jià)（元/kg）11006521002536035 管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法解：設(shè) xij 表示第 i 種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮： 對(duì)于甲： x11，x12，x13； 對(duì)于乙： x21，x22，x23； 對(duì)于丙： x31，x32，x33； 對(duì)于原料1： x11，x21，x31； 對(duì)于原料2： x12，x22，x32； 對(duì)于原料3： x13，x23，x33； 目標(biāo)函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法n利潤(rùn)=總收入-總成本=甲乙丙三種

36、產(chǎn)品的銷售單價(jià)*產(chǎn)品數(shù)量-甲乙丙使用的原料單價(jià)*原料數(shù)量，故有目標(biāo)函數(shù)目標(biāo)函數(shù)Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）= -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 約束條件：約束條件： 從第1個(gè)表中有： x110.5(x11+x12+x13) x120.25(x11+x12+x13) x210.25(x21+x22+x23) x220.5(x21+x22+x23)管理運(yùn)籌學(xué)第2章線性規(guī)劃

37、與單純形法 從第2個(gè)表中，生產(chǎn)甲乙丙的原材料不能超過(guò)原材料的供應(yīng)限額，故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60 管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法習(xí)題習(xí)題1、某鍋爐制造廠要制造一種新鍋爐鍋爐制造廠要制造一種新鍋爐10臺(tái)，每臺(tái)鍋臺(tái)，每臺(tái)鍋爐需要不同長(zhǎng)度的鍋爐鋼管數(shù)量如下：爐需要不同長(zhǎng)度的鍋爐鋼管數(shù)量如下：規(guī)格（mm）2640165117701440需要數(shù)量（根）835421庫(kù)存的原材料的長(zhǎng)度只有庫(kù)存的原材料的長(zhǎng)度只有5500mm一種規(guī)格，問(wèn)一種規(guī)格，問(wèn)如何下料才能使總的用料根數(shù)最少？如何下料才能使總的用料根數(shù)最少？管理運(yùn)籌學(xué)第2章線

38、性規(guī)劃與單純形法2.、前進(jìn)電器廠生產(chǎn)前進(jìn)電器廠生產(chǎn)A，B，C三種產(chǎn)品有關(guān)資料如下表三種產(chǎn)品有關(guān)資料如下表：產(chǎn)品產(chǎn)品材料消耗材料消耗（千克（千克/件）件）臺(tái)時(shí)消耗臺(tái)時(shí)消耗（臺(tái)時(shí)（臺(tái)時(shí)/件）件）產(chǎn)品利潤(rùn)產(chǎn)品利潤(rùn)（元（元/件）件）市場(chǎng)容量市場(chǎng)容量（件）（件）A1.0210200B1.51.212250C4.0114100資源資源限制限制2000千克千克1000臺(tái)時(shí)臺(tái)時(shí)問(wèn)問(wèn):在資源及市場(chǎng)允許的條件下如何安排生產(chǎn)獲利最大在資源及市場(chǎng)允許的條件下如何安排生產(chǎn)獲利最大管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法3.某公司在今后四個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資某公司在今后四個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資已知各個(gè)月所需的倉(cāng)庫(kù)面積數(shù)字

39、如下表已知各個(gè)月所需的倉(cāng)庫(kù)面積數(shù)字如下表：月份月份1234所需倉(cāng)庫(kù)面積所需倉(cāng)庫(kù)面積(百平方米百平方米)15102012合同租借期限合同租借期限1個(gè)月個(gè)月 2個(gè)月個(gè)月 3個(gè)月個(gè)月 4個(gè)月個(gè)月合同期內(nèi)每百平方米合同期內(nèi)每百平方米倉(cāng)庫(kù)面積的租借費(fèi)用倉(cāng)庫(kù)面積的租借費(fèi)用2800450060007300表表2表表1管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法倉(cāng)庫(kù)的租借費(fèi)用倉(cāng)庫(kù)的租借費(fèi)用,當(dāng)租借合同期限越長(zhǎng)時(shí)當(dāng)租借合同期限越長(zhǎng)時(shí),享受享受的折扣優(yōu)惠也越大的折扣優(yōu)惠也越大,具體數(shù)字如表具體數(shù)字如表2,租借倉(cāng)庫(kù)的租借倉(cāng)庫(kù)的合同每月初都可辦理合同每月初都可辦理,每份合同具體規(guī)定租用每份合同具體規(guī)定租用面積數(shù)和期限面積數(shù)和期

40、限.因此該廠可根據(jù)需要在任何一因此該廠可根據(jù)需要在任何一個(gè)月初辦理租借合同個(gè)月初辦理租借合同,且每次辦理可簽一份也且每次辦理可簽一份也可同時(shí)簽若干份租用面積和租借期限不同的合可同時(shí)簽若干份租用面積和租借期限不同的合同同.求一個(gè)所付的租借費(fèi)為最小的租借方案求一個(gè)所付的租借費(fèi)為最小的租借方案.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)xij(i=1,2,3,4)(j=1, 4-i+1)為第i個(gè)月初簽定的租借期為j個(gè)月的合同的租界面積minZ=2800 x11+4500 x12+6000 x13+7300 x14+2800 x21+ 4500 x22+6000 x23+ 2800 x31+4500 x32

41、+2800 x41 x11+x12+x13+x1415s.t x12+x13+x14 +x21+x22+x2310 x13+x14 +x22+x23+x31+x32 20 x14+x23+x32+x4115 xij 0管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法4、某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1,A2將貨物運(yùn)往三個(gè)銷地將貨物運(yùn)往三個(gè)銷地B1,B2B3,各產(chǎn)地的產(chǎn)量及各銷地的銷量和各產(chǎn)地運(yùn)往各銷各產(chǎn)地的產(chǎn)量及各銷地的銷量和各產(chǎn)地運(yùn)往各銷地的每件物品的運(yùn)費(fèi)如下表地的每件物品的運(yùn)費(fèi)如下表,問(wèn)如何調(diào)運(yùn)使得總運(yùn)輸問(wèn)如何調(diào)運(yùn)使得總運(yùn)輸費(fèi)用最小費(fèi)用最小?運(yùn)費(fèi)運(yùn)費(fèi) 銷地銷地 單價(jià)單價(jià)產(chǎn)地產(chǎn)地B1B2B3產(chǎn)量產(chǎn)量(

42、件件)A1646200A2655300銷量銷量150150200管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法設(shè)設(shè)xij表示從產(chǎn)地表示從產(chǎn)地Ai調(diào)運(yùn)到調(diào)運(yùn)到Bj的運(yùn)輸量的運(yùn)輸量(i=1,2;j=1,2,3)min f=6x11+ 4x12+ 6x13+ 6x21+5x22+ 5x23 x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x21=150 x12+ x22=150 x13+ x23=200 xij0s.t.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 班次 時(shí)間 所需人數(shù) 1 6：00-10：0015 2 10：00 -14：0025 3 14：00 -18：0020 4

43、18：00 -22：0018 5 22：00-2：0012 6 2：00-6：00105、某醫(yī)院晝夜24h各時(shí)段內(nèi)需要的護(hù)士數(shù)量如下：若醫(yī)院可聘用合同工護(hù)士，上班時(shí)間同正式護(hù)士。護(hù)士于每班開(kāi)始上班，并連續(xù)工作8小時(shí)，若正式工護(hù)士報(bào)酬為10元/h,合同工為15元/h,問(wèn)醫(yī)院是否應(yīng)聘用合同工護(hù)士及聘用多少名？管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法6、紅英公司承諾為某建設(shè)項(xiàng)目從2003年起的4年中每年年初分別提供以下數(shù)額的貸款：2003年100萬(wàn)元、2004年150萬(wàn)元、2005年120萬(wàn)元、2006年110萬(wàn)元。為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額的情況下，可將多余資金分別用于下列投資項(xiàng)目：（

44、1）于2003年初購(gòu)買A種債券，期限3年，到期后本息合計(jì)為投資額的140%，但限購(gòu)60萬(wàn)元。（2）于2003年初購(gòu)買B種債券，期限2年，到期后本息合計(jì)為投資額的125%，但限購(gòu)90萬(wàn)元。（3）于2004年初購(gòu)買C種債券，期限2年，到期后本息合計(jì)為投資額的130%，但限購(gòu)50萬(wàn)元。（4）于年初將任意數(shù)額的資金存放于銀行，年息4%，于年底取出。問(wèn)：該公司應(yīng)如何運(yùn)用好這筆籌集到的資金，問(wèn)：該公司應(yīng)如何運(yùn)用好這筆籌集到的資金，使使20022002年底需籌集到的資金數(shù)額為最少？年底需籌集到的資金數(shù)額為最少？管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法7、某廠生產(chǎn)甲乙丙丁四種產(chǎn)品，產(chǎn)品甲需經(jīng)過(guò)、某廠生產(chǎn)甲乙丙丁四種

45、產(chǎn)品，產(chǎn)品甲需經(jīng)過(guò)A A、B B兩兩種機(jī)器加工，產(chǎn)品乙需經(jīng)過(guò)種機(jī)器加工，產(chǎn)品乙需經(jīng)過(guò)A A、C C兩種機(jī)器加工，產(chǎn)品兩種機(jī)器加工，產(chǎn)品丙需經(jīng)過(guò)丙需經(jīng)過(guò)B B、C C兩種機(jī)器加工，產(chǎn)品丁需經(jīng)過(guò)兩種機(jī)器加工，產(chǎn)品丁需經(jīng)過(guò)A A、B B兩種兩種機(jī)器加工。有關(guān)數(shù)據(jù)如下，試為該廠制定一個(gè)最優(yōu)的生機(jī)器加工。有關(guān)數(shù)據(jù)如下，試為該廠制定一個(gè)最優(yōu)的生產(chǎn)計(jì)劃。產(chǎn)計(jì)劃。產(chǎn) 品機(jī)器生產(chǎn)率（件/小時(shí)） 原料成本（元）產(chǎn)品價(jià)格（元）ABC甲10201665乙20102580丙10151250丁20101870機(jī)器成本 元/小時(shí)200150225每周可用小時(shí)數(shù)15012070管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法8 8、某快餐

46、店坐落于一個(gè)旅游景點(diǎn)，平時(shí)游客不多，而在、某快餐店坐落于一個(gè)旅游景點(diǎn)，平時(shí)游客不多，而在每周六游客猛增。該快餐店雇傭了兩名正式員工，正式每周六游客猛增。該快餐店雇傭了兩名正式員工，正式員工每天工作員工每天工作8 8小時(shí)，其余工作由臨時(shí)工來(lái)?yè)?dān)任，臨時(shí)小時(shí)，其余工作由臨時(shí)工來(lái)?yè)?dān)任，臨時(shí)工每班工作工每班工作4 4小時(shí)。根據(jù)游客就餐情況，在星期六每個(gè)小時(shí)。根據(jù)游客就餐情況，在星期六每個(gè)營(yíng)業(yè)小時(shí)所需職工數(shù)（包括正式工和臨時(shí)工）如下表。營(yíng)業(yè)小時(shí)所需職工數(shù)（包括正式工和臨時(shí)工）如下表。已知一名正式工已知一名正式工1111點(diǎn)開(kāi)始上班，工作點(diǎn)開(kāi)始上班，工作4 4小時(shí)后休息小時(shí)后休息1 1小時(shí)小時(shí)而后再工作而后再

47、工作4 4小時(shí)；另一名正式工小時(shí)；另一名正式工1313點(diǎn)開(kāi)始上班，工作點(diǎn)開(kāi)始上班，工作4 4小時(shí)后休息小時(shí)后休息1 1小時(shí)，而后再工作小時(shí)，而后再工作4 4小時(shí)。又知臨時(shí)工每小小時(shí)。又知臨時(shí)工每小時(shí)的工資為時(shí)的工資為4 4元。在滿足對(duì)職工需求的條件下，如何安元。在滿足對(duì)職工需求的條件下，如何安排臨時(shí)工的班次，使得使用臨時(shí)工的成本最小排臨時(shí)工的班次，使得使用臨時(shí)工的成本最?。抗芾磉\(yùn)籌學(xué)第2章線性規(guī)劃與單純形法時(shí)間時(shí)間所需職工數(shù)所需職工數(shù)時(shí)間時(shí)間所需職工數(shù)所需職工數(shù)11:00-12:00917:00-18:00612:00-13:00918:00-19:001213:00-14:00919:00-

48、20:001214:00-15:00320:00-21:00715:00-16:00321:00-22:00716:00-17:003管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法x2x3x4x51 3 x3x4x5x62 3 x4x5x6x71 6 x5x6x7x82 12 x6x7x8x92 12 min f=16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11） st x11 9 x1 x21 9 x1 x2x32 9 x1x2x3x42 3 管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法9、某廠按合同規(guī)定于當(dāng)年每個(gè)季度末分別提供、某廠按合同規(guī)定于當(dāng)年每個(gè)季度末分別提供10、15、25、2

49、0臺(tái)臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及每臺(tái)柴油機(jī)的同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及每臺(tái)柴油機(jī)的成本如下表所示，又如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每成本如下表所示，又如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15元。要求在完成合同的情況元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)費(fèi)用最小的決策。下，做出使該廠全年生產(chǎn)費(fèi)用最小的決策。 季度季度1 12 23 34 4生產(chǎn)能力生產(chǎn)能力2525353530301010單位成本（萬(wàn)元）單位成本（萬(wàn)元）10.810.811.111.111.011.011.311.3

50、管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2.4 2.4 單純形法基本原理及計(jì)算步驟單純形法基本原理及計(jì)算步驟一、單純形法的基本思路一、單純形法的基本思路 從可行域中某一個(gè)頂點(diǎn)開(kāi)始從可行域中某一個(gè)頂點(diǎn)開(kāi)始 判斷此頂點(diǎn)是判斷此頂點(diǎn)是否是最優(yōu)解，如不是則再找另一個(gè)使得目標(biāo)否是最優(yōu)解，如不是則再找另一個(gè)使得目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代。再判斷此函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代。再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為最優(yōu)點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解能判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解管理運(yùn)籌學(xué)第2章線

51、性規(guī)劃與單純形法n最優(yōu)解一定在可行域的頂點(diǎn)上最優(yōu)解一定在可行域的頂點(diǎn)上,將頂點(diǎn)坐標(biāo)代入目標(biāo)函數(shù)有將頂點(diǎn)坐標(biāo)代入目標(biāo)函數(shù)有:n(0,0):z=30+20=0n(5,0):z=35+20=15n(0,8):z=30+28=16n(2,6):z=32+26=18n單純形法的基本思路就是基本單純形法的基本思路就是基本可行解的轉(zhuǎn)移，先找到一個(gè)初可行解的轉(zhuǎn)移，先找到一個(gè)初始基本可行解，如果不是最優(yōu)始基本可行解，如果不是最優(yōu)解，設(shè)法轉(zhuǎn)移到另一個(gè)基本可解，設(shè)法轉(zhuǎn)移到另一個(gè)基本可行解，并使目標(biāo)函數(shù)值不斷增行解，并使目標(biāo)函數(shù)值不斷增加，直到找到最優(yōu)解加，直到找到最優(yōu)解。(5,0)(2,6)108302 5 8x2

52、(0,8)x1管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法 二、單純形法計(jì)算步驟：二、單純形法計(jì)算步驟： 1、找出一個(gè)初始基本可行解、找出一個(gè)初始基本可行解 單純形法中可行域的頂點(diǎn)叫做基本可行解，找到的第一個(gè)基本可行解叫做初始基本可行解管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法目標(biāo)函數(shù)目標(biāo)函數(shù) max Z= 50 x1+100 x2 x1+x2+s1 =300 2x1+x2 +s2 =400 x2 +s3=250 x1,x2, s1, s2, s3, 0系數(shù)矩陣系數(shù)矩陣A= 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1由于由于A中存在一個(gè)不為零的三階子式，可知中存在一個(gè)不為零的三階子式，可知A的秩

53、為的秩為3因?yàn)橐驗(yàn)锳的秩的秩m小于此方程組的變量的個(gè)數(shù)小于此方程組的變量的個(gè)數(shù) n，可知其有，可知其有無(wú)窮多組解無(wú)窮多組解管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法基本概念基本概念 基基：已知A是約束條件的mn系數(shù)矩陣，其秩 為m，若B是A中mm階可逆矩陣，則稱B 是線形規(guī)劃問(wèn)題中的一個(gè)基。B是由A中m個(gè)線形無(wú)關(guān)的系數(shù)列向量組成的。 本例中 1 1 1 與 1 0 0 2 1 0 0 1 0 0 1 0 0 0 1 都是該線性規(guī)劃的一個(gè)基。它們都是由3個(gè)線性 無(wú)關(guān)的系數(shù)列向量組成。管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法基向量基向量:基基B中的一列稱為一個(gè)基向量?；械囊涣蟹Q為一個(gè)基向量。基B中共有中共有m

54、 個(gè)基向量個(gè)基向量非基向量非基向量:在在A中除了基中除了基B之外的一切列稱為基之外的一切列稱為基B的的非基非基 向量向量基變量基變量:與基向量與基向量pi對(duì)應(yīng)的變量對(duì)應(yīng)的變量xi叫做基變量叫做基變量,基變量有基變量有m個(gè)個(gè)非基變量非基變量:與非基向量與非基向量pj對(duì)應(yīng)的變量對(duì)應(yīng)的變量xj叫做非基變量叫做非基變量,基基 變量有變量有n-m個(gè)個(gè).例中對(duì)基基B1= 1 1 1 來(lái)說(shuō)來(lái)說(shuō) 1 1 1 2 1 0 2 1 0 0 1 0 0 1 0 都是基都是基B1的基向量的基向量,對(duì)應(yīng)的變量對(duì)應(yīng)的變量x1,x2,s1叫做基變量叫做基變量, s2,s3是基是基B1的非基變量的非基變量.管理運(yùn)籌學(xué)第2章線

55、性規(guī)劃與單純形法例中對(duì)基基B2= 1 0 0 來(lái)說(shuō)來(lái)說(shuō) 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 都是基都是基B2的基向量的基向量,對(duì)應(yīng)的變量對(duì)應(yīng)的變量s1, s2,s3叫做基變量叫做基變量, x2,x3是基是基B2非基變量非基變量.在約束方程系數(shù)矩陣中找到一個(gè)基在約束方程系數(shù)矩陣中找到一個(gè)基,令這個(gè)基的非基變令這個(gè)基的非基變量為零量為零,再求解這個(gè)再求解這個(gè)m元線性方程組就可得到唯一的解元線性方程組就可得到唯一的解了了,這個(gè)解稱之為線性規(guī)劃的這個(gè)解稱之為線性規(guī)劃的基本解基本解.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法例取B3= 1 1 0 為為A的一個(gè)基的一個(gè)基,令非基變量令非基

56、變量x1,s2 1 0 0 為零為零,這時(shí)約束方程就變?yōu)閮H含這時(shí)約束方程就變?yōu)閮H含 1 0 1 基變量的約束方程基變量的約束方程. x2+s1 =300 求解得x2=400 s1= -100 s3= -100 x2 =400 x1=0 s2=0 x2 +s3=250由于由于s1 ,s30,顯然不是此線性規(guī)劃的可行解顯然不是此線性規(guī)劃的可行解一個(gè)基本解可以是可行解一個(gè)基本解可以是可行解,也可以是非可行解也可以是非可行解,它們之間它們之間的主要區(qū)別在于其所有變量的解是否滿足非負(fù)的條件的主要區(qū)別在于其所有變量的解是否滿足非負(fù)的條件.把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解把滿足非負(fù)條件的一個(gè)基本解叫

57、做基本可行解,并把這并把這樣的基叫做可行基樣的基叫做可行基.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法它們之間的關(guān)系管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法選B1= 1 1 0 2 0 0 0 0 1令其非基變量令其非基變量x2,s2為零為零,約束方程約束方程 變?yōu)榛兞康募s束方程變?yōu)榛兞康募s束方程 x1 +s1 =300 2x1 =400 s3=250求解得到基變量的唯一解求解得到基變量的唯一解,基變量基變量s3=250 x1 =200 s1 =100 非基變量非基變量x2=0 s2=0所有變量都大于等于零所有變量都大于等于零,此基本解為基本此基本解為基本可行解可行解. 只要找到一個(gè)基是單位矩陣只要找到

58、一個(gè)基是單位矩陣,或者說(shuō)一個(gè)基是由單位或者說(shuō)一個(gè)基是由單位矩陣各列向量組成矩陣各列向量組成(列向量前后順序無(wú)關(guān)緊要列向量前后順序無(wú)關(guān)緊要),那么所那么所求得的基本解一定是基本可行解求得的基本解一定是基本可行解.練習(xí)練習(xí):設(shè)設(shè)B2為基為基,求一組基本解求一組基本解,并判別其是否為基本并判別其是否為基本 可行解可行解.管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法2、最優(yōu)性檢驗(yàn)、最優(yōu)性檢驗(yàn)-判斷已求得的基本可行解是否判斷已求得的基本可行解是否 為最優(yōu)解為最優(yōu)解最優(yōu)性檢驗(yàn)的依據(jù)最優(yōu)性檢驗(yàn)的依據(jù)-檢驗(yàn)數(shù)檢驗(yàn)數(shù)j 要求只用非基變量來(lái)表示目標(biāo)函數(shù)要求只用非基變量來(lái)表示目標(biāo)函數(shù), ,這只要在約束這只要在約束等式中通過(guò)移

59、項(xiàng)處理就可以用非基變量來(lái)表示基等式中通過(guò)移項(xiàng)處理就可以用非基變量來(lái)表示基變量變量, ,然后用非基變量的表示式代替目標(biāo)函數(shù)中基然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量變量, ,這樣目標(biāo)函數(shù)中就只含非基變量了這樣目標(biāo)函數(shù)中就只含非基變量了, ,或者說(shuō)目或者說(shuō)目標(biāo)函數(shù)中基變量的系數(shù)都為零了標(biāo)函數(shù)中基變量的系數(shù)都為零了. .此時(shí)目標(biāo)函數(shù)中此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù), ,把變量把變量x xi i的的檢驗(yàn)數(shù)記為檢驗(yàn)數(shù)記為i.i.顯然所有基變量的檢驗(yàn)數(shù)必為零顯然所有基變量的檢驗(yàn)數(shù)必為零. .管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法1 122nnMaxZc xc

60、 xc x11,m 111,122,112,2,11,12. .,0mnnmmnnmm mmm nnmnxaxa xbxaxaxbstxaxaxbx xx管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法基變量的非基變量表達(dá)式： 令所有的非基變量取值為零，即，由此求出初始基本可行解為：120mmnxxx(0)12( ,0,0)TmXb bb111,111,221,222,112,222,11,22,()()()mmmmnnmmmmnnnmm mmm mmm nnxbaxaxa xxbaxaxaxxbaxaxax管理運(yùn)籌學(xué)第2章線性規(guī)劃與單純形法,11,22,1 = (i=1,2,m)iii mmi mmi n