數(shù)據(jù)、模型與決策（原書第16版）課件 第2章、線性規(guī)劃引論

數(shù)據(jù)、模型與決策,第16版第2章、線性規(guī)劃引論章節(jié)內(nèi)容2-1 一個(gè)簡(jiǎn)單的最大化問題2-2 圖解法2-3 極點(diǎn)和最優(yōu)解2-4 Par公司問題的計(jì)算機(jī)求解2-5 一個(gè)簡(jiǎn)單的最小化問題2-6 特例2-7 線性規(guī)劃的通用符號(hào)

本章小結(jié)學(xué)習(xí)目標(biāo)(1of2)完成本章后，你將能夠：LO2.1 確定可以在線性規(guī)劃中用作目標(biāo)函數(shù)或約束條件的線性數(shù)學(xué)關(guān)系。LO2.2 為線性規(guī)劃問題做出一張含目標(biāo)函數(shù)和約束條件的圖，并找出滿足約束條件的解。LO2.3 從線性規(guī)劃的圖形表示中確定可行域和極值點(diǎn)。LO2.4 使用圖解法求解線性規(guī)劃問題并解釋結(jié)果。LO2.5 從問題的文字描述中，公式化并解釋線性規(guī)劃模型的目標(biāo)函數(shù)和約束條件。學(xué)習(xí)目標(biāo)(2of2)LO2.6 在線性規(guī)劃的解中識(shí)別緊的、非緊的和冗余約束，并找到與約束條件相關(guān)的松弛/剩余變量。LO2.7 寫出線性規(guī)劃模型的標(biāo)準(zhǔn)形式。LO2.8 在Excel中建立線性規(guī)劃模型，并使用ExcelSolver求解。LO2.9 確定并解釋線性規(guī)劃的最優(yōu)解的情況:唯一最優(yōu)解，多重最優(yōu)解，不可行解，無界解。引言線性規(guī)劃是一種幫助管理者制定決策的解決問題的方法。線性規(guī)劃涉及在問題的數(shù)學(xué)模型僅包含線性函數(shù)時(shí)選擇行動(dòng)方案。所有線性規(guī)劃問題的目標(biāo)是某一數(shù)量的最大化或最小化。所有線性規(guī)劃問題都有約束，這些約束條件限制了目標(biāo)函數(shù)的取值。2-1一個(gè)簡(jiǎn)單的最大化問題Par公司高爾夫球袋業(yè)務(wù)Par公司是一個(gè)生產(chǎn)高爾夫器材的小型制造商，公司決定進(jìn)入中高價(jià)位的高爾夫球袋市場(chǎng)。分銷商對(duì)新產(chǎn)品十分感興趣，且同意買進(jìn)Par公司未來3個(gè)月內(nèi)生產(chǎn)的全部產(chǎn)品。生產(chǎn)的每個(gè)高爾夫袋都需要以下操作：切割和印染縫制成型檢查和包裝Par公司約束Par公司的生產(chǎn)還受各個(gè)部門生產(chǎn)時(shí)間的限制。經(jīng)過對(duì)各個(gè)生產(chǎn)部門工作量的研究，生產(chǎn)主管估計(jì)未來3個(gè)月內(nèi)每個(gè)部門可用的最大生產(chǎn)時(shí)間分別是：切割和印染630小時(shí)縫紉600小時(shí)成型708小時(shí)檢查和包裝135小時(shí)會(huì)計(jì)部門考慮了生產(chǎn)數(shù)據(jù)、相關(guān)變動(dòng)成本以及產(chǎn)品價(jià)格之后，得出了標(biāo)準(zhǔn)球袋和高級(jí)球袋的單位產(chǎn)品利潤分別為10美元和9美元。2-1Par公司問題的數(shù)學(xué)表述

