管理決策第二章

第2章數(shù)學(xué)規(guī)劃方法22023/5/19

2.1基本概念及模型

2.1.1數(shù)學(xué)規(guī)劃（1）數(shù)學(xué)規(guī)劃概述

研究對(duì)象：數(shù)值最優(yōu)化問(wèn)題 分支：線性規(guī)劃、非線性規(guī)劃、多目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、參數(shù)規(guī)劃、組合優(yōu)化和整數(shù)規(guī)劃、隨機(jī)規(guī)劃、模糊規(guī)劃、非光滑優(yōu)化、多層規(guī)劃、全局優(yōu)化、變分不等式與互補(bǔ)問(wèn)題等。

（2）一般形式

（3）數(shù)學(xué)規(guī)劃問(wèn)題的表述求滿足約束條件的x*，使成為最優(yōu)，而將x*稱為數(shù)學(xué)規(guī)劃問(wèn)題的最優(yōu)解，將稱為最優(yōu)值。32023/5/19

2.1.2線性規(guī)劃（1）線性規(guī)劃概念(Linearprogramming)

針對(duì)數(shù)學(xué)規(guī)劃，如果決策變量為可控的連續(xù)變量，且目標(biāo)函數(shù)和約束函數(shù)都是線性的，則稱此類數(shù)學(xué)規(guī)劃問(wèn)題為線性規(guī)劃問(wèn)題。（2）基本性質(zhì)比例性

要求每個(gè)決策變量在目標(biāo)函數(shù)和約束函數(shù)中，其貢獻(xiàn)與決策變量的值存在直接比例性?？杉有? 指所有決策變量對(duì)目標(biāo)函數(shù)和約束函數(shù)的貢獻(xiàn)是相互獨(dú)立的（包括正向貢獻(xiàn)和負(fù)向貢獻(xiàn)），目標(biāo)函數(shù)值等于每個(gè)決策變量各自對(duì)目標(biāo)函數(shù)貢獻(xiàn)的總和。確定性 指線性規(guī)劃中所有目標(biāo)函數(shù)和約束函數(shù)中的系數(shù)都是確定的常數(shù)，不含隨機(jī)因素。連續(xù)性 指所有的決策變量取值為連續(xù)的數(shù)。

2.1基本概念及模型42023/5/19

2.1.3整數(shù)規(guī)劃（1）整數(shù)變量

決策變量是整數(shù)，如電視產(chǎn)量，人的數(shù)量。（2）整數(shù)規(guī)劃問(wèn)題（IntegerProgramming，IP）

在數(shù)學(xué)規(guī)劃中，某些決策變量是整數(shù)變量的問(wèn)題。（3）整數(shù)變量的分類一般離散型整數(shù)變量，即取值為多個(gè)離散整數(shù)的變量，如產(chǎn)品個(gè)數(shù)等。0-1變量，即取值為0或者1的變量，如表示某一經(jīng)濟(jì)、管理活動(dòng)是否執(zhí)行等。2.1基本概念及模型52023/5/19

2.1.4目標(biāo)規(guī)劃目標(biāo)規(guī)劃（GoalProgramming，GP）概念解決多目標(biāo)決策的定量分析的數(shù)學(xué)規(guī)劃方法。2.1基本概念及模型

2.1.5非線性規(guī)劃非線性規(guī)劃（NonlinearProgramming，NLP）概念若某一數(shù)學(xué)規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束函數(shù)中至少有一個(gè)是非線性的，則稱此類數(shù)學(xué)規(guī)劃為非線性規(guī)劃。62023/5/19線性規(guī)劃的建模，是將語(yǔ)言文字上的問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題。線性規(guī)劃的建模從內(nèi)容上主要包括三部分：決策變量的識(shí)別與描述目標(biāo)函數(shù)的識(shí)別與描述約束條件的識(shí)別與描述2.2線性規(guī)劃建模方法72023/5/19

2.2.1決策變量的識(shí)別與描述決策變量

指運(yùn)籌學(xué)問(wèn)題或系統(tǒng)中待確定的某些變量，是決策方案的主要組成部分。

范例 牛奶廠生產(chǎn)計(jì)劃制定問(wèn)題2.2線性規(guī)劃建模方法2023/5/19某奶制品加工廠用牛奶生產(chǎn)甲、乙兩種奶制品;生產(chǎn)每千克甲需要0.25桶牛奶在A車間加工4工時(shí);生產(chǎn)每千克乙需要0.2桶牛奶在B車間加工2工時(shí)。預(yù)計(jì)生產(chǎn)出的甲、乙能夠全部售出；每千克甲獲利32元，每千克乙獲利16元。加工廠每天能得到80桶牛奶的供應(yīng)；每天A車間的最大生產(chǎn)能力為640工時(shí)；B車間的最大生產(chǎn)能力為500工時(shí)。試為該廠制定生產(chǎn)計(jì)劃，使得每天的獲利最大。2.2線性規(guī)劃建模方法92023/5/19決策變量的識(shí)別： 這個(gè)優(yōu)化問(wèn)題的目標(biāo)是使每天的獲利最大，要做的決策是制定生產(chǎn)計(jì)劃，即每天生產(chǎn)多少千克的甲奶制品和乙奶制品。決策變量的定義：設(shè)每天生產(chǎn)x1千克甲奶制品，x2千克乙奶制品。2.2線性規(guī)劃建模方法102023/5/19

2.2.2目標(biāo)函數(shù)的識(shí)別與描述目標(biāo)函數(shù)是最優(yōu)化標(biāo)準(zhǔn)或評(píng)價(jià)方法的數(shù)學(xué)描述，通常表示為決策變量的函數(shù)。在線性規(guī)劃中，目標(biāo)函數(shù)是決策變量的線性函數(shù)。范例中的目標(biāo)是使每天的獲利最大，設(shè)每天的獲利為z元。每千克甲可獲利32元，則x1千克甲可獲利32x1元。每千克乙可獲利16元，則x2千克乙可獲利16x2元，故目標(biāo)函數(shù)可表示為：2.2線性規(guī)劃建模方法2023/5/192.2.3約束條件的識(shí)別與描述約束條件：求目標(biāo)函數(shù)最優(yōu)值時(shí)的某些限制

約束函數(shù)決策變量的非正性/非負(fù)性約束

范例2.2線性規(guī)劃建模方法牛奶A車間B車間利潤(rùn)甲產(chǎn)品0.25桶4工時(shí)—32乙產(chǎn)品0.20桶—2工時(shí)16供應(yīng)量80桶640工時(shí)500工時(shí)122023/5/192.2線性規(guī)劃建模方法范例中，決策受到三方面的限制：

原料供應(yīng)：生產(chǎn)甲、乙兩種奶制品的原料總量不得超過(guò)每天的供應(yīng)，即0.25x1+0.2x2

≤80(桶)。A車間的生產(chǎn)能力：生產(chǎn)甲奶制品不得超過(guò)A車間的最大生產(chǎn)能力，即4x1

≤640。B車間的生產(chǎn)能力：生產(chǎn)乙奶制品不得超過(guò)B車間的最大生產(chǎn)能力，即2x2

≤500。132023/5/19

2.3.1線性規(guī)劃的求解方法線性規(guī)劃的求解方法圖解法、單純形法、橢球法、內(nèi)點(diǎn)法等基于常用的運(yùn)籌學(xué)軟件包進(jìn)行求解的，如winQSB、LINDO、LINGO和Excel等。

2.3線性規(guī)劃求解及決策分析142023/5/19

2.3線性規(guī)劃求解及決策分析范例的可行域O(0,0)z法向D(0,250)C(160,0)H(160,200)G(160,250)I(120,250)x2x1=1600.25x1+0.2x2=80x2=250z=0x1(0,520)152023/5/19線性規(guī)劃的解可能有以下幾種情況：唯一最優(yōu)解

存在一個(gè)頂點(diǎn)使得目標(biāo)函數(shù)達(dá)到最值。如上題中點(diǎn)H（160，200）。多重最優(yōu)解

線性規(guī)劃問(wèn)題有無(wú)數(shù)個(gè)最優(yōu)解。如：在上例中如果因市場(chǎng)需求變化，甲奶制品的的獲利減少為20元，其他條件不變，則目標(biāo)函數(shù)變?yōu)椋簔=20x1+16x2。此時(shí)當(dāng)目標(biāo)函數(shù)向上移動(dòng)時(shí)會(huì)與約束條件0.25x1+0.2x2

≤80重合，所以這條直線上在可行域內(nèi)的所有的點(diǎn)（即線段IH上的所有點(diǎn)）都是函數(shù)的最優(yōu)解。

2.3線性規(guī)劃求解及決策分析162023/5/19無(wú)界解，即最優(yōu)解無(wú)界目標(biāo)函數(shù)：maxz=x1+x2約束條件：

2.3線性規(guī)劃求解及決策分析z法向-3x1+2x2=6X22023/5/19

可行域（如下圖）：

2.3線性規(guī)劃求解及決策分析Z=0x1-x2=1X1182023/5/19無(wú)可行解

