題目1[50分]線性規(guī)劃Max

z=–5x1+5x2+13x3

s.t.

–

x1+

x2+

3x3≤20

12x1+4x2+10x3≤90

x1,

x2,

x3≥0的最優(yōu)表為：cj-551300θiCBXBb’x1x2x3x4x5

5x220-11310

0x510160-2-41

-z-10000-2-50

分析在以下條件下，最優(yōu)解分別有什么變化〔1〕b2由90變?yōu)?0?！?〕c1由-5變?yōu)?10?！?〕增加一個約束條件

4x1+3x2+6x3≤50?！渤鲎缘谌龁卧炒鸢福?〕由最優(yōu)基不變的條件

Max{-bi/βir?βir>0}≤Dbr≤Min{-bi/βir?βir<0}

得-10=-10/1≤Db2

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是非基變量的系數(shù)，最優(yōu)解不變的條件是：Dc1≤-s1，

c1由-5→-10，Dc1=-5<0=-s1，不影響最優(yōu)解。

3〕增加一個約束條件4x1+3x2+6x3≤50，原最優(yōu)解不滿足這個約束。引入松弛變量，得到4x1+3x2+6x3+x6=50填入最優(yōu)單純形表，進(jìn)一步求解，得到最優(yōu)解為X=(0，10，10/3)T，最優(yōu)值為280/3。

題目2[50分]某廠生產(chǎn)三種型號的鋁鍋，單耗數(shù)據(jù)如下：產(chǎn)品資源大號中號小號可用資源量鋁板(張)624400勞力(小時)486360機(jī)器(臺)8410420售價(元/個)504030

試制定最優(yōu)生產(chǎn)方案使總收入最大?！渤鲎缘诙卧炒鸢福航猓涸O(shè)x1、x2、x3分別表示大號、中號、小號鋁鍋的產(chǎn)量，

這樣可以建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Max

50x1+40x2+30x3

約束條件：s.t.

6x1+2x2+4x3

≤400〔鋁板限制〕

4x1+8x2+6x3

≤360〔勞力限制〕

8x1+4x2+10x3≤420〔機(jī)器限制〕

x1，x2，x3≥0〔非負(fù)約束〕

化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：Max

50x1+40x2+30x3

約束條件：s.t.

6x1+2x2+

4x3+x4

=

400

4x1+8x2+

6x3

+x5

=

360

8x1+4x2+10x3

+x6

=

420

x1，x2，x3，x4，x5，x6≥0

使用單純形法求解：得到最優(yōu)解〔40,25,0,110,0,0〕，最優(yōu)值3000。即應(yīng)該生產(chǎn)大號鋁鍋40個，中號鋁鍋25個單位，小號鋁鍋產(chǎn)量為0〔不生產(chǎn)〕，最大利潤為3000元。題目3[50分]有一個工廠要確定明年各季度的生產(chǎn)方案，通過訂貨了解到各季度對產(chǎn)品的需求量dk分別為4000件、3000件、4000件和4000件。又知，工廠生產(chǎn)該產(chǎn)品的季度固定本錢為10萬元〔但如果在某季度中，該種產(chǎn)品1件也不生產(chǎn)，那么不需支付固定本錢費(fèi)〕，單位產(chǎn)品的可變本錢為50元，由于設(shè)備的能力所限，每季度最多只能生產(chǎn)5000件。假設(shè)產(chǎn)品銷售不出，那么每件每季度的存貯費(fèi)為8元。假設(shè)本年底無存貨轉(zhuǎn)入下年，明年末也不需要留有存貨，問每季度的生產(chǎn)方案應(yīng)如何安排〔假設(shè)生產(chǎn)產(chǎn)量以千件為單位〕，才能使生產(chǎn)的總費(fèi)用最省？〔出自第五單元〕答案：解：首先建立動態(tài)規(guī)劃模型〔1〕階段k：每個季度作為一個階段，k=1,2,3,4〔2〕狀態(tài)變量sk：第k個季度初的庫存量〔千件〕〔3〕決策變量uk：第k個季度的生產(chǎn)量〔千件〕〔4〕狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk-dk(需求，千件)〔即季度末庫存量=季度初庫存量+季度生產(chǎn)量-季度銷售量或需求量〕〔5〕階段指標(biāo)：gk(sk,uk)=生產(chǎn)本錢C(uk)+庫存本錢E(sk)〔6〕最優(yōu)指標(biāo)函數(shù)fk(sk)：第k個季度的狀態(tài)為sk時從該季度至方案結(jié)束的最低總費(fèi)用〔萬元〕〔7〕遞推方程：fk(sk)=min{gk(sk,uk)+fk+1(sk+1)}〔8〕終端條件：f5(s5)=0下面進(jìn)行求解，采用逆序解法。〔1〕k=5，f5(s5)=0

