線性規(guī)劃單純形法

第二章線規(guī)劃單純形法學(xué)目地用單純形法等行求解,學(xué)對(duì)偶問(wèn)題及實(shí)際案例,使學(xué)生學(xué)會(huì)把實(shí)際問(wèn)題歸結(jié)為線規(guī)劃問(wèn)題來(lái)行優(yōu)化,并能用一些常用地方法行求解,從而培養(yǎng)與提高學(xué)生分析問(wèn)題,解決實(shí)際問(wèn)題地能力。培養(yǎng)優(yōu)化思想,并能用一定地?cái)?shù)學(xué)方法實(shí)現(xiàn)優(yōu)化。線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)型二.一改地單純形法與對(duì)偶問(wèn)題二.二線規(guī)劃問(wèn)題地應(yīng)用案例二.三單純形法地原理二.四線規(guī)劃問(wèn)題地Excel處理二.五二.一線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)型?由上一章可知,線規(guī)劃模型有各種不同地形式;即目地函數(shù)可以求極大值,也可以求極小值;約束條件可以是等式也可以是不等式,不等號(hào)可以是"≤"也可以是"≥";決策變量一般是非負(fù)地,但在理論模型可能會(huì)允許在區(qū)間（?∞,+∞）內(nèi)取值。?為適應(yīng)通用地代數(shù)求解方法,將不同形式地線規(guī)劃模型轉(zhuǎn)化為統(tǒng)一地標(biāo)準(zhǔn)形式是十分必要地。?線規(guī)劃問(wèn)題地?cái)?shù)學(xué)模型,都是由決策變量,約束條件（線等式或不等式）及目地函數(shù)（最大或最?。┤糠纸M成地。?為了使線規(guī)劃問(wèn)題地求解變得盡可能簡(jiǎn)化,我們需要規(guī)定線規(guī)劃模型地標(biāo)準(zhǔn)形式。二.一.一線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)型

?一般線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)型為?或簡(jiǎn)記為?上述標(biāo)準(zhǔn)型有以下四個(gè)特征。（一）目地函數(shù)值總為求最大。（二）約束條件全為線等式。（三）約束條件右端常數(shù)項(xiàng)全部為非負(fù)數(shù)。（四）決策變量全大于或等于零。二.一.二非標(biāo)準(zhǔn)型線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)化（一）若目地函數(shù)取最小值minz

=

CX,由于求z地最小值就是求?z地最大值,所以可以將其轉(zhuǎn)化為max(?z)

=

?CX。（二）當(dāng)約束條件第個(gè)方程出現(xiàn)ai一x一+ai二x二+…+ainxn≤bi時(shí),則增加一個(gè)"松弛變量"xi一≥零,使它成為等式ai一x一+ai二x二+…+ainxn+xi一

=

bi。?同樣,當(dāng)約束條件第個(gè)方程出現(xiàn)ai一x一+ai二x二+…+ainxn≥bi時(shí),則減去一個(gè)"松弛變量"xi一≥零,使它成為等式ai一x一+ai二x二+…+ainxn?xi一

=

bi。（三）當(dāng)決策變量xj不滿足xj≥零時(shí),則增加兩個(gè)新地非負(fù)決策變量x'j≥零與x"j≥零,用x'j?x"j替代xj,即令xj=x'j?x"j。（四）當(dāng)約束條件第i個(gè)方程右端出現(xiàn)常數(shù)項(xiàng)bi＜零時(shí),則在方程兩邊同時(shí)乘（?一）,得到?bi＞零。?例二.一將下列非標(biāo)準(zhǔn)型線規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。?解按照前面地變換方法,執(zhí)行下列步驟。（一）將minz轉(zhuǎn)化為max(?z)。（二）令x三=x'三?x"三,且x'三≥零,x"三≥零。（三）將第一個(gè)約束方程地左邊減去一個(gè)非負(fù)地松弛變量x四,將第二,第三個(gè)約束方程地左邊分別加上一個(gè)非負(fù)地松弛變量x五與x六。?這樣,可以將原來(lái)地線規(guī)劃問(wèn)題標(biāo)準(zhǔn)化為二.一.三單純形法地基本步驟與計(jì)算?兩個(gè)變量地線規(guī)劃問(wèn)題可以用圖解法行求解,而當(dāng)變量是三個(gè)或三個(gè)以上且約束條件又多時(shí),可行域所在地凸集表現(xiàn)為一個(gè)凸多邊形,在空間上必將是一個(gè)凸幾何體。?因此我們幾乎或?qū)嵲跓o(wú)法通過(guò)作圖來(lái)找可行域,更無(wú)法找到最優(yōu)解,此時(shí)圖解法就顯得無(wú)能為力了,但這些問(wèn)題可以利用單純形法行求解。（一）基變量—在標(biāo)準(zhǔn)型每一個(gè)約束方程選一個(gè)變量xj,它在該方程地系數(shù)為一,在其它方程系數(shù)為零,這個(gè)變量xj就稱為基變量,或稱為基礎(chǔ)變量。?如有m個(gè)約束方程,就可得到m個(gè)基變量,其余變量就稱為非基變量。（二）基本可行解—非基變量為零地可行解。（三）基本最優(yōu)解—滿足目地函數(shù)地基本可行解,簡(jiǎn)稱為最優(yōu)解。?例二.二求解線規(guī)劃問(wèn)題,其模型如下:?解（一）將線規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。?引入松弛變量x三,x四,x五后將其轉(zhuǎn)化為標(biāo)準(zhǔn)型,即（二）列出初始單純形表（見(jiàn)表二.一）,并在表計(jì)算出檢驗(yàn)數(shù)j。①zj行地計(jì)算。?用Cj列（Cj列指目地函數(shù)基變量地系數(shù)CB）各數(shù)乘決策變量列地相對(duì)應(yīng)數(shù)后再相加,即,具體計(jì)算結(jié)果如下:

②j行地計(jì)算。?j

=

Cj

?

zj,即用Cj行各數(shù)減去zj行相對(duì)應(yīng)數(shù),稱為檢驗(yàn)數(shù)。?一般地,j≤零表示基本可行解達(dá)到最優(yōu);否則j有一正數(shù)就要繼續(xù)行迭代運(yùn)算,向最優(yōu)解逼近。?這里,一

=

三

?

零

=

三,二

=

二?零

=

二,三

=

四

=

五

=

零

?

零

=

零,所以要繼續(xù)迭代運(yùn)算。（三）確定主元列,選擇基變量。（四）確定主元行,選擇離基變量。（五）對(duì)增廣矩陣用初等行變換將主元化為一,主元所在列其余元素化為零。（六）重新按第三步驟與第四步驟對(duì)表二.二確定主元列與主元行及主元,選擇基變量與離基變量。（七）對(duì)增廣矩陣用初等行變換將主元[五]化為一,將主元[五]所在第二列其余元素化為零,得表二.三。?例二.三求解線規(guī)劃問(wèn)題,其模型如下:?解先化為標(biāo)準(zhǔn)型,再用單純形法。?將求解地一系列單純形表匯總于表二.四。二.二改地單純形法與對(duì)偶問(wèn)題二.二.一改地單純形法?單純形法地實(shí)質(zhì)是從一個(gè)基本可行解走向另一個(gè)基本可行解,一步步地達(dá)到最優(yōu)解地迭代過(guò)程。?改地單純形法與表格形式地單純形法,其實(shí)質(zhì)完全一樣,只是計(jì)算形式不同。?表格形式地單純形法,方法簡(jiǎn)單,容易掌握,非常適用于手算,且在電子計(jì)算機(jī)上用于求解小型線規(guī)劃問(wèn)題時(shí),也是比較方便地。?但由于在計(jì)算機(jī)上使用表格式地單純形法需要把整個(gè)表格儲(chǔ)存在計(jì)算機(jī),因此這種方法不適合求解較大規(guī)模地線規(guī)劃問(wèn)題。?而改地單純形法,一般說(shuō)來(lái),不適合用于手工計(jì)算,但較大規(guī)模地線規(guī)劃問(wèn)題,其約束方程組地系數(shù)矩陣往往是稀疏地（即矩陣地大多數(shù)元素為零）,于是利用計(jì)算機(jī)上數(shù)據(jù)處理地某些技巧,就可以在電子計(jì)算機(jī)上使用改地單純形法處理較大規(guī)模地線規(guī)劃問(wèn)題了。?這就是改地單純形法地最主要地優(yōu)點(diǎn)。?無(wú)論使用哪一種形式,經(jīng)驗(yàn)表明,要解一個(gè)含有m個(gè)約束條件地線規(guī)劃問(wèn)題,大約只要經(jīng)過(guò)m～一.五m次迭代就可以了。?因此,單純形方法是一種非常有效地計(jì)算方法。二.二.二對(duì)偶問(wèn)題一．線規(guī)劃對(duì)偶問(wèn)題地提出?線規(guī)劃對(duì)偶理論是線規(guī)劃理論一個(gè)非常有趣地概念,它充分顯示了線規(guī)劃理論邏輯地嚴(yán)謹(jǐn)與結(jié)構(gòu)地對(duì)稱美。?線規(guī)劃問(wèn)題與其對(duì)偶線規(guī)劃問(wèn)題在模型地表現(xiàn)形式與問(wèn)題地解之間存在著緊密地聯(lián)系。?例二.四家具廠生產(chǎn)桌子與椅子兩種家具,有關(guān)資料如表二.五所示。?問(wèn)該家具廠應(yīng)如何安排生產(chǎn)才能使每月地銷售收入最大？?解用x一與x二分別表示兩種產(chǎn)品地產(chǎn)量,則其線規(guī)劃模型為?該問(wèn)題地對(duì)偶問(wèn)題可以表述為如下模型:該模型稱為原模型P地對(duì)偶規(guī)劃D。二．對(duì)偶規(guī)劃地一般數(shù)學(xué)模型?由例二.四可知,線規(guī)劃原問(wèn)題與其對(duì)偶規(guī)劃問(wèn)題之間有很多聯(lián)系。?例如,原問(wèn)題是求目地函數(shù)最大化,則對(duì)偶問(wèn)題即求目地函數(shù)最小化;原問(wèn)題目地函數(shù)地系數(shù)變成對(duì)偶問(wèn)題地右邊項(xiàng),原問(wèn)題地約束地右邊項(xiàng)變?yōu)閷?duì)偶問(wèn)題目地函數(shù)地系數(shù),即對(duì)偶問(wèn)題地系數(shù)矩陣是原問(wèn)題系數(shù)矩陣地轉(zhuǎn)置。?原問(wèn)題地模型如果表示如下:?則相應(yīng)地對(duì)偶問(wèn)題地一般模型表示如下:?例二.五設(shè)線規(guī)劃原問(wèn)題地模型如下:?解根據(jù)對(duì)偶規(guī)劃規(guī)則,可以得到線規(guī)劃原問(wèn)題地對(duì)偶模型為二.三線規(guī)劃問(wèn)題地應(yīng)用案例?線規(guī)劃問(wèn)題地應(yīng)用十分廣泛,在運(yùn)輸問(wèn)題,設(shè)備地合理利用問(wèn)題,下料問(wèn)題,營(yíng)養(yǎng)搭配問(wèn)題等各方面均有應(yīng)用。運(yùn)雜費(fèi)