若在范例中再增加兩個(gè)約束條件5x1+4x2≥1800和5x1+4x2≤2200時(shí)，此線性規(guī)劃問(wèn)題的新可行域?yàn)榭沼?如下圖)，此時(shí)不存在滿足所有條件的x1和x2，即無(wú)可行解。2.3線性規(guī)劃求解及決策分析5x1+4x2≥18005x1+4x2≤2200192023/5/19

2.3.2線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化（1）線性規(guī)劃問(wèn)題（LP問(wèn)題）有許多不同形式目標(biāo)函數(shù)的優(yōu)化準(zhǔn)則包括max和min形式。函數(shù)性約束的表達(dá)式包括≧、=和≦形式。決策變量的本身約束包括非負(fù)性約束，非正性約束和無(wú)約束（自由變量）形式。2.3線性規(guī)劃求解及決策分析202023/5/19（2）LP問(wèn)題的標(biāo)準(zhǔn)形式（簡(jiǎn)稱標(biāo)準(zhǔn)形）

(M1):

2.3線性規(guī)劃求解及決策分析212023/5/19（3）LP問(wèn)題的簡(jiǎn)記形式（一）（M2）：2.3線性規(guī)劃求解及決策分析222023/5/19（3）

LP問(wèn)題的簡(jiǎn)記形式（二）（M3）：2.3線性規(guī)劃求解及決策分析其中，cj稱之為價(jià)值系數(shù)，bi稱之為右端常數(shù)項(xiàng)，aij稱之為消耗系數(shù)。232023/5/19（4）非標(biāo)準(zhǔn)形LP問(wèn)題的標(biāo)準(zhǔn)化方法：目標(biāo)函數(shù)若目標(biāo)函數(shù)形如minz=CTX，可令z′=－z，則有maxz′=－CTX，例如minz=4x1＋6x2可變換為maxz′=－4x1－6x2。函數(shù)性約束條件①若bi<0，則表達(dá)式兩邊同時(shí)乘以-1；②若函數(shù)性約束為“≤”形式，則在“≤”左側(cè)加上松弛變量；③若函數(shù)性約束為“≥”形式，則在“≥”左側(cè)減去剩余變量。決策變量

若xk≤0即滿足非正性約束時(shí)，令xk=－xk′,則xk′≥0；若xk為自由變量時(shí)，令xk=xk′－xk〞，且xk′,xk〞≥0。

2.3線性規(guī)劃求解及決策分析242023/5/19

2.3.3線性規(guī)劃的解（1）可行解 若令某一LP問(wèn)題的所有決策變量的解所構(gòu)成的向量記為X，則滿足LP問(wèn)題所有約束條件的X稱為可行解，所有可行解所構(gòu)成的集合稱為可行域，記為R。（2）最優(yōu)解 滿足目標(biāo)要求的可行解稱為最優(yōu)解，記為X*。最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記為Z*。2.3線性規(guī)劃求解及決策分析252023/5/19（3）基本解基本解的概念只適用于標(biāo)準(zhǔn)形LP問(wèn)題。范例的標(biāo)準(zhǔn)形：

2.3線性規(guī)劃求解及決策分析262023/5/19 設(shè)B是由標(biāo)準(zhǔn)型中函數(shù)性約束方程中的m個(gè)線性無(wú)關(guān)的系數(shù)列向量構(gòu)成的m階方陣且，則稱B為L(zhǎng)P問(wèn)題標(biāo)準(zhǔn)形(M)的一個(gè)基矩陣(簡(jiǎn)稱基)。 設(shè)其中

它是A（也是B）陣中第j個(gè)列向量，稱為基向量；其余n-m個(gè)列向量稱為非基向量?；蛄繉?duì)應(yīng)的變量稱為基變量；非基向量對(duì)應(yīng)的變量稱為非基變量。2.3線性規(guī)劃求解及決策分析272023/5/19 令所有非基變量等于0，基于(2-3)式中函數(shù)約束方程，則可得到所有基變量的取值，由此得到的解稱為一個(gè)關(guān)于基B的基本解，簡(jiǎn)稱基本解，也稱之為標(biāo)準(zhǔn)形LP問(wèn)題的一個(gè)基本解。若基本解中有一個(gè)或更多個(gè)基變量等于0，則稱之為退化基本解。譬如范例，取基矩陣為

2.3線性規(guī)劃求解及決策分析

由于，則x3，x4，x5為基變量，x1，x2為非基變量。令x1=0且x2=0，則范例標(biāo)準(zhǔn)型變?yōu)椋?82023/5/19

2.3線性規(guī)劃求解及決策分析求解上述方程組，可得關(guān)于B0的基本解為：292023/5/19另取

2.3線性規(guī)劃求解及決策分析

因?yàn)?，所以它也是一個(gè)基。它對(duì)應(yīng)的基變量為x2，x3，x4，非基變量為x1，x5。令這時(shí)范例標(biāo)準(zhǔn)型方程組變?yōu)椋?02023/5/19該方程組有唯一解，為

2.3線性規(guī)劃求解及決策分析于是可得到關(guān)于基的基本解為312023/5/19再取2.3線性規(guī)劃求解及決策分析為基（因）,同理可得關(guān)于基的基本解為：322023/5/19

2.3線性規(guī)劃求解及決策分析

再取為基（因），同理可得關(guān)于B3的基本解為：

它的前兩個(gè)分量為：恰好是范例的最優(yōu)解，故稱為最優(yōu)基本解。332023/5/19總結(jié)

有一個(gè)基，就有一個(gè)基本解。圖2-1中的點(diǎn)O，C，D，H，G，I各對(duì)應(yīng)范例的一個(gè)基本解。O(0，0)點(diǎn)對(duì)應(yīng)基本解X0，D(0，250)點(diǎn)對(duì)應(yīng)基本解X1，G(160，250)點(diǎn)對(duì)應(yīng)基本解X2，H(160，200）點(diǎn)對(duì)應(yīng)基本解X*

。

2.3線性規(guī)劃求解及決策分析342023/5/19

2.3.4線性規(guī)劃問(wèn)題的靈敏度分析概述概念

靈敏度分析是分析研究一個(gè)線性規(guī)劃模型中的參數(shù)取值的變化對(duì)最優(yōu)解或最優(yōu)基的影響。

靈敏度分析的任務(wù)之一就是確定參數(shù)的影響范圍。

可以借助WinQSB等運(yùn)籌學(xué)軟件包求解模型參數(shù)的影響范圍。

2.3線性規(guī)劃求解及決策分析352023/5/19當(dāng)某一右端常數(shù)項(xiàng)或價(jià)值系數(shù)在其影響范圍內(nèi)發(fā)生變化時(shí)，最優(yōu)基與最優(yōu)解的變化情況如下：（1）當(dāng)單獨(dú)某一bi在其影響范圍內(nèi)變化時(shí)，最優(yōu)基保持不變，但最優(yōu)解可能變化。（2）當(dāng)某一參數(shù)cj為非基變量的系數(shù)并單獨(dú)在其影響范圍內(nèi)變化時(shí)，最優(yōu)基保持不變，且最優(yōu)解和最優(yōu)值也保持不變。（3）當(dāng)某一參數(shù)cj為基變量的系數(shù)并單獨(dú)在其影響范圍內(nèi)變化時(shí)，最優(yōu)基與最優(yōu)解保持不變，但最優(yōu)值發(fā)生變化。2.3線性規(guī)劃求解及決策分析362023/5/19如范例，經(jīng)計(jì)算可得c1的影響范圍是[20,+)，c2的影響范圍是[0,25.6]。由于x1和x2均是基變量，所以當(dāng)c1和c2均在影響范圍內(nèi)變化時(shí)，最優(yōu)基與最優(yōu)解保持不變，但最優(yōu)值發(fā)生變化。另外，經(jīng)計(jì)算可得，每天可得的牛奶桶數(shù)b1的影響范圍是[40,90]，A車間的生產(chǎn)能力上限b2的影響范圍是[480，1280]，B車間的生產(chǎn)能力上限b3的影響范圍是[400,+)。上述三個(gè)參數(shù)在影響范圍內(nèi)變化時(shí)，最優(yōu)基保持不變，但是最優(yōu)解和最優(yōu)值有可能發(fā)生變化。2.3線性規(guī)劃求解及決策分析372023/5/19

2.4.1人力資源分配問(wèn)題

例2-1某醫(yī)院安排護(hù)士值班班次，每班工作時(shí)間及各時(shí)間段所需護(hù)士人數(shù)如表2-1所示。每班護(hù)士連續(xù)工作8小時(shí)，相鄰兩班人員有重疊，試求該醫(yī)院最少需要聘用多少名護(hù)士？表2-1各班次時(shí)間及所需人數(shù)

2.4管理中的線性規(guī)劃問(wèn)題班次工作時(shí)間所需人數(shù)12：00-6：004026：00-10：0040310：00-14：00196414：00-18：00118518：00-22：0045622：00-2：0040382023/5/19解：設(shè)xi表示第i班次開(kāi)始上班的護(hù)士人數(shù)，因?yàn)橐筮@六個(gè)班次開(kāi)始上班的護(hù)士人數(shù)之和最少，即要求 最小，建立模型如下：2.4管理中的線性規(guī)劃問(wèn)題392023/5/19經(jīng)求解，最優(yōu)解如下：

