[理學(xué)]第4章：目標(biāo)規(guī)劃ppt課件

1、第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃(Goal programming)目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃的靈敏度分析 WinQSBWinQSB軟件應(yīng)用軟件應(yīng)用 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。目標(biāo)規(guī)劃是決策的需要而逐步發(fā)展起來的一個分支。目標(biāo)規(guī)劃是60年代初年代初由美國科學(xué)家由美國科學(xué)家A.charnes和和W.cooper在在管理模型和線性規(guī)劃的管理模型和線性規(guī)劃的工業(yè)應(yīng)用工業(yè)應(yīng)

2、用中一書提出的。中一書提出的。 線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)可行解，而目線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)可行解，而目標(biāo)規(guī)劃可以在相互矛盾的約束條件下找到滿意解，得出決策問標(biāo)規(guī)劃可以在相互矛盾的約束條件下找到滿意解，得出決策問題的滿意方案。題的滿意方案。 線性規(guī)劃只能處理一個目標(biāo)的問題，而目標(biāo)規(guī)劃則能夠統(tǒng)線性規(guī)劃只能處理一個目標(biāo)的問題，而目標(biāo)規(guī)劃則能夠統(tǒng)籌兼顧多個目標(biāo)的關(guān)系，更能適用于經(jīng)營管理中的多目標(biāo)決策籌兼顧多個目標(biāo)的關(guān)系，更能適用于經(jīng)營管理中的多目標(biāo)決策問題。問題。目標(biāo)規(guī)劃與線性規(guī)劃的比較目標(biāo)規(guī)劃與線性規(guī)劃的比較: : 目標(biāo)規(guī)劃找到的最優(yōu)解是指盡可能達(dá)到或接近一個或多個目標(biāo)

3、規(guī)劃找到的最優(yōu)解是指盡可能達(dá)到或接近一個或多個已給定目標(biāo)值的滿意解。已給定目標(biāo)值的滿意解。 線性規(guī)劃對約束條件是不分主次地同等對待，而目標(biāo)規(guī)劃線性規(guī)劃對約束條件是不分主次地同等對待，而目標(biāo)規(guī)劃可以根據(jù)實際需要靈活地給予輕重緩急的考慮。可以根據(jù)實際需要靈活地給予輕重緩急的考慮。第一節(jié)第一節(jié) 目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型一、目標(biāo)規(guī)劃問題的提出一、目標(biāo)規(guī)劃問題的提出 【例例4-14-1】產(chǎn)品生產(chǎn)問題。某企業(yè)計劃生產(chǎn)產(chǎn)品生產(chǎn)問題。某企業(yè)計劃生產(chǎn)I I、IIII兩種型號的兩種型號的產(chǎn)品，具體相關(guān)數(shù)據(jù)如下表所示：產(chǎn)品，具體相關(guān)數(shù)據(jù)如下表所示：108利潤1021設(shè)備工時1112原材料擁有

4、量 產(chǎn)品 消耗 資源 解：解：若用若用x xi i（i i1,21,2）分別表示）分別表示I I、IIII兩種產(chǎn)品的生產(chǎn)量，兩種產(chǎn)品的生產(chǎn)量，則問題可以歸結(jié)為如下的線性規(guī)劃問題數(shù)學(xué)模型：則問題可以歸結(jié)為如下的線性規(guī)劃問題數(shù)學(xué)模型： 21108maxxxZ0,102112212121xxxxxx 這是一個單目標(biāo)的線性規(guī)劃模型，可求出最優(yōu)解為這是一個單目標(biāo)的線性規(guī)劃模型，可求出最優(yōu)解為x14件，件，x23件，件，Max z=62元。元。企業(yè)生產(chǎn)中可能有下列情況出現(xiàn)：企業(yè)生產(chǎn)中可能有下列情況出現(xiàn)： 根據(jù)市場對該產(chǎn)品銷售預(yù)測得知，產(chǎn)品根據(jù)市場對該產(chǎn)品銷售預(yù)測得知，產(chǎn)品I I的利潤有下降的的利潤有下降的

