chapter線性規(guī)劃回顧

1、第四章 環(huán)境規(guī)劃與管理數(shù)學基礎(chǔ)的補充內(nèi)容 11、線性規(guī)劃回顧2、目標規(guī)劃模型擴展 一、線性規(guī)劃的一般模型1、線性規(guī)劃問題的三個要素 決策變量：決策問題待定的量值稱為決策變量。決策變量的取值要求非負。約束條件 任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。約束條件是決策方案可行的保障。 LP的約束條件，都是決策變量的線性函數(shù)。目標函數(shù) 衡量決策方案優(yōu)劣的準則，如時間最省、利潤最大、成本最低。目標函數(shù)是決策變量的線性函數(shù)。 有的目標要實現(xiàn)極大，有的則要求極小。 矩陣式線性規(guī)劃的一般形式教材page742、單純形法的計算步驟 將線性規(guī)劃問題化成標準型。找出

2、或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。計算各非基變量xj的檢驗數(shù)j=CBPj- Cj，若所有j0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步。在大于0的檢驗數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk0，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步。根據(jù)maxjj0=k原則，確定xk為換入變量(進基變量)，再按規(guī)則計算：=minbi/aik| aik0=bl/ aik 確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。以aik為主元素進行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第 步。 3、線性規(guī)劃模型在環(huán)境規(guī)劃與管理中的

3、應(yīng)用 污染物總量控制模型，用數(shù)學語言構(gòu)造的數(shù)學模型，其表示式如下：由此可寫出相應(yīng)的污染物總量控制模型 如果某規(guī)劃區(qū)有m個污染源，每個污染源存在n種可供選擇的污染控制方法，控制p種污染物。根據(jù)環(huán)境規(guī)劃的基本原理，課構(gòu)造出比例削減模型的通用線性規(guī)劃模型m、n、q分別表示污染源、排放控制方法、大氣污染物的總數(shù)量；i、j、p分別表示第i個污染源，第j種控制方法、第p種污染物；cij表示i污染源采用j種控制方法生產(chǎn)單位產(chǎn)品所需支付的污染控制費用；xij控制變量，表示污染源i采用j種控制方法可生產(chǎn)產(chǎn)品的數(shù)量；aij生產(chǎn)邏輯變量，若污染源i采用j種控制污染排放方法可行，則aij=1，否則則為0；Si表示對第

4、i種污染源實施各種污染控制方法后產(chǎn)品產(chǎn)量的約束；bijp為污染源排放系數(shù)；表示i污染源采用j種污染控制方法審查單位產(chǎn)品時的排放的污染物p的數(shù)量目標規(guī)劃與線性規(guī)劃相比有以下優(yōu)點： 1、線性規(guī)劃只能處理一個目標，而現(xiàn)實問題往往要處理多個目標。目標規(guī)劃就能統(tǒng)籌兼顧地處理多個目標的關(guān)系，求得更切合實際要求的解。 2、線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)解，而在實際問題中，可能存在相互矛盾的約束條件。目標規(guī)劃可以在相互矛盾的約束條件下找到滿意解。 3、目標規(guī)劃的最優(yōu)解指的是盡可能地達到或接近一個或若干個已給定的指標值。 4、線性規(guī)劃的約束條件是不分主次地同等對待，而目標規(guī)劃可根據(jù)實際的需要給予輕重緩急

5、的考慮。 因此，可以認為目標規(guī)劃更能確切地描述和解決經(jīng)營管理中的許多實際問題。2 目標規(guī)劃模型目標函數(shù) 目標規(guī)劃的目標函數(shù)（準則函數(shù)）是按照各目標約束的正、負偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當每一目標確定后，盡可能縮小與目標值的偏離。因此，目標規(guī)劃的目標函數(shù)只能是基本形式有3種： 要求恰好達到目標值，就是正、負偏差變量都要盡可能小,即 2 目標規(guī)劃模型 要求不超過目標值，即允許達不到目標值，就是正偏差變量要盡可能小，即 要求超過目標值，也就是超過量不限，但負偏差變量要盡可能小，即 在實際問題中，可以根據(jù)決策者的要求，引入正、負偏差變量和目標約束，并給不同目標賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)

6、造目標函數(shù)，建立模型。 假定有L個目標，K個優(yōu)先級(KL)，n個變量。在同一優(yōu)先級 中不同目標的正、負偏差變量的權(quán)系數(shù)分別為 、 ，則多目標規(guī)劃問題可以表示為目標規(guī)劃模型的一般形式 在以上各式中： 、 分別為賦予 優(yōu)先因子的第 個目標的正、負偏差變量的權(quán)系數(shù)； 為第 個目標的預(yù)期值； 為決策變量； 、 分別為第 個目標的正、負偏差變量。求解目標規(guī)劃問題的單純形法（一）、一般形式： 1、建立初始單純形表。 一般假定初始解在原點，即以約束條件中的所有負偏差變量或松弛變量為初始基變量，按目標優(yōu)先等級從左至右分別計算出各列的檢驗數(shù)，填入表的下半部 。 2、檢驗是否為滿意解。判別準則如下： .首先檢查k

7、 (k=1.2K)是否全部為零？如果全部為零，則表示目標均已全部達到，獲得滿意解，停止計算轉(zhuǎn)到第6步；否則轉(zhuǎn)入。 （二）、單純形法的計算步驟 .如果某一個k 0。說明第k個優(yōu)先等級的目標尚未達到,必須檢查Pk這一的檢驗數(shù)kj(j=1.2n+2m).若Pk這一行某些負檢驗數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進，轉(zhuǎn)到第3步；若Pk這一行全部負檢驗數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗數(shù)，說明目標雖沒達到，但已不能改進，故得滿意解，轉(zhuǎn)到第6步。 3、確定進基變量。 在Pk行，從那些上面沒有正檢驗數(shù)的負檢驗數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數(shù)，取其絕對值最大的負檢驗數(shù)的所在列的xs為進基變量。假如仍無法確定，則選最左邊的變量（變量下標小者）為進基變量。 4、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr 。 5、旋轉(zhuǎn)變換（變量迭