C類運(yùn)籌學(xué)第2章線性規(guī)劃1課件

第一章線性規(guī)劃與單純形法年G.B.Dantzig提出單純形法上海交通大學(xué)安泰管理學(xué)院2第一節(jié)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

問(wèn)題的提出:在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常提出一類問(wèn)題，即如何合理的利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。2023/7/23上海交通大學(xué)安泰管理學(xué)院3

例1某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表1-1所式。該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？2023/7/23上海交通大學(xué)安泰管理學(xué)院42023/7/23上海交通大學(xué)安泰管理學(xué)院52工作人員安排問(wèn)題聯(lián)邦航空公司2023/7/23上海交通大學(xué)安泰管理學(xué)院6

以上例子可以看出，他們都是一類優(yōu)化問(wèn)題。它們的共同特征：

(1)每一個(gè)問(wèn)題都用一組決策變量表示某一方案；這組決策變量的值就代表一個(gè)具體方案。一般這些變量取值是非負(fù)的。2023/7/23上海交通大學(xué)安泰管理學(xué)院7(2)存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示。

(3)都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策的線性函數(shù)（稱為目標(biāo)函數(shù)）來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。2023/7/23上海交通大學(xué)安泰管理學(xué)院8

滿足以上三個(gè)條件的數(shù)學(xué)模型成為線性規(guī)劃的數(shù)學(xué)模型。其一般形式為：

2023/7/23上海交通大學(xué)安泰管理學(xué)院92023/7/23上海交通大學(xué)安泰管理學(xué)院10

在線性規(guī)劃的數(shù)學(xué)模型中，方程（1.1）稱為目標(biāo)函數(shù)；（1.2）（1.3）成為約束條件；（1.3）也稱為變量的非負(fù)約束條件。2023/7/23上海交通大學(xué)安泰管理學(xué)院11

線性規(guī)劃的圖解法2023/7/23上海交通大學(xué)安泰管理學(xué)院122023/7/23上海交通大學(xué)安泰管理學(xué)院132023/7/23上海交通大學(xué)安泰管理學(xué)院14線性規(guī)劃的解唯一解無(wú)窮多解無(wú)可行解無(wú)界解MaxZ=x1+x2-2x1+x2<=4X1-x2<=2X1>=0,x2>=02023/7/23上海交通大學(xué)安泰管理學(xué)院15

線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：線性規(guī)劃問(wèn)題的可性解的集合是凸集線性規(guī)劃問(wèn)題的基礎(chǔ)可行解一般都對(duì)應(yīng)于凸集的極點(diǎn)凸集的極點(diǎn)的個(gè)數(shù)是有限的最優(yōu)解只可能在凸集的極點(diǎn)上，而不可能發(fā)生在凸集的內(nèi)部2023/7/23上海交通大學(xué)安泰管理學(xué)院16maxZ=

1.2.1線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式2023/7/23上海交通大學(xué)安泰管理學(xué)院17標(biāo)準(zhǔn)型向量形式矩陣形式2023/7/23上海交通大學(xué)安泰管理學(xué)院18

變換的方法：目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令f(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)第i個(gè)約束的bi

為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向第i個(gè)約束為型，在不等式左邊增加一個(gè)非負(fù)的變量xn+i

，稱為松弛變量；同時(shí)令cn+i

=0第i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i

，稱為剩余變量；同時(shí)令cn+i

=0若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0若xj不限，令

xj=xj-

xj，xj

0，xj0，代入非標(biāo)準(zhǔn)型2023/7/23上海交通大學(xué)安泰管理學(xué)院19

變換舉例：2023/7/23上海交通大學(xué)安泰管理學(xué)院20線性規(guī)劃標(biāo)準(zhǔn)型解的若干基本概念：標(biāo)準(zhǔn)型有n+m個(gè)變量，m個(gè)約束行“基”的概念在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有n+m列，即

A=(P1,P2,…,Pn+m)A中線性獨(dú)立的m列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基，即

B=(P1,P2

,…,Pm

)，

|

B|0

