【正文】 ?? ????????? ? ? ??? ?????或 A、 B 兩 種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見下表： A B 生產(chǎn)成本（萬元 /噸） 銷售價(jià)格（萬元 /噸） 甲 乙 丙 8 5 18 30 20 35 原料成本（萬元 /噸） 5 7 原料可用數(shù)量（噸） 350 460 （ 1）請(qǐng)寫出使總銷售利潤(rùn)最大的線性規(guī)劃模型（其中甲、乙、丙產(chǎn)產(chǎn)量分別記為 x1,x2,x3,約束依 A,B 原料次序） : (2)寫出此問題的對(duì)偶規(guī)劃模型（ 2022） 解：⒈① maxz=30x1+20x2+35x38x15x218x35(x1++)7(++) 目標(biāo)函數(shù) maxz=++ 約束條件 x1++≤ 350 ++≤ 460 x1≥ 0,x2≥ 0,x3≥ 0 ②對(duì)偶規(guī)劃模型 目標(biāo)函數(shù) minw=350y1+460y2 約束條件 y1+≥ +≥ +≥ y1≥ 0,y2≥ 0 三、（ 10%）某服裝廠制造大、中、小三種尺寸的防寒服，所用資源有尼龍綢、尼龍棉、勞動(dòng)力和縫紉設(shè)備。又設(shè)若選擇了第 1 種培訓(xùn)方式，則第 3 種培訓(xùn)方式也要選擇。 1． 現(xiàn)欲求各無害物的產(chǎn)量 xj 以使總的處理費(fèi)用為最小，請(qǐng)寫出此問題的線性規(guī)劃模型； 2． 寫出此問題的對(duì)偶規(guī)劃模型，并解釋對(duì)偶規(guī)劃模型的經(jīng)濟(jì)意義。 5) 填完表 2，該表是否是終表 ?____是 _____。（ 1999） 解： x1+x2+x3≥ 1 x2≥ x4 2． 考慮線形規(guī)劃問題 1 2 31 2 31 2 31 2 3m a x 5 12 425. . 2 3 2, , 0Z x x xx x xs t x x xx x x? ? ?? ? ??? ? ? ??? ?? 用單純型法求解，得其終表如下： Cj 5 12 4 0 M CB XB B1b x1 x2 x3 x4 x5 12 x2 8/5 5 x1 9/5 0 1 1/5 2/5 1/5 1 0 7/5 1/5 2/5 ? j 0 0 3/5 29/5 M+25 其中 x4 位松弛變量， x5 為人工變量。（ 2022） 解：確定一個(gè)初始基可行解；檢驗(yàn)一個(gè)基可行解是否為最優(yōu)解；尋找一個(gè)更好基可行解；可行性；最優(yōu)性。 (2022) （ a） （ b） （ c） 解： 3．標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其可行解 b 是基本可行解，最優(yōu)解 a 是可行解，最優(yōu)解 a 能在可行域的某頂點(diǎn)達(dá)到。若原問題第 j 個(gè)約束為等式，則對(duì)偶問題第 j 個(gè) 變量 自由。（ 2022） 解： 3. 0,1 3142 ???? xxxx 一、簡(jiǎn)答（ 18%） （ 1）請(qǐng)簡(jiǎn)述影子價(jià)格的定義。 A． 小于 B． 等于 C． 大于 D． 大于等于 （ 2022） 解： 2． B 1． 用大 M法求解 Max型線形規(guī)劃時(shí)，人工變量在目標(biāo)函數(shù)中的系數(shù)均為 ____________，若最優(yōu)解的 _______________中含有人工變量，則原問題無解。 （ 2022） 解： 1． (1)出基變量為 x4；進(jìn)基變量為 x3。一、線性規(guī)劃 二、運(yùn)輸問題 三、多目標(biāo)規(guī)劃 四、動(dòng)態(tài)規(guī)劃 五、 圖論 六、網(wǎng)絡(luò)計(jì)劃技術(shù) 七、決策論 八、存儲(chǔ)論 九、排隊(duì)論 十、對(duì)策論 十一、模擬技術(shù) 一、線性規(guī)劃 （一）選擇填空題 （二）線性規(guī)劃建模 （三）互補(bǔ)松弛應(yīng)用 （四）靈敏度分析 （五）證明題 （一）選擇填空題 1．下面給出某線性規(guī)劃問題的單純形初表和終表（ Min 型）： CB XB B1b 0 1 3 0 2 0 x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 1 0 2 0 0 2 4 1 0 0 0 4 3 0 8 1 σ j CB XB B1b x1 x2 x3 x4 x5 x6 x2 x6 2/5 0 1/10 0 1/5 1 3/10 0 1 0 1/2 1 σ j (1)初表的出基變量為 ，進(jìn)基變量為 。 (2)*121 05 1 013 05 1 01112B ???????????????。（ 2022） 解： M 基變量 1. 設(shè)線性規(guī)劃問題 ?? 0m ax ?? bxAxcx 有最優(yōu)解 *x 和影子價(jià)格 *y ,則 線性規(guī)劃問題?? 02m ax ?? bxAxcx 的最優(yōu)解 = ，影子價(jià)格 = 。 （ 2）在使用單純型表求解型線性規(guī)劃時(shí)，資源的影子價(jià)格在單純型表的什么位置上？ （ 3）寫出影子價(jià)格的數(shù)學(xué)表達(dá)式并用其定義加以驗(yàn)證 （ 4）試述運(yùn)輸問題中檢驗(yàn)數(shù)的經(jīng)濟(jì)意義（ 2022） 解：一、簡(jiǎn)答 ⑴當(dāng)各資源增加一單位時(shí)引起的總收入的增量，影子價(jià)格大于零的資源一定沒有剩余，有剩余一定為零。（ 2022） 解： 2． 設(shè)線性規(guī)劃問題 max:{cx|Ax≤ bx≥ 0}有最優(yōu)解，且最優(yōu)解值 z0；如果 c 和 b 分別被 v1所乘，則改變后的問題 也有 （也有、 不一定有）最優(yōu)解；若有最優(yōu)解，其最優(yōu)解 大于 (大于、小于、等于 )z。 (2022) （ a）一定 （ b）不一定 （ c）一定不 解： 4．目標(biāo)函數(shù)取極?。?min Z）的線性規(guī)劃問題可以轉(zhuǎn)化為目標(biāo)函數(shù)取極大 b 的線性規(guī)劃問題求解，原問題的目標(biāo)函數(shù)值等于 c 。 2. 設(shè)有線性規(guī)劃問題 ? ? ? ?0,|,m i n ????? XbAXXRXCXf ，有一可行基 B（為 A中的前 m 列），記相應(yīng)基變量為 ?X ，價(jià)格系數(shù)為 CB，相應(yīng)于非基變量為 XN，價(jià)格系數(shù)為CN，則相應(yīng)于 B 的基本可行解為 X= ；用非基變量來表示基變量的表達(dá)式為XB= ；用非基變量表示目標(biāo)函數(shù)的表達(dá)式為 f= ， B 為最優(yōu)基 的條件是 。 （ 1）上述模型的對(duì)偶模型為 ， （ 2）對(duì)偶模型的最優(yōu)解為 ， （ 3）當(dāng)兩種資源分別單獨(dú)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值分別增加 和 ， （ 4）最優(yōu)基的逆矩陣 1B? ??????? （ 5）如果原問題增加一個(gè)變量，則對(duì)偶問題的可行域?qū)⒖赡茏兇筮€是變?。浚?1999） 解： 2．（ 1） 1212121212m in 5 2252 12340,W y yyyyyyyyy?????? ???? ???? ?? 無 符 號(hào) 限 制 （ 2） Y*=（ 295 ， 25 ） （ 3） 295 ， 25 （ 4）21551255????????? （ 5）變小 1．下面給出某線形規(guī)劃的單純形初表（表 1）與某一中間表（表 2）（ Min 型）： 表 1 CB XB B1b 0 1 3 0 2 0 x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 1 0 2 0 0 2 4 1 0 0 0 4 3 0 8 1 j? ? 表 2 x2 x6 2/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 1/2 10 j? 1) 初表的出基變量為 __________，進(jìn)基變量為 _________。若是，最優(yōu)值 ?*Z __11______ 此線形規(guī)劃對(duì)偶問題的最優(yōu)解 ?*Y ?????? ?? ,054,51 解： 解： 解： 解： 解： 解： （二）線性規(guī)劃建模 二（ 20 分）、某化學(xué)制藥廠有 m 種有害副產(chǎn)品，它們的數(shù)量為 bi（ i=1，?， m）。（ 2022） 解： 1． 111 1 12 2 1 121 1 22 2 2 21 1 2 212m in.., , 0njjjnnnnm m m n n mnz c xa x a x a x ba x a x a x bsta x a x a x bx x x?? ?? ? ? ? ??? ? ? ? ? ??????? ? ? ? ? ?????? ， 2． 111 1 21 2 1 112 1 22 2 2 21 1 2 212m a x.., , 0miiimmmmn n m n m nmz y ba y a y a y ca y a y a y csta y a y a y cy y y?? ?? ? ? ? ??? ? ? ? ? ??????? ? ? ? ? ?????? ， 經(jīng)濟(jì)意義： iy 為第 i 種有害副產(chǎn)品不經(jīng)處理直接廢棄的費(fèi)用。記 xij 為第 i 種需求由第 j 方式培訓(xùn)的人員數(shù)量， z 為培訓(xùn)總費(fèi)用?？p制一件防寒服所需各種資源的數(shù)量如表（單位已適當(dāng)給定）。 (2022) 型號(hào) 資源 小 中 大 尼龍綢 1． 6 1． 8 1． 9 尼龍棉 1． 3 1． 5 1． 6 勞動(dòng)力 4 4． 5 5 縫紉設(shè)備 2． 8 3． 8 4． 2 解：三、解：設(shè)三種防寒服分別生產(chǎn) x1,x2,x3件。有關(guān)數(shù)據(jù)如表 1。 （ 3）對(duì)偶問題模型： ???????????????????????0,094132651010121107135708600630m i n21432143214321yyyyyyyyyyyyyyW 對(duì)偶問題最優(yōu)解： ? ?09 6 7 7 * ?y 由對(duì)偶問題的強(qiáng)對(duì)偶性知，對(duì)偶問題與原問題的最優(yōu)值相同 W*=Z*=7668 (美元 ) （ 4）成型時(shí)間影子價(jià)格為 75 0 12 5 0 63 0 37 5 1 56 25 0 60 00 5 0 75 0 70 8 43 75 0 40 62 5 1 13 51 .87 5 63 0 12 5 ( 70 8 ) 0 37 5 6