第2章線性規(guī)劃導(dǎo)論

第二章線性規(guī)劃導(dǎo)論講授人：朱玉春教授單位：經(jīng)濟(jì)管理學(xué)院

2011年西北農(nóng)林科技大學(xué)引言線性規(guī)劃的例子:1.制造商希望建立一個(gè)生產(chǎn)時(shí)間表和庫(kù)存計(jì)劃，以滿足未來(lái)一段時(shí)間的市場(chǎng)需求，同時(shí)使生產(chǎn)和庫(kù)存成本最低。2.財(cái)務(wù)分析師必須選擇若干股票和債券進(jìn)行投資組合，使其所做的投資組合的回報(bào)最大。3.營(yíng)銷經(jīng)理希望將固定的廣告預(yù)算在廣播、電視、報(bào)紙、雜志等廣告媒體進(jìn)行最好的分配，使廣告效果最好。4.一家公司的倉(cāng)庫(kù)分布于全美各地，現(xiàn)在有一些顧客訂單，公司希望確保每個(gè)倉(cāng)庫(kù)到每個(gè)顧客的發(fā)貨量，使總的運(yùn)輸成本最低。共同的特點(diǎn)：1、某個(gè)量的最大化或最小化為目標(biāo)。2、存在某些限制或約束條件。本章主要內(nèi)容2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題2.2圖解法2.3極點(diǎn)與最優(yōu)解2.4Par公司問(wèn)題的計(jì)算機(jī)求解（略）2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

Par公司是一個(gè)生產(chǎn)高爾夫器材的小型公司，它決定進(jìn)入中等和高等價(jià)位的高爾夫袋市場(chǎng)。分銷商對(duì)新產(chǎn)品很感興趣，且同意買進(jìn)Par公司未來(lái)3個(gè)月內(nèi)的全部產(chǎn)品。高爾夫袋生產(chǎn)過(guò)程：

切割并染印材料縫合成型（插入支撐架，球棒分離裝置等）檢查與包裝2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

經(jīng)過(guò)對(duì)各個(gè)生產(chǎn)小時(shí)部門工作量的研究，生產(chǎn)主管估計(jì)未來(lái)3個(gè)月內(nèi)每個(gè)部門可用的最大生產(chǎn)時(shí)間分別是：切割與印染630個(gè)，縫合600個(gè)小時(shí)，成型708個(gè)小時(shí)，檢查與包裝135個(gè)小時(shí)。會(huì)計(jì)部門經(jīng)過(guò)對(duì)生產(chǎn)數(shù)據(jù)，各種生產(chǎn)成本的分析得出了以下結(jié)論：生產(chǎn)一個(gè)標(biāo)準(zhǔn)袋的利潤(rùn)是10美元，生產(chǎn)一個(gè)高級(jí)袋的利潤(rùn)是9美元。我們現(xiàn)在可以為Par公司建立一個(gè)數(shù)學(xué)模型來(lái)解決標(biāo)準(zhǔn)袋和高級(jí)袋各生產(chǎn)多少，以最大化公司的利潤(rùn)貢獻(xiàn)。表2-1生產(chǎn)每個(gè)高爾夫袋所需要時(shí)間2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

2.1.1問(wèn)題模型化

問(wèn)題模型化或建模，是將語(yǔ)言文字描述轉(zhuǎn)化為數(shù)學(xué)描述的過(guò)程。下面我們以Par公司為例講解一下建立數(shù)學(xué)模型的基本原則。全面了解問(wèn)題對(duì)于比較復(fù)雜的例子，模型需要詳細(xì)考慮的因素可能比較多，我們可以先快速瀏覽一下整個(gè)問(wèn)題，以了解問(wèn)題所包含的內(nèi)容，做一些記錄對(duì)抓住關(guān)鍵問(wèn)題和重點(diǎn)事實(shí)會(huì)有很多大幫助。描述目標(biāo)本題目標(biāo)是使產(chǎn)品的利潤(rùn)貢獻(xiàn)最大。描述約束條件對(duì)于生產(chǎn)時(shí)間來(lái)說(shuō)，一共有4個(gè)約束條件，它們制約著兩種高爾夫袋的生產(chǎn)。2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題約束條件1

用于切割與印染的總時(shí)間必須小于等于切割與印染部所能承受的最大工作時(shí)間。約束條件2

