下述IP問題能否通過LP解的圓整而得最優(yōu)

習(xí)題六6.1下述IP問題能否通過LP解的圓整而得最優(yōu)？（1） maxz=3x什2x2‘2為+3x2蘭142為+x2蘭9s.t.論Z0,x2±0x1,x2為整數(shù)（2） maxz=3x什2x2”一4治+3x2蘭63捲+2x2蘭18s.t.x,^0,x2蘭0xnx2為整數(shù)6.2試用分支定界法求解下述IP問題。（1） maxz=5x1+8x2x1x2<65x19x^-45s.t.捲_0,x2_0x1,x2為整數(shù)（2） maxz=x1+x2"14%+9x2蘭51-6%+3x2蘭1s.t.c%Z0,x2狂0xnx2為整數(shù)（3） maxz=X1+2x2-2x<H4x2蘭12論+4x2蘭3s.t.2為+x2蘭3x1,x2為整數(shù)（4） maxz=X1-2x2-5捲+5x2蘭4-3x1+3x^1s.t.x^>0兇,x2為整數(shù)（5）maxz=3x1+2x2"2為—4x2+2x3 =54%+2x2 +2x4=3s.t.Xi,X2,X3,X4蘭0x2,x3為整數(shù)6.3試用割平面法求解下述IP問題。6.2題之(1);maxz=xi+x22Xr+x2蘭64為+5x2蘭20.t.%K0,x230X,x2為整數(shù)maxz=3xi+X2‘2%+x2蘭52xi—X2王2s.t.捲_0,x2_0x1,x2為整數(shù)6.4試建立下述問題的數(shù)學(xué)模型：（1）設(shè)有m臺(tái)同一類型的機(jī)床，有n（＞m）種零件各一個(gè)要在這些機(jī)床上加工，加工一個(gè)第 j種零件需要a機(jī)時(shí)。應(yīng)如何分配加工任務(wù)，才能使各機(jī)床的負(fù)荷盡可能均衡。（2）某省外貿(mào)局?jǐn)M從下列應(yīng)試者中招聘四名工作人員， 希望所招四人平均業(yè)務(wù)能力評(píng)分最高， 且滿足下述要求：①專業(yè)不得相同；②女性最多不超過二人；③至少有一名精通日語者；④精通英語者最多入選一人。姓名性別專業(yè)精通語種業(yè)務(wù)能力評(píng)分戴勝春男紡織英95楊光女機(jī)械英93馬躍男化工德87李玉芬女電子法87康平男機(jī)械日83姜潔女食品日73（3）某廠為生產(chǎn)某種新產(chǎn)品設(shè)計(jì)了三種生產(chǎn)方案，如下表所示:方案一次性投資（萬元）生產(chǎn)費(fèi)用（元/件）生產(chǎn)能力（萬件）I1058n16414出25322該產(chǎn)品銷價(jià)為每件10元。據(jù)市場(chǎng)調(diào)研，在該產(chǎn)品生命周期內(nèi)的需求量為 30萬見。應(yīng)如何擬訂生產(chǎn)計(jì)劃能使經(jīng)濟(jì)效益最佳？（4）某石油化學(xué)工業(yè)公司的某項(xiàng)產(chǎn)品售價(jià)為每公升 1.20元，產(chǎn)量隨生產(chǎn)過程中溫度的升高而增加，其數(shù)量關(guān)系如圖6-15所示。假定產(chǎn)品成本與生產(chǎn)中的溫度成正比，每提高一度的費(fèi)用為 30元，則應(yīng)生產(chǎn)多少公升該項(xiàng)產(chǎn)品，才能使利潤(rùn)為最大？