2.4管理中的線性規(guī)劃問(wèn)題第1班次上班的人數(shù)應(yīng)為40人；第2班次上班人數(shù)應(yīng)為83人；第3班次上班人數(shù)應(yīng)為113人；第4班次上班人數(shù)應(yīng)為5人；第5班次上班人數(shù)應(yīng)為40；此時(shí)所需護(hù)士人數(shù)達(dá)到最小，醫(yī)院至少聘用281人。402023/5/19

2.4.2生產(chǎn)計(jì)劃問(wèn)題

例2-2GX公司某車間生產(chǎn)3種型號(hào)的產(chǎn)品，該車間有4臺(tái)設(shè)備可以加工這3種產(chǎn)品。 各設(shè)備生產(chǎn)這些產(chǎn)品每小時(shí)所獲得的利潤(rùn)如表2-2所示，生產(chǎn)不同產(chǎn)品的速度參見(jiàn)表2-3。 預(yù)計(jì)市場(chǎng)下個(gè)月對(duì)三種產(chǎn)品的需求量分別為900千克，800千克，600千克； 這4臺(tái)設(shè)備每月用來(lái)生產(chǎn)此產(chǎn)品的最長(zhǎng)工作時(shí)間分別為90小時(shí)，70小時(shí)，80小時(shí)，90小時(shí)。 該車間在三種產(chǎn)品下月產(chǎn)量不超過(guò)下月需求量的前提下，應(yīng)該如何安排生產(chǎn)，才能保證下個(gè)月的利潤(rùn)最大？2.4管理中的線性規(guī)劃問(wèn)題412023/5/19表2-2設(shè)備生產(chǎn)產(chǎn)品的利潤(rùn)(單位：元/小時(shí))產(chǎn)品類型設(shè)備編號(hào)1234I100120110100II10011090110III1101208090

2.4管理中的線性規(guī)劃問(wèn)題表2-3設(shè)備生產(chǎn)產(chǎn)品的速度(單位：千克/小時(shí))產(chǎn)品類型設(shè)備編號(hào)1234I73410II6754III5753422023/5/19解：設(shè)xij表示安排在第j臺(tái)設(shè)備上生產(chǎn)第i種產(chǎn)品的小時(shí)數(shù)，該問(wèn)題的線性規(guī)劃模型可以表示為： 目標(biāo)函數(shù)：

2.4管理中的線性規(guī)劃問(wèn)題約束條件：

432023/5/19經(jīng)求解，最優(yōu)解如下：

2.4管理中的線性規(guī)劃問(wèn)題計(jì)算結(jié)果表明:1號(hào)設(shè)備應(yīng)被安排生產(chǎn)第III種產(chǎn)品90小時(shí)；2號(hào)設(shè)備應(yīng)被安排生產(chǎn)第I種產(chǎn)品70小時(shí)；3號(hào)設(shè)備應(yīng)被安排生產(chǎn)第I種產(chǎn)品80小時(shí)；4號(hào)設(shè)備應(yīng)被安排生產(chǎn)II種產(chǎn)品90小時(shí)。442023/5/19

2.4.3套材下料問(wèn)題

例2-3DL制造廠有一批長(zhǎng)度為3米的鋼管，為制造某零件，需要將鋼管截成長(zhǎng)度分別為200厘米，110厘米和55厘米的三種管料，三種管料的需求量分別為200，400和100根。 把一根鋼管截成幾段需要的管料時(shí)，一般會(huì)產(chǎn)生殘料。例如，把3米長(zhǎng)的鋼管截成1根200厘米，和1根55厘米的管料，要剩殘料45厘米；如果截成2根的110厘米，1根55厘米的管材，要剩殘料25厘米。根據(jù)實(shí)際情況共有4種截分方案，如表2-4所示。請(qǐng)問(wèn)采用4種截法各截多少根鋼管，既能滿足需求量，又能使殘料最少？

2.4管理中的線性規(guī)劃問(wèn)題452023/5/19表2-4鋼管的截分方案2.4管理中的線性規(guī)劃問(wèn)題管料類型（厘米）截分方案ⅠⅡⅢⅣ20010001100210551135殘料45252525解：定義決策變量：設(shè)xi表示采用第i種截分方案截?cái)嗟匿摴軘?shù)量。則截得的200厘米鋼管的數(shù)量為：x1截得的110厘米鋼管的數(shù)量為：

截得的55厘米鋼管的數(shù)量為：殘料的數(shù)量為：

462023/5/19目標(biāo)函數(shù)：約束條件：

2.4管理中的線性規(guī)劃問(wèn)題經(jīng)求解，最優(yōu)解如下：計(jì)算結(jié)果表明，按照截法Ⅰ截200根鋼管，按截法Ⅱ截200根鋼管，鋼管能滿足管料的需求量，并且使殘料達(dá)到最小值14000厘米。472023/5/19

2.4.4配料問(wèn)題

例2-4某食品廠用原料A,B,C加工生產(chǎn)甲，乙，丙三種不同口味的餅干。已知各種口味的餅干中A,B,C的含量，原料成本，各種原料每月的限制用量，三種口味餅干的單位加工費(fèi)及售價(jià)如表2-5所示。表2-52.4管理中的線性規(guī)劃問(wèn)題ABC加工費(fèi)/元/千克售價(jià)/元/千克甲≥30%≤20%≥40%16乙≤40%≥60%0.75.8丙≥60%≤20%0.65.4原材料成本/元/千克232每月限制用量/千該廠每月生產(chǎn)這三種口味的餅干各多少千克，使得利潤(rùn)最大？482023/5/19解：設(shè)為生產(chǎn)i種餅干所使用的j種原材料數(shù)量。i=1,2,3分別代表甲、乙、丙，j=1,2,3分別代表A,B,C。目標(biāo)函數(shù)：

2.4管理中的線性規(guī)劃問(wèn)題原料的約束條件：492023/5/19產(chǎn)品中各種原料含量的約束條件：

2.4管理中的線性規(guī)劃問(wèn)題等價(jià)于502023/5/19該問(wèn)題的總體模型：

2.4管理中的線性規(guī)劃問(wèn)題512023/5/19經(jīng)求解，最優(yōu)解如下：

2.4管理中的線性規(guī)劃問(wèn)題計(jì)算結(jié)果表明生產(chǎn)計(jì)劃如下：生產(chǎn)甲種餅干共2850千克；使用A原料1140千克，B原料570千克，C原料1140千克；生產(chǎn)乙種餅干共600千克，使用B原料240千克，C原料360千克；生產(chǎn)丙種餅干共450千克，使用A原料360千克，B原料90千克。這樣可以獲得最大利潤(rùn)10770元。522023/5/19

2.4.5投資問(wèn)題

例2-5某公司現(xiàn)有資金3000萬(wàn)元，今后五年內(nèi)計(jì)劃對(duì)以下項(xiàng)目進(jìn)行投資：項(xiàng)目A：從第一年到第五年每年年初都可以投資，當(dāng)年年末能 收回本利105%。項(xiàng)目B：從第一年到第四年每年年初都可以投資，次年年末收 回本利135%，但規(guī)定每年最大投資額不能超過(guò)450萬(wàn)元。項(xiàng)目C：第三年年初可以投資，到第五年年末能收回本利130%， 但規(guī)定最大投資額不能超過(guò)1200萬(wàn)元。項(xiàng)目D：第二年年初可以投資，到第五年年末能收回本利140%， 但規(guī)定最大投資額不能超過(guò)1500萬(wàn)元。應(yīng)如何確定這些項(xiàng)目每年的投資額，從而使得第五年末擁有資金的本利金額最大？

2.4管理中的線性規(guī)劃問(wèn)題532023/5/19解：設(shè)xij為第i年初投資于項(xiàng)目j的金額（單位：萬(wàn)元），根據(jù)題意將變量列于表2-6中。表2-62.4管理中的線性規(guī)劃問(wèn)題年份項(xiàng)目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D第一年：該公司年初有資金3000萬(wàn)元，故有 x1A+x1B=3000第二年：該公司在第二年初擁有資金僅為項(xiàng)目A在第一年投資額所收回的本息105%x1A，故有x2A+x2B+x2D=1.05x1A

542023/5/19第三年：第三年年初的資金額是從項(xiàng)目A第二年投資和項(xiàng)目B第一年投資所回收的本息總和，即1.05x2A+1.35x1B，故有x3A+x3B+x3C=1.05x2A+1.35x1B第四年：同以上分析，可得x4A+x4B

=1.05x3A+1.35x2B第五年：同一上分析，可得x5A=1.05x4A+1.35x3B另外，對(duì)項(xiàng)目B，C，D的投資額的限制有xiB≤450（i=1,2,3,4）x3C≤1200X2D≤1500此問(wèn)題要求在第五年年末該部門所擁有的資金額達(dá)到最大，則目標(biāo)函數(shù)可以表示為：

