《運籌學》習題集

《運籌學》習題集《運籌學》習題集PAGEPAGE8第一章 線性規(guī)劃將下述線性規(guī)劃問題化成標準形式1) minz＝－3x1＋4x2－2x3＋5x44x1－x2＋2x3－x4＝－2st. x1＋x2－x3＋2x4≤14－2x1＋3x2＋x3－ x4≥x1，x2，x3≥0，x4無約束2) minz＝2x1－2x2＋3x3－x1＋x2＋x3＝4st. －2x1＋x2－x3≤1 2 x≤0，x ≥0，x1 2 用圖解法求解LP無可行解。1 minz＝2x＋1 1 4x＋6x≥61 1 st 2x＋2x1 x ，x 1 21 maxz＝3x＋1 1 2x＋x≤21 1 st 3x＋4x1 x ，x 1 21 maxz＝3x＋1 1 6x＋10x≤1201 1st 5≤x≤10123≤x≤821 maxz＝5x＋1 1 2x－x≥21 1 st －2x＋3x1 x ，x 1 2LP問題所有基解，指出哪些是基可行解，并確定最優(yōu)解1 2 3 （1）minz＝5x－2x＋3x＋1 2 3 1 2 3 x＋2x＋3x＋4x＝71 2 3 st 2x＋2x＋x ＋2x＝31 2 3 4x1，x2，x3，x4≥0分別用圖解法與單純形法求解下列LP問題，并對照指出最優(yōu)解所對應(yīng)的頂點。1 maxz＝10x＋1 1 3x＋4x≤91 1 st 5x＋2x1 x ，x 1 21 maxz＝2x＋1 1 3x＋5x≤151 1 st 6x＋2x1 x ，x 1 2M法與兩階段法求解下列LP問題。1 2 minz＝2x＋3x＋x1 2 1 2 x＋4x＋2x≥1 2 1 1 2 st 3x＋2x x，x ，x1 1 2 1 2 maxz＋1 2 1 1 2 . 3x＋xSt. 2x＋x 1 1 2 1 2 x＋x－x1 2 1 2 maxz＝5x＋3x1 2 1 2 x＋2x －x≤181 2 1 2 st 2x＋x －3x≤1 2 1 2 1 2 x＋x －xx，x ，x1 2 1 2 maxz10x1

15x2

12x35x3xx 91 2 3st.

5x6x15x151 2 32xxx,1 2

x53

x,x01 2 3jj求下表中a～ljjcj（a）－1200CBXBbx1x2x3x4x50x46（b）（c）（d）100x51-13（e）01（a）-1200（a）x1（f）（］2-11/200x54（h）（I）11/210-7（j）（k）（l）3020人，周日去植樹。根據(jù)經(jīng)驗，一天男生平均每人挖坑20個，3025102015棵樹澆水。問應(yīng)怎樣安排，才能使植樹（包括挖坑、栽樹、澆水）模型，不必求解。某糖果廠用原料A、、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中ABC價如下表所示。甲乙甲乙丙原料成本(元/千克)每月限量（千克）A≥60％≥15％2.002000B1.502500C≤20％≤60％1.001200加工費（元/千克）0.500.400.30售 價 3.402.852.257－12500月底已存貨200貨各多少，才能使總收入最多？請建立此問題的線性規(guī)劃模型。月份 7 8 9 10 11 12買進單價282425272323售出單價292426282225某廠接到生產(chǎn)AB兩種產(chǎn)品的合同，產(chǎn)品A200B300件。這兩種產(chǎn)A每件需要2小時，產(chǎn)品B每件需要4小時。機械加工階段又分粗加工和精加工兩道工序，每件產(chǎn)品A410B712170010003000小時。又加工費用在毛坯、粗加工、精加工時分別為每小時3元、32工階段允許設(shè)備可進行500小時的加班生產(chǎn)，但加班生產(chǎn)時間內(nèi)每小時增加額外成本4.,5元。試根據(jù)以上資料，為該廠制訂一個成本最低的生產(chǎn)計劃?；蛴梢粋€技工和兩個力工組成的小組來完成100804842和36100002000030000400800(第二章對偶與靈敏度分析寫出以下線性規(guī)劃問題的DLP1 2 minz＝2x＋2x＋1 2 1 2 x＋3x＋4x ≥21 2 1 2 st 2x＋x＋3x 1 2 1 2 x＋4x＋3x ＝1 2 x x x x 1 2 31 2 maxz＝5x＋6x＋1 2 1 2 x＋2x＋2x ＝51 2 1 2 st －x＋5x－x 1 2 1 2 4x＋7x＋3x 1 2 2 x1無約束，x≥0，x2 11 22 3maxz＝cx＋cx＋11 22 3a x＋a x＋a x ≤b111 122 133 1st a x a x a x st a x a x a x 211 222 233 2a x a x a x a x a x a x 311 322 333 3x x x x 1 2 3LP：1 2 3 minz＝2x＋3x＋5x＋1 2 3 1 2 3 x＋2x＋3x＋x ≥21 2 3 1 2 3 st －2x＋x－x＋3x 1 2 3 x≥0（j=1,2,3,4）xj寫出DLP；用圖解法求解DLP；2）的結(jié)果及根據(jù)對偶性質(zhì)寫出原問題的最優(yōu)解。LP：1 2 maxz＝x＋2x＋1 2 x x ＋ － ≤2x x 1 2 31 2 1 2 st x－x＋x 2x＋x＋1 2 1 2 x x x x 1 2 3DLP；利用對偶問題性質(zhì)證明原問題目標函數(shù)值Z≤1LP：maxz＝x1＋x2－x1＋x2＋x3 ≤2st －2x1＋x2－x3 ≤1xj≥0試根據(jù)對偶問題性質(zhì)證明上述線性問題目標函數(shù)值無界。LP：1 2 3 maxz＝2x＋4x＋x＋1 2 3 x 1 2 x＋3x ＋x ≤82＋ x 1 2 1 23 st. x2＋x＋x3 x x x x 1 2 3x≥0xj寫出DLP；已知原問題最優(yōu)解X（2,4,用對偶單純形法求解下列線性規(guī)劃問題1 2 1) minz＝4x＋12x＋1 2 x1 ＋3x3 ≥3st 2x2＋2x3 ≥5x≥0(j=1,2,3)xj2)minz5x1