02402468圖6-15公升*102（5）考慮1.2題之（2）o假定預(yù)計(jì)明年A,B,C三市用煤量分別增加8,10,12萬噸。計(jì)劃部門為了使產(chǎn)銷平衡，打算增加一套年產(chǎn)30萬噸煤的成套設(shè)備，這套設(shè)備安放到甲，乙煤礦，年產(chǎn) 30萬噸煤所增加的生產(chǎn)費(fèi)用分別為20,25萬元。應(yīng)講設(shè)備撥給哪個(gè)煤礦，能使增加的總費(fèi)用（包括生產(chǎn)與運(yùn)輸兩部分）為最低?（6）某人要去A市探親，由于他已領(lǐng)取了個(gè)體經(jīng)營(yíng)（干鮮水果）的執(zhí)照，因此打算順便販運(yùn)本地產(chǎn)的橘子，香蕉兩種鮮果。橘子，香蕉在本地的購價(jià)分別為每箱 4,5元，每箱毛重分別為8，12公斤。由于春節(jié)將臨，因此他考慮兩種販運(yùn)方式：若乘飛機(jī)，能在除夕前趕到，從而能賣高價(jià)，且能保證果品無損；若乘輪船，則在初四趕到，只能賣中高價(jià)格，且因途中果品會(huì)有損傷而使每箱收入減少 10%，有關(guān)數(shù)據(jù)如下表所示。另外，他已決定要用相當(dāng)于毛重各為半箱數(shù)量的橘子，香蕉饋贈(zèng)親友，而且途中要攜帶 2公斤的生活日用品。問他應(yīng)乘坐哪種交通工具且攜帶兩種果品各多少箱，才能使這次販運(yùn)預(yù)計(jì)盈利最高。販運(yùn)方式單程票價(jià)（元）免費(fèi)攜重（公斤）超重收費(fèi)（元/公斤）限重（公斤）限容（箱數(shù)）A市時(shí)價(jià)（元/箱）橘子香蕉飛機(jī)450101.005052428輪船60300.401001020236.5考慮下述數(shù)學(xué)模型minz=^（xj*f2（x2）滿足下述約束條件：（1） 非x^-10即x2亠10；（2） 下列不等式至少有一個(gè)成立:（3） 咅—X2|=0獲5，或10；(4)捲-0,x2-0；其中:20其中:205x-!,x1 00,x^=0126x2,x2 0f2（X2）0,x2=0試把此模型化為一個(gè)混合整數(shù)規(guī)劃模型。6.6試用異序枚舉法求解下述0-1規(guī)劃：（1） maxz=3xr2x2+5x3x<|+2X2—X3蘭2%+4x2+x3蘭4s.t. x1 x2 -34x2+x3蘭6Xj=0或1,j=1,2,3（2） minz=4x1+3X2+3X32為一5X2+3x3蘭44為+X2+3x3^3X2+X3色1Xj=0或1,j=1,2,3（3） minz=2x1+5x2+3x3+4x4一咅+x2+x3+x4X0一2捲+4x2+2x3+4x4蘭4s.t.片+x2_X3+X4蘭1Xj=0或1,j=1,2,3（4） maxz=8x什2x2-4xs-7x4-5x53%+3x2+x3+2x4+3x5蘭4s.t.$5^+3x2—2x3—X4+疋蘭4Xj=0或1,j=1,2,3,4,5（5） minz=2x1-x2+5x3-3x4+4x53%-2x2+7x3-5x4+4x5蘭6s.t.%-x22x3-4x42x^-0Xj—0^或1,j=1,2,3,4,5（6） minz=5x什6x2+7x3+8x4+9x53為_x2+x3+&_2x5Z2嚴(yán)+3X2—X3—2x4十卷王0一％-x2+3x3+x4+疋色1Xj=0或1,j=1,2,3,4,56.7試用分支定界法求解上題中的（3）-（6）。6.8證明匈牙利法的定理1，畫岀匈牙利法計(jì)算步驟的框圖。6.9某廠擬用五臺(tái)機(jī)床加工五種零件，其加工費(fèi)（元）如下表所示。若每臺(tái)機(jī)床只加工一種零件則應(yīng)如何

6.10五名游泳運(yùn)動(dòng)員的四種泳姿的百米最好成績(jī)?nèi)缦卤硎?。?yīng)從中選哪四個(gè)人組成一個(gè) 4X100米混合泳6.11五人翻譯五種外文的速度(印刷符號(hào) /小時(shí))如下表所示:人語種英俄日德 法甲900400600800500乙8005009001000600丙900700300500800丁400800600900500戊1000500300600800若規(guī)定每人專門負(fù)責(zé)一個(gè)語種的翻譯工作，那么，試解答下列問題：應(yīng)如何指派，使總的翻譯效率最高？若甲不懂德文，乙不懂日文，其他數(shù)字不變，則應(yīng)如何指派？若將效益陣中各數(shù)字都除以100,然后求解，問最優(yōu)解有無變化？為什么？6.12某運(yùn)輸隊(duì)有五量汽車，待駛往三個(gè)目的地送貨。一地的貨物只需一輛汽車運(yùn)送，其運(yùn)費(fèi)(元)如下表(2) 若表中數(shù)字表示所得利潤(rùn)，則應(yīng)如何調(diào)運(yùn)？⑶若車2載不A地所需貨物，車5載貨時(shí)爬不上通往B地必由之路上的山坡，則對(duì)(1)、(2)之最優(yōu)解各有何影響？6.13某廠人事部門擬選拔四人分別擔(dān)任生產(chǎn)、技術(shù)、行政、后勤四個(gè)部門的領(lǐng)導(dǎo)工作。經(jīng)過反復(fù)篩選，最

后確定從下表所示六名人選中產(chǎn)生。根據(jù)群眾和不同部門、不同層次的干部對(duì)這六人在有關(guān)四個(gè)方面的能力與績(jī)效進(jìn)行考