2.4管理中的線性規(guī)劃問(wèn)題552023/5/19建立數(shù)學(xué)模型為：

2.4管理中的線性規(guī)劃問(wèn)題562023/5/19經(jīng)求解，最優(yōu)解如下：2.4管理中的線性規(guī)劃問(wèn)題由結(jié)果可知，第一年對(duì)項(xiàng)目A投資2550萬(wàn)元，對(duì)項(xiàng)目B投資450萬(wàn)元；第二年對(duì)項(xiàng)目A投資727.4999萬(wàn)元，對(duì)項(xiàng)目B投資450萬(wàn)元，對(duì)項(xiàng)目D投資1500萬(wàn)元；第三年對(duì)項(xiàng)目A投資0萬(wàn)元，對(duì)項(xiàng)目B投資450萬(wàn)元，對(duì)項(xiàng)目C投資921.3749萬(wàn)元；第四年對(duì)項(xiàng)目A投資157.5萬(wàn)元，對(duì)項(xiàng)目B投資450萬(wàn)元，第五年對(duì)項(xiàng)目A投資772.875萬(wàn)元；第五年年末擁有資金的本利金額為4716.806萬(wàn)元。572023/5/19

2.4.6市場(chǎng)營(yíng)銷調(diào)查問(wèn)題例2-6

一個(gè)廚具制造公司要調(diào)查消費(fèi)者對(duì)近期推出的一款洗碗機(jī)的反應(yīng)，計(jì)劃展開(kāi)個(gè)人入戶調(diào)查，擬從有老人的家庭和無(wú)老人的家庭中獲得回答，計(jì)劃要調(diào)查的家庭總數(shù)為800個(gè)，并且要同時(shí)開(kāi)展工作日和雙休日調(diào)查，另外對(duì)于此次調(diào)查還有以下要求：1．至少訪問(wèn)300個(gè)有老人的家庭；2．至少訪問(wèn)300個(gè)無(wú)老人的家庭；3．雙休日訪問(wèn)的家庭數(shù)量必須不少于工作日訪問(wèn)的家庭數(shù)量的1/2；4．至少40％有老人的家庭必須在雙休日訪問(wèn)；5．至少40％無(wú)老人的家庭必須在雙休日訪問(wèn)。預(yù)計(jì)的調(diào)查費(fèi)用如表2-7所示：

2.4管理中的線性規(guī)劃問(wèn)題582023/5/19表2-7調(diào)查費(fèi)用

2.4管理中的線性規(guī)劃問(wèn)題調(diào)查費(fèi)用家庭情況工作日（元/家）雙休日（元/家）有老人1216無(wú)老人1014應(yīng)怎樣安排調(diào)查計(jì)劃以使總調(diào)查費(fèi)用最??？解：設(shè)WO：工作日調(diào)查的有老人的家庭個(gè)數(shù) RO：雙休日調(diào)查的有老人的家庭個(gè)數(shù) WNO：工作日調(diào)查的無(wú)老人的家庭個(gè)數(shù) RNO：雙休日調(diào)查的無(wú)老人的家庭個(gè)數(shù) z：總調(diào)查費(fèi)用則該問(wèn)題的數(shù)學(xué)模型為：592023/5/19 經(jīng)求解，最優(yōu)解如下：

2.4管理中的線性規(guī)劃問(wèn)題由結(jié)果可知，當(dāng)工作日調(diào)查的有老人的家庭個(gè)數(shù)為180個(gè)，雙休日調(diào)查的有老人的家庭個(gè)數(shù)為120個(gè)，工作日調(diào)查的無(wú)老人的家庭個(gè)數(shù)為300個(gè)，雙休日調(diào)查的無(wú)老人的家庭個(gè)數(shù)為200個(gè)時(shí)，總調(diào)查費(fèi)用最小，最小調(diào)查費(fèi)用為9880元。602023/5/19

2.4.7收益管理問(wèn)題例2-7某航空公司的一架波音737客機(jī)的航線為：廣州——上?！筮B，飛機(jī)早上從廣州飛往大連，中途經(jīng)停上海，飛機(jī)最多可容納112個(gè)座位。圖2-4說(shuō)明了該客機(jī)的航線狀況。該航空公司為此客機(jī)制定了兩種級(jí)別的機(jī)票：A級(jí)別和B級(jí)別機(jī)票。表2-8詳細(xì)說(shuō)明了該客機(jī)各旅程的兩種級(jí)別機(jī)票的票價(jià)和需求預(yù)測(cè)情況。

2.4管理中的線性規(guī)劃問(wèn)題圖2-4客機(jī)的航線狀況612023/5/192.4管理中的線性規(guī)劃問(wèn)題出發(fā)地目的地機(jī)票級(jí)別票價(jià)(元)預(yù)測(cè)的需求數(shù)廣州上海B64034上海大連B31041廣州大連B87547廣州上海A102025上海大連A58031廣州大連A137517表2-8客機(jī)各旅程的兩種級(jí)別機(jī)票的票價(jià)和需求預(yù)測(cè)情況應(yīng)如何安排該客機(jī)各旅程的兩種級(jí)別機(jī)票的數(shù)量以使總收益最大化。解：設(shè)GSB：廣州到上海旅程的B級(jí)機(jī)票數(shù) SDB：上海到大連旅程的B級(jí)機(jī)票數(shù) GDB：廣州到大連旅程的B級(jí)機(jī)票數(shù) GSA：廣州到上海旅程的A級(jí)機(jī)票數(shù) SDA：上海到大連旅程的A級(jí)機(jī)票數(shù) GDA：廣州到大連旅程的A級(jí)機(jī)票數(shù) z：總收益622023/5/19此問(wèn)題的數(shù)學(xué)模型為：

2.4管理中的線性規(guī)劃問(wèn)題632023/5/192.4管理中的線性規(guī)劃問(wèn)題經(jīng)求解，最優(yōu)解如下：由結(jié)果可知： 廣州到上海旅程的B級(jí)機(jī)票數(shù)為34； 上海到大連旅程的B級(jí)機(jī)票數(shù)為28； 廣州到大連旅程的B級(jí)機(jī)票數(shù)為36； 廣州到上海旅程的A級(jí)機(jī)票數(shù)為25； 上海到大連旅程的A級(jí)機(jī)票數(shù)為31； 廣州到大連旅程的A級(jí)機(jī)票數(shù)為17； 最大總收益為128795元。642023/5/19

2.5.1線性規(guī)劃的對(duì)偶問(wèn)題引例（1）在周長(zhǎng)為4米的矩形中，怎樣的矩形面積最大？（2）在面積為1米的矩形中，怎樣的矩形周長(zhǎng)最??？答案均是邊長(zhǎng)為1米的正方形。上述兩個(gè)問(wèn)題就互為對(duì)偶問(wèn)題（Dualproblem）。

2.5線性規(guī)劃的對(duì)偶問(wèn)題652023/5/19在2.2節(jié)提出的范例中，假定有另一個(gè)企業(yè)欲收購(gòu)該企業(yè)擁有的資源（原擬用于每天生產(chǎn)這兩種奶制品的牛奶供應(yīng)量，A車間生產(chǎn)能力和B車間生產(chǎn)能力三種資源），至少應(yīng)付出多少代價(jià)（如何考慮這三種資源的出售價(jià)格），才能使該企業(yè)愿意放棄生產(chǎn)活，出讓資源動(dòng)呢?*顯然原企業(yè)放棄自己組織生產(chǎn)活動(dòng)的條件時(shí)，對(duì)同等數(shù)量資源出讓的代價(jià)不低于原企業(yè)自己組織生產(chǎn)活動(dòng)時(shí)的產(chǎn)值。

2.5線性規(guī)劃的對(duì)偶問(wèn)題662023/5/19設(shè)y1，y2，y3分別為出售每桶牛奶、A車間1工時(shí)，B車間1工時(shí)所得利潤(rùn)，為總利潤(rùn)。由于原擬用0.25桶牛奶、4個(gè)A車間工時(shí)生產(chǎn)1千克甲奶制品可創(chuàng)造32元利潤(rùn)，所以出售上述數(shù)量的各資源所獲得的利潤(rùn)至少應(yīng)不低于32元，于是有：2.5線性規(guī)劃的對(duì)偶問(wèn)題

同理可得：把原擬用于生產(chǎn)甲、乙兩種奶制品的三種資源全部售出所獲得的總利潤(rùn)如下：

672023/5/19該問(wèn)題的LP模型：

2.5線性規(guī)劃的對(duì)偶問(wèn)題其最優(yōu)解為：恰好符合min=maxz，即。我們把上述LP模型稱為范例原始LP模型的對(duì)偶問(wèn)題。682023/5/19

2.5.2線性規(guī)劃的對(duì)偶關(guān)系

