第二章-物流運(yùn)籌學(xué)線性規(guī)劃課件

學(xué)習(xí)目標(biāo)知識(shí)目標(biāo)掌握線性規(guī)劃的基本形式及標(biāo)準(zhǔn)形式；掌握單純形法計(jì)算過(guò)程；理解對(duì)偶問(wèn)題；掌握對(duì)偶問(wèn)題的求法及性質(zhì)；了解靈敏度分析。技能目標(biāo)能夠結(jié)合實(shí)際情況建立線性規(guī)劃的模型，并可利用單純形法求解。學(xué)習(xí)目標(biāo)知識(shí)目標(biāo)1第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型問(wèn)題的提出線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型問(wèn)題的提出2問(wèn)題的提出【例2-1】某企業(yè)要將產(chǎn)品包裝成Ⅰ、Ⅱ兩種規(guī)格，需要A、B兩種原材料的數(shù)量、獲利情況及兩種材料數(shù)量限制見(jiàn)表2-1，兩種規(guī)格的產(chǎn)品各包裝多少件可獲利最多？表2-1

問(wèn)題的提出【例2-1】某企業(yè)要將產(chǎn)品包裝成Ⅰ、Ⅱ兩種規(guī)格，表3第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件4第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件5第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件6上面兩個(gè)例子的共同特征：（1）每一個(gè)問(wèn)題都由一組決策變量來(lái)表示某一方案，一般情況下這些變量的取值是非負(fù)且連續(xù)的。（2）存在一定的約束條件，這些約束條件可以用一組線性的等式或不等式來(lái)表示。（3）都有一個(gè)要求達(dá)到的目標(biāo)，它用決策變量的線性函數(shù)（稱(chēng)為目標(biāo)函數(shù)）來(lái)表示。按照具體問(wèn)題的不同，要求目標(biāo)實(shí)現(xiàn)最小或最大。上面兩個(gè)例子的共同特征：7求取一組變量，使之既滿足線性約束條件，又使具有線性表達(dá)式的目標(biāo)函數(shù)取得極大值或極小值的一類(lèi)最優(yōu)化問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題，簡(jiǎn)稱(chēng)線性規(guī)劃（LP）。決策變量、約束條件和目標(biāo)函數(shù)是其三個(gè)基本要素。線性規(guī)劃定義求取一組變量，使之既滿足線性約束條件，線性規(guī)8第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件9第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件10第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件11線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式12第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件13第二節(jié)線性規(guī)劃模型的求解圖解法單純形法第二節(jié)線性規(guī)劃模型的求解圖解法14滿足所有約束條件的向量稱(chēng)為線性規(guī)劃問(wèn)題的可行解所有可行解構(gòu)成的集合稱(chēng)為可行域。在可行域中使得目標(biāo)函數(shù)值最大（或最?。┑目尚薪猓Q(chēng)為線性規(guī)劃問(wèn)題的最優(yōu)解。最優(yōu)解的全體稱(chēng)為最優(yōu)解集合。最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值稱(chēng)為最優(yōu)值。滿足所有約束條件的向量稱(chēng)為線性規(guī)劃問(wèn)題的可行解15圖解法圖解法16第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件17線性規(guī)劃解的可能情況唯一最優(yōu)解無(wú)窮多最優(yōu)解無(wú)界解無(wú)可行解線性規(guī)劃解的可能情況唯一最優(yōu)解18單純形法單19第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件20單純形法的基本原理：尋找一種規(guī)則，從一個(gè)基可行解轉(zhuǎn)移到另一個(gè)基可行解，目標(biāo)函數(shù)值是增大的，即“頂點(diǎn)轉(zhuǎn)換，目標(biāo)上升”。單純形法的基本原理：21對(duì)矩陣作初等變換：對(duì)矩陣作初等變換：22第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件23單純形法的計(jì)算步驟單純形法的計(jì)算步驟24第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件25解初始單純形表解初始單純形表26得到新的單純形表得到新的單純形表27得到新的單純形表得到新的單純形表28第三節(jié)線性規(guī)劃對(duì)偶問(wèn)題與

靈敏度分析對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的基本性質(zhì)靈敏度分析第三節(jié)線性規(guī)劃對(duì)偶問(wèn)題與

