《數(shù)據(jù)、模型與決策》 課件 2.1線性規(guī)劃圖解法

《MBA數(shù)據(jù)、模型與決策》

Data,ModelsandDecision-making第2章線性規(guī)劃模型的圖解法什么是

圖解法?例2.1廣州電器廠生產(chǎn)優(yōu)化問題廣州電器廠生產(chǎn)A、B兩種電器產(chǎn)品。產(chǎn)品A與產(chǎn)品B在生產(chǎn)過程中均使用原材料1，其中每件所消耗的原材料1的數(shù)量分別為6與2。同時(shí)，產(chǎn)品B還需使用原材料2，每件產(chǎn)品的消耗量為1。此外，每生產(chǎn)一件產(chǎn)品A與一件產(chǎn)品B所需的勞動時(shí)間分別為2與4。該廠提供的原材料和勞動時(shí)間的數(shù)量是有限的。在第一個月初，該廠可提供的原材料1的數(shù)量是1800，原材料2的數(shù)量是350，可提供的2.1一個簡單的最大化問題總勞動時(shí)間為1600。該兩種原材料的保存時(shí)間是一個月，也就是說，第一個月用不完的原材料只能丟棄。經(jīng)財(cái)務(wù)部門分析計(jì)算，產(chǎn)品A與B每件利潤分別為3元與8元，而且根據(jù)市場調(diào)查得到的該兩種產(chǎn)品的市場需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有產(chǎn)品均能銷售出去。問第一個月內(nèi)產(chǎn)品A與產(chǎn)品B各應(yīng)生產(chǎn)多少，可使總利潤最大？項(xiàng)目1件產(chǎn)品A1件產(chǎn)品B總量原材料1621800原材料201350勞動時(shí)間241600利潤38表2.1廣州電器廠月生產(chǎn)安排分析：在上述問題中，目標(biāo)是總利潤的最大化，所要決策的變量是產(chǎn)品的產(chǎn)量，而產(chǎn)品的產(chǎn)量則受到可提供的原材料與勞動時(shí)間的約束，因此，該問題可以用目標(biāo)、決策變量和約束條件三個因素加以描述。實(shí)際上，所有的線性規(guī)劃問題都包括這三個因素。①目標(biāo)函數(shù)是指系統(tǒng)所追求的目標(biāo)的數(shù)學(xué)描述。例如最大利潤、最小成本等。②決策變量是指系統(tǒng)中有待確定的未知因素。例如決定企業(yè)經(jīng)營目標(biāo)的各產(chǎn)品的產(chǎn)量等。③約束條件是指實(shí)現(xiàn)系統(tǒng)目標(biāo)的限制因素，它們限制了目標(biāo)值所能達(dá)到的程度。例如原材料供應(yīng)量、市場需求等。

解：此問題可用表2.1表示項(xiàng)目1件產(chǎn)品A1件產(chǎn)品B總量原材料1621800原材料201350勞動時(shí)間241600利潤38表2.1廣州電器廠月生產(chǎn)安排①決策變量此問題的決策變量是第一個月產(chǎn)品A與產(chǎn)品B的產(chǎn)量?？稍O(shè)：X為第一個月產(chǎn)品A的產(chǎn)量（件）；Y為第一個月產(chǎn)品B的產(chǎn)量（件）。X、Y即為本問題的決策變量。②目標(biāo)函數(shù)此問題的目標(biāo)函數(shù)是總利潤最大。由于產(chǎn)品A與產(chǎn)品B每件利潤分別為3元與8元，而其產(chǎn)量分別為X與Y,所以總利潤可計(jì)算如下：總利潤=3X+8Y③約束條件此問題共有四個約束條件。第一個約束是原材料1的約束。每件產(chǎn)品A與產(chǎn)品B對原材料1的消耗量分別為6與2，而兩種產(chǎn)品的產(chǎn)量分別為X與Y，所以該兩種產(chǎn)品在第一個月對原材料1的總消耗量為6X+2Y。由題意，原材料1的可提供量為1800。由此，可得第一個約束如下：

6X+2Y≤1800第二個約束是原材料2的約束。由于只有產(chǎn)品B需消耗原材料2，而且單位產(chǎn)品B對原材料2的消耗量為1，產(chǎn)品B的產(chǎn)量為Y。由題意，原材料2的可提供量為350。由此可得第二個約束如下：

