計(jì)算機(jī)算法設(shè)計(jì)與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-wenkub
2022-10-31 14:35:09 本頁(yè)面
【正文】 ??xxxxxxxxxxxxxxxxx2021年 11月 12日 21 單純形算法 ?第 1步： 選 取 入基變量 。具體做法是，引入 松弛變量 ，將不等式轉(zhuǎn)化為等式，且引入的松弛變量具有非負(fù)性 。 ?這一類(lèi)特殊的標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題稱(chēng)為 約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題 。 nn2021年 11月 12日 12 約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題 ?標(biāo)準(zhǔn)型線性規(guī)劃： . )(,2,10)(,2,11njxmibxajnjijij????????)(m a x1??njjj xc2021年 11月 12日 13 約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題 ?在標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題中，如果每一個(gè)等式約束中，至少有一個(gè)變量的系數(shù)為正，且這個(gè)變量只在該約束中出現(xiàn)。 2021年 11月 12日 11 單純形及單純形算法 ?如果有 個(gè)變量，每個(gè)約束定義了 維空間中的一個(gè)半空間，這些半空間的交集形成的可行區(qū)域稱(chēng)作單純形。 ? 在最優(yōu)解處目標(biāo)函數(shù)的值稱(chēng)為 最優(yōu)值 。 2021年 11月 12日 5 線性規(guī)劃問(wèn)題及表示 ?問(wèn)題表示 設(shè) 、 、 、 分別表示支出在修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及汽油稅廣告上的千美元數(shù) 目標(biāo)：最小化表達(dá)式 滿(mǎn)足約束： 1x 2x 3x 4x4321 xxxx ???5010082 4321 ????? xxxx1000025 4321 ???? xxxx2521053 4321 ???? xxxx0, 4321 ?xxxx2021年 11月 12日 6 線性規(guī)劃問(wèn)題及表示 ?一般線性規(guī)劃問(wèn)題表示 . )(,2,10)(,1)(,1)(,2,1321211211111njxmmmmmkbxammmtbxamibxajnjkjkjnjtjtjnjijij???????????????????????? )(mi nma x1??njjj xc2021年 11月 12日 7 ? 滿(mǎn)足約束條件 ()()式的一組變量值稱(chēng)為線性規(guī)劃問(wèn)題的一個(gè) 可行解 。一個(gè)政治家希望在每一個(gè)選區(qū)都贏得大多數(shù)的選票。主要政策有修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及增加公共運(yùn)輸?shù)钠投悺? ? 使約束條件 ()()式中的某 n個(gè)約束以等號(hào)滿(mǎn)足的可行解稱(chēng)為線性規(guī)劃問(wèn)題的 基本可行解 。 ? 有些情況下 可能不存在最優(yōu)解 。 ?單純形算法以一個(gè)線性規(guī)劃作為輸入，輸出它的一個(gè)最優(yōu)解。 ?在每一約束方程中選擇一個(gè)這樣的變量，并以它作為變量求解該約束方程。 2021年 11月 12日 14 約束標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題 ?例如： ?此例中， n=6， m=3；基本變量為 ， 和 ；非基本變量為 ， 和 。 ?在求解過(guò)程中，應(yīng)當(dāng)將松弛變量與原來(lái)變量同樣對(duì)待。 ?選出使目標(biāo)函數(shù)增加的非基本變量作為 入基變量 。 ? 在單純形表中考察由第 1步選出的入基變量所相應(yīng)的列。 ? 受限的增加量可以用入基變量所在列的元素（稱(chēng)為 主元素 ）來(lái)除主元素所在行的 “ 常數(shù)列 ” 元素而得到。 2021年 11月 12日 23 單純形算法 ?第 3步：轉(zhuǎn)軸變換（主元操作） ?將入基變量與離基變量互調(diào)位臵。 ? 整個(gè)問(wèn)題的解可以從最后一張單純形表的常數(shù)列中讀出 。 單純形算法 2021年 11月 12日 27 ? ?? ?? ?????????????????????????elieilejieijijeieiileelleljejleleeaaaaaaadoeNje a c hf o rbabbdolBie a c hf o rn t sc o n s t r a ir e m a i n i n gt h eoft n t sc o e f f i ci e nt h eC o m p u t eaaaaadoeNje a c hf o rabbxa r i a b l evb a s i e wf o re q u a t i o nt h eoft n t sc o e f f i ci e nt h eC o m p u t eelvcbABNP I V O T1110987.615432.1),(??? ?? ? ? ?? ? ? ?),(201918.1716151413.12????????????????????????????vcbABNr et u r nelBBleNNa r i a b l esvn o n b a s i candb a s i cofs et sn ewC o m p u t eaccacccdoeNjea c hf o rbcvvf u n ct i o no b j ect i v et h eC o m p u t eelelejejjee?? 單純形算法的主元操作 2021年 11月 12日 28 單純形算法描述 ?????????????iieiiieeje l s eabt h e naifdoBii n d e xe a c hf o rcw h i c hf o rNei n d e xanc h o o s edoch a sNji n d e xs o m ew h i l ecbAS I M P L E XI N I T I A L I Z EvcbABNcbAS I M P L E X760540302),(),(1),(),(160151413112),(),(11109821 niiilixxxr e t u r nxe l s ebxt h e nBiifdontoif o relvcbABNP I V O TvcbABNe l s eu n b o u n d e dr e t u r nt h e nifi n i m i z e smt h a
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1