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