【正文】 解。滿足所有約束條件的解的集合，稱為可行域。 ? 不等式約束的轉(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。 OR1 33 基可行解的概念 ? 基可行解： 基解可正可負(fù)，負(fù)則不可行（違背非負(fù)性約束條件），稱滿足所有約束條件的基解為 基可行解。進(jìn)行等價變換－－約束方程兩端分別左乘 B－ 1 得 X1+ +a’ 1m+1xm+1+…+ a’ 1nxn=b’ 1 x2+ +a’ 2m+1xm+1+…+ a’ 2nxn=b’ 2 …………………………….. xm+a’ mm+1xm+1+…+ a’ mnxn=b’ m 令非基變量為 0，得基可行解 X(0)=(b1’， b2’， ……b m， 0， ……0 ） T z0=∑cibi’ OR1 37 ? ： LP經(jīng)過若干步迭代，成為如下形式： X1+ +a’ 1m+1xm+1+…+ a’ 1nxn=b’ 1 x1=b’ 1 ∑ a’ 1jxj x2+ +a’ 2m+1xm+1+…+ a’ 2nxn=b’ 2 x2=b’ 2 ∑a’2jxj …………………………….. …………….. xm+a’ mm+1xm+1+…+ a’ mnxn=b’ m xm=b’ m ∑a’mjxj OR1 38 單純形法 一般性表示 ： xi=b’ i ∑a’ijxj i=1,2,…m 將 xi代入目標(biāo)函數(shù)得 ： Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’ i ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj ∑ cia’ij)xj 令： σj= cj ∑ cia’ij z0=∑cibi’ 則 Z=z0+ ∑ σj xj σj判別準(zhǔn)則 ： σj ≤0 時 ,達(dá)到最優(yōu)解 OR1 39 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應(yīng)之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進(jìn)基。否則轉(zhuǎn)下步 ? 若某 σK ≥ 0而 P’ K ≤0 ， 則最優(yōu)解無界，結(jié)束。 方案 料型 1 2 3 4 5 6 7 8 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合計 殘料 0 OR1 46 應(yīng)用舉例之二 ? 例 14混合配方問題 A、 B、 C、 D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場容量。求費(fèi)用最小的生產(chǎn)計劃。 3y1 +y3=1 x4 ≤ 0。 ? 結(jié)合例題 1講解影子價格： y1=0:第一種資源過剩 y2=：設(shè)備臺時最緊張，每增加一個臺時， 利潤增加。對偶問題最優(yōu)解： Y1=2,Y2=0 ? C1的變化范圍：以 C1代入末表， C1 ≥1 ?右端項變化范圍： xB= B1b ≥0 ? ?b1 ≥6， ?b2≥10 OR1 70 演講完畢，謝謝觀看！ 。 例題 6：新增一種 C產(chǎn)品，單位利潤 110元，使用勞動力 6工時，設(shè)備 5臺時，原材料 7公斤，問要否調(diào)整產(chǎn)品結(jié)構(gòu)？ 先算檢驗數(shù) σj =CjCBB1pj