Y≤350第三個約束是勞動時(shí)間的約束。由于每單位產(chǎn)品A與產(chǎn)品B對勞動時(shí)間的需要量分別為2與4，而兩種產(chǎn)品的產(chǎn)量分別為X與Y，所以兩種產(chǎn)品在第一個月所需的總勞動時(shí)間為2X+4Y。由題意，勞動時(shí)間的可提供量為1600。由此可得第三個約束如下：

2X+4Y≤1600第四個約束是決策變量的非負(fù)約束。由于產(chǎn)量不可能為負(fù)值，所以有：

X≥0，,Y≥0

由上述分析可建立本問題的線性規(guī)劃模型如下：o.b.max3X+8Ys.t.6X+2Y≤1800Y≤3502X+4Y≤1600X，,Y≥0所謂的線性規(guī)劃就是：

(1)每一個問題都用一組決策變量（x1,x2,…xn）表示某一方案；這組決策變量的值就代表一個方案。一般，這些變量取值是非負(fù)的。（2）存在一定的約束條件，這些約束條件是一組關(guān)于決策變量的線性等式或線性不等式。（3）都有一個要求達(dá)到的目標(biāo)，目標(biāo)函數(shù)是關(guān)于決策變量的線性函數(shù)。所謂的線性規(guī)劃就是：

(1)每一個問題都用一組決策變量（x1,x2,…xn）表示某一方案；這組決策變量的值就代表一個方案。一般，這些變量取值是非負(fù)的。（2）存在一定的約束條件，這些約束條件是一組關(guān)于決策變量的線性等式或線性不等式。（3）都有一個要求達(dá)到的目標(biāo)，目標(biāo)函數(shù)是關(guān)于決策變量的線性函數(shù)。滿足以上三個條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。它的一般形式為：目標(biāo)函數(shù)

max(min)z=c1x1+c2x2+…+cnxn滿足約束條件:

a11x1+a12x2+…+a1nxn≤(＝,≥)b1

a21x1+a22x2+…+a2nxn≤(＝,≥)b2

………….……….am1x1+am2x2+…+amnxn≤(＝,≥)bmx1,x2,…,xn≥0由此可知，線性規(guī)劃模型有各種不同的形式，目標(biāo)函數(shù)有的求max，有的求min，約束條件可以是“≤”，也可以是“≥”不等式，還可以是等式，決策變量一般是非負(fù)約束，在實(shí)際問題中有一定的意義,但也允許在（－∞，∞）范圍內(nèi)取值。線性規(guī)劃問題的解可能出現(xiàn)下列情況：1.有惟一解這里，線性規(guī)劃問題有惟一解是指該規(guī)劃問題有且僅有一個既在可行域內(nèi)，又使目標(biāo)值達(dá)到最優(yōu)的解，即只有一個最優(yōu)解。2.2線性規(guī)劃問題的圖解法例如，例2.1廣州電器廠生產(chǎn)優(yōu)化問題，它的線性規(guī)劃模型為：o.b.max3X+8Y（利潤最大化）s.t.6X+2Y≤1800（原材料約束）

Y≤350（原材料約束）

2X+4Y≤1600（勞動時(shí)間約束）

X，，,Y≥0（非負(fù)約束）1.有惟一解線性問題的圖解法2004006008001002003004005006007008009006X+2Y=18002X+4Y=16000ODCBAY=350XY3X+8Y=Z線性問題的圖解法步驟在坐標(biāo)圖上作出代表各約束條件的直線；確定滿足所有約束條件的可行域；作出任意一條等利潤直線；朝著使目標(biāo)函數(shù)最優(yōu)化的方向，平行移動該等利潤直線，直到再繼續(xù)移動就會離開可行域?yàn)橹?。線性規(guī)劃問題的解的討論唯一解無窮多解目標(biāo)函數(shù)為：MaxZ=2X+4Y時(shí)線性規(guī)劃問題無可行域的情況：線性規(guī)劃問題可行域無界的情況：