2-1問題模型化問題模型化或稱建模，是將語言文字描述轉(zhuǎn)化為數(shù)學(xué)描述的過程。全面的了解問題。描述目標(biāo)。描述約束條件定義決策變量用決策變量寫出目標(biāo)用決策變量寫出約束條件最優(yōu)解是滿足所有約束條件的可行解，使得目標(biāo)函數(shù)值在最大化時(shí)盡可能大（或在最小化時(shí)盡可能?。．?dāng)有兩個(gè)變量時(shí)，可以使用圖解法求解線性規(guī)劃。2-2切割和印染約束線

2-2對(duì)應(yīng)切割和印染約束的可行解用陰影區(qū)域表示滿足切割和印染約束條件的解。滿足所有約束條件的解，被稱為可行解。圖中的陰影區(qū)域被稱為可行解的集合，簡(jiǎn)稱可行域。2-2對(duì)應(yīng)縫制、定型、檢查和包裝約束的可行解2-2圖解法求解過程可行域

最優(yōu)解

2-2圖解法求解最大化問題的步驟小結(jié)為每個(gè)約束條件畫出可行解圖形。確定出同時(shí)滿足所有約束條件的解的可行域。畫出目標(biāo)函數(shù)線，表示在特定目標(biāo)函數(shù)值下的決策變量值。沿目標(biāo)函數(shù)值增長(zhǎng)方向平移目標(biāo)函數(shù)線，直到移動(dòng)到可行域的邊界。取得最大值的目標(biāo)函數(shù)線上的可行解都是最優(yōu)解。2-2松弛變量所有變量都是非負(fù)的，并且所有約束條件都是等式形式的線性規(guī)劃被稱為標(biāo)準(zhǔn)型。通過向“小于或等于”約束添加松弛變量，并通過從“大于或等于”約束中減去剩余變量來實(shí)現(xiàn)標(biāo)準(zhǔn)型。松弛和剩余變量代表約束的左側(cè)和右側(cè)之間的差異。松弛和剩余變量在目標(biāo)函數(shù)中的系數(shù)等于0。在Par公司最優(yōu)解中，縫制和檢查與包裝部門有120和18小時(shí)的未用時(shí)間。Max10S+9D++++s.t.+1D++++=630+++++=6001S+++++=708+++++=1352-2標(biāo)準(zhǔn)型的線性規(guī)劃通常在制定線性規(guī)劃問題時(shí)會(huì)添加松弛變量，以表示閑置或未用容量。未用容量不會(huì)對(duì)利潤做出貢獻(xiàn)；因此，松弛變量在目標(biāo)函數(shù)中的系數(shù)為零。在添加了四個(gè)松弛變量（表示為S1、S2、S3和S4）之后，Par公司問題的數(shù)學(xué)模型變?yōu)?2-3極點(diǎn)與最優(yōu)解可行區(qū)域的頂點(diǎn)被稱為極點(diǎn)在尋找最優(yōu)解時(shí)，不必評(píng)估所有可行解點(diǎn)線性規(guī)劃問題的最優(yōu)解可以在可行區(qū)域的極點(diǎn)找到。Par公司問題有5個(gè)可行區(qū)域的極點(diǎn)。Par公司問題的最優(yōu)解位于極點(diǎn)③。2-4計(jì)算機(jī)求解現(xiàn)在對(duì)于有成千上萬個(gè)變量和約束條件的問題，用計(jì)算機(jī)求解就成了常規(guī)、可行的方法。一些領(lǐng)先的商業(yè)軟件包,包括CPLEX、Gurobi、LINGO、MOSEK和Excel求解器。也有免費(fèi)的計(jì)算機(jī)軟件包可用，包括Clp（COIN-OR線性規(guī)劃）、基于R語言的lpSolve軟件包和基于Python的PuLPlibrary軟件包。下面我們將解釋為Par公司問題提供的計(jì)算機(jī)輸出結(jié)果:最優(yōu)解提供了7668美元的利潤我們有540個(gè)標(biāo)準(zhǔn)和252個(gè)高級(jí)袋作為最優(yōu)生產(chǎn)量縫制和檢查與包裝部門分別有120和18小時(shí)的未用容量2-5M&D化學(xué)公司：一個(gè)簡(jiǎn)單的最小化問題M&D化學(xué)公司生產(chǎn)兩種用于生產(chǎn)肥皂和清洗劑的原材料。

