【正文】 8 60 X3 4 18—22 50 X4 5 22—02 20 X5 6 02—06 30 x6 OR1 17 例題 3建模 ? 目標(biāo)函數(shù)： min Z=x1+x2+x3+x4+x5+x6 ? 約束條件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非負(fù)性約束： xj ≥0,j=1,2,…6 OR1 18 歸納：線性規(guī)劃的一般模式 ? 目標(biāo)函數(shù)： max(min)Z=c1x1+c2x2+c3x3+…+c nxn ? 約束條件： a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1 a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2 … … … … am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn 非負(fù)性約束： x1 ≥0,x2 ≥0,…,x n ≥0 OR1 19 ? 由中學(xué)知識可知： y=ax+b是一條直線，同理： Z=70x1+120x2→x 2=70/120x1Z/120也是一條直線，以 Z為參數(shù)的一族等值線。 9x1+4x2 ≤360 → x 1 ≤360/94/9x2 是直線 x1=360/94/9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。 OR1 20 例 1圖示 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 ≤ 360 4x1+5x2 ≤200 3x1+10x2 ≤300 A B C D E F G H I Z=70x1+120x2 OR1 21 概念 ? 概念： 可行解：滿足所有約束條件的解。 可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。 基解：約束條件的交點稱為基解（直觀） 基可行解：基解當(dāng)中的可行解。 凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。如：實心球、三角形 OR1 22 結(jié)論 ? 可行域是個凸集 ? 可行域有有限個頂點 ? 最優(yōu)值在可行域的頂點上達到 ? 無窮多解的情形 ? 無界解情形 ? 無解情形 OR1 23 ? 代數(shù)式 maxZ=c1x1+c2x2+…+c nxn a11x1+a12x2+…+a 1nxn=b1 a21x1+a22x2+…+a 2nxn=b2 … … … am1x1+am2x2+…+a mnxn=bm xj ≥0 j=1,2,…,n OR1 24 線性規(guī)劃的標(biāo)準(zhǔn)型 ? 和式： maxZ=∑cjxj ∑aijxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n j=1 n n j=1 OR1 25 線性規(guī)劃的標(biāo)準(zhǔn)型 ?向量式： maxZ=CX ∑pjxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n C=(c1,c2,c3,…,c n) X=(X1,X2,X3,…,X n) T n j=1 OR1 26 線性規(guī)劃的標(biāo)準(zhǔn)型 ? 矩陣式： maxZ=CX AX=b X ≥0 其中： b=(b1,b2,…,b m)T a11 a12 …. a1n A= a21 a22 … a2n … … … am1 am2 … amn OR1 27 標(biāo)準(zhǔn)型的特征 ? 目標(biāo)函數(shù)極大化 ? 約束條件為等式 ? 決策變量非負(fù) OR1 28 非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型 ? 目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=－ max(－ Z) ，一個數(shù)的極小化等價于其相反數(shù)的極大化。 ? 不等式約束的轉(zhuǎn)化： ∑aijxj≤bi 加入松弛變量 ∑aijxj≥bi 減去剩余變量 ?非正變量：即 xk ≤0 則令 x’k =－ xk 自由變量：即 xk無約束，令 xk= x’k－ x”k OR1 29 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例 之一 maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2≤360 9X1+4X2+X3=360 4X1+5X2 ≤200 4X1+5X2 +x4=200 3X1+10X2 ≤300 3X1+10X2+x5 =300 X1≥0 X2≥0 Xj≥0 j=1,2,…,5 OR1 30 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例 之二 minZ=x1+2x23x3 maxZ’=x’1－ 2x2+3(x’3－ x”3) x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9 x12x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 x5= 2 3x1+x23x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5 x1 ≤0 x2 ≥0 x3無約束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0 OR1 31 ?基的概念 ：如前所述 LP標(biāo)準(zhǔn)型