6X+2Y=18002X+4Y=1600Y=350X=400max3X+8Ys.t.X+Y=350X，Y≥0本問題是利潤最大化，所以應(yīng)在可行域內(nèi)選擇使利潤達(dá)到最大值的解。不妨考慮一下哪些解可以使利潤達(dá)到3X+8Y=1200，可作出等利潤線3X+8Y=2400；可得出：3X+8Y=k，k取不同的值表示不同的利潤。不難發(fā)現(xiàn)所有的等利潤都相互平行，且離原點(diǎn)越遠(yuǎn)的等利潤線，利潤最高。因此，最優(yōu)解應(yīng)是在可行域內(nèi)離原點(diǎn)最遠(yuǎn)的那條等利潤直線上的點(diǎn)?？梢夿點(diǎn)就是。而B點(diǎn)是直線②和直線③的交點(diǎn)。解此方程組可得：X=100，Y=350。例如下面一個線性規(guī)劃模型：o.b.max3X+8Y（利潤最大化）s.t.6X+2Y≤1800（原材料約束）

Y≤350（原材料約束）

2X+4Y≤1600（勞動時(shí)間約束）

X≥350X，,Y≥0（非負(fù)約束）松弛變量與線性規(guī)劃模型的標(biāo)準(zhǔn)式若在約束條件左邊加上一個變量，使原來的“≤”約束不等式變?yōu)榈仁郊s束Max3X+8Y+0S1+0S2+0S36X+2Y+S1＝1800Y+S2=3502X+4Y+S3=1600X,Y,S1,S2,S3≥0標(biāo)準(zhǔn)型線性規(guī)劃模型變量S1,S2,S3為松弛變量，表示可提供資源與實(shí)際消耗資源之差，即閑置的那部分資源將最優(yōu)解X=100,Y=350帶入約束條件左邊，得到三種資源的實(shí)際使用量如下：6X+2Y=1300≤1800（原材料1約束）（1）Y=350≤350（原材料2的約束）（2）2X+4Y=1600≤1600（勞動時(shí)間約束）（3）原材料1有多余，原材料2、勞動時(shí)間沒有多于約束1稱為非緊約束，表示這時(shí)資源有多于約束2和約束3稱為緊約束，表示這時(shí)資源已全部使用完畢2.有無窮多解這里，線性規(guī)劃問題有無窮多解是指該規(guī)劃問題無窮多個既在可行域內(nèi)，又使目標(biāo)值達(dá)到最優(yōu)的解，即有無窮多個最優(yōu)解。2.有無窮多解

例如下面一個線性規(guī)劃模型：

o.b.max4X+8Y（利潤最大化）

s.t.6X+2Y≤1800（原材料約束）

Y≤350（原材料約束）

2X+4Y≤1600（勞動時(shí)間約束）

X，，，,Y≥0（非負(fù)約束）約束條件和例2.1廣州電器廠生產(chǎn)優(yōu)化問題的約束條件一樣，也就是可行域一樣，但目標(biāo)函數(shù)不一樣，它有無窮多解，解為BC直線上的任意一點(diǎn)，如下圖：4X+8Y=KABCOD例如下面一個線性規(guī)劃模型：o.b.max3X+8Y（利潤最大化）s.t.6X+2Y≤1800約束）

Y≤350（原材料約束）

2X+4Y≤1600（勞動時(shí)間約束）

X≥350X，,Y≥0（非負(fù)約束）如下圖，不存在可行域，無解3.無解ABCODEF4.可行域無界

這里，線性規(guī)劃問題的可行域無界是指最大化問題的目標(biāo)函數(shù)值可以無限增大，或最小化問題的目標(biāo)函數(shù)值可以無限減小。例如下面一個線性規(guī)劃模型：o.b.max4X+8Y（利潤最大化）s.t.X+Y≥350（資源約束）

X，,Y≥0（非負(fù)約束）如下圖，可行域無界，目標(biāo)函數(shù)值可以無限增大4.可行域無界AB圖解法適合于求解含有兩個決策變量的線性規(guī)劃問題。歸納步驟如下：1在坐標(biāo)圖上作出代表各約束條件的直線；2確定滿足所有約束條件的可行域；3作出任意一條等利潤直線，可令利潤函數(shù)值等于任意一個特定值；4朝著使目標(biāo)函數(shù)最優(yōu)化的方向，平行移動該等利潤直線，直到再繼續(xù)移動就會離開可行域?yàn)橹?。此時(shí)，該等利潤直線在可行域的那些點(diǎn)，就是最優(yōu)解。圖解法步驟例2.3廣州金屬廠成本優(yōu)化問題廣州金屬廠從Ⅰ、Ⅱ兩種礦石中提煉A、B兩種金屬。已知每噸礦石中金屬A、B的含量和兩種礦石的價(jià)格如表2.4.1所示。據(jù)預(yù)測，金屬B的需求量不少于420千克，而金屬A由于銷路問題，該廠決定，其產(chǎn)量不得超過600千克。此外，礦石Ⅱ由于庫存積壓，要求其使用量不得少于800噸，問應(yīng)使用各種礦石多少噸，使得在滿足要求的前提下總費(fèi)用最??？2.3最小化問題