用于縫合的總時(shí)間必須小于等于縫合部所能承受的最大工作時(shí)間。約束條件3

用于成型的總時(shí)間必須小于等于成型部所能承受的最大工作時(shí)間。約束條件4

用于檢查與包裝的總時(shí)間必須小于等于檢查與包裝部所能承受的最大工作時(shí)間。2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

定義決策變量

（1）標(biāo)準(zhǔn)袋產(chǎn)量；（2）高級(jí)袋產(chǎn)量。設(shè)

S——標(biāo)準(zhǔn)袋產(chǎn)量

D——高級(jí)袋產(chǎn)量

S和D叫做決策變量。用決策變量寫(xiě)出目標(biāo)

Par公司的利潤(rùn)來(lái)源于兩方面（1）生產(chǎn)S個(gè)標(biāo)準(zhǔn)袋所獲得的利潤(rùn)；（2）生產(chǎn)D個(gè)高級(jí)袋所獲得的利潤(rùn)。如果公司生產(chǎn)一個(gè)標(biāo)準(zhǔn)袋創(chuàng)造10美元利潤(rùn)，一個(gè)高級(jí)袋獲得9美元，那么總利潤(rùn)貢獻(xiàn)=10S+9D

因?yàn)楣镜哪繕?biāo)是利潤(rùn)貢獻(xiàn)最大化，所以10S+9D是目標(biāo)函數(shù)，使用max來(lái)表示函數(shù)最大化。

Max10S+9D2.1一個(gè)簡(jiǎn)單的最大化問(wèn)題用決策變量寫(xiě)出約束條件約束條件1

（切割與印染所用的時(shí)間）≤（公司切割與印染部的最大工作時(shí)間）

因?yàn)槊總€(gè)標(biāo)準(zhǔn)袋都需要用7/10個(gè)小時(shí)的切割與印染，因此制造S個(gè)標(biāo)準(zhǔn)袋所需要的切割印染時(shí)間是7S/10。同理，制造一個(gè)高級(jí)袋需要1小時(shí)切割印染，制造D個(gè)高級(jí)袋所用的切割與印染時(shí)間是1D。于是生產(chǎn)S個(gè)標(biāo)準(zhǔn)袋和D個(gè)高級(jí)袋共需要的切割印染時(shí)間是總切割與印染時(shí)間=7S/10+D

生產(chǎn)主管估計(jì)的總切割印染時(shí)間為630小時(shí)，需要滿足7S/10+D≤6302.1一個(gè)簡(jiǎn)單的最大化問(wèn)題約束條件2:（縫合所用時(shí)間）≤（公司縫合部最大工作時(shí)間）每個(gè)標(biāo)準(zhǔn)袋縫合時(shí)間是1/2小時(shí)，每個(gè)高級(jí)袋的縫合時(shí)間是5/6小時(shí)，而可用的縫合時(shí)間是600小時(shí)，所以1S/2+5D/6≤600約束條件3：（成型所用時(shí)間）≤（公司成型部的最大工作時(shí)間）每個(gè)標(biāo)準(zhǔn)袋需要1個(gè)小時(shí)成型，每個(gè)高級(jí)袋需要2/3個(gè)小時(shí)成型。成型部最大工作時(shí)間708小時(shí)。所以S+2D/3≤7082.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

約束條件4：（檢查與包裝所用時(shí)間）≤（公司檢查與包裝部最大工作時(shí)間）

檢查與包裝一個(gè)標(biāo)準(zhǔn)袋需要1/10小時(shí)，檢查與包裝一個(gè)高級(jí)袋需要1/4小時(shí)，檢查與包裝部最大時(shí)間135小時(shí)。所以1S/10+1D/4≤135

另外，Par公司的高爾夫袋的產(chǎn)量不能為負(fù)，必須S≥0且D≥0。這樣的約束條件可以確保模型的解是非負(fù)值，因此稱為非負(fù)約束。縮寫(xiě)為S,D≥02.1一個(gè)簡(jiǎn)單的最大化問(wèn)題2.1.2Par問(wèn)題的數(shù)學(xué)描述

Par公司問(wèn)題的數(shù)學(xué)描述或數(shù)學(xué)構(gòu)造已經(jīng)完成。我們已經(jīng)成功將問(wèn)題的目標(biāo)和約束用一組數(shù)學(xué)關(guān)系式——數(shù)學(xué)模型表述出來(lái)。Par問(wèn)題的完整數(shù)學(xué)模型如下：

