chapter線性規(guī)劃回顧

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

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

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

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

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

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

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