哈爾濱工業(yè)大學(xué)運(yùn)籌學(xué)教案教案

1、檢驗(yàn)數(shù)的概念和計(jì)算檢驗(yàn)數(shù)的概念和計(jì)算最優(yōu)性判別最優(yōu)性判別基變換（換入變量和換出變量的確定）基變換（換入變量和換出變量的確定）旋轉(zhuǎn)變換旋轉(zhuǎn)變換2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 39231 基本思想 對(duì)于一個(gè)標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型LP問(wèn)題，從一個(gè)初始基可行解初始基可行解出發(fā)，判斷判斷其是否為最優(yōu)解，若是則結(jié)束；否則求一個(gè)與其“相鄰相鄰”的、的、改進(jìn)的基可行解改進(jìn)的基可行解。再判斷這個(gè)解是否最優(yōu)，若是則結(jié)束，否則再求一個(gè)“相鄰”的、改進(jìn)的基可行解如此迭代下去，直到找到基最優(yōu)解基最優(yōu)解或判定問(wèn)題無(wú)解為止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=1

2、2x1+2x2=82x1+3x2=03Q2如例如例1，O Q1 Q2或或 O Q4 Q3 Q22022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 393單純形法要解決的三方面的問(wèn)題：?jiǎn)渭冃畏ㄒ鉀Q的三方面的問(wèn)題：（1）如何確定）如何確定初始的基可行解初始的基可行解？（2）如何進(jìn)行解的）如何進(jìn)行解的最優(yōu)性判別最優(yōu)性判別？（3）如何尋找）如何尋找改進(jìn)的基可行解改進(jìn)的基可行解？2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 39432 確定初始基可行解確定初始基可行解 定義：線性規(guī)劃規(guī)范型，當(dāng)線性規(guī)劃標(biāo)準(zhǔn)型： Max z = Max z

3、 = CXCX1.0njjjP xbs tX2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 395其中系數(shù)矩陣A=P1，P2，Pn中含有一單位矩陣I，不妨設(shè)單位矩陣I1210.000.0,.00.1mP PP即為一即為一初始可行基初始可行基。令非基變量取值為零，便。令非基變量取值為零，便得到一組得到一組基可行解基可行解。 2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3963.23.2最優(yōu)性檢驗(yàn)和解的判別最優(yōu)性檢驗(yàn)和解的判別 對(duì)標(biāo)準(zhǔn)型的一般線性規(guī)劃問(wèn)題，經(jīng)過(guò)變換、迭代，總可將線性規(guī)劃約束條件中非基變量移至方程右邊，得如下形式

4、：即：即：111,111222,112,11.mmnnmmnnmmm mmmnnxbaxaxxbaxaxxbaxax,1niiijjjmxbax其中其中i=1，2，m2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3972022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 398 nmjjjxzz10 棗 z 與與當(dāng)當(dāng)前前非非基基變變量量的的關(guān)關(guān)系系 由此可知，若存在 j 0(m+1 j n)，則有 xj 0，其其它它非非基基變變量量仍仍為為零零的的可可行行解解，其目標(biāo)函數(shù)值,zxzzjj00 這說(shuō)明當(dāng)前解不是最優(yōu)解。若所有 j 0

5、(m+1 j n)，則 z0為可行解所能取得的目標(biāo)函數(shù)最大值，說(shuō)明當(dāng)前解是最優(yōu)解。故稱 j 為檢驗(yàn)數(shù)。將基變量的系數(shù) 0 也視為其檢驗(yàn)數(shù)，可得： 注意：注意：xj的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 是當(dāng)是當(dāng)z表示為非基變量的函數(shù)時(shí)目標(biāo)函表示為非基變量的函數(shù)時(shí)目標(biāo)函數(shù)中數(shù)中xj的系數(shù)?；兞康臋z驗(yàn)數(shù)為零。的系數(shù)?；兞康臋z驗(yàn)數(shù)為零。 2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 399為對(duì)應(yīng)于基為對(duì)應(yīng)于基B的一個(gè)基可的一個(gè)基可(0)12 ,.,0,.,0TmXb bb若若 行解，對(duì)于一切行解，對(duì)于一切 1,.,jmn有檢驗(yàn)數(shù)有檢驗(yàn)數(shù) , 0j則則 ）（ 0X為最優(yōu)解。為最優(yōu)解。

6、 定理定理5:（最優(yōu)解的判別定理）（最優(yōu)解的判別定理）2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3910 定理定理 6 （無(wú)窮多最優(yōu)解的判別定理）（無(wú)窮多最優(yōu)解的判別定理） 若若 對(duì)應(yīng)于基對(duì)應(yīng)于基B的一個(gè)基可的一個(gè)基可 行解，對(duì)于一切行解，對(duì)于一切 ，有檢驗(yàn)數(shù)，有檢驗(yàn)數(shù) 且存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)且存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) =0，則該，則該 線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。(0)12 , ,., ,0,.,0TmXb bb1,.,jmnmk, 0j2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 ftp:/211.71.

