【正文】 所有約束條件的解，稱之為可行解。滿足所有約束條件的解的集合，稱為可行域。 ? 不等式約束的轉(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。 OR1 33 基可行解的概念 ? 基可行解： 基解可正可負，負則不可行（違背非負性約束條件），稱滿足所有約束條件的基解為 基可行解。進行等價變換－－約束方程兩端分別左乘 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代入目標函數(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判別準則 ： σj ≤0 時 ,達到最優(yōu)解 OR1 39 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應之非基變量 XK若取非零，將使 Z增加 ,故令 XK 進基。否則轉(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 應用舉例之二 ? 例 14混合配方問題 A、 B、 C、 D四種原料配制三種產(chǎn)品，三類約束：技術要求、原料限量、市場容量。求費用最小的生產(chǎn)計劃。 3y1 +y3=1 x4 ≤ 0。 ? 結(jié)合例題 1講解影子價格： y1=0:第一種資源過剩 y2=：設備臺時最緊張，每增加一個臺時， 利潤增加。對偶問題最優(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工時，設備 5臺時，原材料 7公斤，問要否調(diào)整產(chǎn)品結(jié)構？ 先算檢驗數(shù) σj =CjCBB1pj σ6=C6YP6=110（ 0， ， ）（ 6， 5， 7） T