2.5線性規(guī)劃的對(duì)偶問(wèn)題LP問(wèn)題及其對(duì)偶問(wèn)題的一般關(guān)系對(duì)偶問(wèn)題(P)(D)備注目標(biāo)要求maxmin本質(zhì)屬性不變規(guī)范不等式約束的式號(hào)≤≥與自身目標(biāo)要求相反系數(shù)陣(aij)m×n(aji)n×m

互為轉(zhuǎn)置陣函數(shù)約束與變量第k個(gè)約束第k個(gè)變量約束個(gè)數(shù)=變量個(gè)數(shù)第k個(gè)右端常數(shù)=第k個(gè)價(jià)值系數(shù)k=i或ji=1，2，…，mj=1，2，…，n(非)規(guī)范不等式約束非負(fù)(正)變量等式約束自由變量692023/5/19例2-8

試寫(xiě)出下述LP問(wèn)題的對(duì)偶問(wèn)題2.5線性規(guī)劃的對(duì)偶問(wèn)題解：對(duì)偶問(wèn)題的目標(biāo)函數(shù)：702023/5/19由x1的系數(shù)得對(duì)偶問(wèn)題的第一個(gè)約束：

2.5線性規(guī)劃的對(duì)偶問(wèn)題由x2的系數(shù)得對(duì)偶問(wèn)題的第二個(gè)約束：由x3的系數(shù)得對(duì)偶問(wèn)題的第三個(gè)約束：變量y1，y2，y3：712023/5/19聯(lián)立，得出所求解的對(duì)偶問(wèn)題：

2.5線性規(guī)劃的對(duì)偶問(wèn)題722023/5/19

2.5.3對(duì)偶變量的經(jīng)濟(jì)學(xué)含義影子價(jià)格(ShadowPrice)由相關(guān)的對(duì)偶性質(zhì)可證明成立，可見(jiàn)，在經(jīng)濟(jì)上可表示為bi單獨(dú)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的最優(yōu)值的增量。

2.5線性規(guī)劃的對(duì)偶問(wèn)題732023/5/19范例的三種資源的討論：

（1）牛奶供應(yīng)量增加1桶。約束條件變?yōu)椋?.25x1+0.2x2

﹤81，這相當(dāng)于把圖2-5中的界線②移到②*,這時(shí)最優(yōu)點(diǎn)變H2(160,205)，相應(yīng)的目標(biāo)為z*=8400,則△z=z*―z=80，即牛奶的影子價(jià)格為80元/桶。

2.5線性規(guī)劃的對(duì)偶問(wèn)題圖2-50.25x1+0.2x2=81②②*H2(160,205)742023/5/19

(2)A車間最大生產(chǎn)能力增加1個(gè)工時(shí)。約束條件變?yōu)?x1≤641，這相當(dāng)于把可行域的界限①移到①*，最優(yōu)點(diǎn)變成H1（160.25，199.6875）,相應(yīng)的目標(biāo)為z*=8323,則△z=z*―z=3，即A車間生產(chǎn)能力的影子價(jià)格為3元/工時(shí)。 (3)B車間最大生產(chǎn)能力增加1個(gè)工時(shí)。約束條件變?yōu)?x2≤501，這相當(dāng)于把可行域的界限③移到③*，但最優(yōu)點(diǎn)仍為H（160，200）,所以相應(yīng)的目標(biāo)不變?yōu)閦*=8320,則△z=z*―z=0，即B車間生產(chǎn)能力的影子價(jià)格為0元/工時(shí)。

2.5線性規(guī)劃的對(duì)偶問(wèn)題

影子價(jià)格是對(duì)有限資源的估價(jià)。并且如果當(dāng)企業(yè)的目標(biāo)是實(shí)現(xiàn)最大產(chǎn)值時(shí)，可利用對(duì)資源i總存量進(jìn)行評(píng)估。若設(shè)資源i的市場(chǎng)價(jià)值為，則當(dāng)時(shí)，企業(yè)可以買進(jìn)該資源，即增加其總存量；當(dāng)時(shí)，企業(yè)可以賣出該資源，即減少其總存量；從而實(shí)現(xiàn)產(chǎn)值最大化。752023/5/19

2.5線性規(guī)劃的對(duì)偶問(wèn)題圖2-5O(0,0)D(0,250)C(160,0)H(160,200)G(160,250)I(120,250)x2①x1=160②0.25x1+0.2x2=80③x2=250x1H2（160，205）H1（160.25，199.6875）②*0.25x1+0.2x2=81①*x1=160.25③*x2=250762023/5/19

2.6.1整數(shù)線性規(guī)劃的類型基于整數(shù)規(guī)劃中決策變量的類型分類純整數(shù)規(guī)劃（PureIntegerProgramming，PureIP）混合整數(shù)規(guī)劃（MixedIntegerprogramming，MixedIP）0-1整數(shù)規(guī)劃從目標(biāo)函數(shù)與約束函數(shù)是否為線性的角度分類整數(shù)線性規(guī)劃（ILP）整數(shù)非線性規(guī)劃（INLP）

2.6整數(shù)線性規(guī)劃問(wèn)題772023/5/19

2.6.2工廠的選址問(wèn)題例2-9某水泥公司欲向大連、沈陽(yáng)、天津、北京、太原、青島六地銷售水泥，六地的需求量如表2-10所示?，F(xiàn)擬在石家莊、本溪、煙臺(tái)三地中選址建設(shè)水泥廠來(lái)生產(chǎn)水泥以滿足供應(yīng)，且規(guī)定一地最多只能建一個(gè)工廠。這三地的生產(chǎn)能力及固定費(fèi)用如表2-11所示，三個(gè)可能的產(chǎn)地至六個(gè)銷售地的運(yùn)價(jià)如表2-12所示。應(yīng)如何選擇廠址和安排調(diào)運(yùn)以使每天各廠固定費(fèi)用與總運(yùn)費(fèi)之和最少？

2.6整數(shù)線性規(guī)劃問(wèn)題782023/5/19表2-10各銷售地的需求量銷售地需求量（噸/天）大連270沈陽(yáng)205天津300北京360太原120青島280

2.6整數(shù)線性規(guī)劃問(wèn)題表2-11各生產(chǎn)地的生產(chǎn)能力及固定費(fèi)用生產(chǎn)地生產(chǎn)能力（噸/天）固定費(fèi)用（元/天）石家莊135027000本溪108021000煙臺(tái)120030500792023/5/19

表2-12各生產(chǎn)地至各銷售地的運(yùn)價(jià)

2.6整數(shù)線性規(guī)劃問(wèn)題生產(chǎn)地銷售地運(yùn)價(jià)（元/噸）石家莊大連72沈陽(yáng)63天津21北京17太原14青島40本溪大連25沈陽(yáng)7天津50北京58太原85青島90煙臺(tái)大連20沈陽(yáng)95天津53北京62太原70青島15802023/5/19解:

設(shè)n：銷售地個(gè)數(shù)，這里取值為6m：生產(chǎn)地個(gè)數(shù)，這里取值為3bj：j銷售地的需求量（噸/天），取值見(jiàn)表2-10ai：i地的生產(chǎn)能力（噸/天），取值見(jiàn)表2-11di：i地的固定費(fèi)用（元/天），取值見(jiàn)表2-11cij：i地至銷售地j的運(yùn)價(jià)（元/噸），取值見(jiàn)表2-12xij：從i地至銷售地j的運(yùn)量（噸/天）z：總費(fèi)用（元/天）

2.6整數(shù)線性規(guī)劃問(wèn)題812023/5/19該類問(wèn)題的數(shù)學(xué)模型為：

2.6整數(shù)線性規(guī)劃問(wèn)題822023/5/19本例的數(shù)學(xué)模型：2.6整數(shù)線性規(guī)劃問(wèn)題832023/5/19經(jīng)求解，最優(yōu)解如下：

2.6整數(shù)線性規(guī)劃問(wèn)題由結(jié)果可知,在石家莊和本溪兩地建廠；由本溪運(yùn)往大連270噸，本溪運(yùn)往沈陽(yáng)205噸；由石家莊運(yùn)往天津300噸，石家莊運(yùn)往北京360噸；石家莊運(yùn)往太原120噸，石家莊運(yùn)往青島280噸，此時(shí)每天各廠固定費(fèi)用與總運(yùn)費(fèi)之和最少，為81485元。842023/5/19

2.6.3固定成本問(wèn)題例2-10東方文具制品廠要生產(chǎn)小、中、大三種型號(hào)的黑板，所需資源為玻璃板、勞動(dòng)力和機(jī)器設(shè)備。制造這三種黑板所需的各種資源數(shù)量如表2-13所示：表2-13

2.6整數(shù)線性規(guī)劃問(wèn)題資源小號(hào)黑板中號(hào)黑板大號(hào)黑板玻璃板（單位：塊）勞動(dòng)力(單位：人日)機(jī)器設(shè)備（單位：臺(tái)時(shí)）121232443不考慮固定費(fèi)用，每種黑板售出一塊所得的利潤(rùn)分別為20元、30元、40元，可使用的玻璃板為100塊，勞動(dòng)力為100人日，機(jī)器設(shè)備為50臺(tái)時(shí)。此外，不管每種黑板制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)25元，中號(hào)50元，大號(hào)75元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)最大。852023/5/19解：設(shè)x1，x2，x3分別為小號(hào)黑板、中號(hào)黑板和大號(hào)黑板的生產(chǎn)數(shù)量。