P1,P2,…,Pm

稱為基向量與基向量對(duì)應(yīng)的變量稱為基變量，記為

XB=(x1,x2

,…,xm

)T，其余的變量稱為非基變量，記為XN=(xm+1,xm+2,…,xm+n

)T

，有

X

=XB+XN最多有個(gè)基2023/7/23上海交通大學(xué)安泰管理學(xué)院21

關(guān)于標(biāo)準(zhǔn)型解的若干基本概念：可行解滿足約束條件和非負(fù)條件的解X稱為可行解，基礎(chǔ)解令非基變量XN=0，求得基變量

XB的值稱為基礎(chǔ)解即XB=B-1

bXB

是基礎(chǔ)解的必要條件為XB的非零分量個(gè)數(shù)m基礎(chǔ)可行解基礎(chǔ)解

XB的非零分量都0時(shí)，稱為基礎(chǔ)可行解，否則為基礎(chǔ)非可行解基礎(chǔ)可行解的非零分量個(gè)數(shù)<

m

時(shí)，稱為退化解2023/7/23上海交通大學(xué)安泰管理學(xué)院22

線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系約束方程的解空間基礎(chǔ)解可行解非可行解基礎(chǔ)可行解退化解2023/7/23上海交通大學(xué)安泰管理學(xué)院23線性規(guī)劃幾何意義凸集凸組合頂點(diǎn)2023/7/23上海交通大學(xué)安泰管理學(xué)院24線性規(guī)劃基本定理定理1若線性規(guī)劃問(wèn)題存在可行域,則其可行域是凸集.引理線性規(guī)劃問(wèn)題的可行解X為基可行解的充要條件是X的正分量對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的.定理2線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)定理3若可行域有界,線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到.2023/7/23上海交通大學(xué)安泰管理學(xué)院25單純型法思路舉例2023/7/23上海交通大學(xué)安泰管理學(xué)院26單純型法初始基可行解的確定最優(yōu)性檢驗(yàn):檢驗(yàn)數(shù)解的判別基變換2023/7/23上海交通大學(xué)安泰管理學(xué)院27

關(guān)于檢驗(yàn)數(shù)的數(shù)學(xué)解釋設(shè)B是初始可行基，則目標(biāo)函數(shù)可寫為兩部分(1)約束條件也寫為兩部分，經(jīng)整理得XB的表達(dá)式(2)，注意XB中含有非基變量作參數(shù)把XB代入目標(biāo)函數(shù)，整理得到(3)式第j

個(gè)非基變量的機(jī)會(huì)成本如(4)式若有cj-zj>0,則未達(dá)到最優(yōu)2023/7/23上海交通大學(xué)安泰管理學(xué)院28

標(biāo)準(zhǔn)型的單純型算法找初始基礎(chǔ)可行基對(duì)于(max,)，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣檢驗(yàn)當(dāng)前基礎(chǔ)可行解是否為最優(yōu)解所有檢驗(yàn)數(shù)cjzj0，則為最優(yōu)解，否則確定改善方向從(cjzj)>0中找最大者，選中者稱為入變量，xj*

第j*列稱為主列確定入變量的最大值和出變量最小比例原則2023/7/23上海交通大學(xué)安泰管理學(xué)院29

標(biāo)準(zhǔn)型的單純型算法確定入變量的最大值和出變量設(shè)第i*行使最小，則第i*行對(duì)應(yīng)的基變量稱為出變量，第i*行稱為主行迭代過(guò)程主行i*行與主列j*相交的元素ai*j*稱為主元，迭代以主元為中心進(jìn)行迭代的實(shí)質(zhì)是線性變換，即要將主元ai*j*變?yōu)?，主列上其它元素變?yōu)?，變換步驟如下：(1)變換主行2023/7/23上海交通大學(xué)安泰管理學(xué)院30

單純型表及其格式2023/7/23上海交通大學(xué)安泰管理學(xué)院31

例試列出下面線性規(guī)劃問(wèn)題的初始單純型表2023/7/23上海交通大學(xué)安泰管理學(xué)院32

