【正文】 中 z行為 不考慮 dj 的初始模型，根據(jù)單純形方法選擇進(jìn)基變量和離基變量，進(jìn)行單純形運(yùn)算，得到如下形式 基 x1 x2 x3 x4 x5 x6 解 z 4d2/4+3/2d3d1 0 0 1+d2/2 2d2/4+d3/2 0 1350+100d2+230d3 x2 1/4 1 0 1/2 1/4 0 100 x3 3/2 0 1 0 1/2 0 230 x6 2 0 0 2 1 1 20 除了簡(jiǎn)約費(fèi)用（ Z方程系數(shù)）發(fā)生改變外，新的最優(yōu)表與原始的最優(yōu)表完全相同。這意味著目標(biāo)函數(shù)系數(shù)的改變可以只影響問(wèn)題的最優(yōu)性條件。 88 新的 z行的檢查說(shuō)明 dj 的系數(shù)直接來(lái)自最優(yōu)表約束的系數(shù)。計(jì)算新的簡(jiǎn)約費(fèi)用的一種方法就是，在最有表上增加新的頂行和新的最左邊列，頂行的這些變量是相應(yīng)于每個(gè)變量的該變量 dj 。最左邊的列，由 z行的 1和每個(gè)基變量行中的 dj構(gòu)成。記住，對(duì)于松弛變量 dj=0. d1 d2 d3 0 0 0 解 基 x1 x2 x3 x4 x5 x6 1 z 4 0 0 1 2 0 1350 d2 x2 1/4 1 0 1/2 1/4 0 100 d3 x3 3/2 0 1 0 1/2 0 230 0 x6 2 0 0 2 1 1 20 89 對(duì)于每個(gè)變量（或 z 的值）計(jì)算新的簡(jiǎn)約費(fèi)用，用最左端列相應(yīng)的元素乘以它所在列的元素，并求和，然后減去頂行的元素。例如對(duì)于 x1，有 左端列 d1 x1列 左端列 基 x1 1 z 4 4 1 d2 x2 1/4 d2/4 d3 x3 3/2 3/2d3 0 x6 2 2 0 x1的簡(jiǎn)約費(fèi)用 = 4d2/4+3/2d3d1 注意，對(duì)于基變量應(yīng)用這些計(jì)算總是產(chǎn)生零簡(jiǎn)約費(fèi)用，這事一個(gè)已經(jīng)理論證明的結(jié)果。對(duì)于解列應(yīng)用相同的規(guī)則，得到 Z=1350+100d2+230d3 90 因?yàn)樘幚淼氖菢O大化問(wèn)題，所以只要對(duì)于所有的非基變量新簡(jiǎn)約費(fèi)用（ z方程的系數(shù)），保持非負(fù)（單純形法迭代結(jié)束時(shí)，非基變量的系數(shù)要為正?。?，則當(dāng)前解就保持最優(yōu)。因此，對(duì)于所有非基變量 x1， x4， x5，有下列最優(yōu)性條件 4d2/4+3/2d3d1≥0 1+d2/2 ≥0 2d2/4+d3/2 ≥0 這些條件必須同時(shí)滿足才能維持當(dāng)前最優(yōu)解的最優(yōu)性。 91 為了解釋這些條件的使用，假定 TOYCO的目標(biāo)函數(shù)從 Max z=3x1+2x2+5x3 變?yōu)? Max z=2x1+1x2+6x3 則 d1=23=1美元， d2=12=1美元， d3=65=1美元，代入給定條件中，得到 92 4d2/4+3/2d3d1=44(1) +3/2(1)(1)=≥0 （滿足） 1+d2/2 =1+1/2(1)=≥0 （滿足） 2d2/4+d3/2 =2(1)/4+(1)/2=≥0 （滿足） 結(jié)果說(shuō)明，所作的上述改變?nèi)匀槐３之?dāng)前解(x1=0,x2=100,x3=230)最優(yōu)。因此，除了目標(biāo)函數(shù)變化到Z=1350+100（ 1） +230 （ 1） =1480美元，不需要做進(jìn)一步計(jì)算。如果有任何一個(gè)條件不滿足的話，則必須求出新的解。 到目前為止的討論已經(jīng)處理了極大化情況，對(duì)于極小化情況，差別僅是簡(jiǎn)約費(fèi)用（ z方程系數(shù)）必須是 ≤0才能維持最優(yōu)性 . 93 一般最優(yōu)性條件可以確定特定的情況，這里改變量 dj一次僅有一個(gè)發(fā)生變化，而不是同步改變。這種分析等價(jià)于考慮下列 3種情況： 1 1 2 31 2 2 31 2 3 3( 1 ) m a x ( 3 ) 2 5( 2) m a x 3 ( 2 ) 5( 3 ) m a x 3 2 ( 5 )z d x x xz x d x xz x x d x? ? ? ?? ? ? ?? ? ? ?當(dāng)個(gè)條件可以看成是同步改變的特例 情況 1 在同步改變的條件中置 d2= d3=0，則有 114 0 4dd? ? ? ?? ? ?94 情況 2 在同步改變的條件中置 d1= d3=0，則有 222 2 22214 0 16411 0 2 2 8212 0 84ddd d ddd?? ? ? ????? ? ? ? ? ? ? ? ????? ? ? ???情況 3 在同步改變的條件中置 d1= d2=0，則有 2332338408231 32 0 42ddddd?? ? ? ? ? ??? ? ? ? ???? ? ? ? ???95 所給出的單個(gè)條件能夠依照總的單位收入來(lái)表示。例如，對(duì)于玩具卡車(chē) (變量 x2)，總的單位收入是 2+d2，相應(yīng)的條件是 2≤d2≤8，表示成 2+(2) ≤d2≤2+8 或 0美元 ≤玩具卡車(chē)的單位收入 ≤10美元 這個(gè)條件假定玩具火車(chē)和玩具汽車(chē)的單位收入分別固定在 3美元和 5美元。 允許區(qū)間 [0,10]美元表明，玩具卡車(chē) (變量 x2)的單位收入可以是最低 0美元或最高 10美元而不改變當(dāng)前的最優(yōu)解， x1=0， x2=100， x3=230，但總收入將變化到 1350+100d2 96 注意到下列事實(shí)是重要的，改變量 d1， d2， d3可以均在它們所許可的單個(gè)區(qū)域內(nèi)，而不必滿足同步條件，反之亦然。例如，考慮 max z=6x1+8x2+3x3 這里 d1=63美元， d2=82=6美元， d3=35=2美元，他們都在可以允許的單個(gè)區(qū)域 1 2 38( 4 , 2 8 , )3d d d? ? ? ? ? ? ? ? ? ? ?然而，相應(yīng)的同步改變條件將產(chǎn)生 212231 3 1 34 4 ( 6) ( 2) 3 0 ( )4 2 4 2111 1 ( 6) 4 0 ( )221 1 1 12 2 ( 6) ( 2) 0 ( )4 2 4 2ddddd? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?不 滿 足滿 足不 滿 足97 上述結(jié)果可以總結(jié)如下： （ 1）只要改變目標(biāo)函數(shù)系數(shù)的該變量 dj， j=1,2,…,n 滿足所有的最優(yōu)性條件（當(dāng)改變是同時(shí)發(fā)生時(shí)），或落在最優(yōu)性區(qū)域之內(nèi)（當(dāng)改變是單個(gè)發(fā)生時(shí)），那么最優(yōu)變量的最優(yōu)值保持不變。 （ 2）對(duì)于其他的情況，也就是同步改變時(shí)最優(yōu)性條件不滿足或者不滿足單個(gè)可行性區(qū)域，那么可以用新的 dj 值重新解該問(wèn)題，或者應(yīng)用將在后續(xù)課程介紹的后最優(yōu)分析來(lái)解決此類(lèi)問(wèn)題。 98 習(xí)題 Electra公司生產(chǎn) 4種類(lèi)型的馬達(dá)，每種馬達(dá)在各自的裝配線上裝配。裝配線各自的生產(chǎn)能力是每天 500， 500， 800， 750臺(tái)馬達(dá)。 1型馬達(dá)使用8個(gè)單位的某種電子元件， 2型馬達(dá)使用 5個(gè)單位， 3型馬達(dá)使用 4個(gè)單位，4型馬達(dá)使用 6個(gè)單位。電子元件的供應(yīng)者每天提供 8000件。對(duì)于每種類(lèi)型的馬達(dá)，每臺(tái)的售價(jià)分別為 60、 25和 30美元。 （ a）確定每天的最優(yōu)產(chǎn)品生產(chǎn)策略 （ b）現(xiàn)有的生產(chǎn)計(jì)劃安排能滿足 Electra的需要。然而，由于競(jìng)爭(zhēng)，Electra可能需要降低 2型馬達(dá)的售價(jià)。要想不改變現(xiàn)有的生產(chǎn)計(jì)劃安排最多可以降價(jià)多少？ （ c） Electra還決定大幅度把所有類(lèi)型的馬達(dá)價(jià)格降低 25%。用靈敏度分析是否保持最優(yōu)解保持不變。 （ d）目前， 4型馬達(dá)不生產(chǎn)。它的價(jià)格應(yīng)該在生產(chǎn)計(jì)劃中增加多少？ 99 第 3章 對(duì)偶性與后最優(yōu)分析 前一章討論的是資源的可利用性（約束右端項(xiàng)）變化的靈敏度、單位利潤(rùn)或單位費(fèi)用（目標(biāo)函數(shù)的系數(shù)）變化的靈敏度分析問(wèn)題，旨在回答資源該如何使用、生產(chǎn)量如何決策的問(wèn)題。 如果需要對(duì)模型的參數(shù)進(jìn)行有目的的調(diào)整，求出新的最優(yōu)解，則需要進(jìn)行后最優(yōu)分析。 100 前一章討論了利用有限的資源如何安排生產(chǎn)才能獲得最大的利潤(rùn)的問(wèn)題。 在線性規(guī)劃模型中，決策變量個(gè)數(shù)比約束的個(gè)數(shù)小得多，通過(guò)求解對(duì)偶問(wèn)題可以節(jié)省計(jì)算量，因?yàn)閺膶?duì)偶問(wèn)題的解可以自動(dòng)地求出原始問(wèn)題的解。 現(xiàn)在從另一角度來(lái)討論這個(gè)問(wèn)題。 對(duì)偶問(wèn)題的提出 對(duì)偶問(wèn)題的定義 101 例 I II 資源限量 設(shè)備 原材料 A 原材料 B 1 4 0 2 0 4 8 臺(tái)時(shí) 16kg 12kg 利潤(rùn) 2 3 假設(shè)該工廠的決策者決定這些資源不用來(lái)生產(chǎn)而是考慮將其出租或出售。這時(shí)決策者就要考慮給每種資源如何定價(jià)的問(wèn)題。 102 數(shù)學(xué)模型 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x x2 ? 0 x1 x2 ? 設(shè)用 y1,y2,y3分別表示出租單位設(shè)備臺(tái)時(shí)的價(jià)格和出讓單位原材料 A,B的價(jià)格 。 于是 ? y1+4y2≥2 ? 2y1+4y3≥3 ? 則所有資源出租和出讓 ， 其所得收入為 ? ω=8y1+16y2+12y3 ? 則得到下面的線性規(guī)劃問(wèn)題 ? minω=8y1+16y2+12y3 ? y1+4y2≥2 ? 2y1+4y3≥3 ? y1,y2,y3≥0 ? 稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為原問(wèn)題的對(duì)偶問(wèn)題。 103 ? 在大多數(shù)線性規(guī)劃處理中，其原始的形式包含最優(yōu)化含義（極大化或者極小化）、約束的類(lèi)型（ ≤、 ≥或＝），以及變量的方向（非負(fù)、無(wú)限制）。 ? 這種處理有點(diǎn)混亂，對(duì)此我們給出一種單一的定義，把所有形式的原始問(wèn)題自動(dòng)地包含進(jìn)來(lái)。這就需要我們了解對(duì)偶問(wèn)題。 ? 對(duì)偶問(wèn)題是由原始線性規(guī)劃模型直接按照系統(tǒng)化定義的一種線性規(guī)劃。這個(gè)問(wèn)題有著極為緊密的關(guān)系，以至于一個(gè)問(wèn)題的最優(yōu)解自動(dòng)地提供另一個(gè)問(wèn)題的最優(yōu)解。 104 關(guān)于對(duì)偶問(wèn)題的定義，要求將原始問(wèn)題表示成為單純法中提出的等式形式約束（所有約束是等式方程，有非負(fù)的右端項(xiàng)，并且變量非負(fù)）。 從原始問(wèn)題最優(yōu)解得到的任何結(jié)果都可以直接用到相應(yīng)的對(duì)偶問(wèn)題上。 為了說(shuō)明如何構(gòu)造對(duì)偶問(wèn)題，定義等式形式的原始問(wèn)題如下： 11m a x( m in). . , 1 , 2 , ... ,0 , 1 , 2 , ... ,njjjnij j ijjz c xs t a x b i mx j n??? ??????或變量 xj， j=1,2,…,n 包含任何剩余變量、松弛變量和人工變量。 105 對(duì)偶變量 原始問(wèn)題變量 右端項(xiàng) x1 x2 … xj … xn c1 c2 … cj … y1 a11 a12 … a1j … a1j y2 a21 a22 … a2j … a2j ┋ ┋ ┋ ┋ ┋ ┋ ┋ ym am1 am2 … amj … amj ↑ 第 j個(gè)對(duì)偶約束 對(duì)偶目標(biāo)函數(shù)系數(shù) 表 1 從原始問(wèn)題構(gòu)造對(duì)偶問(wèn)題 106 原始問(wèn)題 對(duì)偶問(wèn)題 11m a x. . , 1 , 2 , ... ,0 , 1 , 2 , ... ,njjjnij j ijjz c xs t a x b i mx j n??? ??????11m in. . , 1 , 2 , ...,0 , 1 , 2 , ...,mjjimij j jiiw b ys t a y c j ny i m??? ??????上表和上式說(shuō)明了如何從原始問(wèn)題構(gòu)造出對(duì)偶問(wèn)題。事實(shí)上，我們有 （ 1）對(duì)偶變量是針對(duì)原始問(wèn)題每個(gè)（約束）方程定義的； （ 2）對(duì)偶約束是針對(duì)原始問(wèn)題的每個(gè)變量定義的； （ 3）原始問(wèn)題變量約束（列）的系數(shù)定義對(duì)偶約束左端項(xiàng)的系數(shù)，它的目標(biāo)系數(shù)定義了右端項(xiàng)； （ 4）對(duì)偶目標(biāo)系數(shù)等于原始問(wèn)題約束方程的右端項(xiàng) 107 下表 2概況了確定最優(yōu)化含義（極大化或者極小化）、約束的類(lèi)型（ ≤、 ≥或＝），以及對(duì)偶變量符號(hào)的規(guī)則。 注意： 在對(duì)偶問(wèn)題中，最優(yōu)化含義總是與原始問(wèn)題最優(yōu)化含義相反。 記住： 對(duì)偶問(wèn)題約束類(lèi)型（ ≤或 ≥ ）的一種容易的方法是，如果對(duì)偶目標(biāo)求極小，則所有約束都是 ≥型的，當(dāng)對(duì)偶目標(biāo)求極大化時(shí)，約束類(lèi)型相反。 原始問(wèn)題的目標(biāo) * 對(duì)偶問(wèn)題 目標(biāo) 約束類(lèi)型 變量符號(hào) 極大化 極小