Max10S+9Ds.t.

7S/10+D≤630切割與印染

1S/2+5D/6≤600縫合

S+2D/3≤708成型

1S/10+1D/4≤135檢查與包裝

S,D≥02.1一個(gè)簡(jiǎn)單的最大化問(wèn)題

我們接下來(lái)的工作就是找到合適的組合（即S和D的組合），既滿足約束條件，又能使目標(biāo)函數(shù)的值最大。一旦這些值都計(jì)算出來(lái)了，我們也就找到了問(wèn)題的最優(yōu)解。我們稱Par問(wèn)題的數(shù)學(xué)模型為線性規(guī)劃模型或線性規(guī)劃。線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束條件都是決策變量的線性函數(shù)。

線性函數(shù)是指函數(shù)中的每個(gè)變量都是分離的且冪次為1。上述問(wèn)題中的目標(biāo)函數(shù)和約束條件都是線性函數(shù)，因此這個(gè)問(wèn)題的數(shù)學(xué)模型為線性規(guī)劃。2.2圖解法

線性問(wèn)題只需包含兩個(gè)變量就可以使圖形求解。我們通過(guò)畫(huà)圖表示Par公司問(wèn)題的可能的解來(lái)介紹圖解法。

如圖所示，我們用橫軸代表S，用縱軸代表D。圖形上任意一點(diǎn)都對(duì)應(yīng)一個(gè)確定的S和D的值，可以通過(guò)對(duì)此點(diǎn)的作垂直線和水平線分別求得。因?yàn)槊總€(gè)點(diǎn)（S,D）都是一個(gè)可能的解，所以圖形上的點(diǎn)成為解點(diǎn)。S=0且D=0的解點(diǎn)就是原點(diǎn)。因?yàn)镾和D都應(yīng)該是非負(fù)的，所以圖中只畫(huà)出S≥0且D≥0的部分。2.2圖解法

前面我們已經(jīng)得出了用來(lái)表示切割與印染時(shí)間的約束函數(shù)7S/10+D≤630

為了找到所有滿足此關(guān)系的解點(diǎn)，我們先將不等式改寫(xiě)為等式，求出滿足7S/10+D=630的點(diǎn)。假設(shè)S=0，解方程求D，可以得到解點(diǎn)（S=0，D=630）。為了找到另一個(gè)滿足方程的點(diǎn)，我們假設(shè)D=0，解出S，我們得到7S/10=630，S=900。因此第二個(gè)滿足方程的解點(diǎn)就是（S=900，D=0）。有了這兩點(diǎn)，我們可以畫(huà)出滿足等式7S/10+D=630的直線。這條直線成為切割與印染的約束線。2.2圖解法仔細(xì)觀察這兩個(gè)解：（S=200,D=200）和（S=600，D=500）。第一個(gè)解在約束線下面，第二個(gè)解在約束線上面。將這兩個(gè)解代入方程，分別得到340小時(shí)和920小時(shí)。因?yàn)?20大于630小時(shí)，所以解點(diǎn)（S=600，D=500）不滿足條件。因此它是不可行解。那么它所在的直線一側(cè)的解都是不可行的。另一側(cè)對(duì)這一約束條件是可行的。2.2圖解法如圖，我們用陰影區(qū)域表示滿足切割與印染約束條件的解。2.2圖解法

我們可以繼續(xù)得到對(duì)于每個(gè)單獨(dú)的約束條件可行解的范圍。每個(gè)約束條件的可行解如圖。2.2圖解法

將以上求得的圖重疊起來(lái)，就可以在一張圖里畫(huà)出四條約束線。陰影區(qū)包含了每一個(gè)同時(shí)滿足所有約束條件的解點(diǎn)。我們稱能夠滿足所有約束條件的解為可行解?？尚薪馑诘年幱皡^(qū)域?yàn)榭尚杏?。任何在可行域邊界上或在可行域?nèi)的解點(diǎn)都是可行解。2.2圖解法

