【正文】 XK 進基。 ? 基解的數(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 基可行解的概念 ? 基可行解： 基解可正可負，負則不可行（違背非負性約束條件），稱滿足所有約束條件的基解為 基可行解。 n j=1 n j=1 OR1 32 基解的概念 不失一般性 ,設(shè) B是 A的前 m列 ,即B=(p1,p2,…,p m） ,其相對應(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 非標準型轉(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 非標準型轉(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標準型 和式： maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩陣式： maxZ=CX AX=b X ≥0 約束方程的系數(shù)矩陣 A的秩為 m，且 mn。 凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。滿足所有約束條件的解的集合，稱為可行域。 可行域：即可行解的集合。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。據(jù)統(tǒng)計： 序號 時段 最少人數(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建模 ? 目標函數(shù)： min Z=x1+x2+x3+x4+x5+x6 ? 約束條件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非負性約束： xj ≥0,j=1,2,…6 OR1 18 歸納：線性規(guī)劃的一般模式 ? 目標函數(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 非負性約束： x1 ≥0,x2 ≥0,…,x n ≥0 OR1 19 ? 由中學(xué)知識可知： y=ax+b是一條直線，同理： Z=70x1+120x2→x 2=70/120x1Z/120也是一條直線，以 Z為參數(shù)的一族等值線。飼料 III x3kg…… ? 目標函數(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 非負性要求： x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0 OR1 16 例題 3：人員安排問題 ? 醫(yī)院護士 24小時值班，每次值班 8小時。現(xiàn)有五種飼料，搭配使用，飼料成分如下表： 飼料 Va Vb Vc 價格元 /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有一組有待決策的變量， 一個線性的目標函數(shù)， 一組線性的約束條件 。 ? 本書有現(xiàn)成的程序可以利用 ? 要學(xué)會解題的思路與方法，建立模型很重要。 ? 數(shù)學(xué)模型：用符號或數(shù)學(xué)工具描述現(xiàn)實系統(tǒng)。 ? 形象模型：如地球儀、沙盤、風(fēng)洞 ? 模擬模型：建港口，模擬船只到達。但定量不可替代定性。 ? 定性有主觀性也有有效性，定量有科學(xué)性也有局限性。 ?中國定義：運籌學(xué)是應(yīng)用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。O