管科大二上學期課件-運籌學or-chap4new

第四章目標規(guī)劃問題的提出

目標規(guī)劃的數(shù)學模型

目標規(guī)劃的求解第四章目標規(guī)劃1.問題的提出及其數(shù)學模型1.1目標約束問題例1：某公司生產(chǎn)3種產(chǎn)品I、II和III，采用4種資源A、B、C和D，產(chǎn)品價格、每件產(chǎn)品所需資源量和資源總量如下表。請制定產(chǎn)值最大的生產(chǎn)計劃。產(chǎn)品I產(chǎn)品II產(chǎn)品III資源總量設(shè)備A/h312200設(shè)備B/h224220材料C/kg451360材料D/kg235300價格/(萬元/件)4030501.1目標約束問題現(xiàn)在決策者由于對企業(yè)現(xiàn)狀和市場需求的進一步掌握，感到上述最優(yōu)解不能直接用于決策，進一步提出一些經(jīng)營目標并按優(yōu)先順序列出如下：（1）利潤不少于3400萬元；（2）產(chǎn)品I的產(chǎn)量不能超過產(chǎn)品II產(chǎn)量的1.5倍；（3）產(chǎn)品III的產(chǎn)量不低于30件；（4）設(shè)備能力不足時可以加班，但應(yīng)盡可能少加班；（5）材料不能超過總量。1.1目標約束問題約束不能同時滿足，也就是說不存在上述約束的可行域。這些約束是矛盾的，屬于目標約束問題。1.2多目標優(yōu)化問題例2：航空公司根據(jù)航線一天累積需求隨時間的分布、票價和旅客延誤成本來決定一天的航班頻率和時刻，要求利潤最大、旅客損失最少和旅客計劃延誤成本最小，這就是航班計劃問題。這里的計劃延誤是指由于航班計劃的出發(fā)時刻與旅客最佳出行時間不一致造成的延誤。一般來說，航班頻率越高，計劃延誤將越小，則旅客的出行成本越小，服務(wù)水平越高。但航班頻率高了，航空公司的運行成本將增加，同時每航班的旅客需求將減少，造成航班虧損。航班計劃的優(yōu)化應(yīng)當在這兩者之間尋得平衡。假設(shè)航線每天早晨7點開始有旅客需求，到晚上23點后沒有旅客需求。該航線的日累積需求分布圖由3段直線構(gòu)成，直線的斜率代表需求密度，每段直線的斜率不同。該航線航班的可用座位數(shù)為125，每航班成本為15200元，平均票價為650元，旅客計劃延誤成本為30元/人·h。出于安全，前后兩航班的間隔不小于0.4h，如果旅客計劃延誤超過0.6h，旅客就會流失到其它航空公司，航班計劃應(yīng)力求減少旅客損失。請給出合適的航班計劃。航線累積需求曲線航線累積需求曲線m:每天的航班頻率li:第i個航班的客座率ti:第i個航班的出港時刻q(t):旅客需求密度Q(t):累積需求航線累積需求曲線航班計劃問題的三個目標一般不能同時滿足，該問題叫做多目標優(yōu)化問題。1.2多目標優(yōu)化問題多目標優(yōu)化問題的一般形式能使所有p個目標函數(shù)同時達到最優(yōu)的可行解定義為多目標優(yōu)化問題的絕對最優(yōu)解。如果絕對最優(yōu)解不存在或不容易解得，將尋求所謂有效解，即Pareto最優(yōu)解。該解是滿足約束條件的可行解，它使各目標函數(shù)值相對于其它可行解不差，且至少有一個目標函數(shù)達到了最優(yōu)。1.3多目標優(yōu)化問題的常用處理方法1.加權(quán)和法2.主要目標法3.加權(quán)理想值差法目標規(guī)劃的數(shù)學模型第四章目標規(guī)劃2.目標規(guī)劃的數(shù)學模型1961年A.Charns和W.Kupe在考慮不可行線性規(guī)劃問題的近似解時，首先提出了目標規(guī)劃的方法，它已經(jīng)成為處理多目標規(guī)劃和目標約束問題的最為廣泛的一種方法。2.1多目標優(yōu)化問題的處理只考慮線性多目標規(guī)劃問題時，目標規(guī)劃數(shù)學模型可以寫成：正、負偏差量2.1多目標優(yōu)化問題的處理目標規(guī)劃的數(shù)學模型中對正負偏差可以采用不同的權(quán)值，有2.2目標約束的處理如果把前面的和分別看做目標約束條件的左右兩項，則目標規(guī)劃模型仍然適合于目標約束的情況：目標約束問題主要由于約束條件過于剛性化，通過加入偏差變量使其具有一定的柔性，可以在一定的范圍內(nèi)變動，從而化“不可行”為“可行”。多目標規(guī)劃問題主要是因為各目標函數(shù)的最優(yōu)點不重合，如果對各目標函數(shù)降低一些要求，讓它們可以在理想點附近變動，這樣便可以找到對各目標都可以“接受”的解。兩種處理思路在數(shù)學表達上具有相同的形式2.3帶有優(yōu)先級的目標規(guī)劃無論是目標約束問題還是多目標規(guī)劃問題，轉(zhuǎn)化為目標規(guī)劃后，可能還是無法找到滿足所有指標的最優(yōu)解，而只能優(yōu)先滿足其中某些指標要求。此時可以給目標制訂相應(yīng)的優(yōu)先級，在不能滿足所有目標時，首先應(yīng)滿足優(yōu)先級較高的指標?；?.3帶有優(yōu)先級的目標規(guī)劃更一般的目標規(guī)劃模型：根據(jù)例1給出的5個指標要求及其優(yōu)先順序，給出問題的目標規(guī)劃模型：允許加班可以表達為：但盡可能少加班應(yīng)表達為：2.3帶有優(yōu)先級的目標規(guī)劃取表示設(shè)備A增加工時比設(shè)備B稍微困難。第四章目標規(guī)劃3.目標規(guī)劃的求解3.1目標規(guī)劃的圖解法

