物流運(yùn)籌學(xué)單純形法

1、物流運(yùn)籌學(xué)物流運(yùn)籌學(xué)第五節(jié)：?jiǎn)渭冃畏ǖ谖骞?jié)：?jiǎn)渭冃畏ū敬握n學(xué)習(xí)任務(wù)：本次課學(xué)習(xí)任務(wù)： 1.5.11.5.1單純形法原理單純形法原理 1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟學(xué)習(xí)要求：理解單純形法的原理，會(huì)用單純形法求解線性規(guī)劃問(wèn)題。學(xué)習(xí)要求：理解單純形法的原理，會(huì)用單純形法求解線性規(guī)劃問(wèn)題。1.5.11.5.1單純形法原理單純形法原理單純形法原理頂點(diǎn)的轉(zhuǎn)移：頂點(diǎn)的轉(zhuǎn)移： 單純形法的每一步的可行解對(duì)應(yīng)著圖解法可行域中的一個(gè)單純形法的每一步的可行解對(duì)應(yīng)著圖解法可行域中的一個(gè)頂點(diǎn)。頂點(diǎn)。即從可行域的一個(gè)頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)即從可行域的一個(gè)頂點(diǎn)（基本可行解）開始，轉(zhuǎn)移到

2、另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過(guò)程，（另一個(gè)基本可行解）的迭代過(guò)程，轉(zhuǎn)移的條件轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得到了最優(yōu)解。到了最優(yōu)解。需要解決的問(wèn)題：需要解決的問(wèn)題： (1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？ (2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)？判斷標(biāo)準(zhǔn)是什么？目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)？判斷標(biāo)準(zhǔn)是什么？ 1.5.11.5.1單純形法原理單純形法原理單純形法步驟確定初始基本可行解確定初始基本可行解檢驗(yàn)其檢驗(yàn)其是否為最優(yōu)是否為最優(yōu)尋找更好的尋找更好的基本

3、可行解基本可行解停否否是是主要工作：主要工作：最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)主要工作：主要工作：1、基變換（將原來(lái)的基換成新的基）、基變換（將原來(lái)的基換成新的基）2、修正單純形表，得到新的基本可行解、修正單純形表，得到新的基本可行解1、首先引入松弛變量或剩余變量使線性規(guī)劃模型化為標(biāo)準(zhǔn)形式，且標(biāo)準(zhǔn)形式的系數(shù)、首先引入松弛變量或剩余變量使線性規(guī)劃模型化為標(biāo)準(zhǔn)形式，且標(biāo)準(zhǔn)形式的系數(shù)矩陣中含有一個(gè)單位矩陣。（矩陣中含有一個(gè)單位矩陣。（ “”型約束添加松弛變量，型約束添加松弛變量， “”約束添加剩余變量變約束添加剩余變量變?yōu)榈仁郊s束為等式約束 ）。）。1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟單純形法步

4、驟2、確定初始基和初始基本可行解。寫出基本可行解和目標(biāo)函數(shù)值。、確定初始基和初始基本可行解。寫出基本可行解和目標(biāo)函數(shù)值。3、最優(yōu)性檢驗(yàn)、最優(yōu)性檢驗(yàn)（1）計(jì)算機(jī)會(huì)成本行）計(jì)算機(jī)會(huì)成本行 （2）計(jì)算檢驗(yàn)數(shù)行）計(jì)算檢驗(yàn)數(shù)行 j（3）最優(yōu)性檢驗(yàn)：但所有檢驗(yàn)數(shù)小于等于）最優(yōu)性檢驗(yàn)：但所有檢驗(yàn)數(shù)小于等于0時(shí)，得到最優(yōu)解，計(jì)算結(jié)束。否則，轉(zhuǎn)時(shí)，得到最優(yōu)解，計(jì)算結(jié)束。否則，轉(zhuǎn)入下一步。入下一步。4、基變換、基變換 （1） 用用j確定進(jìn)基列向量和進(jìn)基變量。確定進(jìn)基列向量和進(jìn)基變量。 （2）用）用規(guī)則確定出基列向量及出基變量。規(guī)則確定出基列向量及出基變量。5、修正單純形表。、修正單純形表。資源資源 產(chǎn)品產(chǎn)品單耗單