5、趨勢，故應(yīng)考慮產(chǎn)品趨勢，故應(yīng)考慮產(chǎn)品I I的產(chǎn)量不應(yīng)大于產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品IIII的產(chǎn)量。的產(chǎn)量。 盡可能不超過計劃使用原材料，因為超過計劃后，需要盡可能不超過計劃使用原材料，因為超過計劃后，需要高價采購原材料，導(dǎo)致成本增加。高價采購原材料，導(dǎo)致成本增加。 應(yīng)盡量充分利用原有的設(shè)備工時，而不希望加班生產(chǎn)。應(yīng)盡量充分利用原有的設(shè)備工時，而不希望加班生產(chǎn)。 應(yīng)盡可能達(dá)到或超過原計劃利潤指標(biāo)應(yīng)盡可能達(dá)到或超過原計劃利潤指標(biāo)5656。 此時，企業(yè)決策者的考慮用數(shù)學(xué)表達(dá)式表述為：此時，企業(yè)決策者的考慮用數(shù)學(xué)表達(dá)式表述為： 56108102112021212121xxxxxxxx二、目標(biāo)規(guī)劃的一般概念

6、二、目標(biāo)規(guī)劃的一般概念 1 1目標(biāo)值和偏差變量目標(biāo)值和偏差變量 目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。 實現(xiàn)值或決策值：是指當(dāng)決策變量實現(xiàn)值或決策值：是指當(dāng)決策變量x xj j 選定以后，目標(biāo)函數(shù)選定以后，目標(biāo)函數(shù)的對應(yīng)值。的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目標(biāo)值偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目標(biāo)值之間的差異之間的差異, ,記為記為 d d 。 正偏差變量：表示實現(xiàn)值超過目標(biāo)值的部分，記為正偏差變量：表示實現(xiàn)值超過目標(biāo)值的部分，記為 d d。 負(fù)偏差變量：表示實現(xiàn)值未達(dá)到目標(biāo)值的部分，記為負(fù)偏差變量：表示

7、實現(xiàn)值未達(dá)到目標(biāo)值的部分，記為 d d。 在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有故有 d d d d 0,0,并規(guī)定并規(guī)定d d0, d d0 當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d d0，d d0 當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示： d d0，d d0 當(dāng)恰好完成指標(biāo)時則表示：當(dāng)恰好完成指標(biāo)時則表示： d d0，d d0 d d d d 0 0 成立。成立。 引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，即

8、目標(biāo)約束。限制，即目標(biāo)約束。 目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。2 2、目標(biāo)約束和絕對約束、目標(biāo)約束和絕對約束 絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。解。所以，絕對約束是硬約束。3 3、優(yōu)先因子與權(quán)系數(shù)、優(yōu)先因子與權(quán)系數(shù) 優(yōu)先因子優(yōu)先因子Pk 是將決策

9、目標(biāo)按其重要程度排序并表示出來。是將決策目標(biāo)按其重要程度排序并表示出來。P1P2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)權(quán)系數(shù)k 區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定?？梢暰唧w情況而定。4 4、目標(biāo)規(guī)劃的目標(biāo)函數(shù)、目標(biāo)規(guī)劃的目標(biāo)函數(shù) 目標(biāo)函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為：目標(biāo)函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為：ddfZ,min 一般說來，有以下三種情況，但只能出現(xiàn)其中之一：一般說來，有以下三種情況，但只能出現(xiàn)其中之一： 要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差

10、變量要盡可能小，則：小，則： 要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則：變量盡可能小，則：ddfZmin 要求超過目標(biāo)值，即對目標(biāo)的正偏差要求不限，而負(fù)偏差要求超過目標(biāo)值，即對目標(biāo)的正偏差要求不限，而負(fù)偏差越小越好，這時的目標(biāo)函數(shù)為：越小越好，這時的目標(biāo)函數(shù)為：dfZmin對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。dfZmin 對于這種解來說，前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn)，而對于這種解來說，前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標(biāo)就不一定能保證實現(xiàn)