2.6整數(shù)線性規(guī)劃問(wèn)題目標(biāo)函數(shù)：

玻璃板、勞動(dòng)力以及機(jī)器設(shè)備資源限制的約束條件：

862023/5/19為了避免出現(xiàn)某種黑板不投入固定費(fèi)用就生產(chǎn)這樣一種不合理的情況，必須加上以下約束條件：

2.6整數(shù)線性規(guī)劃問(wèn)題這里M是充分大的數(shù)，從一個(gè)黑板至少要兩個(gè)勞動(dòng)力約束條件可知，各種黑板的制造數(shù)量不會(huì)超過(guò)50塊，我們可以取M為50，即得872023/5/19此問(wèn)題的數(shù)學(xué)模型：

2.6整數(shù)線性規(guī)劃問(wèn)題882023/5/19經(jīng)求解，最優(yōu)解如下：2.6整數(shù)線性規(guī)劃問(wèn)題生產(chǎn)50塊小號(hào)黑板可得最大利潤(rùn)975元；約束（1）的松弛變量為50，即有50塊玻璃板沒(méi)用；約束（2）的松弛變量為0，即勞動(dòng)力充分利用；約束（3）的松弛變量為0，即機(jī)器設(shè)備全部用完。892023/5/19

2.6.1投資決策問(wèn)題例2-11凌格電器公司正在考慮隨后4年內(nèi)有不同資金要求的投資項(xiàng)目。面對(duì)每年有限的可用資金，公司管理者需要選擇部分項(xiàng)目進(jìn)行投資。每個(gè)項(xiàng)目的投資凈現(xiàn)值、資金需求和公司4年內(nèi)擁有的可用投資的資金數(shù)量如表2-14所示。另外，由于公司現(xiàn)有庫(kù)存能力嚴(yán)重不足，公司決定倉(cāng)庫(kù)1和倉(cāng)庫(kù)2至少有一個(gè)需要擴(kuò)建。試求該公司凈現(xiàn)值總和最大的投資組合方案。

2.投資決策問(wèn)題902023/5/19表2-14

2.6整數(shù)線性規(guī)劃問(wèn)題解：

設(shè)決策變量x1、x2、x3、x4、x4分別代表是否投資工廠擴(kuò)建項(xiàng)目、倉(cāng)庫(kù)1擴(kuò)建項(xiàng)目、倉(cāng)庫(kù)2擴(kuò)建項(xiàng)目、設(shè)備更新項(xiàng)目和新產(chǎn)品研發(fā)項(xiàng)目

。項(xiàng)目工廠擴(kuò)建倉(cāng)庫(kù)1擴(kuò)建倉(cāng)庫(kù)2擴(kuò)建設(shè)備更新新產(chǎn)品研發(fā)凈現(xiàn)值10050403050可用資金第一年資金201010102050第二年資金2015201540第三年資金201510101550第四年資金30102040912023/5/19目標(biāo)函數(shù)：

2.6整數(shù)線性規(guī)劃問(wèn)題每年的資金約束可以分別表示如下：關(guān)于倉(cāng)庫(kù)1和倉(cāng)庫(kù)2至少有一個(gè)需要擴(kuò)建的約束可以表示如下：922023/5/19

2.6整數(shù)線性規(guī)劃問(wèn)題數(shù)學(xué)模型為：經(jīng)計(jì)算，最優(yōu)解為：由計(jì)算結(jié)果可知未來(lái)4年內(nèi)應(yīng)選擇工廠擴(kuò)建、倉(cāng)庫(kù)1擴(kuò)建、設(shè)備更新三個(gè)項(xiàng)目進(jìn)行投資，可獲得最大凈現(xiàn)值180萬(wàn)元。932023/5/19

2.6.5指派問(wèn)題例2-12甲、乙、丙、丁4個(gè)人都懂得英、法、俄、西班牙4種語(yǔ)言?，F(xiàn)讓這4人去翻譯A（英語(yǔ)撰寫(xiě)）、B（法語(yǔ)撰寫(xiě)）、C（俄語(yǔ)撰寫(xiě)）、D（西班牙語(yǔ)撰寫(xiě)）4篇文獻(xiàn)，每人翻譯各篇文獻(xiàn)所需時(shí)間見(jiàn)表2-15。應(yīng)如何安排能使總的翻譯時(shí)間最少？表2-15

2.6整數(shù)線性規(guī)劃問(wèn)題文獻(xiàn)人ABCD甲乙丙丁

1087149612118313616101513942023/5/19解：引入0-1變量：

2.6整數(shù)線性規(guī)劃問(wèn)題數(shù)學(xué)模型：952023/5/19該例具體的數(shù)學(xué)模型：

2.6整數(shù)線性規(guī)劃問(wèn)題962023/5/19經(jīng)計(jì)算，最優(yōu)解如下：2.6整數(shù)線性規(guī)劃問(wèn)題計(jì)算結(jié)果表明：當(dāng)x13=1,x21=1,x34=1,x42=1時(shí)，目標(biāo)函數(shù)值最小，最小值為32；即由甲翻譯文獻(xiàn)C，乙翻譯A，丙翻譯D，丁翻譯B時(shí)，總的翻譯時(shí)間最少。972023/5/19

2.6.6產(chǎn)品設(shè)計(jì)和市場(chǎng)份額的優(yōu)化問(wèn)題例2-13彩虹服飾有限公司計(jì)劃設(shè)計(jì)一款秋季風(fēng)衣，并想以之占領(lǐng)秋季風(fēng)衣服飾的主要市場(chǎng)。彩虹公司的服飾設(shè)計(jì)師已經(jīng)確定了顧客在購(gòu)買秋季風(fēng)衣時(shí)最關(guān)心的3個(gè)屬性：款式、面料和顏色?？钍椒譃椋洪L(zhǎng)款和短款；面料分為：亞麻和純棉；顏色分為：暗色系、亮色系和中性色系。目前風(fēng)衣服飾市場(chǎng)上主要有兩個(gè)品牌： 奇跡（長(zhǎng)款、純棉、中性色的風(fēng)衣） 飛兒（短款、亞麻、亮色的風(fēng)衣）。

2.6整數(shù)線性規(guī)劃問(wèn)題982023/5/19

2.6.6產(chǎn)品設(shè)計(jì)和市場(chǎng)份額的優(yōu)化問(wèn)題表2-16是7位目前購(gòu)買奇跡或飛兒風(fēng)衣，但有可能轉(zhuǎn)向彩虹的潛在顧客給出的每一種屬性的局部?jī)r(jià)值。對(duì)于顧客1：長(zhǎng)款款式的局部?jī)r(jià)值為8，而短款的為5，這就意味著他偏好長(zhǎng)款款式。在面料屬性上，亞麻的局部?jī)r(jià)值是5，而純棉的為7，這就意味著顧客1對(duì)純棉有輕微偏好。同理，該顧客對(duì)暗色系有輕微偏好。綜上所述，顧客1喜歡長(zhǎng)款、純棉、暗色系的風(fēng)衣。其他顧客的局部?jī)r(jià)值也是如此解釋。

2.6整數(shù)線性規(guī)劃問(wèn)題992023/5/19

表2-16

2.6整數(shù)線性規(guī)劃問(wèn)題

顧客款式面料顏色長(zhǎng)短亞麻純棉暗色中性亮色123456785578511721364155781620146928113171212971411915512162032627825291081416

局部?jī)r(jià)值還可以用來(lái)確定每位顧客對(duì)某一種風(fēng)衣的整體評(píng)價(jià)（效用），從而確定該顧客最中意的風(fēng)衣。

一般地，每位顧客對(duì)于某種風(fēng)衣的評(píng)價(jià)就是簡(jiǎn)單的偏好的局部?jī)r(jià)值的相加。1002023/5/19整數(shù)規(guī)劃模型：

定義決策變量如下：如果彩虹在屬性j上選擇品質(zhì)i，則,否則為0；如果顧客k選擇彩虹服飾，則，否則為0。目標(biāo)是使選擇彩虹風(fēng)衣的顧客人數(shù)達(dá)到最大，所以目標(biāo)函數(shù)就是：每一位顧客都有一個(gè)約束條件。以顧客1為例：顧客1的效用=8l11+5l21+5l12+7l22+12l13+9l23+7l33>24顧客1的選擇條件：8l11+5l21+5l12+7l22+12l13+9l23+7l33≥1+24y1即8l11+5l21+5l12+7l22+12l13+9l23+7l33﹣24y1≥1

2.6整數(shù)線性規(guī)劃問(wèn)題1012023/5/19同理可得其他7位顧客的約束條件；對(duì)于屬性的選擇還有約束，每一種屬性只需一個(gè)。對(duì)于屬性1（款式），有以下約束：

