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

第二章物流運(yùn)籌學(xué)線性規(guī)劃第1頁(yè)，共47頁(yè)，2023年，2月20日，星期三學(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ī)劃的模型，并可利用單純形法求解。第2頁(yè)，共47頁(yè)，2023年，2月20日，星期三第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型問(wèn)題的提出線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式第3頁(yè)，共47頁(yè)，2023年，2月20日，星期三問(wèn)題的提出【例2-1】某企業(yè)要將產(chǎn)品包裝成Ⅰ、Ⅱ兩種規(guī)格，需要A、B兩種原材料的數(shù)量、獲利情況及兩種材料數(shù)量限制見(jiàn)表2-1，兩種規(guī)格的產(chǎn)品各包裝多少件可獲利最多？表2-1

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

靈敏度分析對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的基本性質(zhì)靈敏度分析第30頁(yè)，共47頁(yè)，2023年，2月20日，星期三對(duì)偶問(wèn)題的提出一般稱這個(gè)線性規(guī)劃問(wèn)題為例2-1線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，例2-1稱為原問(wèn)題。第31頁(yè)，共47頁(yè)，2023年，2月20日，星期三表2-6原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系第32頁(yè)，共47頁(yè)，2023年，2月20日，星期三對(duì)偶問(wèn)題的基本性質(zhì)第33頁(yè)，共47頁(yè)，2023年，2月20日，星期三第34頁(yè)，共47頁(yè)，2023年，2月20日，星期三對(duì)偶問(wèn)題最優(yōu)解的經(jīng)濟(jì)解釋：影子價(jià)格。線性規(guī)劃問(wèn)題中，當(dāng)某資源增加一個(gè)單位而其他資源都不變時(shí)，所引起目標(biāo)函數(shù)最優(yōu)值的增量稱為資源的影子價(jià)格。影子價(jià)格是對(duì)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)。第35頁(yè)，共47頁(yè)，2023年，2月20日，星期三靈敏度分析目標(biāo)函數(shù)的靈敏度分析約束右端向量的靈敏度分析約束方程系數(shù)的靈敏度分析增加一個(gè)新變量的靈敏度分析增加一個(gè)約束的靈敏度分析第36頁(yè)，共47頁(yè)，2023年，2月20日，星期三第四節(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è)法第37頁(yè)，共47頁(yè)，2023年，2月20日，星期三本章小結(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ī)劃的單純形方法。第38頁(yè)，共47頁(yè)，2023年，2月20日，星期三案例分析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)輸。現(xiàn)在，該公司接到四類貨物的配送要求，信息見(jiàn)表2-13。以A公司在實(shí)際工作中，優(yōu)化其現(xiàn)有配送資源為例，給出線性規(guī)劃模型，說(shuō)明線性規(guī)劃的實(shí)際應(yīng)用情況。第39頁(yè)，共47頁(yè)，2023年，2月20日，星期三重量/噸空間/（立方米/噸）利潤(rùn)/（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850表2-13案例相關(guān)數(shù)據(jù)第40頁(yè)，共47頁(yè)，2023年，2月20日，星期三問(wèn)題分析負(fù)責(zé)運(yùn)輸產(chǎn)品的飛機(jī)有前倉(cāng)、中倉(cāng)和后倉(cāng)三個(gè)貨艙。各自所能裝載的貨物最大重量和體積都有限制，且為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大允許重量成比例。該公司為了既滿足貨機(jī)本身的限制，又能獲得最大利潤(rùn)，建立了下面的模型：第41頁(yè)，共47頁(yè)，2023年，2月20日，星期三第42頁(yè)，共47頁(yè)，2023年，2月20日，星期三第43頁(yè)，共47頁(yè)，2023年，2月20日，星期三第44頁(yè)，共47頁(yè)，2023年，2月20日，星期三問(wèn)題（1）航空運(yùn)輸規(guī)劃時(shí)考慮的因素、目標(biāo)和約束條件的限制有哪些？（2）案例中建模的過(guò)程是怎樣的？（3）如何對(duì)上述建模進(jìn)一步改進(jìn)？第45頁(yè)，共47頁(yè)，2023年，2月20日，星期三實(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)分配方案。第46頁(yè)，共47頁(yè)，2023年，2月20日，星期三某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位