【正文】 3 4 51 3 4 6 7 82 4 5 7 8 91 2 92 2 2 0 02 3 2 1 0 02 3 2 3 5 3 0 0, , , 0x x x x xx x x x x xx x x x x xx x x? ? ? ? ???? ? ? ? ? ???? ? ? ? ? ????? 由于用掉的總料長度為 2 0 0 3 . 1 1 0 0 2 . 5 3 0 0 1 . 7 1 3 8 0? ? ? ? ? ?， 則有廢料長度＝ 9 ? 用料根數(shù)－ 1380 。把最優(yōu)解代入目標(biāo)函數(shù)所得到的目標(biāo)函數(shù)的最大值或最小值稱為最優(yōu)值。其形狀為一個凸多邊形區(qū)域，可行解是凸多邊形內(nèi)的一個點，如圖 。 0 50510154x1+3x2=74x1+3x2=54x1+3x2=34x1+3x2=1可行解域x2X1圖 例題 （ 1）的最優(yōu)解 由觀察可知，等值線離原點越遠， Z 值越大，而通過 B 點的等值線就是使目標(biāo)函數(shù)值達到最大的等值線，這條等值 線和凸多邊形只相交 于 B 點，因此 B 點為最優(yōu)解。若兩個頂點都 是最優(yōu)解，則這兩個頂點連線上的任一點都是最優(yōu)解，若可行解區(qū)域無界， 則可能不存在最優(yōu)解。 一般情況下，在換基時應(yīng)選擇正系數(shù)最大的那個非基變量（本例中的2x）為換入變量（或稱進基變量），而從基變量3x，4x，5x中換出一個能保證其余變量都非負，即345, , 0x x x ?的變量，即若選中5x，即表明5x在三個變量中隨著2x的減小是最先達到 0 的。 繼續(xù)換基的過程，選擇1x為換入變量，從上面的約束條件中得出當(dāng)5 0x ?時，1 2x ?可使3 0x ?，即用3x去代1x，得 1 3 24 3 22522522 4 6 25135x x xx x xxx?? ? ???? ??? ? ? ?? ?????????? 3 5 5 3 521m a x 1 5 2 2 1 9 255Z x x x x x??? ? ? ? ? ? ? ????? 令非基變量35 0xx ??，得m a x 1 9Z ?，即得可行解為 ? ? ? ?22 , 3 , 0 , 1 2 , 0Tx ? 此時目標(biāo)函數(shù)為351m a x 1 9 25Z x x? ? ?，其中非基變量的系數(shù)均非正，變化后不可能再增大 Z 的值，因此? ? ? ?22 , 3 , 0 , 1 2 , 0Tx ?就是最優(yōu)解，m a x 1 9Z ?。 如果1 0Bb ? ?，即0BX ?，稱1BX B b??，0NX ?為基礎(chǔ)可行解， B 為可行基。 因而可得以下法則： 對于基 B ，若1 0Bb? ?，且1 0BC B A C? ??，則對應(yīng)于基 B 的基礎(chǔ)解是最優(yōu)解，又叫基礎(chǔ)最優(yōu)解， B 為最優(yōu)基。 三 . 換基迭代求最優(yōu)解的過程 從一個可行基出發(fā)，經(jīng)如下步驟，求得新基 直到 求出最優(yōu)解 或無解為止。 為了使1rsb ?，只需將原表數(shù)用rsb去除第r 行各數(shù)，得新表第 r 行各數(shù)，即rjrjrsbbb? ? ? ?0 jn??，為使新表中0isb ? ? ?0 i r m? ? ?，需將原表中第 i 行減去第 r 行相應(yīng)數(shù)的isrsbb倍，得新表第 i 行的數(shù)，即 isi j i j r jrsbb b bb? ? ? ?? ?0 , 0i j m j n? ? ? ? ? 換基后，新基 B? 仍是一個可行基，且目標(biāo)函數(shù)值增加。 （ 1 ） 作對應(yīng)于基1B的單純形表 1 1x 2x 3x 4x 5x 6x Z 0 － 2 1 － 1 0 0 0 4x 60 3 1 1 1 0 0 5x 10 1 * － 1 2 0 1 0 6x 20 1 1 － 1 0 0 1 2 判別： 因為表中的檢驗數(shù)有負數(shù)，即01 2b ??，03 1b ??，基1B不滿足最優(yōu)解條件，又01b，03b對應(yīng)的 列向量中的分量有非負數(shù)，所以需換基迭代。 經(jīng)過上述步驟的計算，可得對應(yīng)于基? ?2 4 1 6,B p p p?的單純形表 2 1x 2x 3x 4x 5x 6x Z 20 0 － 1 3 0 2 0 4x 30 0 4 － 5 1 － 3 0 1x 10 1 － 1 2 0 1 0 6x 10 0 2* － 3 0 － 1 1 由于表中的檢驗 數(shù)仍有負數(shù)，應(yīng)重復(fù)上述換基迭代過程，可得新基? ?3 4 1 2,B p p p?的單純形表 3 1x 2x 3x 4x 5x 6x Z 2 5 0 0 3 0 32 12 4x 10 0 0 － 1 1 － 1 － 2 1x 15 1 1 12 0 12 12 2x 5 0 1 32? 0 12? 12 表中的檢驗數(shù)已沒有負數(shù)，且所有? ?0 0 1 , 2 , 3ibi ??，最優(yōu)解已求出： 1 2 4 3 5 61 5 , 5 , 1 0 , 0x x x x x x? ? ? ? ? ?，1 2 3m a x 2 25Z x x x? ? ? ? [ 例題 ] 12m ax 2 5Z x x?? 122121258..2 3 3,0xxxstxxxx? ? ??????? ? ??? ?? 解： 化為標(biāo)準(zhǔn)型： 12m ax 2 5Z x x?? ???????????????????)5,2,1(033285..52142321?jxxxxxxxxxtsj 基為? ?345,p p p，? ?TB如下表： 1x 2x 3x 4x 5x Z 0 － 2 － 5 0 0 0 3x 5 － 1 1 1 0 0 4x 8 0 1 0 1 0 5x 3 － 1 2 0 0 1 對應(yīng)于基 B 的基本可行解為? ?0 , 0 , 5 , 8 , 3 Tx ?，0Z ?，但由于檢驗數(shù)01 20b ? ? ?，02 50b ? ? ?，且? ?1 0 1 , 2 , 3ibi ??，據(jù)定理 2 知，此問題無最優(yōu)解。它早期是線性代數(shù)課的教學(xué)軟件，后來逐步應(yīng)用于實際工程問題的計算，目前已成為工程界和應(yīng)用數(shù)學(xué)人員常用的數(shù)學(xué)軟件之一。 1 1 1 ] 。已知第 j個項目的投資為 億元，可得收益為 億元，問應(yīng)如何進行投資，才能使盈利率（即單位投資可得到的收益）為最高？ ja jc解： 令決策變量為jx，則jx應(yīng)滿足條件? ?10jjxx ?? 同時jx應(yīng)滿足約束條件1njjja x b??? 目標(biāo)函數(shù)是要求盈利率 ? ?1121, , ,njjjn njjjcxf x x xax?????最大。 解： 設(shè)第 i 個倉庫的位置為 ? ?,iixy ? ?1 , 2 , ,im?， 第 i 個倉庫到第 j 個市場的貨物供應(yīng)量為ijz ? ?1 , 2 , , , 1 , 2 , ,i m j n??，則第 i 個倉庫到第 j 個市場的距離為 ? ? ? ?22i j i j i jd x p y q? ? ? ? 目標(biāo)函數(shù)為 ? ? ? ?221 1 1 1m n m ni j i j i j i j i ji j i jz d z x p y q? ? ? ?? ? ? ?? ? ? ? 約束條件為： （ 1 ） 每個倉庫向各市場提供的貨物量之和不能超過它的存儲容量； （ 2 ） 每個市場從各倉庫得到的貨物量之和應(yīng)等于它的需要量； （ 3 ） 運輸量不能為負數(shù)。([mi n ? 設(shè) *x 為問題（ ）的最優(yōu)解，則)。 一般地，可引入如下定義： 定義 6. 1 形如???mirnrriinii xxxcxg12121)( ?的函數(shù)稱為廣義多項式，其中iji rc ,為實數(shù)，而nix i ,2,1,0 ???。 由于算術(shù) —— 幾何平均不等式在這一類特殊的非線性規(guī)劃的早期研究中起著極為重要的作用，幾何規(guī)劃也就由此而得名。若記 ? ? ? ?? ?0 , 1 , 2 , , , 0 , 1 , 2 , ,ijX g X i m h X j l? ? ? ? ? ? 則稱?為可行域。 定理 6. 3 設(shè) ? ?fx是 n 元可微凸函數(shù)，如果 ? ?0fx ???，則 x ? 是上述問題的最小解。我們把上述求解方法稱為解析方法。在許多算法中，k?是由求)( )()( kk sxf ??的極小值來確定，這是求一元函數(shù)的極小問題，稱為一維搜索或線性搜索。用導(dǎo)數(shù)的無約束優(yōu)化方法，包括梯度法（最速下降法），牛頓法，阻尼牛頓法（這兩種方法都要使用二階導(dǎo)數(shù)），共軛梯度法， DFP算法， BFGS算法等。 牛頓法 對正定二次函數(shù)，? ?12TTf X X A X B X c? ? ?，其中 A 為 n 階方陣， B 為 n 維列向量，c 為常數(shù)，設(shè) X ? 為其極小點，則? ? 0f X A X B??? ? ? ?，所以 A X B? ?? ；任給 n)0( EX ? ，? ?? ? ? ?00f X A X B? ? ?，消去 B ，得 ? ?? ? ? ?00f X A X A X ?? ? ? 所以 ? ? ? ?? ?00 1X X A f X??? ? ?， 這說明，從任意近似點出發(fā)，沿? ?? ?01A f X???方向搜索，步長為 1 ，一步即可達極小點。好在科技人員已研制出各種求解無約束優(yōu)化算法的計算軟件，使用它們，多數(shù)情況下可以順利地求得優(yōu)化問題的最優(yōu)解。 凸規(guī)劃具有兩個重要性質(zhì)： ? 凸規(guī)劃的可行集是凸集 ? 凸規(guī)劃的局部最小解就是它的全局最小解 （證明略） [ 例題 ] 驗證下述非線性規(guī)劃為凸規(guī)劃，并求出最優(yōu)解。 定義 6. 6 對于上述非線性規(guī)劃問題，如果可行點 X 處，各起作用約束的梯度向量線性無關(guān)，則稱 X 是約束條件的一個正則點。 （ 2 ） 若? ?1 0gX ?是起作用約束，? ?2 0gX ?是不起作用約束，則有2 0? ?，則 ? ?1 2 1 11 2 1 2221 1 214 2 10 2 02 2 10 2 0500x x xx x xxx????? ? ? ???? ? ? ???? ? ????? 解得 12121210xx????????????? 代入原問題約束條件中檢驗，可知該點? ?1 , 2TX ? ?是可行點，且滿足 K T 定理的條件，又是一個正則點，故它是一個 K T 點。故有 1 2 1 1 21 2 1 2 22212124 2 1 0 2 3 02 2 1 0 2 0506 3 0x x xx x xxxxx????? ? ? ? ???? ? ? ? ???? ? ???? ? ?? 求解上述方程組，得到的解不滿足1 0? ?與2 0? ?，故舍去。因此? ?1 , 2TX ? ?也是本題的全局最小點。 ? 對約束非線性規(guī)劃問題不預(yù)先進行轉(zhuǎn)換