北京大學(xué)線性代數(shù)單純形法課件

第七章線性規(guī)劃線性規(guī)劃研究的主要問(wèn)題：

一類是已有一定數(shù)量的資源（人力、物質(zhì)、時(shí)間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。

——實(shí)際上，上述兩類問(wèn)題是一個(gè)問(wèn)題的兩個(gè)不同的方面，都是求問(wèn)題的最優(yōu)解（maxf或minf）。

另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費(fèi)的資源量為最少。（LinearProgramming，簡(jiǎn)稱LP）

線性規(guī)劃例1.1某廠生產(chǎn)兩種產(chǎn)品，下表給出單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)問(wèn)：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？

§7.1線性規(guī)劃的數(shù)學(xué)模型一、問(wèn)題的提出解：1.決策變量：設(shè)產(chǎn)品I，II的產(chǎn)量分別為

x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：maxz=2x1+3x23.約束條件：

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0模型特點(diǎn)1都用一組決策變量X=(x1,x2,…,xn)T表示某一方案，且決策變量取值非負(fù)；——滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃2都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成

決策變量的線性函數(shù)；3都有一組約束條件，這些約束條件可以用決策變量

的線性等式或線性不等式來(lái)表示。二.線性規(guī)劃的數(shù)學(xué)模型一般表示方式?jīng)Q策變量目標(biāo)函數(shù)約束條件

線性規(guī)劃的標(biāo)準(zhǔn)形有如下四個(gè)特點(diǎn)：目標(biāo)最小化、約束為等式、變量均非負(fù)、右端約束常數(shù)非負(fù)。

線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式2134線性規(guī)劃模型的變換

1．極小化目標(biāo)函數(shù)的問(wèn)題

設(shè)目標(biāo)函數(shù)為令則可轉(zhuǎn)化為標(biāo)準(zhǔn)形2．

右端項(xiàng)有負(fù)值的問(wèn)題

在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)，當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，則把該等式約束兩端同時(shí)乘以－1，得到：

在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量有非負(fù)約束，當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，令4．

變量無(wú)符號(hào)限制的問(wèn)題

例2.線性規(guī)劃模型化為標(biāo)準(zhǔn)型。三線性規(guī)劃模型解的基本概念定義7.1定義7.2性質(zhì)7.1凸集非凸集性質(zhì)7.2若線性規(guī)劃模型的可行域非空，則可行域?yàn)橥辜！?.2線性規(guī)劃問(wèn)題的圖解法0123451243極限位置例1.求LP問(wèn)題

0123451243AB極限位置例3.求LP問(wèn)題

練習(xí).求LP問(wèn)題

ＬＰ的標(biāo)準(zhǔn)型其約束方程為p2p1pm約束方程每給非基變量一組值，就能得到基變量的一組相應(yīng)的值，從而得到線性規(guī)劃問(wèn)題的一個(gè)解。特別地：注:若約束等式中有n個(gè)變量，m個(gè)約束，則基本解的個(gè)數(shù)≤線性規(guī)劃解的性質(zhì)定理7.1

線性規(guī)劃問(wèn)題的一個(gè)解x為基本解的充分必要條件是：x的非零分量所對(duì)應(yīng)的系數(shù)矩陣A的列向量線性無(wú)關(guān)。定理7.2若線性規(guī)劃問(wèn)題存在可行解，則一定存在基本可行解定理7.3若線性規(guī)劃問(wèn)題存在最優(yōu)解，則一定存在基本可行解且此解為最優(yōu)解.定理.

可行域的頂點(diǎn)基本可行解二.單純形法基本思想.1、構(gòu)造初始可行基；根據(jù)可構(gòu)成初始可行基2、求出一個(gè)基本可行解3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；

是否是最優(yōu)解？怎么辦？換基從一個(gè)基本可行解出發(fā)，經(jīng)換基迭代，找出另一個(gè)基本可行解同時(shí)不斷改進(jìn)目標(biāo)函數(shù)直到判斷出是否有最優(yōu)解.4、基變換，尋找新的基本可行解.進(jìn)基：出基：誰(shuí)呢？因此，基由變?yōu)?/p>

轉(zhuǎn)第2步：求出一個(gè)基本可行解f(1)

是否是最優(yōu)解？上例可通過(guò)以下形式求解非基變量基變量00100010

2－3000

121004001004001

81612－23000

0基變量常數(shù)單純形方法是表格化的換基迭代法.

2000

1010400100100

2163－2000

-9基變量常數(shù)

-3-1-3000

211100123010221001

256

313000

0基變量常數(shù)

基變量常數(shù)

基變量常數(shù)算法思路

求一個(gè)初始基本可行解

是

判斷基本可行解是否最優(yōu)結(jié)束

不是

求使目標(biāo)得到改善的基本可行解

是否唯一？如何判斷？如何改善？如何判斷沒(méi)有有限最優(yōu)解？

基變量常數(shù)