天津大學碩士研究報告考試復(fù)習題

1、-. z.例9 *線性規(guī)劃問題用單純形法迭代時，得到的中間*兩步的單純形表如表2.8。請將表中空白的數(shù)字填上。表2.8354000b*1*2*3*4*5*6(1)5*210000*505-100*60401Z0-400(2)5*24*33*1Z表2.9b*1*2*3*4*5*6*2010*3001*1100Z000例 16 *廠準備生產(chǎn)三種產(chǎn)品A,B,C,需消耗勞動力和原料兩種資源，其有關(guān)數(shù)據(jù)如表2.15.表2.15.表 2.15 產(chǎn)品 單位消耗資源A B C資源限量勞動力原料6 3 53 4 545單位30單位單位利潤3 1 5(1)用單純形法確定總利潤最大的生產(chǎn)方案.(2) 分別求出勞動力

2、和原料的影子的價格.假設(shè)原料不夠,可到市場上購置,市場價格0.8問是否要購進,最多可購進多少總利潤增加多少3當產(chǎn)品A,C的單位利潤在何圍變化時，最優(yōu)生產(chǎn)方案不變？4勞動力可減少多少而不改變原最優(yōu)方案？解 (1) 該問題的線性規(guī)劃模型為s.t.其中分別為產(chǎn)品A,B,C的產(chǎn)量.用單純形法迭代的最優(yōu)表如表2.16所示表 2.16因而最優(yōu)生產(chǎn)方案為生產(chǎn)A,B產(chǎn)品均為0，生產(chǎn)C產(chǎn)品可使利潤最大，最大利潤為30.(2)勞動力和原料的影子價格分別為0和1.這說明在企業(yè)最優(yōu)安排中,勞動里資源沒有用完(實際用了30個單元),而原料資源已耗盡.假設(shè)原料市場價格0.8影子價格1,因此應(yīng)適量購進原料擴大生產(chǎn).設(shè)購進的

3、原材料數(shù)為,為保持最優(yōu)基不變,必須有,而=解得 因而最多可購進原料15單位，總利潤增加.凈利潤增加15-0.815=3單位.3產(chǎn)品A()在最優(yōu)方案中是非基變量，設(shè)變化為則當為的檢驗數(shù)，即當時，原最優(yōu)方案不變.產(chǎn)品在最優(yōu)方案中是基變量,設(shè)變化為,要使最優(yōu)方案不變,則所有非基變量檢驗數(shù)應(yīng)非負,即即 因此當產(chǎn)品C的單位利潤時，最優(yōu)方案不變4設(shè)勞動力減少，即右邊常數(shù)列變化為，為使最優(yōu)方案不變，則即 所以 即勞動力可減少15單位，原最優(yōu)方案不變.實際上減去的是充裕勞動力.例1 *鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油，使總的鉆探費用為最小。假設(shè)10個井位的代號為s1,s2,s10,相應(yīng)的鉆

4、探費用為c1,c2, c10,并且井位選擇上要滿足以下限制條件：eq oac(,1)或選擇s1和s7，或選擇s8;eq oac(,2)選擇了s3或s4就不能選s5,或反過來也一樣；eq oac(,3)在s5，s6，s7，s8，中最多只能選兩個。試建立這個問題的整數(shù)規(guī)劃模型。例3*科研工程由三個小組用不同方法獨立進展研究，它們失敗的概率分別為0.40,0.60和0.80為了減少三個小組都失敗的可能性,現(xiàn)決定暫派兩名高級科學家參加這一科研工程,把這兩個分配到各組后,各小組仍失敗的概率如表4.4所示,問應(yīng)如何分派這兩各高級科學家以使三個小組都失敗的概率最小表4.4高級科學家人數(shù)小 組1230120.

5、400.200.150.600.400.200.800.500.30解(1)建立動態(tài)規(guī)劃模型按小組數(shù)將問題劃分3個階段,階段變量狀態(tài)變量表示第階段初可用于分配的科學家數(shù),決策變量表示第階段分配給第個小組的高級科學家人數(shù).狀態(tài)轉(zhuǎn)移方程:允許決策集合:階段指標過程指標函數(shù)因而根本方程采用乘積形式,即(2)采用逆序法求解:當=3時,因為(即尚未分配給第1和第2小組的全局部配給第3小組).計算結(jié)果如表4.5所示.表4.50120120.800.500.30當=2時,計算結(jié)果如表4.6所示.表4.60120.480.300.180.320.200.160020.480.30.0.16當時,計算結(jié)果如表4

6、.7所示.表 4.7 s1*1=0*1=1*1=220.0640.0600.07210.060由表4.7可知*1*= 1 ,= 0.060, 由s1= 1查表4.6可得*2*= 0 ; 由s3= 1查表4.5得*3*=1. 因而此問題的最優(yōu)解為*1* = 1, *2*= 0 ，*3*= 1. 即把兩名高級科學家分派到第1和第3兩小組各一名，可使三個小組都失敗的概率減小到0.060.0.800.48注：此問題還有一種更簡捷的解法，將它化為最短路模型.即將各階段狀態(tài)作為結(jié)點，各小組失敗的概率為弧線上的數(shù)據(jù)，見圖4.1.然后在圖上用逆序法計算，計算結(jié)果標于圖上的方框 .S3=0S2=0 0.60 0

7、.15 0.800.500.060.30 0.40S4=0S3=1S1=2S2=1 0.20 0.60 0.50 0.200.300.16 0.40 0.40 0.30S3=2S2=2 0.60 圖4.1由圖4.1可知，整個工程失敗的概率為0.060 ，最優(yōu)路線為圖中雙線表示 ，即s1=2s2=1s3=1s4=0，由此同樣得出最優(yōu)解為*1*=1, *2*=0 ，*3*=1.因此,所有一維資源分配離散型均可化為最短路問題來求解,在圖上用逆序算法求解較簡便.如表6.8中的資料，求該工程的最低本錢日程。表6.8活動作業(yè)時間天緊前活動正常完成進度的直接費用百元趕進度一天所需費用百元abcdefgh48