在用圖解法解目標規(guī)劃時，首先必須滿足所有絕對約束。在此基礎(chǔ)上，再按照優(yōu)先級從高到低的順序，逐個地考慮各個目標約束。因此，用圖解法求解目標規(guī)劃時，可能會遇到下面兩種情況：（1）最后一級目標的解空間非空。這時得到的解能滿足所有目標的要求。若解不唯一，在實際決策時究竟選擇哪一個解取決于決策者自身的考慮。（2）得到的解不能滿足所有目標。這時要做的是尋找滿意解，使它盡可能滿足高級別的目標，同時又使它對那些不能滿足的較低級別目標的偏離程度盡可能小。3.1目標規(guī)劃的圖解法例：某公司計劃用兩種不同的設(shè)備生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)這兩種產(chǎn)品需要使用兩種材料。產(chǎn)品甲產(chǎn)品乙資源總量材料I3012材料II0416設(shè)備A2212設(shè)備B5315產(chǎn)品單價/萬元2040要求在安排生產(chǎn)計劃時盡可能滿足以下指標要求：（1）努力使總收入不低于80萬元；（2）根據(jù)需求特征，兩種產(chǎn)品的產(chǎn)量盡可能保持1:1的比例；（3）設(shè)備A應(yīng)充分利用，但盡可能不加班；（4）設(shè)備B必要時可以加班，但加班時間盡可能少；（5）材料不能超過總量限制。3.1目標規(guī)劃的圖解法3.1目標規(guī)劃的圖解法圖解法步驟：步驟1和2圖步驟3圖3.1目標規(guī)劃的圖解法練習：某航空公司用某機型飛兩條線，平均運輸能力是6萬客?km/h，正常生產(chǎn)周利用率是70h。根據(jù)市場預測，下周的客運周轉(zhuǎn)量航線I是300萬客?km，航線II是264萬客?km，已知航線I和航線II每客?km的利潤分別是0.4元和0.25元。若航線經(jīng)理只考慮利潤最大，則兩航線應(yīng)分別安排多少飛行h?，F(xiàn)航線經(jīng)理還要考慮其他因素，他制定的管理目標如下：（1）保證有效飛機周利用率的充分利用；（2）必要時可加班飛行，但加班飛行小時盡量不超過10h；（3）努力滿足兩條航線的需求；（4）盡量減少加班飛行時間。問該經(jīng)理該如何決策？3.1目標規(guī)劃的圖解法3.2目標規(guī)劃的單純形法對于線性目標規(guī)劃問題，一般模型如下：滿意解的判斷初始基變量的選擇入基變量的選擇單純形表法中檢驗數(shù)的表達3.2目標規(guī)劃的單純形法滿意解的判斷min

當所有非基變量的檢驗數(shù)大于等于零時，才獲得最優(yōu)解。非基變量的檢驗數(shù)可以寫成：所有非基變量的檢驗數(shù)都可以表達成各目標約束優(yōu)先級別的線性組合，其中i是某非基變量檢驗數(shù)表達式中優(yōu)先級最高的級別。檢驗數(shù)的正負取決于的正負當所有非基變量檢驗數(shù)時（即最高優(yōu)先級別

的系數(shù)為正時），獲得滿意解。3.2目標規(guī)劃的單純形法初始基變量的選擇首先選擇所有的負偏差變量為初始基變量。如果所有約束都是目標約束，那么負偏差變量數(shù)等于方程數(shù)，全部初始基變量都由負偏差變量組成。如果負偏差變量數(shù)小于約束方程數(shù)，則可以選擇松弛變量。如果負偏差變量數(shù)大于約束方程數(shù)，則可以添加人工變量。在沒有基變量的約束方程中加入人工變量，并以人工變量為初始基變量，再將人工變量乘以無限大的正數(shù)M加到目標函數(shù)中。M應(yīng)當被視為最高優(yōu)先級，即3.2目標規(guī)劃的單純形法入基變量的選擇3.2目標規(guī)劃的單純形法入基變量的選擇3.2目標規(guī)劃的單純形法單純形表法中檢驗數(shù)的表達檢驗數(shù)區(qū)由m行組成，每行對應(yīng)一個優(yōu)先級，優(yōu)先級按從高到低的順序在該區(qū)中從上到下排列，非基變量檢驗數(shù)表達式的系數(shù)則填在該變量所在列的各優(yōu)先級所在行中。例：3.2目標規(guī)劃的單純形法3.2目標規(guī)劃的單純形法3.2目標規(guī)