5、耗資源資源甲甲 乙乙資源限量資源限量煤煤(t)電電(kw.h)油油(t)9 44 5 3 10360200300單位產(chǎn)品價(jià)格單位產(chǎn)品價(jià)格 7 12問(wèn)題問(wèn)題1 1: :某工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，某工廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品， 生產(chǎn)生產(chǎn)1kg1kg的甲需耗煤的甲需耗煤9t9t、 電力電力4kw.h4kw.h、 油油3t3t； 生產(chǎn)生產(chǎn)1kg1kg的乙需耗煤的乙需耗煤4t4t、 電力電力5kw.h5kw.h、 油油10t10t； 該廠現(xiàn)有煤該廠現(xiàn)有煤360t360t、電力、電力200kw.h200kw.h、油、油300t300t。 已知甲產(chǎn)品每千克的售價(jià)為已知甲產(chǎn)品每千克的售價(jià)為7 7萬(wàn)元、乙產(chǎn)

6、品每千克的售價(jià)為萬(wàn)元、乙產(chǎn)品每千克的售價(jià)為1212萬(wàn)元。萬(wàn)元。 在上述條件下決定生產(chǎn)方案，使得總收入最大，具體數(shù)據(jù)如表所在上述條件下決定生產(chǎn)方案，使得總收入最大，具體數(shù)據(jù)如表所示示：1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟21127zxxmax0,3001032005436049. .21212121xxxxxxxxts約束約束條件條件目標(biāo)目標(biāo)函數(shù)函數(shù)此問(wèn)題的線性規(guī)劃模型：此問(wèn)題的線性規(guī)劃模型：非標(biāo)準(zhǔn)形式非標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式21127xxmaxz0,3001032005436049. .21212121xxxxxxxxts21127xxmaxz0,30010320054360

7、49. .54321521421321xxxxxxxxxxxxxxts1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第一步：引入松弛變量化為標(biāo)準(zhǔn)型。第一步：引入松弛變量化為標(biāo)準(zhǔn)型?；欠腔蛳蛄苛烤鼐仃囮嚮颈窘狻⒔?、基基本本可可行行解解基基變變量量非非基基變變量量 100010001pppb54310,300200360. .543543xxxxxxts30020036000x1035449ppn2115435431xxxxxxxtb2121n1xxxxxt0,21xx令初始基初始基初始基本初始基本可行解可行解1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第二步：編制初始單

8、純形表并確定初始可行基、初始基本可行解。第二步：編制初始單純形表并確定初始可行基、初始基本可行解。94345101000100011x2x4x5xnb3xa =為了求解初始基本可行解的方為了求解初始基本可行解的方便，選擇單位矩陣為初始基。便，選擇單位矩陣為初始基。1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第二步：編制初始單純形表并確定初始可行基、初始基本可行解。第二步：編制初始單純形表并確定初始可行基、初始基本可行解。cb000cb b-1pjj = cj-cb b-1pjxbx3x4x5b-1b3602003007x19430712x245100120x3100000x401000

9、0x500100基變量基變量基變量的基變量的價(jià)值系數(shù)價(jià)值系數(shù)機(jī)會(huì)成本行機(jī)會(huì)成本行（這一行可以（這一行可以省略）省略）價(jià)值系數(shù)價(jià)值系數(shù)（目標(biāo)函數(shù)中決策變（目標(biāo)函數(shù)中決策變量的系數(shù)）量的系數(shù)）檢驗(yàn)數(shù)行檢驗(yàn)數(shù)行作用：檢驗(yàn)當(dāng)前可行解是否最優(yōu)；作用：檢驗(yàn)當(dāng)前可行解是否最優(yōu)；如果不是最優(yōu)解，確定如果不是最優(yōu)解，確定入基變量入基變量。初始基本初始基本 可可行解行解在以上基本可行解中，在以上基本可行解中， 3002003600054321xxxxx即：甲、乙各生產(chǎn)即：甲、乙各生產(chǎn)0件。件?？偟氖杖霝椋嚎偟氖杖霝椋喝f(wàn)元萬(wàn)元030002000360001207 f這個(gè)基本可行解顯然不是最優(yōu)解，從目標(biāo)函這個(gè)基本可行