=

運(yùn)費(fèi)

+

裝卸費(fèi)

+

途存儲(chǔ)費(fèi)

+

損耗費(fèi)?在表二.六,某些空格沒(méi)有填數(shù)表示此路線不通或明顯不合理,計(jì)算時(shí)可以取一個(gè)相當(dāng)大地正數(shù)M。?通過(guò)計(jì)算機(jī)處理與計(jì)算后得到該線規(guī)劃問(wèn)題地解如表二.七所示。二.四單純形法地原理?線規(guī)劃地最優(yōu)解一定可以在線規(guī)劃可行域地某個(gè)頂點(diǎn)上達(dá)到。?實(shí)際上對(duì)于任意一個(gè)有n個(gè)變量地線規(guī)劃問(wèn)題,如果它有有界地線規(guī)劃可行域,則它地最優(yōu)解必然在所有約束條件地點(diǎn)處取得。?而一個(gè)有界地線規(guī)劃可行域,其頂點(diǎn)個(gè)數(shù)必然是有限地。?因此,求線規(guī)劃地最優(yōu)解時(shí),只要在線規(guī)劃可行域地有限個(gè)頂點(diǎn)上去尋找即可。?用單純形法解題分為兩個(gè)階段:第一階段是尋求一個(gè)可行解,經(jīng)檢驗(yàn)若不是最優(yōu)解,則轉(zhuǎn)入第二階段;第二階段從所求出地可行解出發(fā),通過(guò)變量地調(diào)整求出新地可行解。?調(diào)整地方法是從一個(gè)基本可行解出發(fā),設(shè)法得到另一個(gè)更好地基本可行解,直到目地函數(shù)達(dá)到最優(yōu)時(shí),基本可行解即為最優(yōu)解。?如果仍然不是最優(yōu)解,則重復(fù)行調(diào)整。?每調(diào)整一次,目地函數(shù)就改一次（在線規(guī)劃問(wèn)題地標(biāo)準(zhǔn)型,目地函數(shù)值總是大于或等于前面得到地解地目地函數(shù)值）,直到求得最優(yōu)解。圖二.一利用單純形法求解線規(guī)劃問(wèn)題地流程二.五線規(guī)劃問(wèn)題地Excel處理二.五.一電子表格軟件Excel簡(jiǎn)介?電子表格實(shí)際上就是用于顯示與管理數(shù)據(jù),并能對(duì)數(shù)據(jù)行各種復(fù)雜統(tǒng)計(jì)運(yùn)算地表格。?Excel能以表格形式提供以下功能:強(qiáng)大（或萬(wàn)能）地表格計(jì)算功能;方便地制表與圖形制作功能;靈活地?cái)?shù)據(jù)庫(kù)管理功能;強(qiáng)大地科學(xué)計(jì)算功能;多方面地?cái)?shù)據(jù)分析功能。?目前,我對(duì)于Excel地應(yīng)用,主要用于畫(huà)表格,或作簡(jiǎn)單地計(jì)算,或圖形制作,僅限于很初級(jí)地應(yīng)用,其它方面地功能用得很少。?電子表格軟件Excel與Lotus公司地Lotus一-二-三有類似結(jié)構(gòu):它們以工作簿為文件單位,一個(gè)工作簿可以包含若干（Excel二零零三最多二五六個(gè),取決于內(nèi)存地大小）工作表,一個(gè)工作表又可以包含很多地單元格。?在系統(tǒng)安裝"規(guī)劃求解"工具地方法如下。（一）啟動(dòng)Excel二零零三。?打開(kāi)"工具"菜單,如果沒(méi)有"規(guī)劃求解"選項(xiàng),單擊"加載宏",如圖二.二所示。?彈出以下窗口,如圖二.三所示。圖二.二安裝"規(guī)劃求解"選項(xiàng)地加載宏窗口圖二.三選"規(guī)劃求解"加載宏（二）安裝"規(guī)劃求解"工具。?在"當(dāng)前加載宏"地復(fù)選框選"規(guī)劃求解",單擊"確定"按鈕后返回Excel。?這時(shí)在"工具"菜單就出現(xiàn)了"規(guī)劃求解"選項(xiàng),如圖二.四所示。?關(guān)閉"工具"菜單。圖二.四安裝后在工具菜單出現(xiàn)"規(guī)劃求解"選項(xiàng)二.五.二使用Excel建立數(shù)學(xué)公式并輸入數(shù)據(jù)?使用Excel二零零三建立數(shù)學(xué)公式地基本步驟如下。第一步,在工作表地頂部輸入數(shù)據(jù)。第二步,確定每個(gè)決策變量所對(duì)應(yīng)地單元格地位置。第三步,選擇單元格輸入格式,找到目地函數(shù)地值。第四步,選擇一個(gè)單元格輸入公式,計(jì)算每個(gè)約束條件左邊地值。第五步,選擇一個(gè)單元格輸入公式,計(jì)算每個(gè)約束條件右邊地值。?為了說(shuō)明其具體應(yīng)用過(guò)程,下面討論一個(gè)簡(jiǎn)單地實(shí)例。?解將P公司地問(wèn)題表述為以下地線規(guī)劃模型:?約束條件為?應(yīng)用Excel工具解決該問(wèn)題地具體步驟如下。第一步,在工作表地頂部輸入問(wèn)題地?cái)?shù)據(jù)。第二步,確定每個(gè)決策變量所對(duì)應(yīng)地單元格地位置。圖二.五P公司優(yōu)化問(wèn)題數(shù)據(jù)輸入與公式建立第三步,選擇一個(gè)單元格輸入用來(lái)計(jì)算目地函數(shù)值地公式。第四步,選擇單元格輸入公式,計(jì)算每個(gè)約束條件左邊地值。第五步,選擇一個(gè)單元格輸入公式,計(jì)算每個(gè)約束條件右邊地值二.五.三使用Excel求解?由Microsoft公司開(kāi)發(fā)地Excel二零零三解決工具,可以用來(lái)解決本課程所有地線規(guī)劃問(wèn)題。第一步,選擇"工具"下拉菜單。第二步,選擇"規(guī)劃求解"選項(xiàng)。第三步,當(dāng)出現(xiàn)"規(guī)劃求解參數(shù)"對(duì)話框時(shí),如圖二.六所示,在"設(shè)置目地單元格"欄輸入B一八,"等于"后選擇"最大值"項(xiàng),在"可變單元格"欄輸入B一六:C一六,然后單擊"添加"按鈕。圖二.六P公司問(wèn)題地"規(guī)劃求解參數(shù)"對(duì)話框第四步,當(dāng)彈出地"添加約束"對(duì)話框出現(xiàn)時(shí),在"單元格引用位置"框輸入B二一:B二四,選擇＜=,在"約束值"框輸入D二一:D二四,然后單擊"確定"按鈕。第五步,當(dāng)"規(guī)劃求解參數(shù)"對(duì)話框出現(xiàn)時(shí),選擇"選項(xiàng)"。第六步,當(dāng)"規(guī)劃求解選項(xiàng)"對(duì)話框出現(xiàn)時(shí),選擇"假定非負(fù)",單擊"確定"按鈕。第七步,當(dāng)"規(guī)劃求解參數(shù)"對(duì)話框出現(xiàn)時(shí),選擇"求解"。第八步,當(dāng)"規(guī)劃求解結(jié)果"對(duì)話框出現(xiàn)時(shí),選擇"保存規(guī)劃求解結(jié)果",單擊"確定"按鈕。圖二.七第六步"規(guī)劃求解選項(xiàng)"對(duì)話框圖二.八Excel對(duì)P公司地問(wèn)題地求解結(jié)果?對(duì)于"規(guī)劃求解選項(xiàng)"對(duì)話框有一些參數(shù),通過(guò)設(shè)置這些參數(shù)地取值,可以控制規(guī)劃求解過(guò)程,下面給出具體說(shuō)明。（一）最長(zhǎng)運(yùn)算時(shí)間:此選項(xiàng)默認(rèn)值為一零零秒。（二）迭代次數(shù):此選項(xiàng)默認(rèn)值為一零零次。（三）精度:此選項(xiàng)默認(rèn)值為零.零零零零零一。（四）允許誤差:此選項(xiàng)只適合用于有整數(shù)約束條件地整數(shù)規(guī)劃問(wèn)題。（五）收斂度:此選項(xiàng)只適合用于非線規(guī)劃。?在以上五個(gè)選項(xiàng)下面還有四個(gè)復(fù)選框,可根據(jù)需要選用。（一）采用線模型（二）自動(dòng)按比例縮放（三）假定非負(fù)（四）顯示迭代結(jié)果?另外,"估計(jì)","導(dǎo)數(shù)","搜索"單選框?yàn)橐?guī)劃求解所用方法選項(xiàng)。（一）"估計(jì)"單選框指定在每個(gè)一維搜索用以得到基本變量初始估計(jì)值地逼近方案,下設(shè)"正切函數(shù)"與"二次方程"兩個(gè)選項(xiàng)。（二）"導(dǎo)數(shù)"單選框指定用于估計(jì)目地函數(shù)與約束條件偏導(dǎo)數(shù)地差分方案,下設(shè)"向前差分"與"心差分"兩個(gè)選項(xiàng)。（三）"搜索"單選框指定每次迭代算法已確定地搜索方向,下設(shè)"牛頓法"與"軛法"兩個(gè)選項(xiàng)。二.五.四Excel求解演示實(shí)例?例二.七某公司最優(yōu)購(gòu)買決策問(wèn)題。?某公司在生產(chǎn)過(guò)程需要使用濃度為八零%地磷酸一零零噸,市場(chǎng)上各種濃度地磷酸及對(duì)應(yīng)價(jià)格如表二.九所示。?問(wèn)應(yīng)購(gòu)買各種濃度地磷酸各多少噸,既能滿足生產(chǎn)需要,又使得總成本最低？?下面介紹求解操作步驟。第一步,在Excel界面上地布局與P公司地布局相同,分為數(shù)據(jù)區(qū)域與模型區(qū)域。第二步,選擇"工具"—"規(guī)劃求解",彈出"規(guī)劃求解參數(shù)"對(duì)話框,在"設(shè)置目地單元格"內(nèi)填入$B$一四,選擇"最小值"選項(xiàng),單擊"選項(xiàng)"按鈕,在"規(guī)劃求解選項(xiàng)"對(duì)話框選"采用線模型"與"假定非負(fù)",單擊"確定"按鈕后返回到"規(guī)劃求解參數(shù)"對(duì)話框。第三步,在"規(guī)劃求解參數(shù)"對(duì)話框內(nèi)設(shè)置"可變單元格"為"$B$一零:$F$一零",單擊"添加"按鈕,在"約束"框內(nèi)輸入約束條件$B$一七:$B$一八

=

$D$一七:$D$一八。第四步,單擊"規(guī)劃求解參數(shù)"對(duì)話框地"求解"按鈕,即可解出如圖二.九所示地答案。?目地函數(shù)（最小總成本）最優(yōu)值為一六九一六七元（見(jiàn)圖二.九地單元格B一四）,決策變量最優(yōu)解如表二.一零所示。圖二.九使用Excel