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

1、1.單一方法(1),單一算法最初的單一方法的案例目標(biāo)函數(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-最大目標(biāo)函數(shù)的算法約束被轉(zhuǎn)換成增加松散變量V1,V2,V3的限制一單一方法的意思：V1,V2,V3在方法里,用一個(gè)非根本變量改變一個(gè)根本變

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

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

4、=14 .優(yōu)化條件:,如果目標(biāo)函數(shù)的行的所有系數(shù)是非負(fù)的,就找到最正確方案.否那么就回到第一步選擇總要列這里：優(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,目標(biāo)值是Z = 4200.根本XYV1V2V3方案X101006V2002/31

5、-1/34Y01-2/301/34Z0030001004200故每天生產(chǎn)數(shù)量：標(biāo)準(zhǔn)沙發(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“價(jià)格向量對(duì)決策變量的目標(biāo)函數(shù)系數(shù)的向量0包含只有0的向量B-1 -根本矩陣逆轉(zhuǎn)它可以在列下松散變量找到cB =根本變量的目標(biāo)函數(shù)系數(shù)的向量就像在列里的“根本根本變量的順序待續(xù)本文由作者向AMT提供作者聯(lián)系方式：ycaifs 蔡穎

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

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

9、為它可以對(duì)最大化問題有有用的奉獻(xiàn).如果變量的值是0,它的減少本錢告訴我們多少目標(biāo)函數(shù)系數(shù)必須增加,為了到達(dá)非-零值.或者,減少本錢也許告訴我們有多少變量比起其它變量是“低于價(jià)格在最大化問題里o對(duì)于根本變量減少本錢總是等于0. 影子價(jià)格-> 約束：約束的二元值是可以在約束的右面里用一個(gè)單位增加,得到增加的對(duì)最大化問題.如人工約束的一個(gè)單位的增加將對(duì)目標(biāo)函數(shù)產(chǎn)生100RMB o這個(gè)二元值還可以作為在目標(biāo)函數(shù)里的單位增加是由約束的右面的單位增加引起的.如果一限制沒有約束力或沒有活動(dòng),那么,二元變量就是0,就有一些松散變量可用.-注意減少本錢和影子價(jià)格是邊際概念是一樣的LP的案例2Max 2A - B+ C 目標(biāo)函數(shù)3A + B + C £60約束-資源110約束-資源2A + B - C£20約束-資源3A,B,C30非-負(fù)-約束優(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影子價(jià)格:U1 = 0, U2 = 1.5, U3 = 0.5減少本錢=相對(duì)利潤：W1 = 0, W2 =