11、或部分實現(xiàn)，有些可能就不能后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。實現(xiàn)。 5 5、滿意解（具有層次意義的解）、滿意解（具有層次意義的解） 目標(biāo)規(guī)劃問題的求解是在不破壞上一級目標(biāo)的前提下，實現(xiàn)目標(biāo)規(guī)劃問題的求解是在不破壞上一級目標(biāo)的前提下，實現(xiàn)下一級目標(biāo)的最優(yōu)化。因此，這樣最后求出的解就不是通常意下一級目標(biāo)的最優(yōu)化。因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，我們稱為它為義下的最優(yōu)解，我們稱為它為滿意解滿意解。 三、目標(biāo)規(guī)劃的一般模型三、目標(biāo)規(guī)劃的一般模型 如例如例4-14-1，產(chǎn)品，產(chǎn)品I I的產(chǎn)量不應(yīng)大于產(chǎn)品的產(chǎn)量不應(yīng)大于產(chǎn)品IIII的產(chǎn)量，其目標(biāo)優(yōu)先的產(chǎn)量，其目標(biāo)優(yōu)

12、先級為級為p p1 1，則第一優(yōu)先級的目標(biāo)函數(shù)為：，則第一優(yōu)先級的目標(biāo)函數(shù)為：11min p d 第二個目標(biāo)要求是應(yīng)盡量充分利用原有的設(shè)備工時，而不希第二個目標(biāo)要求是應(yīng)盡量充分利用原有的設(shè)備工時，而不希望加班生產(chǎn)，其目標(biāo)優(yōu)先級為望加班生產(chǎn)，其目標(biāo)優(yōu)先級為p p2 2，則其目標(biāo)函數(shù)應(yīng)為：，則其目標(biāo)函數(shù)應(yīng)為：222min()p dd 第三個目標(biāo)要求是企業(yè)希望達(dá)到并超過計劃利潤第三個目標(biāo)要求是企業(yè)希望達(dá)到并超過計劃利潤5656，其目標(biāo)優(yōu)，其目標(biāo)優(yōu)先級為先級為p p3 3，則其相應(yīng)的目標(biāo)函數(shù)為：，則其相應(yīng)的目標(biāo)函數(shù)為：33min p d則例則例1 1對應(yīng)的目標(biāo)規(guī)劃數(shù)學(xué)模型為對應(yīng)的目標(biāo)規(guī)劃數(shù)學(xué)模型為 ：

13、3322211mindpddpdpZ3 , 2 , 10,5610810201122133212221112121iddxxddxxddxxddxxxxii 對于任何一個多目標(biāo)決策問題，不妨設(shè)問題有對于任何一個多目標(biāo)決策問題，不妨設(shè)問題有n n個決策變量、個決策變量、m m個絕對約束、個絕對約束、L L（1 1）個目標(biāo)約束、）個目標(biāo)約束、K K（KLKL）個優(yōu)先等級。）個優(yōu)先等級?？梢越o出多目標(biāo)決策問題的一般目標(biāo)規(guī)劃模型：可以給出多目標(biāo)決策問題的一般目標(biāo)規(guī)劃模型： KkLlllllkddpZ11minLlddnjxmibxaLlgddxclljinjjijlllnjjlj, 2 , 10, 2

14、 , 10, 2 , 1,2 , 111四、建模步驟四、建模步驟 1 1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；列出目標(biāo)約束與絕對約束； 3 3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 P Pk k（k=1.2Kk=1.2K）。）。 2 2、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。變量即可。 5 5、根據(jù)決策者的要求，

15、按下列情況之一構(gòu)造一個由、根據(jù)決策者的要求，按下列情況之一構(gòu)造一個由 lldd恰好達(dá)到目標(biāo)值，取恰好達(dá)到目標(biāo)值，取 。ld允許超過目標(biāo)值，取允許超過目標(biāo)值，取 。ld不允許超過目標(biāo)值，取不允許超過目標(biāo)值，取 。 優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)?；哪繕?biāo)函數(shù)，即達(dá)成函數(shù)。klkl和和 4 4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)的不同，賦予相應(yīng)的權(quán)系數(shù) 。第二節(jié)第二節(jié) 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法 圖解法同

