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

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

2、2x1+2x2=82x1+3x2=03Q2如例如例1，O Q1 Q2或或 O Q4 Q3 Q22022-7-5管理運籌學(xué)課程組管理運籌學(xué)課程組 393單純形法要解決的三方面的問題：單純形法要解決的三方面的問題：（1）如何確定）如何確定初始的基可行解初始的基可行解？（2）如何進行解的）如何進行解的最優(yōu)性判別最優(yōu)性判別？（3）如何尋找）如何尋找改進的基可行解改進的基可行解？2022-7-5管理運籌學(xué)課程組管理運籌學(xué)課程組 39432 確定初始基可行解確定初始基可行解 定義：線性規(guī)劃規(guī)范型，當線性規(guī)劃標準型： Max z = Max z

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

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

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

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

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

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

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

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

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