運籌學作業(yè)輔導及答案北京外國語大學運籌學作業(yè)

1、題目1 50 分線性規(guī)劃Maxz = 5 x1 + 5 x2 + 13 x3 s.t. x1 +x2 +3 x3 20 12 x1 + 4 x2 + 10 x3 90 x1, x2, x3 0的最優(yōu)表為：cj-551300iCBXBbx1x2x3x4x55x220-113100x510160-2-41-z-10000-2-50分析在下列條件下，最優(yōu)解分別有什么變化（1） b2由90變?yōu)?0。（2） c1由-5變?yōu)?10。（3）增加一個約束條件4 x1 + 3 x2 + 6 x3 50。（出自第三單元）答案：1）由最優(yōu)基不變的條件 Max -bi/irir0DbrMin-bi/irir0 得-1

2、0 = -10/1Db2 b2由90變?yōu)?0，超出了允許變化范圍，繼續(xù)計算或者由B-1(b +Db)=(20,-10)T可以知道最優(yōu)基發(fā)生變化，繼續(xù)迭代。 最優(yōu)解變?yōu)閤1 =0，x2 = 5，x3 = 5，x4 = 0，x5 = 0，最優(yōu)值 z* = 90。2）c1是非基變量的系數，最優(yōu)解不變的條件是：Dc1 - s1， c1由-5-10，Dc1 = -5 0 = - s1，不影響最優(yōu)解。 3）增加一個約束條件4 x1 + 3 x2 + 6 x3 50，原最優(yōu)解不滿足這個約束。引入松弛變量，得到4 x1 + 3 x2 + 6 x3 + x6 = 50填入最優(yōu)單純形表，進一步求解，得到最優(yōu)解為X

3、=(0，10，10/3)T，最優(yōu)值為280/3。題目2 50 分某廠生產三種型號的鋁鍋，已知單耗數據如下：產品資源大號中號小號可用資源量鋁板(張)624400勞力(小時)486360機器(臺)8410420售價(元/個)504030試制定最優(yōu)生產計劃使總收入最大。（出自第二單元）答案：解：設 x1、x2、x3分別表示大號、中號、小號鋁鍋的產量， 這樣可以建立如下的數學模型。目標函數：Max50x1 +40 x2+30 x3約束條件：s.t.6x1 +2 x2+ 4 x3 400（鋁板限制） 4x1 +8 x2+ 6 x3 360（勞力限制） 8x1 +4 x2+10 x3 420 （機器限制）

4、 x1，x2，x3 0（非負約束） 化為標準型：目標函數：Max50x1 +40 x2+30 x3約束條件：s.t.6x1 + 2x2+4 x3 + x4= 400 4x1 +8 x2+6 x3 + x5 =360 8x1 +4 x2+ 10 x3 + x6= 420 x1，x2，x3，x4，x5，x6 0 使用單純形法求解：得到最優(yōu)解（40,25,0,110,0,0），最優(yōu)值3000。即應該生產大號鋁鍋40個，中號鋁鍋25個單位，小號鋁鍋產量為0（不生產），最大利潤為3000元。題目3 50 分有一個工廠要確定明年各季度的生產計劃，通過訂貨了解到各季度對產品的需求量dk分別為4000件、30

5、00件、4000件和4000件。又知，工廠生產該產品的季度固定成本為10萬元（但如果在某季度中，該種產品1件也不生產，則不需支付固定成本費），單位產品的可變成本為50元，由于設備的能力所限，每季度最多只能生產5000件。若產品銷售不出，則每件每季度的存貯費為8元。假設本年底無存貨轉入下年，明年末也不需要留有存貨，問每季度的生產計劃應如何安排（假設生產產量以千件為單位），才能使生產的總費用最??？（出自第五單元）答案：解：首先建立動態(tài)規(guī)劃模型（1）階段k：每個季度作為一個階段，k=1,2,3,4（2）狀態(tài)變量sk：第k個季度初的庫存量（千件）（3）決策變量uk：第k個季度的生產量（千件）（4）狀態(tài)

6、轉移方程： sk+1= sk+ uk - dk (需求，千件)（即季度末庫存量=季度初庫存量+季度生產量 - 季度銷售量或需求量）（5）階段指標： gk (sk, uk) =生產成本C(uk) + 庫存成本E(sk)（6）最優(yōu)指標函數fk (sk)：第k個季度的狀態(tài)為sk時從該季度至計劃結束的最低總費用（萬元）（7）遞推方程： fk (sk)=mingk (sk, uk)+ fk+1(sk+1)（8）終端條件：f5(s5)=0 下面進行求解，采用逆序解法。（1）k=5，f5(s5)=0 （2）k=4，0s44，u4=4-s4，s5=s4+u4-d4（說明：第4季度的需求為4千件，因此庫存量不應

7、超過4且顯然非負，所以有0s44；年底不需要有庫存，所以生產量u4 = 4 - s4） （3）k=3，0s35+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0, 4-s3)u3Min(5, 8-s3)（說明：前兩季度總產量為5+5=10千件，需求量為3+4=7千件，所以第3季度初最大庫存量=10-7=3千件；在產量需求方面，為了滿足需求，至少生產d3-u3=4 - u3，且最大產量為5千件，后兩個季度總需求為4+4=8千件，產量不應該超過8-s3。因此有0s33，Max(0, 4 - s3)u3Min(5, 8-s3)） （4）k=2，0s25-4=1，s3=s2+u2-d

8、2=s2+u2-3，Max(0, 3-s2)u2Min(5, 11-s2) （5）k=1，s1=0，s2=s1+u1-d1=u1-4，4u15 最優(yōu)解為s1=0, u1*=5, s2=1, u2*=5, s3=3, u3*=5, s4=4，u4*=0即前3個季度均生產5000件，第4個季度不生產，最低總費用為111.4萬元。題目4 50 分對于以下的運輸問題，若各個銷地少得到1個單位的產品，將要求得到賠償，金額分別為9、12、6、12，問如何組織運輸，才能使總費用最低。（建立運輸模型，用最小元素法求初始解，并求出最優(yōu)解）答案：解:總產量為99+55+110=264，總銷量44+88+88+77

9、=297，產銷不平衡且供不應求，增加一個虛擬產地A4，其產量為297-264=33。由虛擬產地運往銷地的費用即為賠償金額。因此可以建立運輸模型如下: 銷地產地B1B2B3B4產量A1123391590A2306182755A32421330110銷量44888877297使用最小元素法求初始解:B1B2B3B4產量余額A112339159988.11A23061827550/A3242133011022.0/A4912612330/銷量44888877297余額1133.110/0/ 說明:每次選擇最小元素，因此依次選擇3(x33)、6(x22)、9(x41)、12(x11)、15(x14)、

10、21(x32)、33(x12)。)得到初始解x11=11，x12=11，x14=77，x22=55，x32=22，x33=88，x41=33，其余運量為0，總運費為3003。 使用位勢法計算各非基變量檢驗數，填入括號中:B1B2B3B4產量位勢A11233915990A2306182755-27A32421330110-12A491261233-3銷量44888877297位勢12331515 令u1=0，由基變量滿足ui+vj=cij，依次得到各位勢v1=12，v2=33，v4=15，u4=-3，u2=-27，u3=-12，v3=15，再根據公式sij=cij-ui-vj計算各非基變量檢驗數。進行調整:選負檢驗數中最小的s42，那么x42為主元，作為進基變量。以x42為起點找一條閉回路x42、x41、x11、x12，取偶數標號格的最小運量11作為調整量，調整