29對(duì)偶問(wèn)題的提出一般稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為例2-1線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，例2-1稱(chēng)為原問(wèn)題。對(duì)偶問(wèn)題的提出一般稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為例2-1線性規(guī)劃30表2-6原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系表2-6原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系31對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì)32第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件33對(duì)偶問(wèn)題最優(yōu)解的經(jīng)濟(jì)解釋?zhuān)河白觾r(jià)格。線性規(guī)劃問(wèn)題中，當(dāng)某資源增加一個(gè)單位而其他資源都不變時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值的增量稱(chēng)為資源的影子價(jià)格。影子價(jià)格是對(duì)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)。對(duì)偶問(wèn)題最優(yōu)解的經(jīng)濟(jì)解釋?zhuān)河白觾r(jià)格。34靈敏度分析目標(biāo)函數(shù)的靈敏度分析約束右端向量的靈敏度分析約束方程系數(shù)的靈敏度分析增加一個(gè)新變量的靈敏度分析增加一個(gè)約束的靈敏度分析靈敏度分析目標(biāo)函數(shù)的靈敏度分析35第四節(jié)線性規(guī)劃在物流管理中的應(yīng)用直接應(yīng)用物資配送、調(diào)運(yùn)，人員的分配物流中心選址問(wèn)題配送系統(tǒng)的重新安排項(xiàng)目投資等間接應(yīng)用整數(shù)規(guī)劃中的割平面法和分支定界法運(yùn)輸問(wèn)題中的表上作業(yè)法第四節(jié)線性規(guī)劃在物流管理中的應(yīng)用直接應(yīng)用間接應(yīng)用36本章小結(jié)本章首先結(jié)合具體示例介紹了線性規(guī)劃問(wèn)題及其模型結(jié)構(gòu)、線性規(guī)劃的標(biāo)準(zhǔn)模型、一般線性規(guī)劃模型向標(biāo)準(zhǔn)型轉(zhuǎn)換的方法，接著定義了線性規(guī)劃可行解、最優(yōu)解的概念，重點(diǎn)闡述了求解線性規(guī)劃的一般方法——單純形方法，給出了單純形方法的具體求解步驟。之后，介紹了線性規(guī)劃的對(duì)偶問(wèn)題以及與原問(wèn)題關(guān)系，闡釋了對(duì)偶問(wèn)題的基本性質(zhì)，相應(yīng)地給出了求解線性規(guī)劃問(wèn)題的對(duì)偶單純形方法。并簡(jiǎn)單討論了目標(biāo)函數(shù)系數(shù)向量、約束矩陣以及約束右端項(xiàng)的變化給線性規(guī)劃最優(yōu)解帶來(lái)的影響。最后，介紹了線性規(guī)劃在物流領(lǐng)域中的典型應(yīng)用。本章的重點(diǎn)和難點(diǎn)是實(shí)際物流問(wèn)題的線性規(guī)劃建模以及求解線性規(guī)劃的單純形方法。本章小結(jié)本章首先結(jié)合具體示例介紹了線性規(guī)劃問(wèn)題及其模型結(jié)構(gòu)、37案例分析A公司分撥物流網(wǎng)絡(luò)負(fù)責(zé)把下線產(chǎn)品經(jīng)過(guò)配送中心發(fā)送到客戶手中，包括了原材料采購(gòu)、生產(chǎn)、運(yùn)輸、倉(cāng)儲(chǔ)和配送，除一些偏遠(yuǎn)地區(qū)外，該公司建立了非常完善的物流配送系統(tǒng)，A公司的物流運(yùn)輸途徑大部分都采用航空運(yùn)輸?，F(xiàn)在，該公司接到四類(lèi)貨物的配送要求，信息見(jiàn)表2-13。以A公司在實(shí)際工作中，優(yōu)化其現(xiàn)有配送資源為例，給出線性規(guī)劃模型，說(shuō)明線性規(guī)劃的實(shí)際應(yīng)用情況。案例分析A公司分撥物流網(wǎng)絡(luò)負(fù)責(zé)把下線產(chǎn)品經(jīng)過(guò)配送中心以A公司38表2-13案例相關(guān)數(shù)據(jù)表2-13案例相關(guān)數(shù)據(jù)39問(wèn)題分析負(fù)責(zé)運(yùn)輸產(chǎn)品的飛機(jī)有前倉(cāng)、中倉(cāng)和后倉(cāng)三個(gè)貨艙。各自所能裝載的貨物最大重量和體積都有限制，且為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大允許重量成比例。該公司為了既滿足貨機(jī)本身的限制，又能獲得最大利潤(rùn)，建立了下面的模型：?jiǎn)栴}分析負(fù)責(zé)運(yùn)輸產(chǎn)品的飛機(jī)有前倉(cāng)、中倉(cāng)和后倉(cāng)三個(gè)貨艙。40第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件41第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件42第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件43問(wèn)題（1）航空運(yùn)輸規(guī)劃時(shí)考慮的因素、目標(biāo)和約束條件的限制有哪些？（2）案例中建模的過(guò)程是怎樣的？（3）如何對(duì)上述建模進(jìn)一步改進(jìn)？問(wèn)題44實(shí)訓(xùn)實(shí)訓(xùn)目標(biāo)掌握線性規(guī)劃模型的建立和單純形法實(shí)訓(xùn)內(nèi)容與要求要求了解企業(yè)經(jīng)常遇到資源、設(shè)備等的分配問(wèn)題。在分配時(shí)，用數(shù)學(xué)語(yǔ)言描述各種限制條件并建立相應(yīng)的線性規(guī)劃模型，利用單純形法求解，給出最優(yōu)的分配方案。成果與檢驗(yàn)?zāi)軌蚪⑾鄳?yīng)的線性問(wèn)題模型，利用單純形法求解，得出最優(yōu)分配方案。實(shí)訓(xùn)實(shí)訓(xùn)目標(biāo)45精品課件！精品課件！46精品課件！精品課件！47某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)數(shù)及A、B兩種原材料的消耗量，見(jiàn)表2-11。該工廠每生產(chǎn)一單位產(chǎn)品Ⅰ可獲利潤(rùn)2元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利潤(rùn)3元，問(wèn)應(yīng)如何安排生產(chǎn)使該工廠獲得的利潤(rùn)最大？表2-14實(shí)訓(xùn)相關(guān)數(shù)據(jù)某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知表2-1448學(xué)習(xí)目標(biāo)知識(shí)目標(biāo)掌握線性規(guī)劃的基本形式及標(biāo)準(zhǔn)形式；掌握單純形法計(jì)算過(guò)程；理解對(duì)偶問(wèn)題；掌握對(duì)偶問(wèn)題的求法及性質(zhì)；了解靈敏度分析。技能目標(biāo)能夠結(jié)合實(shí)際情況建立線性規(guī)劃的模型，并可利用單純形法求解。學(xué)習(xí)目標(biāo)知識(shí)目標(biāo)49第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型問(wèn)題的提出線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型問(wèn)題的提出50問(wèn)題的提出【例2-1】某企業(yè)要將產(chǎn)品包裝成Ⅰ、Ⅱ兩種規(guī)格，需要A、B兩種原材料的數(shù)量、獲利情況及兩種材料數(shù)量限制見(jiàn)表2-1，兩種規(guī)格的產(chǎn)品各包裝多少件可獲利最多？表2-1