l11+l21=1（l11和l21都是0-1變量）；同理，對(duì)于屬性2和屬性3分別有：l12+l22=1l13+l23+l33=1

2.6整數(shù)線性規(guī)劃問(wèn)題

此問(wèn)題的數(shù)學(xué)模型為：

目標(biāo)函數(shù)：

1022023/5/19約束條件

2.6整數(shù)線性規(guī)劃問(wèn)題1032023/5/19經(jīng)計(jì)算得：

2.6整數(shù)線性規(guī)劃問(wèn)題即l11=l12=l13=1，y1=y3=y6=1，最優(yōu)值為3，就是說(shuō)彩虹服飾設(shè)計(jì)這種風(fēng)衣，最多將會(huì)得到7位顧客中3位的青睞。由于l11=l12=l13=1，所以彩虹服飾應(yīng)設(shè)計(jì)長(zhǎng)款、亞麻、暗色系的風(fēng)衣，顧客1，3，6將偏好彩虹風(fēng)衣。

1042023/5/19

2.7.1目標(biāo)規(guī)劃問(wèn)題實(shí)例例2-14工廠選址問(wèn)題

工廠選址不僅要考慮廠址與消費(fèi)市場(chǎng)、廠址與原材料產(chǎn)地之間的物流費(fèi)用，還要考慮廠址周圍的勞動(dòng)力、交通運(yùn)輸?shù)纫蛩?，而且隨著環(huán)境問(wèn)題的日益突出，工廠選址還要考慮工廠對(duì)周邊環(huán)境的影響、工廠的公眾形象等問(wèn)題。例2-15市場(chǎng)調(diào)查問(wèn)題

市場(chǎng)調(diào)查往往存在著多個(gè)目標(biāo)，既希望調(diào)查能夠深入和全面以達(dá)到良好的效果，又要考慮成本、時(shí)間等因素。

2.7目標(biāo)規(guī)劃問(wèn)題1052023/5/19例2-16

某玩具廠商手工生產(chǎn)甲、乙兩種玩具，已知生產(chǎn)一個(gè)甲玩具需要耗費(fèi)人力0.5工時(shí)，生產(chǎn)一個(gè)乙玩具需要耗費(fèi)人力1工時(shí)，甲、乙兩種玩具的單位利潤(rùn)分別為30元和55元。生產(chǎn)這兩種玩具的首要目標(biāo)是每周的利潤(rùn)要超過(guò)40000元；另外，為了最大效率的利用人力資源，次要目標(biāo)是每周總耗費(fèi)人力不能低于600工時(shí)，但也不能超過(guò)680工時(shí)的極限；最后，為了保證庫(kù)存需要，還要求甲和乙的每周產(chǎn)量分別不低于700個(gè)和320個(gè)。問(wèn)應(yīng)如何安排甲、乙兩種玩具的產(chǎn)量？

2.7目標(biāo)規(guī)劃問(wèn)題1062023/5/19例2-17

某廠生產(chǎn)A、B兩種產(chǎn)品，利潤(rùn)分別為130元/百件，100元/百件。每生產(chǎn)一百件A、B產(chǎn)品，分別需要某種設(shè)備運(yùn)行2小時(shí)、1.5小時(shí)，該設(shè)備每天的正常運(yùn)行能力為22小時(shí)。根據(jù)市場(chǎng)需求情況，A產(chǎn)品日產(chǎn)量應(yīng)達(dá)到5百件以上，而B(niǎo)產(chǎn)品日產(chǎn)量則不能多于6百件，另外這兩種產(chǎn)品每天總利潤(rùn)應(yīng)達(dá)到1500元。問(wèn)該廠應(yīng)如何安排A、B產(chǎn)品的日產(chǎn)量？

2.7目標(biāo)規(guī)劃問(wèn)題1072023/5/19

2.7.2目標(biāo)規(guī)劃問(wèn)題的一般建模方法（1）基本概念彈性約束在例2-17中，如果設(shè)備的運(yùn)行能力被嚴(yán)格限制在22小時(shí)以內(nèi)，不能有絲毫超出，那么這類約束的性質(zhì)跟一般線性規(guī)劃問(wèn)題的約束相同，稱為剛性約束。但若設(shè)備的運(yùn)行能力不被嚴(yán)格限制在22小時(shí)以內(nèi)，有一定彈性，可以稍微超過(guò)22，即允許存在一定偏差，則稱為彈性約束。偏差變量用d+表示超出目標(biāo)的部分，稱為正偏差變量，用d-表示未達(dá)到目標(biāo)的部分，稱為負(fù)偏差變量，d+和d-統(tǒng)稱為偏差變量。2.7目標(biāo)規(guī)劃問(wèn)題1082023/5/19d+和d-二者至少有一個(gè)為0，因?yàn)楫?dāng)實(shí)際值大于目標(biāo)時(shí)，d+

>0，d-

=0；當(dāng)實(shí)際值小于目標(biāo)時(shí)，d-

>0，d+

=0；當(dāng)實(shí)際值等于目標(biāo)時(shí)，d+

=d-=0。例2-17中設(shè)備的正常運(yùn)行能力為22小時(shí)，引入偏差變量后，該約束可表示為下述彈性約束：

2.7目標(biāo)規(guī)劃問(wèn)題

優(yōu)先級(jí)與權(quán)數(shù)

優(yōu)先級(jí)：表示目標(biāo)規(guī)劃中各目標(biāo)重要程度的明顯差異。

權(quán)數(shù)：區(qū)分具有相同優(yōu)先因子的目標(biāo)間的重要程度。權(quán)數(shù)是具體數(shù)字，但沒(méi)有度量單位。1092023/5/19（2）建模 為例2-17中的各個(gè)約束按優(yōu)先級(jí)順序分別引入偏差變量di-，di+，得到以下4個(gè)彈性約束： 利潤(rùn)： 設(shè)備能力：A產(chǎn)品日產(chǎn)量：B產(chǎn)品日產(chǎn)量：

2.7目標(biāo)規(guī)劃問(wèn)題1102023/5/19每個(gè)優(yōu)先級(jí)的目標(biāo)函數(shù)：針對(duì)P1級(jí)目標(biāo)：P1級(jí)目標(biāo)函數(shù)為針對(duì)P2級(jí)目標(biāo)：P2級(jí)目標(biāo)函數(shù)為針對(duì)P3級(jí)目標(biāo)：P3級(jí)目標(biāo)函數(shù)為例2-17的目標(biāo)規(guī)劃模型：

2.7目標(biāo)規(guī)劃問(wèn)題1112023/5/19（3）目標(biāo)規(guī)劃的一般模型

一般模型：

2.7目標(biāo)規(guī)劃問(wèn)題1122023/5/19（1）式是目標(biāo)函數(shù)，其中Pk是目標(biāo)的優(yōu)先因子，zk是與Pk相對(duì)應(yīng)的第k級(jí)子目標(biāo)函數(shù)，它等于該級(jí)上各偏差變量與其權(quán)數(shù)的乘積之和，zk中偏差變量的列入根據(jù)目標(biāo)要求的不同而不同：若目標(biāo)要求恰好達(dá)到bi，比如例2-17中關(guān)于充分利用設(shè)備運(yùn)行能力且盡量避免超出設(shè)備運(yùn)行能力的目標(biāo)，要求設(shè)備的運(yùn)行時(shí)間最好是22小時(shí)/天，則zk為；若目標(biāo)要求大于bi，比如例2-17中關(guān)于利潤(rùn)的目標(biāo)，要求利潤(rùn)達(dá)到1500元，則zk為；若目標(biāo)要求小于bi，比如例2-17中關(guān)于B產(chǎn)品日產(chǎn)量的目標(biāo)，要求B產(chǎn)品日產(chǎn)量不能超過(guò)6百件，則zk為

。

2.7目標(biāo)規(guī)劃問(wèn)題1132023/5/19

2.7.3目標(biāo)規(guī)劃問(wèn)題的求解與分析對(duì)例2-17經(jīng)求解，結(jié)果如下：決策變量x1=500，x2=850；偏差變量d1-=0，d1+=0，d2-=0，d2+=0.75，d3-=0，d3+=0，d4-=0，d4+=250。

計(jì)算結(jié)果表明總利潤(rùn)為1500元，設(shè)備的運(yùn)行時(shí)間為22.75小時(shí)，A產(chǎn)品的日產(chǎn)量為500件，B產(chǎn)品的日產(chǎn)量為850件，可見(jiàn)利潤(rùn)目標(biāo)實(shí)現(xiàn)了，但是關(guān)于設(shè)備運(yùn)行時(shí)間和日產(chǎn)量的目標(biāo)有一些偏差。

2.7目標(biāo)規(guī)劃問(wèn)題1142023/5/19（1）存儲(chǔ)問(wèn)題 家庭中的存儲(chǔ)儲(chǔ)備品，工廠儲(chǔ)備原材料，商店存儲(chǔ)商品等都是存儲(chǔ)問(wèn)題。存儲(chǔ)論研究的意義：保持合理的存儲(chǔ)水平，以節(jié)約資金，獲得更多利潤(rùn)。存儲(chǔ)論主要解決的問(wèn)題：①訂貨量是多少？②什么時(shí)候訂貨？