2x2

4x33xx2x4st 1 2 3.6x3x5x

10x1 2 3,x,x01 2 3st1)2)3)4)1)2)3)

考慮如下線性規(guī)劃問題1 2 1 2 1 2 1 2 minz＝60x＋40x＋80x3x＋2x＋x 4x＋x＋3x 2x＋2x1 2 1 2 1 2 1 2 x≥0xj寫出DLP；用對偶單純形法求解原問題；用單純形法求解其對偶問題；對比以上兩題計算結(jié)果。1 2 已知LP：maxz＝2x－x＋1 2 x x ＋ ＋ ≤6x x 1 2 31 st －x＋2x 1 x x ，，x x 1 2 3用單純形法求最優(yōu)解1 2 分析當目標函數(shù)變?yōu)閙axz＝2x＋3x＋x31 2 給出線性規(guī)劃問題2 1 2 maxz＝2x＋3x＋x1/3x1＋1/3x＋1/3x2 1 2 2 st 1/3x1＋4/3x＋7/3x2 x≥0xj用單純形法求解得最終單純形表如下cj23100CBXBBx1x2x3x4X52x1110－14－13x22012－11j00－3－5－1試分析下列各種條件下，最優(yōu)解（基）的變化：目標函數(shù)中變量x36；1分別確定目標函數(shù)中變量x1x2的系數(shù)CC2在什么范圍內(nèi)變動時最優(yōu)解不變；1約束條件的右端由 1 變?yōu)?2 ；3 3某廠生產(chǎn)甲、乙兩種產(chǎn)品，需要A、B兩種原料，生產(chǎn)消耗等參數(shù)如下表（/件。產(chǎn)品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0銷售價（元）1316請構(gòu)造數(shù)學模型使該廠利潤最大，并求解。原料A、B的影子價格各為多少?，F(xiàn)有新產(chǎn)品丙，每件消耗3千克原料A4千克原料B少為多少時才值得投產(chǎn)。工廠可在市場上買到原料A題最優(yōu)基的不變的情況下，最多應(yīng)購入多少？可增加多少利潤？3.5某玩具公司分別生產(chǎn)三種新型玩具，每月可供量分別為1000、2000、2000件，它們分別被送到甲、乙、丙三個百貨商店銷售。已知每月百貨商店各類玩具預(yù)期銷售量均為1500見下表。又知丙百貨商店要求至少供應(yīng)C1000A分配方案。甲乙丙可供量A54－1000B16892000C1210112000第三章運輸問題根據(jù)下表，用表上作業(yè)法求最優(yōu)解。BB1B2B3B4AAA123銷量413612754556601388420根據(jù)下表，用表上作業(yè)法求最優(yōu)解。BB1B2B3B4AAA123銷量945139738462752533511求給出的產(chǎn)銷不平衡問題的最優(yōu)解BB1B2B3B4AAA123產(chǎn)量859銷量511941287335154956食品廠123面粉廠產(chǎn)值某市有三個面粉廠，他們供給三個面食加工廠所需的面粉，各面粉廠的產(chǎn)量、各面食加23面食加工廠制作單位面粉食品的利潤分別為121611食品廠123面粉廠產(chǎn)值面粉廠131022024118303811420銷量152520光明儀器廠生產(chǎn)電腦繡花機是以產(chǎn)定銷的。已知16和單臺電腦繡花機平均生產(chǎn)費用見下表：1月份正常生產(chǎn)能力（臺）60加班生產(chǎn)能力（臺）10銷量（臺）104單臺費用（萬元）152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.5已知上年末庫存103臺繡花機，如果當月生產(chǎn)出來的機器當月不交貨，則需要運到分廠庫房，0.1,0.27--8月份銷16月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機器每臺增加成本1萬元。問應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費用（倉儲、維護）最少？設(shè)有AC三個化肥廠供應(yīng)4數(shù)據(jù)如下表：1234產(chǎn)量A1613221750B1413191560C19202350最低需要量3070010最高需要量507030不限試求總費用為最低的化肥調(diào)撥方案第四章 動態(tài)規(guī)劃現(xiàn)有天然氣站A，需鋪設(shè)管理到用氣單位E各點是中間加壓站，各線路的費用如圖所標注（單位：萬元，試設(shè)計費用最低的線路。B1B11513C1752 D17A57B2105C214E1110B3634D2C3一艘貨輪在A港裝貨后駛往F港，中途需靠港加油、加淡水三次，從A港到F港3個碼頭F，試求最合30303030