相對(duì)于每一個(gè)可行解計(jì)算利潤(rùn)貢獻(xiàn)，不如對(duì)任意利潤(rùn)貢獻(xiàn)值找出所有的能產(chǎn)生同樣目標(biāo)值的可行解（S,D）。因?yàn)槲覀兊哪康氖且业疆a(chǎn)生最大利潤(rùn)貢獻(xiàn)的可行解，那么我們應(yīng)該選擇大一些的利潤(rùn)貢獻(xiàn)值，然后尋找可行解。因此假設(shè)利潤(rùn)分別為1800,3600和5400時(shí)，可以得到10S+9D=1800,10S+9D=3600,10S+9D=5400.2.2圖解法

從已經(jīng)畫(huà)出的利潤(rùn)線可以看出：(1)利潤(rùn)線之間相互平行；（2）利潤(rùn)越高的直線離原點(diǎn)越遠(yuǎn)。用P代表利潤(rùn)，目標(biāo)函數(shù)為P=10D+9D,整理得D=-10S/9+1P/9

因此每條利潤(rùn)線斜率都一樣，隨著P增加，D的截距也增加，所以利潤(rùn)越高的直線離原點(diǎn)越遠(yuǎn)?？尚杏蛏献罡叩狞c(diǎn)就是線性規(guī)劃的最優(yōu)解。2.2圖解法

仔細(xì)觀察圖，發(fā)現(xiàn)最優(yōu)解在切割印染約束線與成型約束線的交點(diǎn)處。7S/10+D=630S+2D/3=708

聯(lián)立解得D=252，S=540

所以Par公司的最優(yōu)生產(chǎn)量為540個(gè)標(biāo)準(zhǔn)袋和252個(gè)高級(jí)袋，利潤(rùn)貢獻(xiàn)為10*540+9*252=7668美元。對(duì)只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，決策變量的精確解可以先由圖解法確定最優(yōu)解點(diǎn)，然后解相應(yīng)的兩個(gè)方程得到。2.2圖解法2.2.1畫(huà)圖時(shí)的注意事項(xiàng)

畫(huà)圖的一個(gè)關(guān)鍵就是畫(huà)線性規(guī)劃的約束直線和目標(biāo)函數(shù)。畫(huà)直線方程的過(guò)程我們采用先找出滿足方程的任何兩個(gè)點(diǎn)，然后過(guò)這兩個(gè)點(diǎn)畫(huà)一條直線。如果約束線上的兩個(gè)點(diǎn)可以確定，那么雙變量線性規(guī)劃中的所有的約束線和目標(biāo)函數(shù)都可以畫(huà)出來(lái)。有時(shí)候找出約束線上的兩個(gè)點(diǎn)不容易，那么可以采取將圖形拉大、展開(kāi)的方法，描在負(fù)軸的擴(kuò)展圖形上。2.2圖解法2.2.2圖解法求解最大化問(wèn)題小結(jié)

1.為每個(gè)約束條件畫(huà)出可行解圖形

2.識(shí)別出同時(shí)滿足所有約束條件的解的可行域

3.畫(huà)出目標(biāo)函數(shù)線，表示可產(chǎn)生特定目標(biāo)函數(shù)值的決策變量的值

4.朝著使目標(biāo)函數(shù)值最大化方向平行移動(dòng)目標(biāo)函數(shù)線，直到移動(dòng)到可行域的邊界

5.在目標(biāo)函數(shù)線上具有最大值的任何可行解都是一個(gè)最優(yōu)解2.2圖解法

2.2.3松弛變量

除了最優(yōu)解和與之相關(guān)的利潤(rùn)貢獻(xiàn)，Par公司管理層希望知道關(guān)系每個(gè)生產(chǎn)運(yùn)作所需要的生產(chǎn)時(shí)間的信息。我們可以將最優(yōu)值（S=540，D=252）代入線性規(guī)劃的約束條件里來(lái)獲得該信息。2.2圖解法

這個(gè)完全方案告訴管理層生產(chǎn)540個(gè)標(biāo)準(zhǔn)袋和252個(gè)高級(jí)袋將需要耗用所有可用的切割與印染時(shí)間（630小時(shí)）以及所有可用的成型時(shí)間（708小時(shí)），但還有120個(gè)縫合時(shí)，18個(gè)小時(shí)檢查與包裝剩余，對(duì)這兩個(gè)部門來(lái)說(shuō)這些小時(shí)剩余是松弛的。在線性規(guī)劃術(shù)語(yǔ)里，對(duì)a≤約束條件的任何未用產(chǎn)能，都成為與約束條件對(duì)應(yīng)是松弛的。2.2圖解法