10、解顯然不是最優(yōu)解，從目標(biāo)函數(shù)來(lái)考慮，還可以通過(guò)增加甲、乙的產(chǎn)量，數(shù)來(lái)考慮，還可以通過(guò)增加甲、乙的產(chǎn)量，來(lái)增加總收入。來(lái)增加總收入。下面介紹：如何檢驗(yàn)現(xiàn)有基本可行解是否為下面介紹：如何檢驗(yàn)現(xiàn)有基本可行解是否為最優(yōu)解。最優(yōu)解。cb000xbx3x4x5b-1b3602003007x194312x245100x31000x40100x5001基本可行解1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第三步：最優(yōu)性檢驗(yàn)，確定當(dāng)前基本可行解是否是最優(yōu)解。（第三步：最優(yōu)性檢驗(yàn)，確定當(dāng)前基本可行解是否是最優(yōu)解。（ j 檢驗(yàn)數(shù)的檢驗(yàn)數(shù)的計(jì)算）計(jì)算）如果所有的檢驗(yàn)數(shù)都小于等于如果所有的檢驗(yàn)數(shù)都小于等于0，則

11、當(dāng)前解為最優(yōu)解。，則當(dāng)前解為最優(yōu)解。cb000機(jī)會(huì)成本行機(jī)會(huì)成本行j xbx3x4x5b-1b3602003007x19430712x245100120x3100000x4010000x500100904030基變量基變量基變量的基變量的價(jià)值系數(shù)價(jià)值系數(shù)基本基本 可行解可行解因?yàn)榛兞康臋z驗(yàn)數(shù)因?yàn)榛兞康臋z驗(yàn)數(shù)1和和2都大于都大于0，所以當(dāng)前解不是最優(yōu)。需要變換可行基，所以當(dāng)前解不是最優(yōu)。需要變換可行基，尋找新的解。即原來(lái)的非基變量尋找新的解。即原來(lái)的非基變量x1 、x2，要有一個(gè)被換為基變量，基變量中，要有一個(gè)被換為基變量，基變量中也要有一個(gè)被換為非基變量，以確定新的基、新的解。也要有一個(gè)被

12、換為非基變量，以確定新的基、新的解。1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第四步：基變換第四步：基變換（1）如果經(jīng)過(guò)檢驗(yàn)不是最優(yōu)解，確定如何換基，首先確定由哪個(gè)非基變量作為）如果經(jīng)過(guò)檢驗(yàn)不是最優(yōu)解，確定如何換基，首先確定由哪個(gè)非基變量作為進(jìn)基變量進(jìn)基變量檢驗(yàn)數(shù)檢驗(yàn)數(shù)j中最大的正數(shù)對(duì)應(yīng)的非基變量作為進(jìn)基變量中最大的正數(shù)對(duì)應(yīng)的非基變量作為進(jìn)基變量。（2）用）用檢驗(yàn)數(shù)確定出基變量。檢驗(yàn)數(shù)確定出基變量。檢驗(yàn)數(shù)中最小的正數(shù)對(duì)應(yīng)的基變量作為出檢驗(yàn)數(shù)中最小的正數(shù)對(duì)應(yīng)的基變量作為出基變量?；兞俊b000cb b-1pjz=xbx3x4x5j = cj-cb b-1pjb-1b36020030

13、07x19430712x24510 012 0x3100000x4010000x5001001 =360/4=902 =200/5=40 3 =300/10=30主元列主元列（確定入基變量）（確定入基變量）主元行主元行（確定（確定出基變出基變量）量）主元素主元素檢驗(yàn)數(shù)（用來(lái)檢驗(yàn)數(shù)（用來(lái)確定出基變量）確定出基變量）現(xiàn)分析，確定現(xiàn)分析，確定x1和和 x2誰(shuí)入基，因?yàn)檎l(shuí)入基，因?yàn)閤2的系數(shù)最大，即單位收入的系數(shù)最大，即單位收入最高，自然先考慮增加乙的產(chǎn)量，固確定最高，自然先考慮增加乙的產(chǎn)量，固確定x2為入基變量。為入基變量。54321000127maxxxxxxf 如何確定入基變量如何確定入基變量（

14、可以按照下述方法來(lái)理解）（可以按照下述方法來(lái)理解）當(dāng)當(dāng)x2定為入基變量后，必須從定為入基變量后，必須從x3 、 x4 、 x5中換出來(lái)一個(gè)，并保中換出來(lái)一個(gè)，并保證其余的變量在新可行解中還都是非負(fù)，即：證其余的變量在新可行解中還都是非負(fù)，即： x30 、 x4 0 、 x5 0 0,3001032005436049. .54321521421321xxxxxxxxxxxxxxts 0,3001020053604.54321524232xxxxxxxxxxxts 0,1030052004360.54321252423xxxxxxxxxxxts如何確定出基變量（可以按照下述方法來(lái)理解）如何確定出基