7、69.23911無(wú)窮多最優(yōu)解判別定理無(wú)窮多最優(yōu)解判別定理：TmbbbX)0 , 0 ,(21)0(若若B的一個(gè)基可行解，且對(duì)一切的的一個(gè)基可行解，且對(duì)一切的 j=m+1,.,n有有為對(duì)應(yīng)于基為對(duì)應(yīng)于基, 0j又存在某個(gè)非基變量的檢驗(yàn)數(shù)又存在某個(gè)非基變量的檢驗(yàn)數(shù), 0km則線性規(guī)劃則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。問(wèn)題有無(wú)窮多最優(yōu)解。證明：證明：kmx非基變量非基變量新基可行解新基可行解)1(X新的目標(biāo)函數(shù)新的目標(biāo)函數(shù)值不變值不變換入換入)1(X,)0(X兩個(gè)最優(yōu)解兩個(gè)最優(yōu)解，連線上的所有點(diǎn)均是最優(yōu)連線上的所有點(diǎn)均是最優(yōu)解。2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 ftp:/211.71.6

8、9.23912定理定理 7 （無(wú)界解的判別定理）（無(wú)界解的判別定理）若若 為對(duì)應(yīng)于基為對(duì)應(yīng)于基B的一個(gè)基可行解，的一個(gè)基可行解，存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)存在某個(gè)非基變量對(duì)應(yīng)的檢驗(yàn)數(shù) 0，并且對(duì)應(yīng)的，并且對(duì)應(yīng)的變量系數(shù)變量系數(shù) ， 則該線性規(guī)劃問(wèn)題則該線性規(guī)劃問(wèn)題有無(wú)界解（或無(wú)最優(yōu)解）。有無(wú)界解（或無(wú)最優(yōu)解）。(0)12 , ,., ,0,.,0TmXb bbm k,0i m ka1 , 2 , . . . ,im2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3913無(wú)界解的判別定理：無(wú)界解的判別定理：若TmbbbX)0 , 0 ,(21)0(一個(gè)基可行解

9、，有一個(gè), 0,kmia為對(duì)應(yīng)于基B的, 0km并且對(duì)i=1,.,m有那么線性規(guī)劃問(wèn)題具有無(wú)界解（無(wú)最優(yōu)解）。證明：構(gòu)造新的解kmjnmjabxjkmkmiii且, 1, 0, 0,)1()1(,)1(lllxxi=1,2,m2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3914驗(yàn)證可行性：因?yàn)閕,m,000 ，而而xj =0(m+1 j n，j k)，要保持，要保持xi 0 ( i=1，2，,m)，即，即必須必須 于是，當(dāng)于是，當(dāng) 為換出變量。為換出變量。若所有若所有 則則xk 可取無(wú)窮大，問(wèn)題無(wú)最優(yōu)解?？扇o(wú)窮大，問(wèn)題無(wú)最優(yōu)解。min0ilkikiklk

10、bbxaaa0ika ,0,lklllkbxxxa2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3917換出變量確定方法換出變量確定方法: : 一般，計(jì)算一般，計(jì)算 = =lklikikiiabaabmin 0，第，第 l 個(gè)約束個(gè)約束對(duì)應(yīng)的基變量為換出變量。對(duì)應(yīng)的基變量為換出變量。2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 39183 迭代迭代 確定換入變量：當(dāng)確定換入變量：當(dāng) ，確定，確定 換入變量；換入變量；確定換出變量：當(dāng)確定換出變量：當(dāng) ，確定，確定 換入變量；換入變量；將交叉元素（主軸元素）將交叉元素（主軸元

11、素） 單位化，單位化，(旋轉(zhuǎn)旋轉(zhuǎn))kxlxlklikikiabaab0minka1kj )0max(2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3919即乘以初等矩陣。重復(fù)上述步驟直到所有的檢驗(yàn)數(shù)即乘以初等矩陣。重復(fù)上述步驟直到所有的檢驗(yàn)數(shù)滿足最優(yōu)條件，得最優(yōu)解。滿足最優(yōu)條件，得最優(yōu)解。2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 3920最優(yōu)性判別定理：最優(yōu)性判別定理： 若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù)若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù) 0 ( j=1，2，,n),n)，則此解是最優(yōu)解，否則不是最優(yōu)解。，則此解是最優(yōu)解，否則不是最優(yōu)解。j 換換入入變變量量的的確確定定方方法法： 一一般般，當(dāng)當(dāng)jmaxj |j 0= k，取取 xk為為換換入入變變量量。 換出變量確定方法換出變量確定方法: : 一般，計(jì)算一般，計(jì)算 = =lklikikiiabaabmin 0，第，第 l 個(gè)約束個(gè)約束對(duì)應(yīng)的基變量為換出變量。對(duì)應(yīng)的基變量為換出變量。結(jié)論結(jié)論:2022-7-5管理運(yùn)籌學(xué)課程組管理運(yùn)籌學(xué)課程組 ftp:/211.7