線性規(guī)劃單純形方法

線性規(guī)劃單純形方法第1頁，課件共23頁，創(chuàng)作于2023年2月線性規(guī)劃問題基本定理定理一若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理二線性規(guī)劃問題的基本可行解X對(duì)應(yīng)線性規(guī)劃問題可行域（凸集）的頂點(diǎn)。定理三若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解(即最優(yōu)解一定在某頂點(diǎn)上)。從上述三個(gè)定理可以看出，要求線性規(guī)劃問題的最優(yōu)解，只要比較可行域（凸集）各個(gè)頂點(diǎn)(或者說基可行解)對(duì)應(yīng)的目標(biāo)函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。第2頁，課件共23頁，創(chuàng)作于2023年2月§3.2單純形方法思路：從一個(gè)基可行解（極點(diǎn)）出發(fā)（如何去找一個(gè)基可行解？），判斷其是否為最優(yōu)解，（如何判斷？），

若不是，則轉(zhuǎn)換到相鄰的基可行解（另一個(gè)極點(diǎn)），并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解為止。第3頁，課件共23頁，創(chuàng)作于2023年2月

單純形法：先找到一個(gè)初始基可行解，如果不是最優(yōu)解，設(shè)法轉(zhuǎn)換到另一個(gè)基可行解（換基迭代，即從極點(diǎn)到極點(diǎn)），并使目標(biāo)函數(shù)不斷增大，一直到找到最優(yōu)解為止。

B1X(1)B1X(1)B2X(2)B3X(3)BnX(n)XN=0X=(XB,XN)第4頁，課件共23頁，創(chuàng)作于2023年2月2.3.1

單純形表單純形法的具體步驟：（一）確定初始基可行解在L.P問題的標(biāo)準(zhǔn)型：中，不妨設(shè)B是一個(gè)可行基，于是A=（B,N)

不失一般性假定B=（P1,…,Pm),基變量XB=（x1,…,xm)T

N

=(Pm+1,…,Pn),非基變量XN=（xm+1,…,xn)T.則

X=〔XB,XN〕T相應(yīng)有C=(CB,CN)第5頁，課件共23頁，創(chuàng)作于2023年2月于是，原問題化為：第6頁，課件共23頁，創(chuàng)作于2023年2月初始基可行解oI第7頁，課件共23頁，創(chuàng)作于2023年2月檢驗(yàn)數(shù)第8頁，課件共23頁，創(chuàng)作于2023年2月為什么？第9頁，課件共23頁，創(chuàng)作于2023年2月。

對(duì)上面分析過程進(jìn)行總結(jié)：（1）在標(biāo)準(zhǔn)型中，找一個(gè)單位基矩陣并求出該基對(duì)應(yīng)的基可行解。當(dāng)L.P問題的約束條件全部為“≤”時(shí)，在變換為標(biāo)準(zhǔn)型的過程引進(jìn)松馳變量，就自然得到了一個(gè)單位矩陣----初始可行基和初始基可行解。（2）檢驗(yàn)該基可行解是否最優(yōu)？通過非基變量的檢驗(yàn)數(shù)。（3）若不是最優(yōu)，則另找一個(gè)基產(chǎn)生一個(gè)基可行解-----換基迭代。直到最優(yōu)。對(duì)此原理，我們可以通過單純形表來實(shí)現(xiàn)。第10頁，課件共23頁，創(chuàng)作于2023年2月單純形表第11頁，課件共23頁，創(chuàng)作于2023年2月說明1、表中基變量所在位置并不一定正好在前m個(gè)位置上，但總可以通過調(diào)換重新排成上表形式。2、表中最下一行稱為檢驗(yàn)數(shù)行，對(duì)應(yīng)于非基變量的檢驗(yàn)數(shù)為：（用于檢驗(yàn)是否還須繼續(xù)迭代）3、不難看出，基變量的檢驗(yàn)數(shù)均為0第12頁，課件共23頁，創(chuàng)作于2023年2月2.3.2單純形法的步驟引例：解L.P問題第13頁，課件共23頁，創(chuàng)作于2023年2月第一步：把模型化為標(biāo)準(zhǔn)形式后找出初始可行基，建立初始單純形表（見下表）。本例中取初始基B1=(P3,P4)=I,則

cj

4300CBXB

b

x1x2x3x400

x3

x42426

23103201

Z0

4300第14頁，課件共23頁，創(chuàng)作于2023年2月

cj

4300CBXB

b

x1x2x3x400

x3

x42426

23103201

Z0

4300由表得基可行解:第15頁，課件共23頁，創(chuàng)作于2023年2月（二）最優(yōu)檢驗(yàn)第16頁，課件共23頁，創(chuàng)作于2023年2月第三步：換基迭代第17頁，課件共23頁，創(chuàng)作于2023年2月

第18頁，課件共23頁，創(chuàng)作于2023年2月

cj

4300CBXBb

x1x2x3x400x3x42426

2310

[3]2011226/3

Z

0

430004x3x120/326/3

0[5/3]1-2/312/301/3413

Z104/3

01/30-4/334x2x1

46

013/5-2/510-2/53/5

Z36

00-1/5-6/5第19頁，課件共23頁，創(chuàng)作于2023年2月

1.上第一表中,x1為換入變量；又由于比值=min(24/2，26/3）=26/3,確定x4為換出變量.x1所在列和x4所在行的交叉處為主元。進(jìn)行迭代后，X(2)=(26/3,0,20/3,0)T，目標(biāo)函數(shù)值為Z（2）=104/3，但不是最優(yōu)值。

2.第二次迭代x2為換入變量，x3為換出變量。進(jìn)行迭代后，X(1)=(6，4，0，0)T,因最后一行的所有檢驗(yàn)數(shù)都已是正數(shù)或零，因此目標(biāo)函數(shù)值為Z*=Z（3）=36是最優(yōu)值。第20頁，課件共23頁，創(chuàng)作于2023年2月第21頁，課件共23頁，創(chuàng)作于2023年2月

cj

31000CBXBb

x1x2x3x4x5000x3X4x54218

11100-11010

[6]20014-3

Z

0

31000003x3X4x1153

02/310-1/604/3011/611/3001/6

Z9

0000-1/2

第22頁，課件共23頁，創(chuàng)作于2023年2月

該問題的最優(yōu)