〔2〕k=4，0≤s4≤4，u4=4-s4，s5=s4+u4-d4

〔說明：第4季度的需求為4千件，因此庫存量不應(yīng)超過4且顯然非負(fù)，所以有0≤s4≤4；年底不需要有庫存，所以生產(chǎn)量u4=4-s4〕〔3〕k=3，0≤s3≤5+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0,4-s3)≤u3≤Min(5,8-s3)

〔說明：前兩季度總產(chǎn)量為5+5=10千件，需求量為3+4=7千件，所以第3季度初最大庫存量=10-7=3千件；在產(chǎn)量需求方面，為了滿足需求，至少生產(chǎn)d3-u3=4-u3，且最大產(chǎn)量為5千件，后兩個季度總需求為4+4=8千件，產(chǎn)量不應(yīng)該超過8-s3。因此有0≤s3≤3，Max(0,4-s3)≤u3≤Min(5,8-s3)〕〔4〕k=2，0≤s2≤5-4=1，s3=s2+u2-d2=s2+u2-3，Max(0,3-s2)≤u2≤Min(5,11-s2)〔

5〕k=1，s1=0，s2=s1+u1-d1=u1-4，4≤u1≤5

最優(yōu)解為s1=0,u1*=5,s2=1,u2*=5,s3=3,u3*=5,s4=4，u4*=0即前3個季度均生產(chǎn)5000件，第4個季度不生產(chǎn)，最低總費(fèi)用為111.4萬元。題目4[50分]對于以下的運(yùn)輸問題，假設(shè)各個銷地少得到1個單位的產(chǎn)品，將要求得到賠償，金額分別為9、12、6、12，問如何組織運(yùn)輸，才能使總費(fèi)用最低?！步⑦\(yùn)輸模型，用最小元素法求初始解，并求出最優(yōu)解〕答案：解:總產(chǎn)量為99+55+110=264，總銷量44+88+88+77=297，產(chǎn)銷不平衡且供不應(yīng)求，增加一個虛擬產(chǎn)地A4，其產(chǎn)量為297-264=33。由虛擬產(chǎn)地運(yùn)往銷地的費(fèi)用即為賠償金額。因此可以建立運(yùn)輸模型如下:銷地產(chǎn)地B1B2B3B4產(chǎn)量A1123391590A2306182755A32421330110銷量44888877297使用最小元素法求初始解:B1B2B3B4產(chǎn)量余額A1123391599A23061827550/A32421330110A4912612330/銷量44888877297余額110/0/說明:每次選擇最小元素，因此依次選擇3(x33)、6(x22)、9(x41)、12(x11)、15(x14)、21(x32)、33(x12)。)得到初始解x11=11，x12=11，x14=77，x22=55，x32=22，x33=88，x41=33，其余運(yùn)量為0，總運(yùn)費(fèi)為3003。使用位勢法計算各非基變量檢驗(yàn)數(shù)，填入括號中:B1B2B3B4產(chǎn)量位勢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，再根據(jù)公式sij=cij-ui-vj計算各非基變量檢驗(yàn)數(shù)。進(jìn)行調(diào)