[ppt模板]線性規(guī)劃-資料下載頁
2025-01-19 09:52本頁面
【正文】 ? 6 x1 + x2 ? 4 A Q1 Q2 Q3 Q4 B 可行域 本問題解的情況： 基礎(chǔ)解： 點(diǎn) （ O， A， B， Q1， Q2， Q3， Q4） 可行解： 由點(diǎn) （ O， Q1， Q2， Q3， Q4） 圍成的區(qū)域。 基礎(chǔ)可行解： 點(diǎn) （ O， Q1， Q2， Q3， Q4） 最優(yōu)解： Q3 解的集合： 非可行解 可行解 解的集合： 基礎(chǔ)解 解的集合： 可行解 基礎(chǔ)解 基礎(chǔ)可行解 解的集合： 可行解 基礎(chǔ)解 基礎(chǔ)最優(yōu)解 基礎(chǔ)可行解 線性規(guī)劃解的性質(zhì)（幾何意義） 凸集概念： 設(shè) D是 n維線性空間 Rn的一個點(diǎn)集，若D中的任意兩點(diǎn) x(1),x(2)的連 線上的一切點(diǎn) x仍在 D中，則稱 D為凸集。 即： 若 D中的任意兩點(diǎn) x(1),x(2) ∈ D，存在0?1 使得 x= ? x(1)+(1 ?)x(2) ∈ D,則稱 D為凸集 例 X1 X2 X(1) X(2) X 圖（ 17） 例 1 . 5 X1 X2 X(1) X(2) X(2) X(1) X(2) 圖（ 17） X 例 1 . 5 X1 X2 X(1) X(2) X X(1) X(2) y= ?(X(1) X(2) ) (0 ? 1) X=X(2)+y = X(2)+ ?(X(1) X(2) ) = ? X(1) +(1 ?)X(2) 圖（ 17） 例 1 . 5 X1 X2 X(1) X(2) X X(2) X(1) X(2) 圖（ 17） X=X(2)+y = X(2)+ ?(X(1) X(2) ) = ? X(1) +(1 ?)X(2) y= ?(X(1) X(2) ) (0 ? 1) 例 1. 6（凸集 ） 例 1. 7（非凸集） 例 （凸集性質(zhì)） ?二個凸集的交還是凸集 ?二個凸集的并不一定是凸集 兩個基本概念： 凸組合： 設(shè) x(1),x(2) … ..x(k)是 n維線性空間Rn中的 k個點(diǎn)，若 存在數(shù) u1,u2,… .uk 且 0 ui 1 (i=1,2,… k), ? ui =1, 使得 x= u1 x(1)+ u2 x(2) +… ..+ uk x(k) 成立，則稱 x為 x(1),x(2) … ..x(k)的凸組合 。 兩個基本概念： 頂點(diǎn)： 設(shè) D是凸集 , 若 D中點(diǎn) x 不能成為 D中任何線段上的內(nèi)點(diǎn)，則稱 x為凸集 D的頂點(diǎn)。 即： 若 D中的任意兩點(diǎn) x(1),x(2) ，不存在數(shù) ? （ 0 ? 1） 使得 x= ? x(1)+(1 ?)x(2) 成立，則稱 x為凸集 D的一個頂點(diǎn)。 例 ： 多邊形上的點(diǎn)是頂點(diǎn) 圓周上的點(diǎn)都是頂點(diǎn) 線性規(guī)劃的基本定理 定理 11 線性規(guī)劃問題的可行解集是凸集。（即連接線性規(guī)劃問題任意兩個可行解的線段上的點(diǎn)仍然是可行解。 ) 線性規(guī)劃的基本定理 定理 12 線性規(guī)劃問題的可行解 x為基礎(chǔ)可行解的充分必要條件是： x的非零分量所對應(yīng)的系數(shù)矩陣 A的列向量是線性無關(guān)。 線性規(guī)劃的基本定理 定理 13 線性規(guī)劃問題的可行解集 D中的點(diǎn) x是頂點(diǎn)的充分必要條件是： x是基礎(chǔ)可行解。 線性規(guī)劃的基本定理 推論： 可行解集 D中的頂點(diǎn)個數(shù)是有限的。 推論： 若可行解集 D是有界的凸集，則 D中任意一點(diǎn) x，都可表示成 D的頂點(diǎn)的凸組合。 例 110： x1 x2 X(1) X(2) X(3) x x1 x2 X(1) X(2) X(3) x X’ X?= ? X(1) +(1 ?)X(3) (0 ? 1) x1 x2 X(1) X(2) X(3) X X’ X = ?X’ +(1 ?)X(2) (0 ? 1) 因?yàn)?x’是 X(1) ， X(3)連線上的一點(diǎn)，故 x’ = ? X(1) +(1 ?)X(3) (0 ? 1) 又因?yàn)?x是 X ’ ， X(2)連線上的一點(diǎn)，故 X = ? X’ +(1 ?)X(2) (0 ? 1) X = ? （ ? X(1) +(1 ?)X(3)） +(1 ?)X(2) = ? ? X(1) +(1 ?)X(2) +(1 ?) ? X(3) =u1X(1) +u2X(2) +u3X(3) 其中 (0ui1) 且 u1 +u2 +u3 = ? ? +(1 ?)+(1 ?) ? =1 x1 x2 X(1) X(2) X(3) X’ X =u1X(1) +u2X(2) +u3X(3) 線性規(guī)劃的基本定理 定理 14 若可行解集 D有界，則線性規(guī)劃問題的最優(yōu)解，必定在 D的頂點(diǎn)上達(dá)到。 說明 1： 若可行解集 D無界，則線性規(guī)劃問題可能有最優(yōu)解，也可能無最優(yōu)解。若有最優(yōu)解，也必在頂點(diǎn)上達(dá)到。 說明 2： 有時(shí)目標(biāo)函數(shù)也可能在多個頂點(diǎn)上達(dá)到最優(yōu)值。這些頂點(diǎn)的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1