溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

線性規(guī)劃算法原理介紹

發(fā)布時(shí)間：2020-08-06 19:38:08 來(lái)源：網(wǎng)絡(luò) 閱讀：6497 作者：158114527090 欄目：開(kāi)發(fā)技術(shù)

線性規(guī)劃定義：

求滿足約束的最優(yōu)目標(biāo)，目標(biāo)是變量的線性函數(shù)，約束是變量的相等或不等表達(dá)式。

單純形算法

1 松弛變量 為將不等式轉(zhuǎn)化為等式添加的非負(fù)變量 
比如 將f(xi) >0 變成 xj= f(xi) ,那么xj就是松弛變量

主元操作（pivot）

1 任意在目標(biāo)函數(shù)中系數(shù)為正的基本變量xi， 計(jì)算對(duì)其約束最緊的松弛變量yj 
2 將yj= f(x) 轉(zhuǎn)換成 xi = f(x,yj) 
3 將上式代入其余約束和目標(biāo)函數(shù) ，從而生成新的線性方程組

單純形算法（simplex）

1 將標(biāo)準(zhǔn)型轉(zhuǎn)化為基本解可行的松弛型 
2 如果目標(biāo)函數(shù)里還有正系數(shù)，就執(zhí)行主元操作 
3 按照基本解，求基本變量和目標(biāo)值，即位最優(yōu)解

單純形算法證明：

求證： 如果線性規(guī)劃有最優(yōu)解，那么單純形算法得到的解一定是最優(yōu)解；如果線性規(guī)劃沒(méi)有最優(yōu)解，那么單純形算法一定會(huì)返回?zé)o解 
已知： 
1 松弛變量>0 
2 第一步轉(zhuǎn)化好松弛型，其基本解可行 
證明： 
如果線性規(guī)劃沒(méi)有最優(yōu)解，那么單純形算法一定會(huì)返回?zé)o解 
證明： 因?yàn)榛窘饪尚校砸欢ㄓ薪?nbsp;
如果線性規(guī)劃有最優(yōu)解，那么單純形算法得到的解一定是最優(yōu)解 
證明： 
1 目標(biāo)函數(shù)都是等價(jià)變換的，不會(huì)影響其值 
2 最后目標(biāo)函數(shù)系數(shù)都是負(fù)的，而基本變量和松弛變量都是非負(fù)數(shù)


向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手