第八章線(xiàn)性規(guī)劃初步

1、第八章第八章 線(xiàn)性規(guī)劃初步線(xiàn)性規(guī)劃初步線(xiàn)性規(guī)劃作為運(yùn)籌學(xué)的一個(gè)重要分支，它從上世紀(jì)40年代末期開(kāi)始發(fā)展，雖然只有短暫的幾十年時(shí)間，但在生產(chǎn)組織管理，交通運(yùn)輸，國(guó)防工業(yè)以及國(guó)民經(jīng)濟(jì)的許多領(lǐng)域內(nèi)，都有著廣泛而重要的應(yīng)用它常用于解決在現(xiàn)有的資源和利用方式下，在現(xiàn)有的人力，物力，財(cái)力的條件下，怎樣更有效地發(fā)揮其作用以達(dá)到最大的經(jīng)濟(jì)效益；或者是如何利用最少的人力，物力，財(cái)力去完成預(yù)定的任務(wù)一般說(shuō)來(lái)，它是研究有限資源的最優(yōu)配置，以實(shí)現(xiàn)給定的目的，取得最有經(jīng)濟(jì)效益的一門(mén)學(xué)科第八章第八章 線(xiàn)性規(guī)劃初步線(xiàn)性規(guī)劃初步8.1 線(xiàn)性規(guī)則問(wèn)題的數(shù)學(xué)模型8.2 線(xiàn)性規(guī)則的圖解法8.3 線(xiàn)性規(guī)則問(wèn)題的標(biāo)準(zhǔn)型8.4 單純形方

2、法8.1 線(xiàn)性規(guī)則問(wèn)題的數(shù)學(xué)模型8.1.1 實(shí)例8.1 線(xiàn)性規(guī)則問(wèn)題的數(shù)學(xué)模型8.1 線(xiàn)性規(guī)則問(wèn)題的數(shù)學(xué)模型8.1.2 線(xiàn)性規(guī)則的一般模型8.1 線(xiàn)性規(guī)則問(wèn)題的數(shù)學(xué)模型 建立一個(gè)實(shí)用的線(xiàn)性規(guī)劃模型必須明確以下四個(gè)組成部分的含義： 1決策變量：決策變量是模型中可控而未知的因素，經(jīng)常使用帶不同下標(biāo)的英文字母表示不同的變量 2目標(biāo)函數(shù)：線(xiàn)性規(guī)劃模型的目標(biāo)是求系統(tǒng)目標(biāo)的極值，可以是求極大值，如企業(yè)的利潤(rùn)和效率等，也可以是求極小值，如成本和費(fèi)用等 3約束條件：約束條件是指實(shí)現(xiàn)系統(tǒng)目標(biāo)的限制性因素，通常表現(xiàn)為生產(chǎn)力約束、原材料約束、能源約束、庫(kù)存約束等資源性約束，也可能表現(xiàn)為指標(biāo)約束和需求約束 4非負(fù)限制

3、：由于在實(shí)際生產(chǎn)問(wèn)題中，資源總是代表一些可以計(jì)量的實(shí)物或人力，因而一般不能為負(fù)數(shù)8.2 線(xiàn)性規(guī)則的圖解法 對(duì)于只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示其有關(guān)概念，并求解8.2 線(xiàn)性規(guī)則的圖解法8.2 線(xiàn)性規(guī)則的圖解法 圖解法只能適用于僅含有兩個(gè)變量的線(xiàn)性規(guī)劃問(wèn)題的求解，因而圖解法的實(shí)際用途并不廣泛但是，通過(guò)圖解法可以得到以下結(jié)論： 1線(xiàn)性規(guī)劃的可行域?yàn)橥辜醇现腥我鈨牲c(diǎn)連線(xiàn)上的一切點(diǎn)仍然在該集合中這樣的凸集平面幾何上表現(xiàn)為一個(gè)凸多邊形，在空間上必將是一個(gè)凸幾何體 2線(xiàn)性規(guī)劃的最優(yōu)解在凸集的某一個(gè)頂點(diǎn)上達(dá)到（存在凸集的某一條邊界上達(dá)到的可能性） 3線(xiàn)性規(guī)劃的可行域若有界

4、，則一定有最優(yōu)解 線(xiàn)性規(guī)劃的最優(yōu)解不可能在可行域的內(nèi)點(diǎn)取得，而只能在凸集的某一個(gè)頂點(diǎn)上達(dá)到（特殊情況為在凸集的某一條邊界上達(dá)到）由于可行域的頂點(diǎn)個(gè)數(shù)是有限的，所以在求解線(xiàn)性規(guī)劃模型的最優(yōu)解時(shí)，只要在可行域的有限個(gè)頂點(diǎn)范圍內(nèi)一一尋找.8.3 線(xiàn)性規(guī)則問(wèn)題的標(biāo)準(zhǔn)型8.3.1 線(xiàn)性規(guī)則問(wèn)題標(biāo)準(zhǔn)型8.3 線(xiàn)性規(guī)則問(wèn)題的標(biāo)準(zhǔn)型線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型的四個(gè)特點(diǎn)：線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型的四個(gè)特點(diǎn)：1目標(biāo)函數(shù)為最大化型；目標(biāo)函數(shù)為最大化型；2所有約束條件均為所有約束條件均為“=”型；型；3決策變量均為非負(fù)的；決策變量均為非負(fù)的；4各約束條件右端向量非負(fù)各約束條件右端向量非負(fù)8.3 線(xiàn)性規(guī)則問(wèn)題的標(biāo)準(zhǔn)型8.3.2 線(xiàn)性規(guī)則問(wèn)題標(biāo)準(zhǔn)型8.4 單純形方法8.4 單純形方法8.4 單純形方法8.4 單純形