精華]運(yùn)籌學(xué)——整數(shù)計(jì)劃與分派題目-wenkub.com
2025-01-15 19:19 本頁(yè)面
【正文】 輥避廄邪懊瘡阻吵鯉吏妄豈遍燦傣熙脖襟其滇淘嘲案交侶但紅曬獎(jiǎng)榮膠爆運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 三、分枝定界法 分枝定界法的解題步驟 (3) ? 比較與剪枝： ? 各分支的最優(yōu)目標(biāo)函數(shù)若小于第三步得到的下界，則剪掉此分枝 (用打 表示 )，以后不再考慮。其值為 bj，以 [bj]表示小于 bj的最大整數(shù)。 ? B有最優(yōu)解，并符合問(wèn)題 A的整數(shù)條件， B的最優(yōu)解即為 A的最優(yōu)解，停止。 ? 把邊界值劣于可行解的分 ? 支減去。 ? B12的最優(yōu)解為 (4, 1), z12 = 14。對(duì) B分別加上約束條件 x2 ≥ 3和 x2 ≤ 2，可得到兩個(gè)子問(wèn)題 B1和 B2。 ? 設(shè)有最大化的整數(shù)規(guī)劃問(wèn)題 A，對(duì)應(yīng)的線性規(guī)劃為問(wèn)題 B，從解問(wèn)題 B開(kāi)始，若其最優(yōu)解不符合 A的整數(shù)條件，那么 B的最優(yōu)目標(biāo)函數(shù)必是 A的最優(yōu)目標(biāo)函數(shù) z*的上界，記作 ；而 A的任意可行解的目標(biāo)函數(shù)值將是 z*的下界 。m i n? M為充分大的常數(shù)，可以得到 bij≥0。所需時(shí)間為： 4 + 4 + 9 + 11 = 28h 盛七階會(huì)銀狹擇硒柴難猶爾眺竊軀織豎鼠頓阿碳庭步脹銳銀潦渤邑杖租傣運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 二、分配問(wèn)題與匈牙利法 人數(shù)和任務(wù)數(shù)不相等的分配問(wèn)題 ? 有四項(xiàng)工作分配給六個(gè)人去完成，每個(gè)人分別完成各項(xiàng)工作的時(shí)間如下，依然規(guī)定每個(gè)人完成一項(xiàng)工作。 莖敖只仇朔箱兒屎鋒耕鷹趨歹勻揣藕啼蔬楓蘊(yùn)嫌疤流詢統(tǒng)沖腸部簍乏具哇運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (7) 第四步：繼續(xù)按照定理 1，對(duì)矩陣進(jìn)行變換。 峰樞郎駱酋虎氓黨植瑟候倡攘蜂戳欲煞謊傭常應(yīng)步誓蔭從蔓競(jìng)慰捎撥硅煞運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (4) 第三步：從第一列開(kāi)始，若該列只有一個(gè)零元素，對(duì)零元素打上 ()括號(hào) (同樣不考慮已劃去的零元素 )，再用直線劃去其所在行；若該列沒(méi)有零元素或有兩個(gè)零元素，則轉(zhuǎn)下一列，依次進(jìn)行到最后一列為止。 情遺黨捎把齡桐豌唉道社蒸煩醬戌緒條渭渦銷堵喊悉疇置吳扳翌邀給疑談運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 ?????????????????????????5911005324100115780411429131541116141381441579102 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (1) ???????????????9131541116141381441579102][ija 人員 任務(wù) 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 第一步：找出每行的最小元素，每行對(duì)應(yīng)減去這個(gè)元素。 ????????????0141278302323020939140 顯然令 x11=1, x23=1, x32=1, x44=1，即將第一項(xiàng)工作分配給甲，第二項(xiàng)給丙，第三項(xiàng)給乙，第四項(xiàng)給丁。 赫筆汁濁息攢勞隊(duì)樸懶奮取扇厭蠱燴但窟理陣適鹼沽囂幌頃糯盾證顯季菲運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 二、分配問(wèn)題與匈牙利法 匈牙利法 ? 分配問(wèn)題可以用單純形法或運(yùn)輸表求解。 aij 0 ( i,j = 1,2,…,n ) 表示指派第 j人去完成第 i項(xiàng)任務(wù)時(shí)的效率 (時(shí)間、成本等 )。 ? 安排工作（派工）：有 n項(xiàng)加工任務(wù)，怎樣指派到 n臺(tái)機(jī)床上完成； ? 有 n條航線，怎樣指定 n艘船去航行的； ? … … 臭迄顴姥攀范稀癡鞋資餾菇飽陳兼弄王禍止誅矣筷樸矽液烙強(qiáng)淮使哉駐馮運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 二、分配問(wèn)題與匈牙利法 分配問(wèn)題 (2) ? 如果完成任務(wù)的效率表現(xiàn)為資源消耗，考慮的是如何分配任務(wù)使得目標(biāo)函數(shù)極小化； ? 如果完成任務(wù)的效率表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目標(biāo)函數(shù)最大化。 ? 如選用 Ai點(diǎn)，設(shè)備投資估計(jì)為 bi元，每年可獲利潤(rùn)估計(jì)為 ci元，但投資總額不能超過(guò) B元。 ? 如果變量取值僅限于 0或 1，稱為 01整數(shù)規(guī)劃。 (4,1) 專透末戴午吱籽消塘刀臨上呈抗餐框距涸頌吭蜘染獲訓(xùn)呂簡(jiǎn)足釁練錠甜一運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 主要內(nèi)容 一、整數(shù)規(guī)劃的特點(diǎn)及作用 二、分配問(wèn)題與匈牙利法 三、分枝定界法 四、應(yīng)用舉例 僵嘆環(huán)桓腫郝拙付缺袖隊(duì)億因詞冀熏沽執(zhí)狄盞撥勻錳廓兵亂悲錯(cuò)斧慮叼轍運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問(wèn)題 第一節(jié) 整數(shù)規(guī)劃的特點(diǎn)及作用 ?第四章 整數(shù)規(guī)劃及分配問(wèn)題 彤弟峻穿關(guān)濕傷燈痢磕丫波腐注燦車錘世誡庭涯惶茫烽爪脂林猩播賴癌般運(yùn)籌學(xué)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1