ERP高級計劃書的解讀―APS算法分析之單一內(nèi)點方

1、1.單一方法(1),單一算法最初的單一方法的案例目標函數(shù)Z = 500 x X + 300 XY => max!約束X £6丫 £82 XX+ 3 X Y £ 24X,Y 3 0Z-500 X X-300 X Y = 0X+ V1=6Y+V2 =82 XX +3 X Y+ V3 =24X, Y ,V1,V2,V330開始表根本XYV1V2V3力殺V1101006V2010108V32300124Z-500-3000000-最大目標函數(shù)的算法約束被轉(zhuǎn)換成增加松散變量V1,V2,V3的限制一單一方法的意思：V1,V2,V3在方法里,用一個非根本變量改變一個根本變

2、量-目標值增加 -根本變量的值和剩余非-負值-根本改變的優(yōu)選：在目標函數(shù)行里,非根本變量和負系數(shù)-如果目標函數(shù)的所有系數(shù)是非負的,最正確方案就找到了.算法：非根本變量的選擇是在根本里：1 .重要列的決定：在目標函數(shù)行的最低負系數(shù)的變量被選擇,由于目標值增加大局部是這個 變量這里：X和 500.在這個順序,重要欄目是q 這里：q = 1重點要素：A11根本XYV1V2V3力殺印V11010066V2010108-V3230012412Z-500-3000000重要步驟根本XYV1V2V3力殺X101006V2010108V303-20112Z0-3005000030002 .重要行的決定：目標函

3、數(shù)增加的值是隨著新的根本變量的值.如這個值應(yīng)該盡可能的大.一般來說,新的根本變量的增加會導(dǎo)致其它一變量的減少,由于,否那么約束就會沖突.如人力約束.因此,新根本變量增加是有條件限制的,其條件是其它根本變量剩余非-負的值.新的根本變量唯一被增加,直到其它變量之一的值等于0.這個變量將是根本.決定這個瓶頸的所有系數(shù) aiq > 0 重要列q的商計算如下：對所有行i和aiq > 0bi是在方案列里行的系數(shù)值.那么在行P的變量必須被根本的在最低的非-負的值的商如：印的值是6.重要因素：all 行p=1,列q=13 .重要步驟：在重要行里用'1'創(chuàng)立一單位向量,如 a*pq

4、=14 .優(yōu)化條件:,如果目標函數(shù)的行的所有系數(shù)是非負的,就找到最正確方案.否那么就回到第一步選擇總要列這里：優(yōu)化條件是不能完成的.=> 回到第一步.待續(xù)本文由作者向AMT提供作者聯(lián)系方式：ycaifs 蔡穎專欄重要要素：a32根本XYV1V2V3方案0X101006-V20101088V303-201124Z0-300500003000重要步驟:根本XYV1V2V3方案X101006V2002/31-1/34Y01-2/301/34Z0030001004200第二重要步驟之后：最正確方案是 X=6和Y=4,目標值是Z = 4200.根本XYV1V2V3方案X101006V2002/31

5、-1/34Y01-2/301/34Z0030001004200故每天生產(chǎn)數(shù)量：標準沙發(fā)：X = 6特別沙發(fā)：Y = 4每天利潤：4200 RMB(2)最初的和二元單一的關(guān)系Min u >b1:1u >A > c案例:Max 500 X1 +300 X X2Min 6 U1 + 8 U2 + 24 X U3X1 £ 6U1 + 0 XU2 + 2 X U3 > 500X2 £ 80 >U1 + U2 + 3 U3 > 3002 )X1 + 3 >X2 £ 24U1, U2, U3 > 0X1, X2 3 0開始表：根本

6、XTVT方案VA_bZ-cT0T0最后表：根本XTVT方案XBB-1 A_B-1B-1 b_ZcBTJ-l A二空cBTB-1cBTB-1 b_二元變量：U = cBT B-1減少本錢： W = cBT B-1 A -cT注意：T匹配列的發(fā)散向量=> 行向量X 決策/問題變量向量V 松散變量的向量=初始化表格里的根本變量A 約束矩陣L 單元矩陣b -右方面向量c“價格向量對決策變量的目標函數(shù)系數(shù)的向量0包含只有0的向量B-1 -根本矩陣逆轉(zhuǎn)它可以在列下松散變量找到cB =根本變量的目標函數(shù)系數(shù)的向量就像在列里的“根本根本變量的順序待續(xù)本文由作者向AMT提供作者聯(lián)系方式：ycaifs 蔡穎

7、專欄« ERP高級方案?書的解讀 一APS算法分析之單一：內(nèi)點方法 三蔡穎文檔號:00.050.714 時間：10-11-20042,內(nèi)部點法開始方案單一算法單一：算法是從多面的頂點到一新的頂點,用一次沿著一邊推進的移動.內(nèi)部點法IPM:算法是通過多面的內(nèi)部的移動.比擬：1. LP的優(yōu)化問題總是落在頂點.如一可行區(qū)域分解線的極點.2. 通過內(nèi)部區(qū)域的移動算法必須注意一個事實,它就是不要離開可行區(qū)域.到達可行區(qū)域的分解線要被懲罰的.這個懲罰是動態(tài)的減少,以至于找到在分解線的一個方案.3. 內(nèi)部點法包含復(fù)雜的數(shù)學(xué)和使用高等數(shù)學(xué)的概念.內(nèi)部點法IPMs的大量變量已經(jīng)完成開發(fā).在線性規(guī)劃,內(nèi)

8、部點發(fā)較好是適用,特別是巨大,稀罕的問題.這里,要考慮計算的時間.優(yōu)化方案的解釋根本XYV1V2V3方案X101006V2002/31-1/34Y01-2/301/34Z0030001004200利潤=4200決策變量：X = 6, Y = 4閑散變量:V1 = 0, V2 = 4, V3 = 0影子價格：U1 = 300, U2 = 0, U3 = 100 減少本錢= 相關(guān)利潤:W1= 0, W2 =0. 人工水平是充分利用.因此一約束力的約束V3=0.標準沙發(fā)的是V1=0那里對特別沙發(fā)就沒有約束力的約束V2>0 減少本錢-> 決策變量:如果一個變量在優(yōu)化方案里取一正值,它就表現(xiàn)

9、為它可以對最大化問題有有用的奉獻.如果變量的值是0,它的減少本錢告訴我們多少目標函數(shù)系數(shù)必須增加,為了到達非-零值.或者,減少本錢也許告訴我們有多少變量比起其它變量是“低于價格在最大化問題里o對于根本變量減少本錢總是等于0. 影子價格-> 約束：約束的二元值是可以在約束的右面里用一個單位增加,得到增加的對最大化問題.如人工約束的一個單位的增加將對目標函數(shù)產(chǎn)生100RMB o這個二元值還可以作為在目標函數(shù)里的單位增加是由約束的右面的單位增加引起的.如果一限制沒有約束力或沒有活動,那么,二元變量就是0,就有一些松散變量可用.-注意減少本錢和影子價格是邊際概念是一樣的LP的案例2Max 2A - B+ C 目標函數(shù)3A + B + C £60約束-資源110約束-資源2A + B - C£20約束-資源3A,B,C30非-負-約束優(yōu)化方案:根本ABCV1V2V3方案V10011-1-210A100.500.50.515B01-1.50-0.50.55利潤001.501.50.525決策變量：A = 15, B = 10, C = 0 => 利潤=25松散變量：V1 = 10, V2 = 0, V3 = 0影子價格:U1 = 0, U2 = 1.5, U3 = 0.5減少本錢=相對利潤：W1 = 0, W2 =