1 2 3C150206030F1A5045B1B230604030C2C3405025D1D22040F2F3F《運籌學》習題集4ABC求最大回報。投資額及收益0101234A041486066B042506066C0646878761000S1與投入機器數(shù)Y1的關(guān)系為0.7S2與投入機器數(shù)Y2的關(guān)系為S2＝5Y2，機器0.9；請制定一個五年計劃，使總產(chǎn)量最大。31 2 3 3AA的生產(chǎn)成本費用為x2xA13個月的需求量分d?，F(xiàn)設(shè)開始時第一個月月初存貨s＝0，第三個月的月末存s31 2 3 1所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費為4，除了調(diào)度費用外，242所示。表1表26t，問應(yīng)運輸每種產(chǎn)品各多少件可使總利潤最大。產(chǎn)品重量（t/件）利潤（千元/件）128023130341809《運籌學》習題集《運籌學》習題集PAGEPAGE12用動態(tài)規(guī)劃方法求解maxz4x1

9x2

2x232x4x

10x 1x ,

2 3,x01 2 3第五章 存儲論800tt2000t0.2%300元，求最佳訂購批量、經(jīng)濟周期與最小費用。150，0000.2元，不允許缺貨，試比較每次訂購費為1,000元或100小費用。某拖拉機廠生產(chǎn)一種小型拖拉機，每月可生產(chǎn)1000需要量為每年4,00015,000為10元，允許缺貨（缺貨費為20臺月，求經(jīng)濟生產(chǎn)批量、經(jīng)濟周期與最小費用。81005元/月件。在不允許缺貨條件下，比較生產(chǎn)速度分別為每月20件和40經(jīng)濟周期與最小費用。4,00015010%500元。求：不允許缺貨條件下的最優(yōu)存貯策略；允許缺貨（100元/件年）條件下的最優(yōu)存貯策略。150件，訂購費為每次400元，存貯費為0.96元/件月，并不允許缺貨。求經(jīng)濟訂購批量、經(jīng)濟周期與最小費用；10%，求這時的最優(yōu)存貯策略。15,000801元/個年，不允1000510004.9元。求該公司的最優(yōu)采購策略。10,0002,000元，存貯費率為20%2,0001002,00080元。求最優(yōu)采購策略。批量（件）0≤Q＜10000 10000≤Q＜30000單價（元） 1.00 0.98批量（件）0≤Q＜10000 10000≤Q＜30000單價（元） 1.00 0.980.96Q≥500000.94EOQ訂購費、但