第一章-線性規(guī)劃與單純形法

檔，歡迎下載第一章習(xí)題思考題(1)微分學(xué)求極值的方法為什么不適用于線性規(guī)劃的求解？(2)線性規(guī)劃的標(biāo)準(zhǔn)形有哪些限制？如何把一般的線性規(guī)劃化為標(biāo)準(zhǔn)形式？(3)圖解法主要步驟是什么？從中可以看出線性規(guī)劃最優(yōu)解有那些特點(diǎn)？(4)什么是線性規(guī)劃的可行解，基本解，基可行解？引入基本解和基可行解有什么(5)對(duì)于任意基可行解，為什么必須把目標(biāo)函數(shù)用非基變量表示出來(lái)？什么是檢驗(yàn)(6)確定換出變量的法則是什么？違背這一法則，會(huì)發(fā)生什么問(wèn)題？(7)如何進(jìn)行換基迭代運(yùn)算？(8)大M法與兩階段法的要點(diǎn)是什么？?jī)烧哂惺裁垂餐c(diǎn)？有什么區(qū)別？(9)松弛變量與人工變量有什么區(qū)別？試從定義和處理方式兩方面分析。(10)如何判定線性規(guī)劃有唯一最優(yōu)解，無(wú)窮多最優(yōu)解和無(wú)最優(yōu)解？為什么？2.建立下列問(wèn)題的線性規(guī)劃模型：(1)某廠生產(chǎn)A，B，C三種產(chǎn)品，每件產(chǎn)品消耗的原料和設(shè)備臺(tái)時(shí)如表1-18所示：ABC耗235機(jī)時(shí)單耗36潤(rùn)最大的模型。錫的比例為3：2：5。12345g(3)某醫(yī)院每天各時(shí)間段至少需要配備護(hù)理人員數(shù)量見(jiàn)表1-20。26:00－10:000:00－14:004:00－18:008:00－22:0022:00－2:002:00－6:00123456假定每人上班后連續(xù)工作8小時(shí)，試建立使總?cè)藬?shù)最少的計(jì)劃安排模型。能否利用(4)某工地需要30套三角架，其結(jié)構(gòu)尺寸如圖1-6所示。倉(cāng)庫(kù)現(xiàn)有長(zhǎng)6.5米的鋼3.用圖解法求下列線性規(guī)劃的最優(yōu)解：12(x+2x12x,6|-x1+x2512|12檔，歡迎下載 11212 4.把下列線性規(guī)劃化為標(biāo)準(zhǔn)形式：12312(x+x-x1(x+2x8|2x1+x-x34-2|-1x+2x1123412x13-12341231212126.求出下列線性規(guī)劃的所有基本解，并指出其中的基可行解和最優(yōu)解。12(x+x=48|12x3+x=12j：(1)()212maxz=2x+x4(3)()4xx-x+x60檔，歡迎下載(1)()212123xxxxx|x1x21|2x1+x234123(3)()4xxx,xx202|x1,1x2,x32,x449.對(duì)于問(wèn)題(AX=b〈X0 (2)如果X，X均為最優(yōu)解，則對(duì)于α∈[0，1]，αX+(1－α)X均為最優(yōu)解。121210.用單純形法求解問(wèn)題2(4)(合理下料問(wèn)題)。456xx6-1-2x421cjXBxxx12x3CB2b242x2x1x5j25(1)把表中缺少的項(xiàng)目填上適當(dāng)?shù)臄?shù)或式子。使上表成為最優(yōu)表，a應(yīng)滿足什么條件？(3)何時(shí)有無(wú)窮多最優(yōu)解？(4)何時(shí)無(wú)最優(yōu)解？檔，歡迎下載(5)何時(shí)應(yīng)以x替換x？31檔，歡迎下載題思考題(1)如何在以B為基的單純形表中，找出B－1？該表是怎樣由初始表得到的？(2)對(duì)偶問(wèn)題的構(gòu)成要素之間，有哪些對(duì)應(yīng)規(guī)律？(3)如何從原問(wèn)題最優(yōu)表中，直接找到對(duì)偶最優(yōu)解？(4)敘述互補(bǔ)松弛定理及其經(jīng)濟(jì)意義。(5)什么是資源的影子價(jià)格？它在經(jīng)濟(jì)管理中有什么作用？(6)對(duì)偶單純形法有哪些操作要點(diǎn)？它與單純形法有哪些相同，哪些地方有區(qū)別？(7)靈敏度分析主要討論什么問(wèn)題？分析的基本思路是什么？四種基本情況的分析請(qǐng)把表中空白處的數(shù)ccj2-11000CXbxxxxxxBB1234560x43111000x51-120100x611-1001σ2-110000x4-1-22x1-1x2σ5-1/2jj的最終表是表2-22：x0030j4-1/2-1/2-1/2-1/25-1/2b01-2000000-2x0x0x0xxxxcCXj11BB223145(2)求初始表。4.寫出下列線性規(guī)劃的對(duì)偶問(wèn)題：檔，歡迎下載23|-1x+x-34x>11231234jjijij5.已知線性規(guī)劃?rùn)n，歡迎下載112233(ax+ax+axb|x2x1,x222332(1)寫出它的對(duì)偶問(wèn)題；(2)引入松弛變量，化為標(biāo)準(zhǔn)形式，再寫出對(duì)偶問(wèn)題；(3)引入人工變量，把問(wèn)題化為等價(jià)模型：11223367(ax+ax+axx+x=b|xx22233572面三個(gè)對(duì)偶問(wèn)題是完全一致的。由此，可以得出什么樣的一般結(jié)論？6.利用對(duì)偶理論說(shuō)明下列線性規(guī)劃無(wú)最優(yōu)解：123(x+x+x412345ccjCXbxxxxxBB12345x3010x11-1/20-1/6σ00-2jj(1)求價(jià)值系數(shù)c和原線性規(guī)劃；j(2)寫出原問(wèn)題的對(duì)偶問(wèn)題；(3)由表2-23求對(duì)偶最優(yōu)解。8.已知線性規(guī)劃問(wèn)題檔，歡迎下載1234(x+2x+x>3(1)寫出對(duì)偶問(wèn)題；(2)已知原問(wèn)題的最優(yōu)解為X*=(1，1，2，0)T，求對(duì)偶問(wèn)題的最優(yōu)解。9*.已知線性規(guī)劃123xxx33(1)寫出對(duì)偶問(wèn)題；(2)求對(duì)偶問(wèn)題最優(yōu)解。單純形法解下列各線性規(guī)劃：x123xxx(3x+x+2x>4312311.設(shè)線性規(guī)劃問(wèn)題jj〈ijji〈ijji12m檔，歡迎下載jjj=1與(2.41)是等價(jià)的，兩者有相同的最優(yōu)解，請(qǐng)說(shuō)明(2.42)的m種資源的影子價(jià)12m12m12*.已知線性規(guī)劃1234(2x+2x+x-x>3|123412341234(1)寫出對(duì)偶問(wèn)題，用圖解法求最優(yōu)解；(2)利用對(duì)偶原理求原問(wèn)題最優(yōu)解。13.線性規(guī)劃23x2135-3j1111-2b60000x0x0x2x20xxcCXj11BB435 (1)x的系數(shù)c在何范圍內(nèi)變化，最優(yōu)解不變？若c=3，求新的最優(yōu)解；222(3)增加新約束－x+2x≥2，求新的最優(yōu)解；13(3)增加新約束－x+2x≥2，求新的最優(yōu)解；13檔，歡迎下載(-1)(4)增加新變量x6，其系數(shù)列向量P6=|(2)|，價(jià)值系數(shù)(-1)耗耗定AB產(chǎn)品價(jià)格量產(chǎn)額消原555341634(1)建立使總產(chǎn)值最大的線性規(guī)劃模型；(2)求最優(yōu)解，并指出原料A，B的影子價(jià)格；(3)產(chǎn)品甲的價(jià)格在什么范圍內(nèi)變化，最優(yōu)解不變？BA廠(6)由于某種原因，該廠決定暫停甲產(chǎn)品的生產(chǎn)，試重新制定最優(yōu)生產(chǎn)計(jì)劃。121212檔，歡迎下載第三章習(xí)題1．表3—35和表3—36分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量，以及各產(chǎn)地至各銷地的單位運(yùn)價(jià)，試用表上作業(yè)法求最優(yōu)解。表3—35A1A2A3B2637B1359B4648B3267-36A1A2A3B1978B2523B3674B47682．試求表3-37給出的產(chǎn)銷不平衡運(yùn)輸問(wèn)題的最優(yōu)解。37A1A2A37573832724926354BBBB42313．如表3-38所示的運(yùn)輸問(wèn)題中，若產(chǎn)地I有一個(gè)單位物資未運(yùn)出，則將發(fā)生儲(chǔ)存費(fèi)用。假定1，2，3產(chǎn)地單位物資儲(chǔ)存費(fèi)用分別為5，4和3。又假定產(chǎn)地2的物資至少運(yùn)出38個(gè)單位，產(chǎn)地3的物資至少運(yùn)出27個(gè)單位，試求解此運(yùn)輸問(wèn)題的最優(yōu)解。表3—38123A112C253B2431234檔，歡迎下載件?？蛻鬊,B在了解到公司完成訂貨任務(wù)后，產(chǎn)品有1000件剩余，因此都想增加訂12貨購(gòu)買剩余的1000件產(chǎn)品。公司賣給客戶的產(chǎn)品利潤(rùn)(元/件)見(jiàn)表3-39。公司如何安排潤(rùn)最大。-39A1A2A3B189B4768B2523B36745．某電站設(shè)備制造廠根據(jù)合同要從當(dāng)年起連續(xù)三年末各提供三種規(guī)格型號(hào)相同的大型電站設(shè)備。已知該廠這三年內(nèi)生產(chǎn)大型電站設(shè)備的能力及每套電站設(shè)備成本如表3-40正正常生產(chǎn)時(shí)間內(nèi)年度可完成的電站設(shè)122431加班生產(chǎn)時(shí)間內(nèi)可完成的電站設(shè)323正常生產(chǎn)時(shí)每套成本(萬(wàn)元)已知加班生產(chǎn)時(shí)，每套電站設(shè)備成本比正常生產(chǎn)時(shí)高出70萬(wàn)元，又知造出來(lái)的電站設(shè)備如當(dāng)年不交貨，每套每積壓一年造成積壓孫]視為40萬(wàn)元。在簽訂合同時(shí)，該廠已積壓了兩套未交貨的電站設(shè)備，而該廠希望在第三年末完成合同后還能儲(chǔ)存一套備用。問(wèn)該廠如何安排每年電站設(shè)備的生產(chǎn)量，使在滿足上述各項(xiàng)要求的情況下，總的生產(chǎn)費(fèi)用檔，歡迎下載第四章習(xí)題B620Ⅰ(小時(shí)/臺(tái))Ⅱ(小時(shí)/臺(tái))利潤(rùn)(元/臺(tái))每周最大加工能力A43如果工廠經(jīng)營(yíng)目標(biāo)的期望值和優(yōu)先等級(jí)如下：123希望工序Ⅰ的每周生產(chǎn)時(shí)間正好為150小時(shí)，工序Ⅱ的生產(chǎn)時(shí)間最好用足，甚試建立這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型。2.在上題中，如果工序Ⅱ在加班時(shí)間內(nèi)生產(chǎn)出來(lái)的產(chǎn)品，每臺(tái)A型機(jī)減少利潤(rùn)10p級(jí)目標(biāo)，試建立這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型。43.用圖解法解下列目標(biāo)規(guī)劃模型。1122334(x+x+dd+=400111223(15x+25x+dd+=600|x3x2+d1d1+=60s.t.〈12221212ii4.用目標(biāo)規(guī)劃的單純形方法解以下目標(biāo)規(guī)劃模型。檔，歡迎下載112332412(2x+x+dd+=20|x12+d1d1+=12st22x,x12iid112233441(x+x+dd+=1003(x10x+dd+=50x+d1d1+=20s.t.〈122212ii2233(5x+5x+4x+dd+=100|x1+x2+3x3+dd=20s.t.〈12322iii(a)求該目標(biāo)規(guī)劃問(wèn)題的滿意解；(b)若約束右端項(xiàng)增加Δb=(0，0，5)T，問(wèn)滿意解如何變化？11233(d)若第二個(gè)約束右端項(xiàng)改為45，則滿意解如何變化？6.某紡織廠生產(chǎn)兩種布料，一種用來(lái)做服裝，另一種用來(lái)做窗簾。該廠實(shí)行兩班生檔，歡迎下載p：每周必須用足80小時(shí)的生產(chǎn)時(shí)間；1p：每周加班時(shí)數(shù)不超過(guò)10小時(shí)；2p：每周銷售窗簾布70000米，衣料布45000米；3p：加班時(shí)間盡可能減少。4試建立這個(gè)問(wèn)題的目標(biāo)規(guī)劃模型。檔，歡迎下載第五章習(xí)題1231012101783455678備選校址代號(hào)備選校址代號(hào)覆蓋的居民小區(qū)編號(hào)675547329438455.4用分支定界法求解下列整數(shù)規(guī)劃問(wèn)題(1)maxz=x+x檔，歡迎下載||平面法求解下列整數(shù)規(guī)劃問(wèn)題312x123452345xxx別如下：(3 (9973987(3 (997398744 |9|||||||5|5|||。趙趙錢張王周仰泳蛙泳.4.28蝶泳5.9分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如表5-15所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案。檔，歡迎下載甲乙丙丁ABDEC5.10從甲、乙、丙、丁、戊五個(gè)人中挑選四人完成四項(xiàng)工作。已知每人完成各項(xiàng)成，每個(gè)人最多承擔(dān)一在滿足上述條件下，如何分配工作，使完成四項(xiàng)工作總的花費(fèi)時(shí)間最少。12345乙25丙3丁276戊9485.11運(yùn)籌學(xué)中著名的旅行商販(貨朗擔(dān))問(wèn)題可以敘述如下：某旅行商販從某一城市出發(fā)，到其他幾個(gè)城市推銷商品，規(guī)定每個(gè)城市均需到達(dá)且只到達(dá)一次，然后回到原出發(fā)使總的旅程最短。試對(duì)此問(wèn)題建立整數(shù)規(guī)劃模型。檔，歡迎下載第七章習(xí)題1.求下列網(wǎng)絡(luò)圖從起點(diǎn)到終點(diǎn)的最短路線及長(zhǎng)度。1DBBA22EED2D2B3B33G4G4BF135F FA22244768FDFD3用動(dòng)態(tài)規(guī)劃方法求解下列問(wèn)題：123(x+x+xajj123jj123(x+x+x6jj11222x,2檔，歡迎下載3.某公司擬投資600萬(wàn)元對(duì)下屬四個(gè)工廠進(jìn)行技術(shù)改造，各工廠改造后的利潤(rùn)與投工工投廠資額01234560000總利潤(rùn)最大？最大利潤(rùn)是零零售店數(shù)0123456202468904677774045666630357888箱5.設(shè)某機(jī)器可在高、低不同負(fù)荷下生產(chǎn)。若機(jī)器在高負(fù)荷下生產(chǎn)，則產(chǎn)品的年產(chǎn)量四年計(jì)劃，每年年初分配完好機(jī)器在不同負(fù)荷下工作，使四年總產(chǎn)量達(dá)到最大。6.某廠生產(chǎn)一種產(chǎn)品，該產(chǎn)品在未來(lái)4個(gè)月的銷售量估計(jì)如表7-24所示。該產(chǎn)品銷售量(百件)4422533檔，歡迎下載進(jìn)價(jià)和售價(jià)如表7-25所示。問(wèn)如何安排進(jìn)貨量和銷售量，使該公司獲得最大利潤(rùn)(假設(shè)四月底庫(kù)存為零)。1234進(jìn)價(jià)(百元/件)998.某人外出旅游，需將5種物品裝入包裹，包裹容量有限，總重量不能超過(guò)13公？ABCDE單件重量(kg)75431單件價(jià)值(元)9432123使設(shè)備的可靠性達(dá)到最大(不考慮重量的限制)。單價(jià)(元單價(jià)(元)D1D2D3檔，歡迎下載第八章習(xí)題1.用破圈法和避圈法求下圖的最小生成樹VVVV25V6V6V8VVV8VV445VVV2.求下列各圖的最小生成樹7312731212344641446433(2)474(2)474162745437 (3)3．寫出下面各圖中的頂點(diǎn)數(shù)、邊數(shù)及頂點(diǎn)的次數(shù)，哪些是簡(jiǎn)單圖。VVV4V6VV3V2V1VVVV5VVVVV563V9V4VV9V4VV643V3VVV7問(wèn)從水源經(jīng)1號(hào)村鎮(zhèn)鋪設(shè)輸水管道將各村鎮(zhèn)連接起來(lái)，應(yīng)如何鋪設(shè)使輸水管道最短(為便于管理和維修，水管要求在各村鎮(zhèn)處分開(kāi))。各村鎮(zhèn)間距離(單位：千米)從12345678578654326．用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流.V848檔，歡迎下載Vt檔，歡迎下載A2A2284VVVt3447．求下列網(wǎng)絡(luò)的最小費(fèi)用最大流.括號(hào)內(nèi)的兩個(gè)數(shù)字,前一個(gè)是單位流量的費(fèi)用,后一個(gè)是該弧的流量.(2,3)VVVtVVtVt8.求解圖8—35中所示的中國(guó)郵遞員問(wèn)題(A點(diǎn)是郵局所在地)324222224235243檔，歡迎下載TT1212ijv1732S2T2S2143S2T2S28v2檔，歡迎下載33第九章習(xí)題dde2b(a)d2a3g38cf7(b)2d3b3cg4(c)絡(luò)圖。檔，歡迎下載abcdefgh－－－acdh－－aabcc3d5f423g3工時(shí)(d)A－F5D，EB－GC，F(xiàn)CA，