表2.3礦石成分與價(jià)格表

金屬礦石AB價(jià)格（元/噸）Ⅰ0.400.4245Ⅱ0.250.1510解：根據(jù)題意可作如下分析：①決策變量本問題的決策變量是兩種礦石的使用量?？稍O(shè)：X為礦石Ⅰ的使用量（噸）；Y為礦石Ⅱ的使用量（噸）。②目標(biāo)函數(shù)本問題的目標(biāo)函數(shù)是總費(fèi)用最小?？傎M(fèi)用可計(jì)算如下：總費(fèi)用=45X+10Y（元）③約束條件本問題共有四個約束。第一個約束是金屬A的產(chǎn)量約束，第二個約束是金屬B的需求約束，第三個約束是礦石Ⅱ的使用量約束，第四個約束是非負(fù)約束。由上述分析，可建立該最小化問題的線性規(guī)劃模型如下：o.b.Min45X+10Ys.t.0.40X+0.25Y≤600（金屬A的產(chǎn)量約束）

0.42X+0.15Y≥420（金屬B的需求約束）

Y≥800（礦石Ⅱ的使用量約束）

X≥0,Y≥0（非負(fù)約束）最小化問題的圖解法5001000150020002500Y50010001500XABC0.40X+0.42Y=6000.42X+0.15Y=420Y=800本問題的目標(biāo)是最小化，所以應(yīng)在可行域內(nèi)選擇使得費(fèi)用達(dá)到最小值的解。作等費(fèi)用直線族45X+10Y=k(k可取不同的常數(shù))，對于等費(fèi)用直線族來說，越靠近原點(diǎn)的等費(fèi)用直線對應(yīng)的費(fèi)用越小。因此，最優(yōu)解應(yīng)是在可行域內(nèi)的、最接近原點(diǎn)的那條等費(fèi)用直線上的點(diǎn)。本問題中，既在可行域內(nèi)的、又最接近原點(diǎn)的那條等費(fèi)用直線上的點(diǎn)是A點(diǎn)，所有A點(diǎn)的坐標(biāo)就是最優(yōu)解。而A點(diǎn)直線①和②的交點(diǎn)。解此線性方程組，得到：X=333.3噸，Y=1866.7噸。相應(yīng)的最優(yōu)解為：45X+10Y=33666（元）。剩余變量（surplus）若將最優(yōu)解X=333.3、Y=1866.7代入約束條件的左邊0.4X+0.25Y=600≤600（1）0.42X+0.15Y=420≥420（2）Y=1867≥800（3）約束（1）與（2）的左邊等于右邊，稱為“緊約束”約束（3）的左邊大于右邊，說明礦石乙的實(shí)際使用量不僅能夠滿足所有求的最小使用量，而且還多用了，稱約束（3）為“非緊”約束在約束條件（3）的左邊減去一個變量，可使原來的“≥”約束不等式變?yōu)榈仁郊s束。同理，在約束條件（2）的左邊減去一個變量，也可使可使原來的“≥”約束不等式變?yōu)榈仁郊s束。在約束條件（1）的右邊加上一個變量，使可使原來的“≤”約束不等式變?yōu)榈仁郊s束Min45X+10Y+0S1+0S2+0S30.4X+0.25Y+S1=6000.42X+0.15Y-S2=420Y-S3=800X,Y,S1,S1,S1≥0案例分析2-1創(chuàng)業(yè)投資基金公司的數(shù)據(jù)分析

廣州某創(chuàng)業(yè)投資基金公司為計(jì)算機(jī)軟件和互聯(lián)網(wǎng)的應(yīng)用發(fā)展提供創(chuàng)業(yè)基金。目前該基金公司有兩個投資機(jī)會：一個是需要資金去開發(fā)互聯(lián)網(wǎng)安全軟件的公司；另一個是需要資金去開發(fā)對顧客滿意度進(jìn)行調(diào)查的應(yīng)用軟件的公司，開發(fā)安全軟件的公司要求