15、變量（可以按照下述方法來(lái)理解）因?yàn)橐驗(yàn)閤1 仍為基變量，仍為基變量，所以將所以將x1=0，帶入約，帶入約束條件，得到：束條件，得到：只能選只能選x5 作為出基變作為出基變量，令量，令x5 =0，請(qǐng)思考，請(qǐng)思考為什么？為什么？因?yàn)椋喝绻x取因?yàn)椋喝绻x取x3 或或x4 作為出基變量，則會(huì)出作為出基變量，則會(huì)出現(xiàn)有的變量為負(fù)值?，F(xiàn)有的變量為負(fù)值。第五步：第五步： 進(jìn)行矩陣的初等變換，修正單純形表繼續(xù)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算。進(jìn)行矩陣的初等變換，修正單純形表繼續(xù)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算。cb000檢驗(yàn)數(shù)檢驗(yàn)數(shù)j0012檢驗(yàn)數(shù)檢驗(yàn)數(shù)jxbx3x4x5x3x4x2b-1b36020030024050307x1943

16、77.82.50.33.4 12x24510 12 00100x3100010000x4010001000x50010-0.4-0.50.1-1.2904030 30.820 100x(1)=0, 30, 240, 50, 0tx(0)=0, 0, 360, 200,300tz(1)=360z(0)=0b(1)=p3, p4, p2b(0)=p3, p4, p5初等變換過(guò)程：初等變換過(guò)程：第第行除以行除以10，變?yōu)?，變?yōu)?；乘上乘?5，加上第，加上第行，變?yōu)樾?，變?yōu)?；乘上乘?4，加上第，加上第行，變?yōu)樾?，變?yōu)椤Ｒ驗(yàn)橐驗(yàn)?0，所以當(dāng)前解所以當(dāng)前解仍不是最優(yōu)解。需要繼仍不是最優(yōu)解。需要繼續(xù)進(jìn)行基

17、變換。續(xù)進(jìn)行基變換。1.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第五步：第五步： 進(jìn)行矩陣的初等變換，修正單純形表繼續(xù)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算。進(jìn)行矩陣的初等變換，修正單純形表繼續(xù)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算。cb000機(jī)會(huì)成本（此行可省略）機(jī)會(huì)成本（此行可省略）檢驗(yàn)數(shù)檢驗(yàn)數(shù)j0012機(jī)會(huì)成本（此行可省略）機(jī)會(huì)成本（此行可省略）檢驗(yàn)數(shù)檢驗(yàn)數(shù)j0xbx3x4x5x3x4x2x3b-1b3602003002405030847x1943077.82.50.33.63.4 012x24510 012 00112000x3100001000010x40100001000-3.120x500100-0.4-0.5

18、0.11.2-1.21.16904030 30.820 100”x(1)=0, 30, 240, 50, 0tx(2)=20, 24, 84, 0, 0tx(0)=0, 0, 360, 200,300tz(1)=360z(2)=428z(0)=0b(1)=p3, p4, p2b(2)=p3, p1, p2b(0)=p3, p4, p51.5.21.5.2單純形法計(jì)算步驟單純形法計(jì)算步驟第六步：得到最優(yōu)解，及目標(biāo)函數(shù)最優(yōu)值，寫出結(jié)果。第六步：得到最優(yōu)解，及目標(biāo)函數(shù)最優(yōu)值，寫出結(jié)果。最優(yōu)解為：最優(yōu)解為：x(2)=20, 24, 84, 0, 0t目標(biāo)函數(shù)最優(yōu)值為：目標(biāo)函數(shù)最優(yōu)值為：z(2)=428即最優(yōu)生產(chǎn)計(jì)劃為：甲生產(chǎn)即最優(yōu)生產(chǎn)計(jì)劃為：甲生產(chǎn)20件，乙生產(chǎn)件，乙生產(chǎn)24件，最大收入為：件，最大收入為：428萬(wàn)元。萬(wàn)元。在最后的單純形表中，所有非基變量的檢驗(yàn)數(shù)在最后的單純形表中，所有非基變量的檢驗(yàn)數(shù)j 0，可以可以判斷已得到最優(yōu)解，此表即為最終單純形表，對(duì)應(yīng)的基判斷已得到最優(yōu)解，此表即為最終單純形表，對(duì)應(yīng)的基p3，p1，p2為最優(yōu)基。為最優(yōu)基。練習(xí)題練習(xí)題cb000zjj=cj-zj基基x3x4x5b152452x1061021x2521010 x3