16、樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。和過程。 圖解法解題步驟如下：圖解法解題步驟如下： 1、確定各約束條件的可行域，即將所有約束條件（包括目、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；示出來； 2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值

17、增大的方向；變量值增大的方向； 3、求滿足最高優(yōu)先等級目標(biāo)的解；、求滿足最高優(yōu)先等級目標(biāo)的解； 4、轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等、轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解； 5、重復(fù)、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止； 6、確定最優(yōu)解和滿意解。、確定最優(yōu)解和滿意解?！纠坑脠D解法求解例用圖解法求解例4-1目標(biāo)規(guī)劃問題目標(biāo)規(guī)劃問題【例例】用圖解法求解目標(biāo)規(guī)劃問題用圖解法求解目標(biāo)規(guī)劃問題0,82122201232124164214421

18、33212221112121iiddxxddxxddxxddxxddxxxx4333322211)(3)(mindpddpddpdpz0 x2 x11d1d2d2dA AB BC C3d3d4d4dE EK KML LJ J0,8212220123212416421442133212221112121iiddxxddxxddxxddxxddxxxx4333322211)(3)(mindpddpddpdpz01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B(0.6250,4.6875) B(0.6250,4.6875)、C(0,5.2083)C(0,5

19、.2083)，B B、C C 線段上的所有點(diǎn)線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。均是該問題的解（無窮多最優(yōu)解）。)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll第三節(jié)第三節(jié) 目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的單純形法mn+2mm2 m1K PK 2n+2m22212P2 1n+2m12111P1 kjemn+2mem2em1bomxjm cjme2n+2me22e21bo2xj2cj2e1n+2me12e11 bo1xj1cj1 xn+2m x2 x1bXBCBcn+2mc2c1Cj 一、目標(biāo)規(guī)

20、劃單純形法的一般形式一、目標(biāo)規(guī)劃單純形法的一般形式目標(biāo)規(guī)劃求解時，其單純形表的一般結(jié)構(gòu)如下表：目標(biāo)規(guī)劃求解時，其單純形表的一般結(jié)構(gòu)如下表： 2 2、建立初始單純形表。、建立初始單純形表。 一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計算出各列的檢驗數(shù)，填入表的下半部算出各列的檢驗數(shù)，填入表的下半部 。 3 3、檢驗是否為滿意解。判別準(zhǔn)則如下：、檢驗是否為滿意解。判別準(zhǔn)則如下： 首先檢查首先檢查k k ( (k k=1.2=1.2K K

21、) )是否全部大于零？如果全部大于是否全部大于零？如果全部大于零，則表示目標(biāo)均已全部達(dá)到，獲得最優(yōu)解，停止計算轉(zhuǎn)到第零，則表示目標(biāo)均已全部達(dá)到，獲得最優(yōu)解，停止計算轉(zhuǎn)到第7 7步；否則轉(zhuǎn)入。步；否則轉(zhuǎn)入。 二、單純形法的計算步驟二、單純形法的計算步驟 如果某一個如果某一個 k k 00。說明第。說明第k k個優(yōu)先等級的目標(biāo)尚未達(dá)到個優(yōu)先等級的目標(biāo)尚未達(dá)到, ,必須檢查必須檢查P Pk k這一的檢驗數(shù)這一的檢驗數(shù)kjkj(j=1.2n+2m).(j=1.2n+2m).若若P Pk k這一行某些負(fù)這一行某些負(fù)檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有

