【正文】 ??? ????，11021010A?????? ????????， ? ? ? ?? ? ? ?00 1 0 , 0 TX X A f X??? ? ? ? 由? ? ? ?0 , 0 TfX ???可知， x ? 確實(shí)為極小點(diǎn)。一般認(rèn)為：變尺度算法是求解無約束優(yōu)化問題時(shí)使用導(dǎo)數(shù)的算法中較為有效而且收斂也較快的一類算法，其中 BFGS算法是數(shù)值穩(wěn)定性較好的一種方法，因而是大家樂于采用的一種算法。 4 ． 檢驗(yàn)所得的下一個(gè)點(diǎn) )1( ?kx是否為)( xf的極小點(diǎn)，或滿足精度要求的近似極小點(diǎn)，檢驗(yàn)的辦法因算法而不同，例如，有些算法看 ??? ? )( )1( kxf 是否成立，若上式成立，迭代結(jié)束，取 )1(* ?? kxx ，否則令 1?? kk ，回到第二步，繼續(xù)進(jìn)行迭代。而一般情況下求解非線性方程組0)( ?? xf也是一件困難的工作，因此求解無約束優(yōu)化問題，一般不采用解析法，而是數(shù)值方法，或者說是迭代方法。 [ 例題 ] 試求二次函數(shù)? ? 221 2 1 1 2 2, 2 8 2 4 2 0f x x x x x x? ? ? ? ?的極小點(diǎn)。因此上述模型可簡記為 ? ?m i n fX . X ?? 當(dāng)一個(gè)非線性規(guī)劃問題的自變量 X 沒有任何約束，或說可行域即是整個(gè) n 維向量空間 ,即nR? ?，則稱這樣的非線性規(guī)劃問題為無約束問題： ? ?m i n fX或? ?m i nnXRfX? 有約束問題與無約束問題是非線性規(guī)劃的兩大類問題， 它們在處理方法上有明顯的不同。 算術(shù) —— 幾何平均不等式是指，對于任何正整數(shù) n ， n 個(gè)正實(shí)數(shù)naaa , 21 ?的幾何平均值nnaaa/121 )( ?一定不會大于它們的算術(shù)平均值)(1 21 naaan??? ?，即 ????????????? niinnii ana1111 并且等號當(dāng)且僅當(dāng)naaa ??? ?21時(shí)成立。若所有的ic均為正數(shù)，則稱)( xg為正項(xiàng)式（ P os yn om i al ），也稱為正定多項(xiàng)式或正定式。( * txy ??即為通過最小二乘法對 n 組數(shù)據(jù)niyt ii ,2,1),( ??的擬合曲線。 因此，問題的數(shù)學(xué)模型為： ? ? ? ?2211m i nmni j i j i jijz x p y q??? ? ??? . 1ni j ijza???,? ?1 , 2 , ,im? 1mi j jizb???,? ?1 , 2 , ,jn? 0ijz ?,? ?1 , 2 , , , 1 , 2 , ,i m j n?? [ 例題 ] 曲線擬合問題 在科學(xué)實(shí)驗(yàn)、工程設(shè)計(jì)和管理工作中，經(jīng)常會遇到下述問題：通過實(shí)驗(yàn)或?qū)崪y得到 n 組數(shù)據(jù)niyt ii ,2,1),( ??，它們可視為平面上的 n 個(gè)點(diǎn)，期望確定一組參數(shù)Tmxxxx ),( 21 ??，使曲線)。 [ 例題 ] 廠址選擇問題： 設(shè)有 n 個(gè)市場，第 j 個(gè)市場位置為 ? ?,jjpq，它對某種貨物的需要量為jb ? ?1 , 2 , ,jn?。A ? ? ? ? ?6 0 。 MATLAB是一種交互式的高級計(jì)算機(jī)軟件，有如下特點(diǎn)： ? 它以矩陣運(yùn)算為基本運(yùn)算，用命令式語句運(yùn)行，附有數(shù)值計(jì)算，最優(yōu)化，信號處理，系統(tǒng)識別，控制系統(tǒng)等幾十個(gè)工具箱（ Toolbox）； ? MATLAB使用十分方便，幾乎是直接把算式鍵入計(jì)算機(jī)，立刻得出計(jì)算結(jié)果，因此有“電子草稿紙”的美譽(yù)； ? 具有很強(qiáng)的圖形表現(xiàn)能力。 第五節(jié) 求解線性規(guī)劃的計(jì)算軟件 ? 一． 用 LINDO軟件解線性規(guī)劃 ? LINDO是“ Linear interactive and discrete optimizer”的縮寫，它是解決線性規(guī)劃，整數(shù)規(guī)劃等規(guī)劃問題的有力工具，在大型計(jì)算機(jī)上，它可用于解決 50000個(gè)約束條件，202200個(gè)變量的線性規(guī)劃問題。 3 求軸心項(xiàng) 在兩個(gè)非負(fù)檢驗(yàn)數(shù)中，取最左邊的01 2b ??，屬1x所在列，對應(yīng)1x的列向量為1p ?，1311p????? ???????，1p ?中 有三個(gè)正分量11 3b ?，121 ?b，31 1b ?，因?yàn)? 0 2 0 3 01 1 2 1 3 16 0 1 0 2 0m in , , m in , , 1 03 1 1b b bb b b?? ?????? ??????，所以 21b為軸心項(xiàng)，在表 1 中把 1 加上“ * ”號，即 1* 。如此循環(huán)，得最優(yōu)解。 1 ． 算出 T ( B ) ，確定 T ( B ) 中的軸心項(xiàng) 在所有0 0jb ?的檢驗(yàn)數(shù)中，選出最左邊的一個(gè)設(shè)為0 sb，其對應(yīng)的非基變量為sX，向量1ssp B p?? ?。 由（ ）式得： ? ?11B N N BZ C B N C X C B b??? ? ?， 即 ? ?110, BBZ C B A C X C B b??? ? ? 又由A X b?得，11B A X B b?? ?，把上面兩式寫成矩陣形式，得 ????????????????????????? ?????bBbBCXZAB0CABCI11B11B 令 ? ?00 01 02 010 11 12 11120 21 22 22110 1 2nnBBm m m m nb b b bb b b bC B b C B A CT B b b b bB b B Ab b b b???????????? ????????????????? 稱 T ( B ) 為對應(yīng)于基 B 的單純形表，? ?0 1 , 2 ,jb j n?稱為檢驗(yàn)數(shù)。 如果一個(gè)可行基 B 進(jìn)一步滿足1 0BNC B N C? ??，則對一切可行解，有1BZ C X C B b???。其經(jīng)濟(jì)意義為生產(chǎn) I產(chǎn)品 2 件， II 產(chǎn)品 3 件，可獲最大利潤 19 萬元。 本例中，當(dāng)1 0x ?時(shí)，應(yīng)當(dāng)考慮由約束條件所得的條件 324528 2 02 4 01 5 5 0xxxxx? ? ???????? ? ?? 中， 可知當(dāng)2 3x ?時(shí)，5 0x ?，而34,0xx ?，所以用2x去代替5x。 第四節(jié) 線性規(guī)劃模型的單純形法 ? 一．用換元迭代法解線性規(guī)劃問題 [ 例題 ] 求解線性規(guī)劃模型 12m ax 2 5Z x x?? s .t . 121212286 2 45 1 5,0xxxxxx?????????? ?? 解 ：對上述線性規(guī)劃模型進(jìn)行標(biāo)準(zhǔn)化，得： 12m ax 2 5Z x x?? s .t . 1 2 314251 2 3 4 5286 2 45 1 5, , , , 0x x xxxxxx x x x x? ? ??????????? ?? 約束方程的系數(shù)矩陣 ? ?????????????100500100600121,54321pppppA 3x，4x，5x 的系數(shù)構(gòu)成的列向量為： ???????????0013p，???????????0104p,???????????1005p可構(gòu)成一組基，記做? ?????????????100010001,543pppB，B 對應(yīng)的變量稱為基變量。由???????51052121xxxx 解出 B 點(diǎn)坐標(biāo)為??????415,45 ，則該問題的最優(yōu)解就是 ??????415,45 ，最優(yōu)值為465 。 0 5051015OCAB可行解域x2x1圖 例題 （ 1）的可行解域 第二步，求最優(yōu)解： 在幾何上，目標(biāo)函數(shù)21 34 xxZ ??代表平面上的一個(gè)平行直線族，族中一條直線對應(yīng)一個(gè) Z 值。 ? 定義 某個(gè)線性規(guī)劃模型的全體可行解組成的集合，稱為該線性規(guī)劃模型的可行解域。 ? [例題 ]（合理配料問題）根據(jù)對 77種食物所含的九種營養(yǎng)物：熱量 (糖與脂肪 )、蛋白質(zhì)、鈣、鐵、維生素 A、維生素 BI、維生素 B草酸與維生素 C的成份及食物的市場價(jià)格調(diào)查，按照醫(yī)生所提出的對每個(gè)人每天所需的營養(yǎng)要求，可得表 ? 問怎樣采購食物才能在保證營養(yǎng)要求的前提下花費(fèi)最??？這就是營養(yǎng)問題或飲食問題，配料問題就是由此而推廣來的。 第一節(jié) 線性規(guī)劃模型的建立 ? 例題 (生產(chǎn)計(jì)劃問題 ) 某廠計(jì)劃內(nèi)將安排生產(chǎn)I,II兩種產(chǎn)品，已知生產(chǎn)單位重量的產(chǎn)品所需的設(shè)備為 A及 B、 C兩種原料的消耗如表 1所示： 生產(chǎn)單位重量的產(chǎn)品 I可獲利 2萬，生產(chǎn)單位重量的產(chǎn)品 II可獲利 5萬。 因此 ， 運(yùn)籌學(xué)既是應(yīng)用數(shù)學(xué) ， 也是管理科學(xué) ， 同時(shí)也是系統(tǒng)工程的基礎(chǔ)之一 。 其研究方法是應(yīng)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng) ， 建立相應(yīng)的數(shù)學(xué)模型 ，并對模型進(jìn)行研究和分析 ， 據(jù)此求得模型的最優(yōu)解；其目的是制定合理運(yùn)用人力 、 物力和財(cái)力的最優(yōu)方案；為決策者提供科學(xué)決策的依據(jù)；其研究對象是各種社會系統(tǒng) ， 可以是對新的系統(tǒng)進(jìn)行優(yōu)化設(shè)計(jì) ， 也可以是研究已有系統(tǒng)的最佳運(yùn)營問題 。 運(yùn)籌學(xué)實(shí)質(zhì)與解決方法 運(yùn)籌學(xué)的主要分支 ? 各個(gè)分支充實(shí)完善形成體系 –確定性模型 ? 數(shù)學(xué)規(guī)劃 – 線性規(guī)劃 – 整數(shù)規(guī)劃 – 非線性規(guī)劃 – 動(dòng)態(tài)規(guī)劃 – 幾何規(guī)劃 – 參數(shù)規(guī)劃 – 多目標(biāo)規(guī)劃 – 組合優(yōu)化 – 圖論與網(wǎng)絡(luò)分析 – 優(yōu)選與統(tǒng)籌方法 ? 隨機(jī)性模型 – 對策論 – 排隊(duì)論（隨機(jī)服務(wù)系統(tǒng)） – 可靠性理論 – 庫存論 – 搜索論 – 計(jì)算機(jī)隨機(jī)模擬 – 決策論 第四章 線性規(guī)劃模型 ? 線性規(guī)劃模型的建立 ? 線性規(guī)劃模型的標(biāo)準(zhǔn)形 ? 線性規(guī)劃模型的圖解法 ? 線性規(guī)劃模型的單純形法 ? 求解線性規(guī)劃的計(jì)算軟件 建立線性規(guī)劃模型有三個(gè)基本步驟： ? 第一步，找出問題中的所有相關(guān)的未知變量（決策變量），并用代數(shù)符號表示它們，根據(jù)變量的物理性質(zhì)研究變量是否有非負(fù)性； ? 第二步，找出問題中的目標(biāo)，寫成變量的線性函數(shù)，作為線性規(guī)劃模型的目標(biāo)函數(shù)； ? 第三步，找出問題中所有的限制或約束，寫成變量的線性方程或線性不等式，作為線性規(guī)劃模型的約束條件。 表 毛坯切割方案表 設(shè)用第 i 種方法下料的總根數(shù)為ix，則用掉的總根數(shù)為1 2 9x x x? ? ? 廢料總長度為： 1 2 3 5 6 7 8 90 . 3 1 . 1 0 . 9 0 . 8 1 . 5 0 . 6 1 . 4 0 . 5x x x x x x x x? ? ? ? ? ? ? 約束條件為所需的零件毛坯數(shù)量： 1 2 3 4 52 2 20 0x x x x x? ? ? ? ? 1 3 4 6 7 82 3 2 10 0x x x x x x? ? ? ? ? ? 2 4 5 7 8 92 3 2 3 5 300x x x x x x? ? ? ? ? ? 由此可得該問題的線性規(guī)劃模型如下： 1 2 3 5 6 7 8 9m in 0. 3 1. 1 0. 9 0. 8 1. 5 0. 6 1. 4 0. 5Z x x x x x x x x? ? ? ? ? ? ? ? 1 2