問(wèn)題的提出【例2-1】某企業(yè)要將產(chǎn)品包裝成Ⅰ、Ⅱ兩種規(guī)格，表51第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件52第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件53第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件54上面兩個(gè)例子的共同特征：（1）每一個(gè)問(wèn)題都由一組決策變量來(lái)表示某一方案，一般情況下這些變量的取值是非負(fù)且連續(xù)的。（2）存在一定的約束條件，這些約束條件可以用一組線性的等式或不等式來(lái)表示。（3）都有一個(gè)要求達(dá)到的目標(biāo)，它用決策變量的線性函數(shù)（稱(chēng)為目標(biāo)函數(shù)）來(lái)表示。按照具體問(wèn)題的不同，要求目標(biāo)實(shí)現(xiàn)最小或最大。上面兩個(gè)例子的共同特征：55求取一組變量，使之既滿足線性約束條件，又使具有線性表達(dá)式的目標(biāo)函數(shù)取得極大值或極小值的一類(lèi)最優(yōu)化問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題，簡(jiǎn)稱(chēng)線性規(guī)劃（LP）。決策變量、約束條件和目標(biāo)函數(shù)是其三個(gè)基本要素。線性規(guī)劃定義求取一組變量，使之既滿足線性約束條件，線性規(guī)56第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件57第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件58第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件59線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式60第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件61第二節(jié)線性規(guī)劃模型的求解圖解法單純形法第二節(jié)線性規(guī)劃模型的求解圖解法62滿足所有約束條件的向量稱(chēng)為線性規(guī)劃問(wèn)題的可行解所有可行解構(gòu)成的集合稱(chēng)為可行域。在可行域中使得目標(biāo)函數(shù)值最大（或最?。┑目尚薪?，稱(chēng)為線性規(guī)劃問(wèn)題的最優(yōu)解。最優(yōu)解的全體稱(chēng)為最優(yōu)解集合。最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值稱(chēng)為最優(yōu)值。滿足所有約束條件的向量稱(chēng)為線性規(guī)劃問(wèn)題的可行解63圖解法圖解法64第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件65線性規(guī)劃解的可能情況唯一最優(yōu)解無(wú)窮多最優(yōu)解無(wú)界解無(wú)可行解線性規(guī)劃解的可能情況唯一最優(yōu)解66單純形法單67第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件68單純形法的基本原理：尋找一種規(guī)則，從一個(gè)基可行解轉(zhuǎn)移到另一個(gè)基可行解，目標(biāo)函數(shù)值是增大的，即“頂點(diǎn)轉(zhuǎn)換，目標(biāo)上升”。單純形法的基本原理：69對(duì)矩陣作初等變換：對(duì)矩陣作初等變換：70第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件71單純形法的計(jì)算步驟單純形法的計(jì)算步驟72第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件73解初始單純形表解初始單純形表74得到新的單純形表得到新的單純形表75得到新的單純形表得到新的單純形表76第三節(jié)線性規(guī)劃對(duì)偶問(wèn)題與