2.8存儲(chǔ)論簡(jiǎn)介1152023/5/19（2）存儲(chǔ)系統(tǒng)

存儲(chǔ)論的對(duì)象是一個(gè)由補(bǔ)充、存儲(chǔ)和需求三個(gè)環(huán)節(jié)構(gòu)成的現(xiàn)實(shí)運(yùn)行系統(tǒng)，且以存儲(chǔ)為中心環(huán)節(jié)，故稱為存儲(chǔ)系統(tǒng)。其一般結(jié)構(gòu)如下圖：2.8存儲(chǔ)論簡(jiǎn)介存儲(chǔ)的輸出：由于生產(chǎn)或銷售等需求，從存儲(chǔ)中取出一定的數(shù)量。存儲(chǔ)的輸入：由于不斷輸出而使存儲(chǔ)減少，因而必須加以補(bǔ)充，否則會(huì)無(wú)法滿足需求。存儲(chǔ)補(bǔ)充需求1162023/5/19需求可能是連續(xù)的，也可能是間斷式的。需求可能是確定性的，也可能是隨機(jī)性的。有一定的隨機(jī)分布的需求：對(duì)于隨機(jī)性的需求，經(jīng)過(guò)大量的統(tǒng)計(jì)，可能會(huì)發(fā)現(xiàn)需求量的統(tǒng)計(jì)規(guī)律。補(bǔ)充有外部訂購(gòu)（采購(gòu)）和內(nèi)部生產(chǎn)兩種方式。備貨時(shí)間：從訂貨到貨物進(jìn)入存儲(chǔ)的時(shí)間。提前時(shí)間：為使存儲(chǔ)在某一時(shí)刻獲得補(bǔ)充，就必須提前一段時(shí)間訂貨的時(shí)間。

2.8存儲(chǔ)論簡(jiǎn)介1172023/5/19（3）存儲(chǔ)策略存儲(chǔ)系統(tǒng)的最優(yōu)運(yùn)營(yíng)問(wèn)題

通過(guò)控制訂貨時(shí)間和訂貨量，來(lái)調(diào)節(jié)存儲(chǔ)系統(tǒng)的運(yùn)行，以便達(dá)到最優(yōu)運(yùn)營(yíng)效果。

存儲(chǔ)策略

決定多長(zhǎng)時(shí)間補(bǔ)充一次貨物以及每次補(bǔ)充多少數(shù)量的策略。存儲(chǔ)策略有以下幾種類型：①

t0-循環(huán)策略，即每隔t0時(shí)間補(bǔ)充存儲(chǔ)量Q。這種決策又稱為經(jīng)濟(jì)批量決策，它適用于需求確定的存儲(chǔ)系統(tǒng)。②(s,S)策略，即每當(dāng)存儲(chǔ)量x≤s時(shí)立即補(bǔ)充存儲(chǔ)量Q，且有x+Q=S。當(dāng)x>s時(shí)，不補(bǔ)充。③(t,s,S)策略，即每隔t時(shí)段檢查存儲(chǔ)量一次，若存儲(chǔ)量x≤s時(shí)立即補(bǔ)充存儲(chǔ)量Q，且有x+Q=S。當(dāng)x>s時(shí)，不補(bǔ)充。

2.8存儲(chǔ)論簡(jiǎn)介1182023/5/19（4）運(yùn)營(yíng)費(fèi)用運(yùn)營(yíng)費(fèi)用是衡量一個(gè)存儲(chǔ)策略優(yōu)劣的常用數(shù)量指標(biāo)。

①進(jìn)貨費(fèi)用進(jìn)貨費(fèi)用是指補(bǔ)充存儲(chǔ)而發(fā)生的費(fèi)用，記為CO，其一般形式為：

2.8存儲(chǔ)論簡(jiǎn)介a和c在外部訂購(gòu)與內(nèi)部生產(chǎn)不同方式下的不同含義：訂購(gòu)費(fèi)用：訂貨與購(gòu)貨所發(fā)生的費(fèi)用。a表示每次訂購(gòu)費(fèi)用，c表示單位貨物購(gòu)置費(fèi)用。生產(chǎn)費(fèi)用：生產(chǎn)貨物所發(fā)生的費(fèi)用。a表示每次的裝配費(fèi)用(或準(zhǔn)備、結(jié)束費(fèi)用)，c表示單位貨物的生產(chǎn)費(fèi)用。1192023/5/19②存儲(chǔ)費(fèi)用

存儲(chǔ)費(fèi)用是指持有貨物而發(fā)生的費(fèi)用，記為CH。它可能包括倉(cāng)庫(kù)使用費(fèi)、貨物保管費(fèi)，及存貨陳舊、變質(zhì)、降價(jià)等所造成的損失等。③缺貨費(fèi)用 缺貨費(fèi)用是指存儲(chǔ)供不應(yīng)求時(shí)所造成的損失費(fèi)，記為CS。運(yùn)營(yíng)費(fèi)用：又稱為總費(fèi)用，等于上述3項(xiàng)費(fèi)用之和，記為CT，則有CT=CO+CH+CS

記f表示單位時(shí)間的平均（或期望）運(yùn)營(yíng)費(fèi)用。 使運(yùn)營(yíng)費(fèi)用f達(dá)到最小的進(jìn)貨批量稱為經(jīng)濟(jì)批量（EconomicLotsize）,記為Q*。對(duì)幾種確定性存儲(chǔ)系統(tǒng),人們已經(jīng)導(dǎo)出了經(jīng)濟(jì)批量Q*的數(shù)學(xué)表達(dá)式，稱為經(jīng)濟(jì)批量公式。由于這些公式也是存儲(chǔ)模型的一種形式，故也稱為經(jīng)濟(jì)批量模型。

2.8存儲(chǔ)論簡(jiǎn)介1202023/5/19（5）存儲(chǔ)論的典型模型

2.8存儲(chǔ)論簡(jiǎn)介存儲(chǔ)論模型確定性存儲(chǔ)系統(tǒng)模型

隨即性存儲(chǔ)模型

不允許缺貨，備貨時(shí)間很短不允許缺貨，生產(chǎn)需要一定時(shí)間允許缺貨，備貨時(shí)間很短

允許缺貨，生產(chǎn)需要一定時(shí)間

定價(jià)有折扣的存儲(chǔ)模型(t,s,S)策略模型1212023/5/19（6）模型一：不允許缺貨，備貨時(shí)間很短假設(shè)條件：①需求是連續(xù)的、均勻的，單位時(shí)間的需求量記為常數(shù)；②不允許缺貨，當(dāng)存儲(chǔ)降到零時(shí)立即補(bǔ)充，即備貨時(shí)間很短，可視為零。③在每一運(yùn)營(yíng)周期t的初始時(shí)刻進(jìn)行補(bǔ)充，每期進(jìn)貨批量相同，均為Q=dt。

2.8存儲(chǔ)論簡(jiǎn)介1222023/5/19存儲(chǔ)狀態(tài)圖2.8存儲(chǔ)論簡(jiǎn)介在[0，t]時(shí)段內(nèi)的存儲(chǔ)量為：

在一個(gè)運(yùn)營(yíng)周期t內(nèi)的存儲(chǔ)費(fèi)用為：

1232023/5/19進(jìn)貨費(fèi)用為：

2.8存儲(chǔ)論簡(jiǎn)介一個(gè)周期t內(nèi)的運(yùn)營(yíng)費(fèi)用：?jiǎn)挝粫r(shí)間的平均運(yùn)營(yíng)費(fèi)用：

由，有利用微積分求最小值方法可得Q=Q*時(shí)，為極小值。1242023/5/19最佳運(yùn)營(yíng)周期為：

2.8存儲(chǔ)論簡(jiǎn)介最優(yōu)值（最小平均運(yùn)營(yíng)費(fèi)用）為：例2-20某發(fā)動(dòng)機(jī)制造廠今年計(jì)劃生產(chǎn)汽車發(fā)動(dòng)機(jī)90000個(gè)，該款發(fā)動(dòng)機(jī)中的一種零件需從另一廠家訂購(gòu)，且每制造1臺(tái)發(fā)動(dòng)機(jī)需要1一個(gè)該零件，每次的訂購(gòu)手續(xù)費(fèi)為120元，該零件的訂購(gòu)價(jià)格為每個(gè)8元，零件的全年庫(kù)存保管費(fèi)用為購(gòu)價(jià)的15%。試求發(fā)動(dòng)機(jī)制造廠今年對(duì)該種零件的最佳存儲(chǔ)策略與費(fèi)用。1252023/5/19解：根據(jù)題意可知，以一年為時(shí)間單位，則有:a=120(元/次)，c=8(元/個(gè))，d=90000(個(gè)/年)，h=0.15c=0.15*8=1.2（元/年）由