M&化學(xué)公司的管理層確定A和B的總產(chǎn)量至少要達(dá)到350加侖。.公司的一個(gè)主要客戶訂購的125加侖a產(chǎn)品必須首先得到滿足。每加侖的處理時(shí)間:產(chǎn)品A需要2小時(shí)產(chǎn)品B需要1小時(shí)生產(chǎn)成本為產(chǎn)品A每加侖2美元，產(chǎn)品B每加侖3美元。公司最大可用工作時(shí)間是600小時(shí)。M&D的目標(biāo)是以最低的總生產(chǎn)成本滿足要求。在添加了非負(fù)約束(A,B≥0)之后，我們得到了M&D化學(xué)品問題的以下線性規(guī)劃：Max2A+3Bs.t.1A≥630產(chǎn)品A的需求1A+1B≥600總產(chǎn)量2A+1B≥708處理時(shí)間A,B≥02-5M&D化學(xué)公司問題的可行域和最優(yōu)解可行域

最優(yōu)解2-5圖解法求解最小化問題的步驟小結(jié)畫出每個(gè)約束條件的可行解。確定滿足所有約束條件的可行域。畫出目標(biāo)函數(shù)線，表示在特定目標(biāo)函數(shù)值下的決策變量值。沿目標(biāo)函數(shù)值減小方向平移目標(biāo)函數(shù)線，直至移動(dòng)到可行域的邊界。目標(biāo)函數(shù)線上具有最小值的可行解即為問題的最優(yōu)解。2-5剩余變量

Max2A+3B+++s.t.1A?=1251A+1B?=3502A+1B+=600≥02-6特例：多重最優(yōu)解

2-6特例：無可行解無可行解是指線性規(guī)劃問題，不存在滿足全部約束條件的解。在圖形中無可行解是指可行域，并不存在。假設(shè)管理層確定公司必須至少生產(chǎn)500個(gè)標(biāo)準(zhǔn)球帶和360個(gè)高級(jí)球帶。生產(chǎn)出500個(gè)標(biāo)準(zhǔn)球袋和360個(gè)高級(jí)球袋所需的資源無可行解原因可能包括：表述錯(cuò)誤管理者的過高期望約束條件過多的問題2-6特例：無界解

2-7線性規(guī)劃的通用符號(hào)我們?cè)赑ar公司問題中選擇了決策變量S和D，在M&D化學(xué)品問題中選擇了A和B，以便于記住這些決策變量在問題中代表的內(nèi)容。.這種方法對(duì)于涉及少量決策變量的線性規(guī)劃效果很好，但在處理涉及大量決策變量的問題時(shí)變得困難。在線性規(guī)劃問題中，更加通用的符號(hào)是帶有下標(biāo)的x

在Par公司例子中，我們可以將決策變量定義為：

x1=標(biāo)準(zhǔn)球袋的數(shù)量

x2=高級(jí)球袋的數(shù)量

使用這種變量命名方法時(shí)的一個(gè)缺點(diǎn)是我們不能夠輕松地識(shí)別出變量在數(shù)學(xué)模型中所代表的含義

如果模型中包含大量的決策變量，使用這種方法命名會(huì)相對(duì)比較容易。本章小結(jié)我們對(duì)如下兩個(gè)線性規(guī)劃問題進(jìn)行了建模:Par行數(shù)學(xué)建模的過程中，我們給出了線性規(guī)劃模型的一公司最大化問題和M&D化學(xué)公司的最小化問題。

對(duì)這兩個(gè)問題，我們給出了圖解法的求解過程，并將不同軟件包的求解結(jié)果展示在表格中。線性規(guī)劃模型是具有如下特點(diǎn)的數(shù)學(xué)模型。求解最大化或是最小化的線性目標(biāo)函數(shù)。存在線性約束集合。滿足非負(fù)約束的決策變量。松弛變量被用來將小于等于形式的約束條件轉(zhuǎn)變?yōu)榈扔谛?/p>