【文章內(nèi)容簡(jiǎn)介】 性規(guī)劃解的基本概念 考慮 標(biāo)準(zhǔn)形式的線性規(guī)劃問題 可行解 ——滿足所有約束條件的解X=(x1,x2,…,x n)T,稱為 LP問題的可行解。所有可行解的集合稱為可行域。 最優(yōu)解 ——使得目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。 LP問題的可行域是一個(gè)凸集。 廣東工業(yè)大學(xué)管理學(xué)院 59 基 ——設(shè) A為約束方程組的 m╳ n階 系數(shù)矩陣 （通?？偧俣?nm，且 A的秩 =m），若B是 A的一個(gè) m╳ m階的 滿秩子矩陣 ，則稱 B是 LP問題的一個(gè) 基 。若 B是 LP問題的一個(gè)基，則它的每一個(gè)列向量稱為 基向量 ，與基向量對(duì)應(yīng)的變量稱為 基變量 ? ?mmmmmmmPPPaaaaaaaaaB ???????21212222111211??????????????LP問題的基本概念（續(xù) 1） 廣東工業(yè)大學(xué)管理學(xué)院 60 秩的概念 如果矩陣 A中有一個(gè) r階子式 Dr不等于零，而所有 r+1階子式（如果存在的話）的值全等于零，則稱 Dr為矩陣 A的一個(gè)最高階非零子式，其階數(shù) r稱為矩陣 A的秩。 注： Dr為行列式 r的值。 廣東工業(yè)大學(xué)管理學(xué)院 61 LP問題的基本概念（續(xù) 2） 基解 在約束方程組 中令所有的非基變量 xm+1=xm+2=…=x n=0,則由于剩下的變量（基變量）構(gòu)成的方程組的系數(shù)行列式 |B|≠0，因此約束方程組此時(shí)有唯一的解XB=（ x1, x2, …, x m, 0, …, 0) T這個(gè)解稱為 LP問題的（對(duì)應(yīng)基 B的） 基解 。 ),2,1(1mibxanjijij ?????很明顯，對(duì)應(yīng)著不同的基， LP問題有不同的基解。因此 LP問題的基解不是唯一的，但總數(shù)不超過 此外基解不一定是可行解 。 mnC廣東工業(yè)大學(xué)管理學(xué)院 62 LP問題的基本概念（續(xù) 3） 基可行解 ——滿足非負(fù)約束條件的基解稱為基可行解 可行基 ——對(duì)應(yīng)著基可行解的基稱為 可行基 很明顯 LP問題的基可行解是有限的。并且每一個(gè)基可行解對(duì)應(yīng)著可行域的一個(gè)頂點(diǎn)。 廣東工業(yè)大學(xué)管理學(xué)院 63 找出下述線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解。 ??????????????????0,41025..32m a x543215242131321xxxxxxxxxxxxtsxxxz廣東工業(yè)大學(xué)管理學(xué)院 64 序號(hào) x1 x2 x3 x4 x5 z 是否基可行解 1 0 0 5 10 4 5 是 2 0 4 5 2 0 17 是 3 5 0 0 5 4 10 是 4 0 5 5 0 1 20 否 5 10 0 5 0 4 15 否 6 5 0 0 是 7 5 4 0 3 0 22 否 8 2 4 3 0 0 19* 是 廣東工業(yè)大學(xué)管理學(xué)院 65 凸集及其頂點(diǎn) 凸集 ——如果一個(gè)非空集合中任意兩點(diǎn)的連線段上所有點(diǎn)仍屬于該集合，則稱該集合為 凸集 。 凸集的頂點(diǎn) ——若凸集中的一個(gè)點(diǎn)不是任何另外兩點(diǎn)連線段上的點(diǎn)，則稱該點(diǎn)為這個(gè)凸集的頂點(diǎn) 。 凸集 凸集 不是凸集 頂點(diǎn) 廣東工業(yè)大學(xué)管理學(xué)院 66 幾個(gè)基本定理 定理 1 若 LP問題存在可行解，則問題的可行域?yàn)橥辜? 定理 2 LP問題的基可行解對(duì)應(yīng)著 LP問題可行域的頂點(diǎn) 定理 3 若 LP問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解 廣東工業(yè)大學(xué)管理學(xué)院 67 單純形法迭代原理 單純形法迭代步驟： 找出一個(gè)基可行解 是否為最優(yōu)解 停止 （依據(jù)： LP問題的最優(yōu)解若存在，則一定有一個(gè)基可行解為最優(yōu)解。） 轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)增大 開始 Y N 廣東工業(yè)大學(xué)管理學(xué)院 68 基可行解 求基解 求解線性 方程組 ),2,1( 1 mi bxanjijij?????求基 B或基變量 廣東工業(yè)大學(xué)管理學(xué)院 69 求基可行解需要考慮的問題 ? 是否便于計(jì)算目標(biāo)函數(shù)值 ? 是否便于判斷其目標(biāo)函數(shù)值是否為最大 ? 是否便于轉(zhuǎn)換到目標(biāo)函數(shù)值更大的相鄰基可行解 廣東工業(yè)大學(xué)管理學(xué)院 70 初始基可行解 通常都是從一種特殊的基可行解出發(fā)求解 LP問題，這一特殊的基可行解稱為 初始基可行解 。初始基可行解對(duì)應(yīng)的基，也稱 初始可行基 ，它具有特定的形式，它是 單位矩陣或者由單位矩陣經(jīng)過交換列以后得到的矩陣 。相應(yīng)的基變量稱為 初始基變量 ，它是一組變量，具有特點(diǎn)： 共有 m個(gè)變量，恰好每個(gè)約束方程包含一個(gè)變量，且該變量的系數(shù)為 1。 廣東工業(yè)大學(xué)管理學(xué)院 71 已知初始基變量，求初始基可行解 以例 1為例說(shuō)明求法。添加松弛變量后例 1可標(biāo)準(zhǔn)化為 ??????????????????0,524261552m a x515214213221xxxxxxxxxxxxz?其中 x3, x4, x5為初始基變量，初始基可行解為 ? ? TX 5241500?廣東工業(yè)大學(xué)管理學(xué)院 72 不難發(fā)現(xiàn)這時(shí)每個(gè)初始 基變量取的值恰好就是包含這個(gè)變量的約束方程的右端常數(shù)值，非基變量取的值為零 。將這個(gè)解代入到目標(biāo)函數(shù)，就可得到這個(gè)解對(duì)應(yīng)的目標(biāo)函數(shù)值。 目標(biāo)函數(shù)目前的值為零，很明顯如果能使的變量 x1或 x2取正值的話，目標(biāo)函數(shù)的值還可以增加。所以目標(biāo)函數(shù)還未達(dá)到其最大值。 一般地， 若目標(biāo)函數(shù)已經(jīng)表示成了非基變量的函數(shù)，且其中非基變量的系數(shù)中還有正數(shù)，則目標(biāo)函數(shù)還可能增大 。這時(shí)目標(biāo)函數(shù)中各變量的系數(shù)稱為 檢驗(yàn)數(shù) 。 這時(shí)目標(biāo)函數(shù)的表達(dá)式為 212 xxz ??廣東工業(yè)大學(xué)管理學(xué)院 73 若基可行解不是最優(yōu)解，則需要轉(zhuǎn)到一個(gè)相鄰的基可行解，并使得目標(biāo)函數(shù)值增加。 所謂 相鄰 的基可行解是指兩個(gè)基可行解只有一個(gè)基變量不同而其它的基變量都相同。 要從一個(gè)基可行解轉(zhuǎn)到與它相鄰的基可行解，意味著需要將一個(gè)非基變量變成基變量，而且將一個(gè)原來(lái)的基變量變?yōu)榉腔兞浚罢叻Q為換入變量 ，后者稱為 換出變量 。 廣東工業(yè)大學(xué)管理學(xué)院 74 確定換入變量 目的： 新的基變量換入后，會(huì)使目標(biāo)函數(shù)值增大（通常還希望增加的越大越好） 因此選擇在目標(biāo)函數(shù)中系數(shù)為正值的非基變量作為換入變量，通常取在目標(biāo)函數(shù)中最大的正系數(shù)對(duì)應(yīng)的非基變量為換入變量，即 取最大的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量為換入變量 。 換入變量為 x1 對(duì)例 1，這時(shí)目標(biāo)函數(shù)為 212 xxz ??廣東工業(yè)大學(xué)管理學(xué)院 75 確定換出變量 由于基變量只有 m個(gè)，因此將一個(gè)非基變量變?yōu)榛兞亢?，必須將一個(gè)原來(lái)的基變量變?yōu)榉腔兞?，這個(gè)變量就是所謂的 換出變量 。 換出變量與 換入變量 是密切相關(guān)的。設(shè) xk是換入變量。若 xk0，則第 i個(gè)約束條件可以寫成 ininkikii bxaxaxxa ??????? ???11并且由于其余的非基變量保持零值，因此 )( kikiiki xabax ??廣東工業(yè)大學(xué)管理學(xué)院 76 由此可見為保證 xi≥0，就必須 從而對(duì)所有的 i，若 aik0，則 ikik abx ?ikik abx ?廣東工業(yè)大學(xué)管理學(xué)院 77 若確定 xk為換入變量，則可估計(jì) xk的取值，使得： 其余的決策變量都取非負(fù)值；并且目標(biāo)函數(shù)得到盡可能的增加 。對(duì)前者，只須 對(duì)所有的 i成立，即 ikikabx ??????? ?? 0m inikikik aabx為了使目標(biāo)函數(shù)盡可能增加，顯然應(yīng)該有 ?????? ?? 0m inikikik aabx設(shè) i = l (1 ? l ? n)時(shí)，上式右端達(dá)到最小值。由于 )( klkllkl xabax ??因此 xl = 0。 廣東工業(yè)大學(xué)管理學(xué)院 78 這意味著 xl可以是非基變量。因此取 xl為換出變量。也就是取 使得 ???????? 0m i n ikikilkl aabab成立的 l 對(duì)應(yīng)的基變量 xl為換出變量 。 ??????????????????0,524261552m a x515214213221xxxxxxxxxxxxz?對(duì)例 1 由于已經(jīng)確定了 x1是換入變量。而 624}15,624m in { ?因此 x4是換出變量 24/6 5/1 廣東工業(yè)大學(xué)管理學(xué)院 79 確定換出變量等價(jià)于確定了一組新的基變量，為了方便地求出相應(yīng)的基解，接下來(lái)將進(jìn)行如下的運(yùn)算： 將這組新的基變量的系數(shù)矩陣化為單位矩陣（或單位矩陣交換列后得到的矩陣），這等價(jià)于使得這組基變量中每個(gè)變量只出現(xiàn)在一個(gè)方程中并且在該方程中的系數(shù)為 1，這稱為 旋轉(zhuǎn) 運(yùn)算 。 旋轉(zhuǎn)運(yùn)算可以利用對(duì)約束方程組進(jìn)行加減消元法完成。 廣東工業(yè)大學(xué)管理學(xué)院 80 ?????????????5242615552142132xxxxxxxx對(duì)例 1的約束方程組 第 2式 ?6 ???????????????54613115552142132xxxxxxxx第 3式 – 第 2式 ?????????????????161324613115554242132xxxxxxxx廣東工業(yè)大學(xué)管理學(xué)院 81 ?????????????????161324613115554242132xxxxxxxx由此可以立即得到新的基解為 1,0,15,0,4 54321 ????? xxxxx很明顯，它是基可行解。為了判斷這一新的基可行解是否為最優(yōu)解， 需要將原目標(biāo)函數(shù)改寫為新的非基變量的函數(shù) 。原目標(biāo)函數(shù)為 但是 421 61314 xxx ??? 代入目標(biāo)函數(shù)，得 212 xxz ??廣東工業(yè)大學(xué)管理學(xué)院 82 即 其中系數(shù) 1/3， 1/6分別是非基變量 x2， x4的檢驗(yàn)數(shù)。 因此對(duì)應(yīng)于這一新的基可行解，目標(biāo)函數(shù)值為 z = 8。問題是 這一目標(biāo)函數(shù)值是否為最優(yōu)的目標(biāo)函數(shù)值 。 由于 x2的系數(shù)（檢驗(yàn)數(shù)）為 1/3，是正數(shù)，因此如果能使 x2取正數(shù)，則目標(biāo)函數(shù)還能增加。因此該基可行解仍不是最優(yōu)解。 一般地，對(duì)一個(gè)基可行解而言， 若非基變量的檢驗(yàn)數(shù)中存在正數(shù)，則該解不是最優(yōu)解；否則它一定是最優(yōu)解 。 42242 61318613142 xxxxxz ?????????? ???42 61318 xxz ???廣東工業(yè)大學(xué)管理學(xué)院 83 單純形法求解過程小結(jié) （ 1）求出初始基可行解 （ 2）通過非基變量在目標(biāo)函數(shù)中的系數(shù)（檢驗(yàn)數(shù)）是