8、635743baaab,de,f,g20301551840101554324736 合計 153 工程間接費用 5百元/天6.19 解 其網(wǎng)絡(luò)圖如圖6.39所示.其中方框數(shù)據(jù)表示結(jié)點最早時間，三角形框數(shù)據(jù)表示結(jié)點最晚時間。關(guān)鍵線路為：。方案一：正常進度完工的工程費用：工程費用=153+15*5=22800元。方案二：在方案一中，關(guān)鍵路線是，且由表6.8中數(shù)據(jù)費用率(即趕進度一天所需費用)知,minc13,c45,c56=4,3,6=3=c45,為此縮短關(guān)鍵工序g一天. 工程費用=228+1*3-1*5=22600(元).調(diào)整后，關(guān)鍵路線有3條：; ; ，工期為14天，見圖：6.40。h eq

9、oac(,11)fa eq oac(,4)68 eq oac(,1) eq oac(,3) eq oac(,2) eq oac(,5) eq oac(,6) eq oac(,4) eq oac(,0) eq oac(,0)b eq oac(,8)c eq oac(,8)d34 eq oac(,4)5e7 eq oac(,11)3 eq oac(,8) eq oac(,8) eq oac(,4)g3 eq oac(,14) eq oac(,14) eq oac(,6)1414圖6.40在圖6.40中各結(jié)點最早時間與最遲時間已相等，因而該項工程的最低本錢日程以求出，為14天，方案二為最優(yōu)方案。 5

10、.1 解：1錯。當一個矩陣對策的鞍點不唯一時，結(jié)論不正確。例如：2 對。3 對。4 錯。當矩陣對策有唯一的鞍點時，局中人采取純策略。5.3 解 B A 即 P=用優(yōu)超法化簡得解得 5.13 表5.8YBby1 y2 y3 s1 s2 s3y1y2y3 1 0 0 -0 1 0 - - 0 0 1 -W0 0 0 表5.9YBby1 y2 y3 s1 s2 s3y3y1y2 0 0 1 -1 0 0 - 0 1 0 -W0 0 0 例2 *電子設(shè)備廠對一種元件的需求為R=2000件年，訂貨提前期為零，每次訂貨費為25元.該元件每件本錢為50元,年存儲費為本錢的20%,如發(fā)生供給短缺,可在下批貨到

11、達時補上,但是缺貨損失費為每件每年30元.要求: 經(jīng)濟訂貨批量及全年的總費用； 如不允許發(fā)生供給短缺，重新求經(jīng)濟訂貨批量，并同的結(jié)果進展比擬.解 k=25，D=2000,=5020%=10,=30，則= .= 115.=.與相比，中的經(jīng)濟訂貨批量減少了，而全年的總費用增加了。3離散型的報童問題例3 *商店準備在新年前定購一批掛歷批發(fā)出售，每售出一批100本可獲利70元.如果掛歷在新年前售不出去，則每100本損失40元，根據(jù)已往銷售經(jīng)歷，該商店售出掛歷的數(shù)量如表7.1所示.問一次訂貨幾百本，使期望的獲利數(shù)最大？表7.1銷售量(100本)123456概率0.050.100.250.350.150.

12、10解 由公式，其中可得.所以一次應(yīng)定購300本表 8.4 如果勘探費用需1萬元，問1應(yīng)先勘探還是直接鉆井，2應(yīng)該怎樣根據(jù)勘探結(jié)果來決定是否鉆井？解并求得：同理有故，不鉆井為最優(yōu)選擇故，鉆井為最優(yōu)選擇。日銷售量件10000s120000(s2)30000(s3)40000(s4)銷售概率0.150.300.350.20又企業(yè)的月最大生產(chǎn)能力為40000件，且通過調(diào)查知各種銷售量狀態(tài)下銷路好與不好的概率如表8.6所示。* s10000(s1)20000(s2)30000(s3)40000(s4)銷路好0.30.50.70.8銷路不好0.70.50.30.2*為銷路，s為銷量。試求EVPI.求在調(diào)

13、查結(jié)果銷路好與不好的生產(chǎn)方案。試求EVSI.例3 *亭有一部，來打的顧客數(shù)服從泊松分布，相繼兩個人到達的平均時間為10分鐘，通話時間服從指數(shù)分布，平均數(shù)為3分鐘，求顧客到達亭要等待的概率等待打的平均顧客數(shù)當一個顧客至少要等3分鐘才能打時，電信局打算增設(shè)一臺機，問到達速度增加到多少時，裝第二臺機才是合理的？打一次要等10分鐘以上的概率是多少？第二臺機安裝后，故可的平均等待時間是多少？解 例4 *航運局擬自己建立1個港口，據(jù)資料知貨船按泊松流到達，平均每小時到達21條，卸貨時間服從負指數(shù)分布，平均卸貨時間為2分鐘。每條船的售價8萬元，每建立1個泊位需投資12萬元，試問建立多少個泊位合理？解 用線性規(guī)劃方法求解以下對策問題?！窘狻?(a)此問題無鞍點，支付矩陣無法用優(yōu)勢原則簡化，對策雙方各擁有3個策略，故用線性規(guī)劃方法求解。將矩陣中各元素，分別加上3以消除原有的負值，得設(shè)A分別為以的概率混合使用，B分別以的概率混合使用，則求A最優(yōu)策略的線性規(guī)劃