1、單純形法的預(yù)備知識(shí),1. 線性規(guī)劃的標(biāo)準(zhǔn)型 (The Standard Form of LP),定義,單純形法的預(yù)備知識(shí),單純形法的預(yù)備知識(shí),令,單純形法的預(yù)備知識(shí),令,單純形法的預(yù)備知識(shí),如何將非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型,(i) 如果是求目標(biāo)函數(shù)極小化的問題，即 min z=CX，則令 w= -z，轉(zhuǎn)化為對(duì)w 實(shí)現(xiàn)極大化，即 max w= -CX .,(v) 如果變量 xi 無符號(hào)限制，可令 其中,(iv) 如果第 i 個(gè)約束條件的右端項(xiàng) bi 0, 則在該約束的兩端同時(shí) 乘以 “-1”, 然后再做相應(yīng)的變換.,單純形法的預(yù)備知識(shí),例 1,單純形法的預(yù)備知識(shí),例 2,單純形法的預(yù)備知識(shí),2 線性規(guī)

2、劃的解的概念,AX=b - m 個(gè)方程，n 個(gè)變量 (mn)，其中R(A)=m.,稱 A 中任一個(gè) m 階可逆矩陣 B 為線性規(guī)劃問題 的一個(gè)基,若記基 則稱 為基 B 中的一個(gè)基向量,單純形法的預(yù)備知識(shí),與基向量 相對(duì)應(yīng)的變量 稱為基 變量。 否則稱為非基變量,取 A 中一個(gè)基 ，則對(duì)應(yīng)的基變量為 這時(shí)稱相應(yīng)的非基變量取值均為零的條件下,滿足約束條件AX=b 的解為 基本解,單純形法的預(yù)備知識(shí),例 3. 求下面方程組的所有基本解。,基變量 非基變量 基本解 x1, x2 x3 (2, 1, 0) x1, x3 x2 (3, 0, -1) x2, x3 x1 (0, 3, 2),稱滿足非負(fù)約束

3、條件的基本解為基可行解。,稱對(duì)應(yīng)于基本可行解的基為可行基,單純形法的預(yù)備知識(shí),例 4 求下面線性規(guī)劃問題的所有基可行解,解: 其約束方程的系數(shù)矩陣為,單純形法的預(yù)備知識(shí),則求解如下： 非基變量 基變量 基本解 基可行解 x1, x2 x3, x4, x5 (0, 0, 100, 80, 40) Y x1, x3 x2, x4, x5 (0, 100, 0, -20, 40) N x1, x4 x2, x3, x5 (0, 80, 20, 0, 40) Y x1, x5 x2 x3, x4 無解 - x2, x3 x1, x4, x5 (50, 0, 0, 30, -10) N x2, x4 x

4、1, x3, x5 (80, 0, -60, 0, -40) N x2, x5 x2, x3, x4 (40, 0, 20, 40, 0) Y x3, x4 x1, x2, x5 (20, 60, 0, 0, 20) Y x3, x5 x1, x2, x4 (40, 20, 0, 20, 0) Y x4, x5 x1, x2, x3 (40, 40, -20, 0, 0) N,單純形法的預(yù)備知識(shí),LP的 解 之間 的關(guān)系,單純形法的預(yù)備知識(shí),3 線性規(guī)劃的基本理論,注: 換句話說, 如果連接 S 中任何兩點(diǎn)的線段都在 S 中，則 S為凸集.,設(shè)集合 若對(duì) 及每一個(gè)數(shù) 都有 則稱 S 凸集,單純形法的預(yù)備知識(shí),如果 S 中的一個(gè)點(diǎn) z 被表示為 S 中兩點(diǎn) x 與 y 的凸組合, 即，如 果對(duì)于某個(gè) 0 t 1，有 則必有 x=y，這時(shí)稱 z 為 S 的 一個(gè)頂點(diǎn).,單純形法的預(yù)備知識(shí),定理 1. 任何線性規(guī)劃問題的可行域都是凸集.,定理 2. 線性規(guī)劃問題的每 一個(gè)基可行解對(duì)應(yīng)于可行域 的一個(gè)頂點(diǎn).,定理 3. 若線性規(guī)劃問題有最 優(yōu)解，則其目標(biāo)函數(shù)的最優(yōu)值 一定可以在其可行域