通常我們會(huì)將松弛變量引入到線性規(guī)劃中來(lái)，表示松弛或閑置的產(chǎn)能。未被使用的能力對(duì)利潤(rùn)并無(wú)貢獻(xiàn)；因此在目標(biāo)函數(shù)里，松弛變量的系數(shù)是零。在增加了四個(gè)松弛變量S1，S2，S3，S4之后，Par公司問(wèn)題的數(shù)學(xué)模型就是：2.2圖解法

如果線性規(guī)劃問(wèn)題的所有約束條件都用等式來(lái)表達(dá)時(shí)，這種寫(xiě)法被稱為標(biāo)準(zhǔn)型。

對(duì)于Par公司問(wèn)題的標(biāo)準(zhǔn)型來(lái)說(shuō)，我們發(fā)現(xiàn)最優(yōu)解（S=540，D=252），松弛變量的值是

縫合約束并不影響可行區(qū)域的大小，不管有沒(méi)有縫合約束，可行域的大小都是一樣的。只要其他3個(gè)部門能按時(shí)完成工作，縫合部門也能完成。這是因?yàn)榭p合工序不影響最優(yōu)解，它被稱為冗余約束。2.3極點(diǎn)與最優(yōu)解

假設(shè)Par公司生產(chǎn)的標(biāo)準(zhǔn)袋利潤(rùn)從10美元降到5美元，而高級(jí)袋的利潤(rùn)和所有的約束條件都不變。這個(gè)新問(wèn)題的數(shù)學(xué)模型同我們?cè)?.1節(jié)里說(shuō)的模型差不多都一樣，唯一有區(qū)別的就是目標(biāo)函數(shù)變成了：Max5S+9D

我們使用圖解法對(duì)目標(biāo)函數(shù)改變后的問(wèn)題求解。注意，約束條件不變，可行域不變，目標(biāo)函數(shù)變化，利潤(rùn)線變化。2.3極點(diǎn)與最優(yōu)解

通過(guò)平移利潤(rùn)線，讓它通過(guò)利潤(rùn)的最大值，我們找到了模型最優(yōu)解。圖形所對(duì)應(yīng)的決策變量值是S=300，D=420。標(biāo)準(zhǔn)袋利潤(rùn)的變化導(dǎo)致最優(yōu)解變化。我們削減了標(biāo)準(zhǔn)袋的產(chǎn)量，增加了高級(jí)袋的產(chǎn)量。2.3極點(diǎn)與最優(yōu)解

我們注意到所有的最優(yōu)解的點(diǎn)都在可行域的頂點(diǎn)或“拐點(diǎn)”上。在線性規(guī)劃術(shù)語(yǔ)中，這樣的頂點(diǎn)稱為可行域的極點(diǎn)。Par公司問(wèn)題的可行域一共有5個(gè)頂點(diǎn)，或者說(shuō)5個(gè)極點(diǎn)。線性規(guī)劃問(wèn)題的最優(yōu)解一定可以在可行區(qū)域的一個(gè)極點(diǎn)上找到。這個(gè)特點(diǎn)意味著我們?cè)趯ふ易顑?yōu)解時(shí)，不必對(duì)每一個(gè)可行解進(jìn)行計(jì)算。事實(shí)上，我們只要計(jì)算可行域的極點(diǎn)就可以了。Par公司的例子，我們只需要對(duì)5個(gè)極點(diǎn)進(jìn)行計(jì)算，找到其中利潤(rùn)值最大的點(diǎn)即可。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