22、正檢驗數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3 3步；若步；若P Pk k這一行全部負(fù)檢驗數(shù)這一行全部負(fù)檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標(biāo)雖沒達(dá)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第7 7步。步。 1 1、將目標(biāo)規(guī)劃問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形。、將目標(biāo)規(guī)劃問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形。 4 4、確定進(jìn)基變量。、確定進(jìn)基變量。 在在P Pk k行，從那些上面沒有正檢驗數(shù)的負(fù)檢驗數(shù)中，選絕對值行，從那些上面沒有正檢驗數(shù)的負(fù)檢驗數(shù)中，選絕對值最大者，對應(yīng)的變量最大者，對

23、應(yīng)的變量x xs s就是進(jìn)基變量。若就是進(jìn)基變量。若P Pk k行中有幾個相同的絕行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負(fù)檢驗數(shù)的所在列的最大的負(fù)檢驗數(shù)的所在列的x xs s為進(jìn)基變量。假如仍無法確定，為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。 5 5、確定出基變量、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則：其方法同線性規(guī)劃，即依據(jù)最小比值法則：rsorisissiebeeb0/min故確定故確定xr為出基變量，為出基

24、變量，ers為主元素。若有幾個相同的行可供為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為選擇時，選最上面那一行所對應(yīng)得變量為xr 。 6 6、旋轉(zhuǎn)變換（變量迭代）、旋轉(zhuǎn)變換（變量迭代） 以主元素為中心進(jìn)行變換，得到新的單純形表，獲得一組新以主元素為中心進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第解，返回到第3 3步。步。 7 7、對求得的解進(jìn)行分析、對求得的解進(jìn)行分析 若計算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)若計算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行

25、第2 2步。步?！纠?-2 】用單純形法求解下列目標(biāo)規(guī)劃問題用單純形法求解下列目標(biāo)規(guī)劃問題3322211mindpddpdpz3 , 2 , 10,561081020112321332122211121321iddxxxddxxddxxddxxxxxii3213,dddx 解：解：本例中由于各目標(biāo)約束中均存在負(fù)偏差變量，取本例中由于各目標(biāo)約束中均存在負(fù)偏差變量，取 為初始基變量，計算檢驗數(shù)，并將有關(guān)數(shù)據(jù)填入單為初始基變量，計算檢驗數(shù)，并將有關(guān)數(shù)據(jù)填入單純形表中，如下表：純形表中，如下表：3232188110200ppppk-1110856-112110-11-1100112110000001

26、p1pjc1xBX2p2p2p3pbBC3p3pij2p1d3x3x3d2x3d1d2d2d2d1d3d-8-1-2-10121表中第一列檢驗數(shù)計算方法為：表中第一列檢驗數(shù)計算方法為：20|max2222jj即即x x2 2進(jìn)基變量進(jìn)基變量1155.652101056,210,111min2d即即 離基變量離基變量331332102302300ppk-115-536-1/21/211/250-1/21/2-113/2501/2-1/213/260000001p1pjc1xBX2p2p2p3pbBC3p3pij1d3x3x3d2x3d1d2d2d2x1d3d表中第一列檢驗數(shù)計算方法為：表中第一列

27、檢驗數(shù)計算方法為：即即x x1 1進(jìn)基變量進(jìn)基變量1-323626,215,235,236min3d即即 離基變量離基變量151-51410/31024212,614,212,213min1d即即 為離基變量為離基變量11114*2x因表中全部檢驗數(shù)均大于因表中全部檢驗數(shù)均大于0，所以得到滿意解：，所以得到滿意解：2*1x3d又因表中又因表中 列的檢驗數(shù)等于列的檢驗數(shù)等于0，則該問題存在多重解。，則該問題存在多重解。則則 為進(jìn)基變量為進(jìn)基變量3d-1/31/3-5-5/3121/6-1/6-4/34/31401/2-1/2-33-11201/2-1/2-22130000001p1p1xBX2p2p2p3pbBC3p3pij1d3x3x3d2x3d1d2d2d2x1d1xjc310*2x因表中全部檢驗數(shù)均大于因表中全部檢驗數(shù)均大于0，所以得到另一個滿意解：，所以得到另一個滿意解：310*1x1-1/31/3-2/32/3110/3-1/31/31