運籌學——整數(shù)規(guī)劃(編輯修改稿)
2025-08-28 15:22 本頁面
【文章內(nèi)容簡介】 x一、什么是 01整數(shù)規(guī)劃 第四節(jié) 01整數(shù)規(guī)劃 投資場所的選定－－相互排斥的計劃 例：某公司擬在市東、西、南三區(qū)建立門市部，擬議中有 7個位置 Ai(i=1,2,… ,7)可供選擇。規(guī)定 在東區(qū)，由 A1， A2， A3三個點中至多選兩個； 在西區(qū)，由 A4， A5兩個點中至少選一個； 在南區(qū)，由 A6， A7兩個點中至少選一個。 如選用 Ai點，設備投資估計為 bi元，每年可獲利潤估計為 ci元，但投資總額不能超過 B元。問應選擇哪個點可使年利潤最大？ 01規(guī)劃的實際問題： ,71 , 2 ,iA0A1x10iii ??????? 點沒被選用，當點被選用，當 令變量解：引入建模如下： ???71iii xcM a x Z???71iii Bxb2xxx 321 ???1xx 54 ??1xx 76 ??10x i 或?? st. 第四節(jié) 01整數(shù)規(guī)劃 相互排斥的約束條件 例：本章例 1中，關于貨運的體積限制為 5x1+4x2≤24 (車 )。今設運貨有車運和船運兩種方式，上面的條件系用車運時的限制條件，如用船運時關于體積的限制條件為 7x1+3x2≤45(船 )。（這兩條件是互相排斥的） 例 運甲、乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如右表所示。問兩種貨物各托運多少箱，可使獲得利潤為最大？ 貨物 甲 乙 托運限制 體 積 每箱（米 3） 5 4 24 重 量 每箱（百公斤） 2 5 13 利 潤 每箱（百元） 20 10 ?????????????????????變量為為整數(shù)10x,x0,135245372445s t .1020Ma x Z212121212121yxxxxxxxxxx解：設甲、乙兩種貨物的托運箱數(shù)分別為 x1,x2。 設變量 y表示運貨的方式，當 y為 1時，用車運， y為 0時，用船運。 +(1y)M +yM 第四節(jié) 01整數(shù)規(guī)劃 二、 01整數(shù)規(guī)劃的解法 ???????????????????????10,64 3 4422.5233213232321321321或例：求解下列問題xxxxxxxxxxxxxstxxxM a xZ隱枚舉法：只檢查變量取值的組合的一部分的方法。 ???????????????????????10,)(64 )(3 )(44)(22.5233213232321321321或例：求解下列問題xxxdxxcxxbxxxaxxxstxxxM a xZ(x1,x2,x3) Z值 a b c d 過濾條件 (0,0,0) 0 √ √ √ √ Z≥0 (0,0,1) 5 √ √ √ √ Z≥5 (0,1,0) 2 (0,1,1) 3 (1,0,0) 3 Z≥8 (1,0,1) √ √ √ √ (1,1,0) 8 1 (1,1,1) 6 按目標函數(shù)中各變量系數(shù)的大小重新排列各變量 最大化問題：由小到大 最小化問題：由大到小 第五節(jié) 指派問題 一、什么是指派問題 某單位需完成任務 n項任務，恰好有 n個人可承擔這些任務，由于每人的專長不同，各人完成不同任務效率也不同。于是產(chǎn)生應指派哪個人去完成哪項任務，使完成 n項任務的總效率最高。這類問題稱為 指派問題(分派問題、分配問題 ) B1 B2 Bn A1 c11 c12 c1n A2 c21 c22 c2n An 1 2 n 人 任務 ?? cij表示第 i個人完成第 j項任務的效率。 第五節(jié) 指派問題 二、指派問題的數(shù)學模型 ?????????????????? ???? ?10),2,1(1),2,1(1.111 1或ijnjijniijninjijijxnixnjxstxcM i n Z??????????????nnnnnnccccccccc???????212222111211=(Cij) B1 B2 Bn A1 c11 c12 c1n A2 c21 c22 c2n An 1 2 n 人 任務 ??解：設 ????????項任務去完成第個人不分配第項任務去完成第個人分配第jijixij ,0 ,1例：某單位現(xiàn)在Ａ、Ｂ、Ｃ、Ｄ四項工作需完成，現(xiàn)在甲、乙、丙、丁四個人均可完成這四項任務。每人完成各項任務所用的時間如右表所示，問應指派何人去完成何項任務，使所需時間最少？ 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 A B C D 任務 人員 ????????????9118713161491514410413152滿足所有約束條件的可行解 xij也可寫成表格或矩陣形式，稱為 解矩陣 ????????????10000001
公司管理相關推薦
鄂ICP備17016276號-1