M&D化學(xué)公司生產(chǎn)兩種產(chǎn)品，它們是生產(chǎn)肥皂和清洗劑的原材料?；趯?duì)當(dāng)前存貨水平和下月的市場(chǎng)需求分析，M&D管理層確定A和B的總產(chǎn)量至少要達(dá)到350加侖。特別地，公司的一個(gè)主要客戶訂購(gòu)的125加侖必須首先得到滿足。A產(chǎn)品的制造時(shí)間是每加侖2小時(shí)，B產(chǎn)品每加侖1小時(shí)。下個(gè)月總加工時(shí)間是600小時(shí)。M&D的目標(biāo)是在滿足客戶需求的前提下盡可能降低成本。每加侖A產(chǎn)品成本2美元，每加侖B產(chǎn)品成本3美元。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題我們首先定義出該問(wèn)題的目標(biāo)函數(shù)和決策變量。假設(shè)：A——A產(chǎn)品產(chǎn)量B——B產(chǎn)品產(chǎn)量因?yàn)锳成本每加侖2美元，B產(chǎn)品成本每加侖3美元，成本最小化目標(biāo)函數(shù)為Min2A+3B公司必須首先滿足主要客戶的125加侖產(chǎn)品。A至少125加侖。A≥125又因?yàn)榭偖a(chǎn)量必須至少350加侖，得到A+B≥350最后，公司最大可用加工時(shí)間600小時(shí)，得到2A+B≤6002.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

增加非負(fù)約束條件（A,B≥0）后，M&D公司問(wèn)題的線性規(guī)劃方程：

Min2A+3Bs.t.A≥125A+B≥3502A+B≤600A,B≥02.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

這個(gè)線性規(guī)劃模型只有兩個(gè)決策變量，所以我們可以用圖解法來(lái)求最優(yōu)產(chǎn)量。首先畫(huà)約束圖，找到可行區(qū)域，通過(guò)分別畫(huà)約束直線，檢驗(yàn)約束直線兩邊的點(diǎn)，每個(gè)約束條件的可行解就確定下來(lái)了。再把約束條件的可行域結(jié)合起來(lái)，我們就得到了整個(gè)問(wèn)題的可行域。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

為了找到使成本最小化的解，我們現(xiàn)在畫(huà)出基于某一特定的總成本值的目標(biāo)函數(shù)線。比如2A+3B=1200。為了能找到總成本較小的A和B，我們將直線左下移動(dòng)，注意，通過(guò)極點(diǎn)A=250和B=100的目標(biāo)函數(shù)是2A+3B=800。?？梢钥闯觯a(chǎn)能力約束與總生產(chǎn)時(shí)間約束是有效約束。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題2.5.1圖解法求解最小化問(wèn)題的主要過(guò)程

1.畫(huà)出每個(gè)約束條件的可行解。

2.確定滿足所有約束條件的可行域。

3.畫(huà)出目標(biāo)函數(shù)線，使不同的目標(biāo)函數(shù)值對(duì)應(yīng)不同的決策變量值。

4.平移目標(biāo)函數(shù)線，直至繼續(xù)移動(dòng)會(huì)使直線完全處于可行區(qū)域外，以確保目標(biāo)函數(shù)值最小。

5.目標(biāo)函數(shù)線上具有最小值的可行解為問(wèn)題的最優(yōu)解。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

2.5.2剩余變量

M&D化學(xué)公司問(wèn)題的最優(yōu)解說(shuō)明了通過(guò)使用所有的2A+B=600小時(shí)，可以達(dá)到A+B=350的產(chǎn)量。另外，A產(chǎn)量超過(guò)其最低要求，A=250加侖大于125加侖。多生產(chǎn)出來(lái)的這部分產(chǎn)品成為剩余。對(duì)于一個(gè)a≥約束條件的問(wèn)題，我們可以在不等式的左邊減去一個(gè)剩余變量使不等式變成等式。同松弛變量一樣，目標(biāo)函數(shù)中多個(gè)變量的值也是零，它們對(duì)目標(biāo)函數(shù)的值沒(méi)有影響。在包括兩個(gè)≥約束條件的剩余變量S1，S2和一個(gè)≤約束條件問(wèn)題的松弛變量S3后，M&D化學(xué)公司的線性規(guī)劃模型發(fā)生改變。Min2A+3B+0S1+0S2+0S3s.t.A-S1=125A+B-S2=3502A+B+S3=600A,B,S1,S2,S3≥02.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

現(xiàn)在所有的約束條件都是等式了。以上形式成為M&D化學(xué)公司問(wèn)題的標(biāo)準(zhǔn)形式。問(wèn)題最優(yōu)解A=250，B=100。松弛變量和剩余變量如下：

