運(yùn)籌學(xué)01-線性規(guī)劃基本性質(zhì)及建模

1、運(yùn)籌學(xué)Tel：1學(xué)習(xí)資料秦裕瑗 秦明復(fù). 運(yùn)籌學(xué)簡明教程. 高等教育出版社,2006.12韓大衛(wèi).管理運(yùn)籌學(xué).大連理工大學(xué)出版社,2006.62第一章 線性規(guī)劃基本性質(zhì)及建模 線性規(guī)劃主要用于研究解決有限資源的最佳分配問題，即如何對(duì)有限的資源做出最佳方式的調(diào)配和最有利的使用，以便最充分的發(fā)揮資源的效能去獲取最佳經(jīng)濟(jì)效益。為敘述簡便，以后我們把“線性規(guī)劃”用LP代替 。3 第一節(jié) 線性規(guī)劃的一般模型1.1產(chǎn)品結(jié)構(gòu)優(yōu)化問題1、范例1 某廠擬生產(chǎn)甲乙兩種適銷產(chǎn)品，每件利潤為3、5百元。甲乙產(chǎn)品的部件各自在A、B兩個(gè)車間分別生產(chǎn)，每件甲乙產(chǎn)品的部件分別需要A、B車間的生產(chǎn)能力1、2工時(shí)；兩種產(chǎn)品的部件

2、最后都要在C車間裝配，裝配每件甲乙產(chǎn)品分別需要3、4工時(shí),A、B、C三個(gè)車間每天可用于生產(chǎn)這兩這種產(chǎn)品的工時(shí)分別為8、12、36，應(yīng)如何安排生產(chǎn)才能獲利最多？ 4列出數(shù)據(jù)表5解：這是一個(gè)典型的產(chǎn)品結(jié)構(gòu)優(yōu)化問題，現(xiàn)在建立這個(gè)問題的數(shù)學(xué)模型。設(shè) 分別為甲、乙產(chǎn)品的日產(chǎn)量，z為這兩種產(chǎn)品每天總的利潤?？傻脭?shù)學(xué)模型簡記為: 其中max是英文maximize(最大化)的縮寫；s.t.是subject to(受約束于)的縮寫。 61.2 線性規(guī)劃的一般模型（1）可用一些變量表示這類問題的待定方案，這些變量的一組定值就代表一個(gè)具體方案。因此可將這些變量稱為決策變量，并要求它們?yōu)榉秦?fù)。（2）存在一定的約束條件

3、，這些約束條件都能用關(guān)于決策變量的線性不等式或等式來表示。（3）有一個(gè)期望達(dá)到的目標(biāo)，這些目標(biāo)能以某種確定的數(shù)量指標(biāo)刻畫出來，而這種數(shù)量指標(biāo)可表示為關(guān)于決策變量的線性函數(shù)，按所考慮問題的不同，要求該函數(shù)值最大化或最小化。這類問題就是線性規(guī)劃問題。一般LP模型可表示如下：其中opt是英文optimize(最優(yōu)化)的縮寫。按問題要求不同，可表示為max或min。7(1-1)式稱為最優(yōu)化目標(biāo)函數(shù)，其中 稱為目標(biāo)函數(shù)，opt稱為其優(yōu)化，也可稱為目標(biāo)要求；(1-2)式稱為函數(shù)約束；(1-3)式中的 稱為非負(fù)性約束； 稱為非正性約束；(1-2)、(1-3)式統(tǒng)稱為約束條件，簡稱約束。 稱為決策變量。 稱為

4、LP模型的參數(shù)。8第二節(jié) 關(guān)于解的幾種可能結(jié)果線性規(guī)劃問題的解可能出現(xiàn)以下幾種情況唯一解有且僅有一個(gè)既在可行域內(nèi)，又使目標(biāo)值達(dá)到最優(yōu)的解。無窮解有無窮多個(gè)既在可行域內(nèi)、又使目標(biāo)值達(dá)到最優(yōu)的解。無可行解約束條件不能同時(shí)滿足，將出現(xiàn)無可行域的情況。有可行解但無最優(yōu)解(無界解)是指最大化問題中目標(biāo)函數(shù)值可以無限增大，或最小化問題中目標(biāo)函數(shù)值可以無限減小9第三節(jié) 非標(biāo)準(zhǔn)形LP問題的標(biāo)準(zhǔn)化1、目標(biāo)函數(shù)。如LP問題的目標(biāo)函數(shù)是： 可以將原目標(biāo)函數(shù)化為2、函數(shù)約束。 (1) 的情形。 (2) 約束為 形式的情形。 (3) 約束為 形式的情形。 3、決策變量 1） 小于零時(shí) 2） 自由變量時(shí)10非標(biāo)準(zhǔn)形LP問

5、題的標(biāo)準(zhǔn)化 例題 將如下LP問題化成標(biāo)準(zhǔn)形：11Answer:12第四節(jié) 線性規(guī)劃的解及其性質(zhì)4.1 線性規(guī)劃的解的概念1 可行解。 滿足LP問題所有的約束條件的向量X稱為可行解，所有可行解構(gòu)成的集合稱為可行域，記為R。2 最優(yōu)解。 滿足目標(biāo)要求的可行解稱為最優(yōu)解，記為 ；它所對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值，記為 。有時(shí)把 統(tǒng)稱為最優(yōu)解，簡稱為解。13第四節(jié) 線性規(guī)劃的解及其性質(zhì)3 基本解。其概念只適用于標(biāo)準(zhǔn)形LP問題。就范例的標(biāo)準(zhǔn)形進(jìn)行研討：14其增廣陣為：其系數(shù)陣A中有一個(gè)三階子陣為單位陣，其行列式不為0，故r(A)=r( )=r=3=m,方程組相容。又因r=35=n,故方程組有無窮多解。取A

6、中單位陣對(duì)應(yīng)的變量x3,x4,x5為基本變量，則x1,x2為自由變量，令x1= c1, x2=c2 ,容易得到一個(gè)通解：15當(dāng)取C1=C2=0 時(shí)，可得方程組一個(gè)特解： X0=（0，0，8，12，36）T 稱之為方程組的一個(gè)基本解。其中x3,x4,x5為基本變量，則x1,x2為不再自由，改稱非基本變量。 由此可見，基本解是由r 個(gè)基本變量與n-r個(gè)非基本變量構(gòu)成的。由于總是規(guī)定標(biāo)準(zhǔn)形LP問題的系數(shù)陣A滿秩，即r(A)=m n,因此可以說，基本解是由m個(gè)基本變量與n-m 個(gè)非基本變量構(gòu)成的，其中基本變量對(duì)應(yīng)的系數(shù)列向量構(gòu)成一個(gè)m階非奇異方陣?；咀兞恳话悴粸?，而非基本變量都須為0。16 現(xiàn)在考慮一般LP問題的標(biāo)準(zhǔn)形。設(shè)B是由方程組(1-5)的m個(gè)線性無關(guān)的系數(shù)列向量構(gòu)成的m階方陣( )，則稱B為LP問題的一個(gè)基矩陣(簡稱基)。為敘述簡便，不妨設(shè)1718這個(gè)解的非零分量的數(shù)目不大于階數(shù)m，稱之為約束方程組(1-5)的一個(gè)關(guān)于基B的基本解，簡稱基本解。也稱之為標(biāo)準(zhǔn)形LP問題的一個(gè)基本解。若基本解中有一個(gè)或更多個(gè)基變量，則 稱之為退化基本解。1