單純型表中元素的幾點(diǎn)說(shuō)明任何時(shí)候，基變量對(duì)應(yīng)的列都構(gòu)成一個(gè)單位矩陣當(dāng)前表中的b

列表示當(dāng)前基變量的解值，通過(guò)變換B1b得到(資源已變成產(chǎn)品)當(dāng)前非基變量對(duì)應(yīng)的向量可通過(guò)變換B1AN

得到，表示第j

個(gè)變量對(duì)第i

行對(duì)應(yīng)的基變量的消耗率非基變量的機(jī)會(huì)成本由給出注意基變量所對(duì)應(yīng)的行2023/7/23上海交通大學(xué)安泰管理學(xué)院33人工變量的引入

當(dāng)約束條件為“”型，引入剩余變量和人工變量由于所添加的剩余變量的技術(shù)系數(shù)為1，不能構(gòu)成初始基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為“=”型），以便取得初始基變量，故稱為人工變量由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定兩種方法大M法二階段法2023/7/23上海交通大學(xué)安泰管理學(xué)院34解法思路橋梁等價(jià)2023/7/23上海交通大學(xué)安泰管理學(xué)院35

大M法的求解過(guò)程

2023/7/23上海交通大學(xué)安泰管理學(xué)院36

表1.3.1例1.3.1的單純型表迭代過(guò)程答：最優(yōu)解為x1=2,x2=2,x3=0,OBJ=362023/7/23上海交通大學(xué)安泰管理學(xué)院37

大M法的一些說(shuō)明大M法實(shí)質(zhì)上與原單純型法一樣，M可看成一個(gè)很大的常數(shù)人工變量被迭代出去后就不會(huì)再成為基變量當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說(shuō)明原線性規(guī)劃問(wèn)題無(wú)可行解大M法手算很不方便因此提出了二階段法計(jì)算機(jī)中常用大M法二階段法手算可能容易2023/7/23上海交通大學(xué)安泰管理學(xué)院381.3.3二階段法的求解過(guò)程第一階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個(gè)沒(méi)有人工變量的基礎(chǔ)可行解第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解若第一階段結(jié)束時(shí)，人工變量仍在基變量中，則原問(wèn)題無(wú)（可行）解為了簡(jiǎn)化計(jì)算，在第一階段重新定義價(jià)值系數(shù)如下：2023/7/23上海交通大學(xué)安泰管理學(xué)院39

表1.3.2用二階段法求解例1.3.1的第一階段2023/7/23上海交通大學(xué)安泰管理學(xué)院40

表1.3.2用二階段法求解例1.3.1的第二階段最優(yōu)解對(duì)應(yīng)的B–1在哪？2023/7/23上海交通大學(xué)安泰管理學(xué)院411.5單純型法的一些具體問(wèn)題1.5.1關(guān)于無(wú)界解問(wèn)題可行區(qū)域不閉合(缺約束條件)單純型表中入變量xj*

對(duì)應(yīng)的列中所有例1.5.12023/7/23上海交通大學(xué)安泰管理學(xué)院42

表1.5.1

例1.5.1的單純型表及其迭代過(guò)程2023/7/23上海交通大學(xué)安泰管理學(xué)院431.5.2關(guān)于退化問(wèn)題退化問(wèn)題的原因很復(fù)雜，當(dāng)原問(wèn)題存在平衡約束時(shí)當(dāng)單純型表中同時(shí)有多個(gè)基變量可選作出變量時(shí)退化的嚴(yán)重性在于可能導(dǎo)致死循環(huán)，克服死循環(huán)的方法有“字典序”法例1.5.22023/7/23上海交通大學(xué)安泰管理學(xué)院441.5.3關(guān)于多重解問(wèn)題多個(gè)基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個(gè)超平面上，且該平面與目標(biāo)函數(shù)等值面平行最優(yōu)單純型表中有非基變量的檢驗(yàn)數(shù)為0最優(yōu)解的線性組合仍是最優(yōu)解，即

X