靈敏度分析對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的基本性質(zhì)靈敏度分析第三節(jié)線性規(guī)劃對(duì)偶問(wèn)題與

77對(duì)偶問(wèn)題的提出一般稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為例2-1線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，例2-1稱(chēng)為原問(wèn)題。對(duì)偶問(wèn)題的提出一般稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為例2-1線性規(guī)劃78表2-6原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系表2-6原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系79對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì)80第二章--物流運(yùn)籌學(xué)線性規(guī)劃課件81對(duì)偶問(wèn)題最優(yōu)解的經(jīng)濟(jì)解釋?zhuān)河白觾r(jià)格。線性規(guī)劃問(wèn)題中，當(dāng)某資源增加一個(gè)單位而其他資源都不變時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值的增量稱(chēng)為資源的影子價(jià)格。影子價(jià)格是對(duì)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)。對(duì)偶問(wèn)題最優(yōu)解的經(jīng)濟(jì)解釋?zhuān)河白觾r(jià)格。82靈敏度分析目標(biāo)函數(shù)的靈敏度分析約束右端向量的靈敏度分析約束方程系數(shù)的靈敏度分析增加一個(gè)新變量的靈敏度分析增加一個(gè)約束的靈敏度分析靈敏度分析目標(biāo)函數(shù)的靈敏度分析83第四節(jié)線性規(guī)劃在物流管理中的應(yīng)用直接應(yīng)用物資配送、調(diào)運(yùn)，人員的分配物流中心選址問(wèn)題配送系統(tǒng)的重新安排項(xiàng)目投資等間接應(yīng)用整數(shù)規(guī)劃中的割平面法和分支定界法運(yùn)輸問(wèn)題中的表上作業(yè)法第四節(jié)線性規(guī)劃在物流管理中的應(yīng)用直接應(yīng)用間接應(yīng)用84本章小結(jié)本章首先結(jié)合具體示例介紹了線性規(guī)劃問(wèn)題及其模型結(jié)構(gòu)、線性規(guī)劃的標(biāo)準(zhǔn)模型、一般線性規(guī)劃模型向標(biāo)準(zhǔn)型轉(zhuǎn)換的方法，接著定義了線性規(guī)劃可行解、最優(yōu)解的概念，重點(diǎn)闡述了求解線性規(guī)劃的一般方法——單純形方法，給出了單純形方法的具體求解步驟。之后，介紹了線性規(guī)劃的對(duì)偶問(wèn)題以及與原問(wèn)題關(guān)系，闡釋了對(duì)偶問(wèn)題的基本性質(zhì)，相應(yīng)地給出了求解線性規(guī)劃問(wèn)題的對(duì)偶單純形方法。并簡(jiǎn)單討論了目標(biāo)函數(shù)系數(shù)向量、約束矩陣以及約束右端項(xiàng)的變化給線性規(guī)劃最優(yōu)解帶來(lái)的影響。最后，介紹了線性規(guī)劃在物流領(lǐng)域中的典型應(yīng)用。本章的重點(diǎn)和難點(diǎn)是實(shí)際物流問(wèn)題的線性規(guī)劃建模以及求解線性規(guī)劃的單純形方法。本章小結(jié)本章首先結(jié)合具體示例介紹了線性規(guī)劃問(wèn)題及其模型結(jié)構(gòu)、85案例分析A公司分撥物流網(wǎng)絡(luò)負(fù)責(zé)把下線產(chǎn)品經(jīng)過(guò)配送中心發(fā)送到客戶手中，包括了原材料采購(gòu)、生產(chǎn)、運(yùn)輸、倉(cāng)儲(chǔ)和配送，除一些偏遠(yuǎn)地區(qū)外，該公司建立了非常完善的物流配送系統(tǒng)，A公司的物流運(yùn)輸途徑大部分都采用航空運(yùn)輸?，F(xiàn)在，該公司接到四類(lèi)貨物的配送要求，信息見(jiàn)表2-13。以A公司在實(shí)際工作中，優(yōu)化其現(xiàn)有配送資源為例，給出線性規(guī)劃模型，說(shuō)明線性規(guī)劃的實(shí)際應(yīng)用情況。案例分析A公司分撥物流網(wǎng)絡(luò)負(fù)責(zé)把下線產(chǎn)品經(jīng)過(guò)配送中心以A公司86表2-13案例相關(guān)數(shù)據(jù)表2-13案例相關(guān)數(shù)據(jù)87問(wèn)題分析負(fù)責(zé)運(yùn)輸產(chǎn)品的飛機(jī)有前倉(cāng)、中倉(cāng)和后倉(cāng)三個(gè)貨艙。各自所能