1、線性規(guī)劃的簡(jiǎn)單應(yīng)用與實(shí)現(xiàn)浙江省杭州二中李宇騫前言線性規(guī)劃帶來(lái)巨額財(cái)富方案在歷史上，沒(méi)有哪種數(shù)學(xué)方法，可以像線性規(guī)劃那樣，直接為人類創(chuàng)造如此巨額的財(cái)富，并對(duì)歷史的進(jìn)程發(fā)生如此直接的影響。孫捷，美國(guó)華盛頓大學(xué)博士曾執(zhí)教于北京清華大學(xué) 。實(shí)例為了要競(jìng)選市長(zhǎng)，你想以最小的開(kāi)支擁有5萬(wàn)的城市居民的投票、10萬(wàn)郊區(qū)居民的投票以及2.5萬(wàn)農(nóng)村居民的投票。城市郊區(qū)農(nóng)村建設(shè)道路253槍支管制825農(nóng)業(yè)津貼0010減免油稅1002實(shí)例讓x1+x2+x3+x4最小滿足： -2x1+8x2+0 x3+10 x4 = 50（城市居民投票不少于5萬(wàn)）5x1+2x2+0 x3+0 x4 = 100（郊區(qū)居民）3x1-5x2

2、+10 x3-2x4 = 25（農(nóng)村居民）x1, x2, x3, x4 = 0（開(kāi)支不能為負(fù)）建設(shè)道路的開(kāi)支槍支管制上的開(kāi)支定義線性規(guī)劃：在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個(gè)線性函數(shù)。x1+x2+x3+x4-2x1+8x2+0 x3+10 x4 = 50 x1 =0 x2=4x1+5=x2應(yīng)用資源優(yōu)化配置有一些資源和產(chǎn)品，在資源有限的情況下如何將其分配給這些產(chǎn)品使得獲利最大。最佳物資供給有一些需求要滿足，如何在保證滿足的前提下，提供最少價(jià)值的物資。多物網(wǎng)絡(luò)流有多個(gè)源點(diǎn)和匯點(diǎn)的網(wǎng)絡(luò)流多物網(wǎng)絡(luò)流源點(diǎn)1源點(diǎn)2匯點(diǎn)1匯點(diǎn)2算法單純形法(Simplex)橢球法（Ellipsoid)內(nèi)點(diǎn)法(I

3、nterior-point)多項(xiàng)式級(jí)別LindoMatlab單純形法標(biāo)準(zhǔn)形式(Standard form)最大化x1+x2+x3+x4目標(biāo)函數(shù)要求最大化滿足：x1+2x2+3x3 = 3x4 = 0所有的變量都有非負(fù)限制單純形法標(biāo)準(zhǔn)形式(Standard form)mnacb單純形法標(biāo)準(zhǔn)形式(Standard form)最大化共n+m個(gè)約束，除了n個(gè)變量的非負(fù)限制外，還滿足m個(gè)約束，第j個(gè)約束為單純形法形象的理解最優(yōu)值在某一頂點(diǎn)上用調(diào)整法，從一個(gè)頂點(diǎn)出發(fā)，直到到達(dá)一個(gè)最優(yōu)值。單純形法主程序初始化：首先找到一個(gè)頂點(diǎn)最優(yōu)化：不斷調(diào)整，直到最優(yōu)化單純形法頂點(diǎn)松弛形式一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)松弛形式單純形法n

4、維空間中的一個(gè)頂點(diǎn)n個(gè)數(shù)的坐標(biāo)n個(gè)n元一次方程組的解n個(gè)不等式取等號(hào)單純形法松弛形式（Slack form)將n+m個(gè)不等式和n+m個(gè)變量一一對(duì)應(yīng)x1=0 xn=0 x1=0 xn=0 xn+j=0第i個(gè)不等式取等號(hào)時(shí)就是xi=0單純形法松弛形式（Slack form）n維空間中的一個(gè)頂點(diǎn)n個(gè)不等式取等號(hào)n個(gè)變量取0N單純形法松弛形式（Slack form）NN點(diǎn)點(diǎn)松弛形式松弛形式單純形法轉(zhuǎn)軸操作（Pivot）n-1個(gè)等式確定一條邊調(diào)換N中的某一個(gè)元素沿著另外n-1個(gè)等式所確定的邊到達(dá)另一個(gè)點(diǎn)單純形法回顧主程序松弛形式轉(zhuǎn)軸操作單純形法時(shí)間復(fù)雜度最多有 個(gè)松弛形式貪心優(yōu)化對(duì)于所有有可能的邊，選一

5、條使v變得最大的邊走。實(shí)驗(yàn) 變量個(gè)數(shù)n限制個(gè)數(shù)m5010050我的程序 小于1秒MATLAB7.0 小于1秒LINDO 小于1秒我的程序 小于1秒MATLAB7.0 17秒LINDO 小于1秒100我的程序 小于1秒MATLAB7.0 17秒LINDO 小于1秒我的程序 小于1秒MATLAB7.0 30秒LINDO 小于1秒實(shí)驗(yàn) 變量個(gè)數(shù)n限制個(gè)數(shù)m200300200普通程序： 8秒，pivot操作5396次加貪心優(yōu)化的程序： 1秒，pivot操作336次LINDO： 1秒，迭代次數(shù)558普通程序： 11秒，pivot操作5310次加貪心優(yōu)化的程序： 1秒，pivot操作349次LINDO： 1秒，迭代次數(shù)578300普通程序： 28秒，pivot操作7864次加貪心優(yōu)化的程序： 2秒，pivot操作485次LINDO： 2秒，迭代次數(shù)819普通程序： 105秒，pivot操作18243次加貪心優(yōu)化的程序： 7秒，pivot操作947次LINDO： 7秒，迭代次數(shù)1369實(shí)驗(yàn) 變量個(gè)數(shù)n限制個(gè)數(shù)m400500400加貪心優(yōu)化的程序： 23秒，pivot操作1368次LINDO： 17秒，迭代次數(shù)2487加貪心優(yōu)化的程序： 22秒，pivot操作1078次LINDO： 11秒，迭代次數(shù)1770500加貪心優(yōu)化的程序： 36秒，pivot操作1521次LINDO： 24秒，迭代次數(shù)