我們發(fā)現(xiàn)有效約束條件的松弛變量或剩余變量的值都為零時(shí)，總產(chǎn)量和生產(chǎn)時(shí)間約束條件達(dá)到最優(yōu)。而A產(chǎn)品需求的非有效約束條件相對(duì)應(yīng)的剩余變量值為125加侖。特定線性規(guī)劃問(wèn)題所面臨的約束條件的類型和數(shù)量取決于問(wèn)題中存在的特定條件。很可能出現(xiàn)的情況是一個(gè)問(wèn)題上既有≥型，也有≤型，還有=型約束條件。對(duì)于等式約束來(lái)說(shuō)，可行解必在約束直線上。2.5一個(gè)簡(jiǎn)單的最小化問(wèn)題

如果用圖解法求解線性規(guī)劃問(wèn)題，則沒(méi)有必要寫(xiě)出問(wèn)題的標(biāo)準(zhǔn)型。然而我們應(yīng)該可以計(jì)算松弛變量和剩余變量值，并理解它們的含義。在第十七章會(huì)介紹解決線性規(guī)劃問(wèn)題的代數(shù)方法——單純形法。用這種方法可以解決變量成千上萬(wàn)的線性規(guī)劃問(wèn)題。最后一點(diǎn)是，線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型其實(shí)是與原始形式等價(jià)的。也就是說(shuō)，一個(gè)線性規(guī)劃問(wèn)題的最優(yōu)解與其標(biāo)準(zhǔn)型的最優(yōu)解應(yīng)該是一樣的。標(biāo)準(zhǔn)型不改變問(wèn)題的本質(zhì)，只改變我們對(duì)問(wèn)題中約束條件的表示方法。2.6特例

這一部分中我們將會(huì)討論3種在求解線性規(guī)劃問(wèn)題中可能遇到的特殊情況。

1.多重最優(yōu)解

在目標(biāo)函數(shù)線與可行域邊界所在的約束線重合時(shí)，會(huì)導(dǎo)致多重最優(yōu)解。函數(shù)的最優(yōu)解將多于一個(gè)。

2.無(wú)可行解

無(wú)可行解是指線性規(guī)劃問(wèn)題不存在滿足全部約束條件（包括非負(fù)約束）的解。沒(méi)有任何一個(gè)點(diǎn)可以同時(shí)滿足所有的約束條件以及非負(fù)約束。

3.無(wú)界解

如果一個(gè)最大化線性規(guī)劃問(wèn)題的解可以無(wú)限地變大，卻不違反任何約束條件，我們就稱這個(gè)解是無(wú)界解。對(duì)于一個(gè)最小化問(wèn)題，如果它的解可以無(wú)限地變小，那么它的解也是無(wú)界的。這種條件被稱為管理烏托邦。2.6特例

2.6.1多重最優(yōu)解

我們?cè)倩氐絇ar公司的例子上去。假設(shè)生產(chǎn)每個(gè)標(biāo)準(zhǔn)袋利潤(rùn)為6.3美元，目標(biāo)函數(shù)就變成6.3S+9D。這時(shí)再用圖解法。如圖，最優(yōu)解雖然還在極點(diǎn)上，但是，兩個(gè)極點(diǎn)都是最優(yōu)點(diǎn)：極點(diǎn)4（S=300，D=420）極點(diǎn)3（S=540，D=252）這兩個(gè)最優(yōu)點(diǎn)之間的任何點(diǎn)也都是最優(yōu)解。如（S=420，D=336）在兩個(gè)極點(diǎn)中間，它也使目標(biāo)函數(shù)達(dá)到最大（5670）2.6特例

2.6.2無(wú)可行解

為了解釋無(wú)可行解，我們?cè)倏碢ar公司的例子。假設(shè)管理層確定公司必須至少生產(chǎn)500個(gè)標(biāo)準(zhǔn)袋和360個(gè)高級(jí)袋。在圖形中就必須重新畫(huà)出問(wèn)題的解的區(qū)域以反映兩個(gè)新增的要求。左下方陰影區(qū)域表示生產(chǎn)能力的解，右上方陰影區(qū)域表示產(chǎn)量要求。因此，如果管理層增加這兩個(gè)產(chǎn)量約束條件，該問(wèn)題就沒(méi)有可行域了。2.6特例

我們可以說(shuō)明這個(gè)問(wèn)題的不可行性，同時(shí)可以知道想要完成管理層的任務(wù)，至少還要增加多少資源。運(yùn)用線性規(guī)劃分析可以發(fā)現(xiàn)不可行的情況，并開(kāi)始改變我們的行為。表