第二章物流運籌學線性規(guī)劃

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

產(chǎn)品規(guī)格AB利潤/（元/件）Ⅰ4212Ⅱ519材料限制208第四頁，共四十七頁，2022年，8月28日第五頁，共四十七頁，2022年，8月28日第六頁，共四十七頁，2022年，8月28日第七頁，共四十七頁，2022年，8月28日上面兩個例子的共同特征：（1）每一個問題都由一組決策變量來表示某一方案，一般情況下這些變量的取值是非負且連續(xù)的。（2）存在一定的約束條件，這些約束條件可以用一組線性的等式或不等式來表示。（3）都有一個要求達到的目標，它用決策變量的線性函數(shù)（稱為目標函數(shù)）來表示。按照具體問題的不同，要求目標實現(xiàn)最小或最大。第八頁，共四十七頁，2022年，8月28日求取一組變量，使之既滿足線性約束條件，又使具有線性表達式的目標函數(shù)取得極大值或極小值的一類最優(yōu)化問題稱為線性規(guī)劃問題，簡稱線性規(guī)劃（LP）。決策變量、約束條件和目標函數(shù)是其三個基本要素。線性規(guī)劃定義第九頁，共四十七頁，2022年，8月28日第十頁，共四十七頁，2022年，8月28日第十一頁，共四十七頁，2022年，8月28日第十二頁，共四十七頁，2022年，8月28日線性規(guī)劃問題的標準形式第十三頁，共四十七頁，2022年，8月28日第十四頁，共四十七頁，2022年，8月28日第二節(jié)線性規(guī)劃模型的求解圖解法單純形法第十五頁，共四十七頁，2022年，8月28日滿足所有約束條件的向量稱為線性規(guī)劃問題的可行解所有可行解構(gòu)成的集合稱為可行域。在可行域中使得目標函數(shù)值最大（或最?。┑目尚薪?，稱為線性規(guī)劃問題的最優(yōu)解。最優(yōu)解的全體稱為最優(yōu)解集合。最優(yōu)解對應(yīng)的目標函數(shù)值稱為最優(yōu)值。第十六頁，共四十七頁，2022年，8月28日圖解法第十七頁，共四十七頁，2022年，8月28日第十八頁，共四十七頁，2022年，8月28日線性規(guī)劃解的可能情況唯一最優(yōu)解無窮多最優(yōu)解無界解無可行解第十九頁，共四十七頁，2022年，8月28日單純形法第二十頁，共四十七頁，2022年，8月28日第二十一頁，共四十七頁，2022年，8月28日單純形法的基本原理：尋找一種規(guī)則，從一個基可行解轉(zhuǎn)移到另一個基可行解，目標函數(shù)值是增大的，即“頂點轉(zhuǎn)換，目標上升”。第二十二頁，共四十七頁，2022年，8月28日對矩陣作初等變換：第二十三頁，共四十七頁，2022年，8月28日第二十四頁，共四十七頁，2022年，8月28日單純形法的計算步驟第二十五頁，共四十七頁，2022年，8月28日第二十六頁，共四十七頁，2022年，8月28日解初始單純形表第二十七頁，共四十七頁，2022年，8月28日得到新的單純形表第二十八頁，共四十七頁，2022年，8月28日得到新的單純形表第二十九頁，共四十七頁，2022年，8月28日第三節(jié)線性規(guī)劃對偶問題與

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