【正文】 } = σK ，相應(yīng)之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進(jìn)基。 ? 基解的數(shù)目：最多 Cmn=n!/m!(nm)! OR1 34 例題 6 基可行解說明 maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj≥0 j=1,2,…,5 這里 m=3,n=5。 OR1 33 基可行解的概念 ? 基可行解： 基解可正可負(fù)，負(fù)則不可行（違背非負(fù)性約束條件），稱滿足所有約束條件的基解為 基可行解。 n j=1 n j=1 OR1 32 基解的概念 不失一般性 ,設(shè) B是 A的前 m列 ,即B=(p1,p2,…,p m） ,其相對(duì)應(yīng)的變量XB=(x1,x2,…,x m)T,稱為基變量；其余變量XN=(Xm+1,?, Xn)T稱為非基變量。 ? 不等式約束的轉(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)型 和式： maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩陣式： maxZ=CX AX=b X ≥0 約束方程的系數(shù)矩陣 A的秩為 m，且 mn。 凸集：集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)均屬于這個(gè)集合。滿足所有約束條件的解的集合，稱為可行域。 可行域：即可行解的集合。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。據(jù)統(tǒng)計(jì)： 序號(hào) 時(shí)段 最少人數(shù) 安排人數(shù) 1 06— 10 60 X1 2 10— 14 70 X2 3 14— 18 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é)知識(shí)可知： y=ax+b是一條直線，同理： Z=70x1+120x2→x 2=70/120x1Z/120也是一條直線，以 Z為參數(shù)的一族等值線。飼料 III x3kg…… ? 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5 ? 約束條件： 3x2+2x2+x3+6x4+18x5 ≥700 營養(yǎng)要求： x1+++2x4+ ≥30 +x2++2x4+ =200 用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40 非負(fù)性要求： x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0 OR1 16 例題 3：人員安排問題 ? 醫(yī)院護(hù)士 24小時(shí)值班，每次值班 8小時(shí)?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表： 飼料 Va Vb Vc 價(jià)格元 /KG I II III IV V 3 2 1 6 18 1 2 1 2 2 7 4 9 5 營養(yǎng)要求 700 30 200 OR1 15 例題 2建模 ? 設(shè)抓取飼料 I x1kg。 LP有一組有待決策的變量， 一個(gè)線性的目標(biāo)函數(shù)， 一組線性的約束條件 。 ? 本書有現(xiàn)成的程序可以利用 ? 要學(xué)會(huì)解題的思路與方法，建立模型很重要。 ? 數(shù)學(xué)模型：用符號(hào)或數(shù)學(xué)工具描述現(xiàn)實(shí)系統(tǒng)。 ? 形象模型：如地球儀、沙盤、風(fēng)洞 ? 模擬模型：建港口，模擬船只到達(dá)。但定量不可替代定性。 ? 定性有主觀性也有有效性，定量有科學(xué)性也有局限性。 ?中國定義：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人力、