運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題-展示頁(yè)
2025-05-26 22:11本頁(yè)面
【正文】 文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 二、分配問(wèn)題與匈牙利法 分配問(wèn)題實(shí)例 (2) ? 效率矩陣 用 [aij]表示。 ? 在分配問(wèn)題中，利用不同資源完成不同計(jì)劃活動(dòng)的效率，通常用表格形式表示為 效率表 ，表格中數(shù)字組成 效率矩陣 。 第二節(jié) 分配問(wèn)題與匈牙利法 第四章 整數(shù)規(guī)劃及分配問(wèn)題 二、分配問(wèn)題與匈牙利法 分配問(wèn)題 (1) ? 指派 n個(gè)人去完成 n項(xiàng)任務(wù)，使完成 n項(xiàng)任務(wù)的總效率最高 (或所需總時(shí)間最少 )，這類問(wèn)題稱為 指派問(wèn)題或分配問(wèn)題 。 ? 問(wèn)：應(yīng)如何 選址 ，可使年利潤(rùn)為最大？ 一、整數(shù)規(guī)劃的特點(diǎn)及作用 01整數(shù)規(guī)劃 ??????iijAAx不選選解：設(shè)0101整數(shù)規(guī)劃的一般形式 : ??????????????????????????)7,1(,01112:7654321772211772211???jxxxxxxxxBxbxbxbSTxcxcxcM a x Zj或???????),1(,01:njxbAxSTXCM a x ZjT?或01整數(shù)規(guī)劃一般都是純整數(shù)規(guī)劃。規(guī)定 ?在東區(qū)，由 A1， A2， A3三個(gè)點(diǎn)中至多選兩個(gè)； ?在西區(qū)，由 A4， A5兩個(gè)點(diǎn)中至少選一個(gè)； ?在南區(qū)，由 A6， A7兩個(gè)點(diǎn)中至少選一個(gè)。 一、整數(shù)規(guī)劃的特點(diǎn)及作用 01整數(shù)規(guī)劃 ? 某公司擬在市東、西、南三區(qū)建立門市部。 ?如果僅一部分決策變量為整數(shù)，則稱為 混合整數(shù)規(guī)劃。 ?如果所有的決策變量、技術(shù)系數(shù)和右端項(xiàng)都是非負(fù)整數(shù)，就稱為 純整數(shù)規(guī)劃。 湊整法求解：比較四個(gè)點(diǎn)（ 4 , 3） ,（ 4 , 2） ,（ 3 , 3） ,（ 3 , 2），前三個(gè)都不是可行解，第四個(gè)雖然是可行解，但 z=13 不是最優(yōu)解。 且最優(yōu)解未必在這些組合中。 例：某線性規(guī)劃問(wèn)題最優(yōu)解為 (x1, x2) = (, )，用湊整法需要比較與上述數(shù)據(jù)最接近的幾種組合： (4, 5), (4, 6), (5, 5), (5, 6)，共四種組合。 例：某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下表： 貨物 體積 米 3/箱 重量 百斤 /箱 利潤(rùn) 百元 /箱 甲 乙 5 4 2 5 20 10 托運(yùn)限制 24 13 問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得的利潤(rùn)為最大？ ????????????，且為整數(shù)， 013522445:102021212121xxxxxxSTxxM a x Z能否先不考慮對(duì)變量的整數(shù)約束，作為一般線性規(guī)劃來(lái)求解，當(dāng)解為非整數(shù)的時(shí)候可以用“ 四舍五入 ”或“ 湊整 ”方法尋找最優(yōu)解？ ?對(duì)于變量取值很大時(shí)，用上述方法得到的解與最優(yōu)解差別不大；但當(dāng)變量取值較小時(shí)，得到的解就可能與實(shí)際整數(shù)最優(yōu)解差別很大。 ?對(duì)于所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)、裝貨的車數(shù)、集裝箱數(shù)量等； ?對(duì)于一些決策變量必須取 Boolean值時(shí)，如要不要在某地建工廠，可選用一個(gè)邏輯變量 x，令 x=0表示不在該地建廠， x=1表示在該地建廠。 第四章 整數(shù)規(guī)劃與分配問(wèn)題 ? 對(duì)于線性規(guī)劃問(wèn)題，最優(yōu)解可能是分?jǐn)?shù)或小數(shù)。但是對(duì)于某些問(wèn)題，會(huì)要求解答必須是整數(shù)（稱為 整數(shù)解 ）。 ? 這時(shí)，分?jǐn)?shù)或小數(shù)的解就不合要求，我們稱這樣的問(wèn)題為 整數(shù)規(guī)劃。 ?當(dāng)問(wèn)題規(guī)模較大（決策變量較多）時(shí)，用“湊整”方法來(lái)算工作量很大。若問(wèn)題中有 10個(gè)整數(shù)變量，則解組合達(dá)到 210 = 1024個(gè)整數(shù)組合。 例：求整數(shù)規(guī)劃問(wèn)題的最優(yōu)解 ????????????且均取整數(shù)值 ,0, 143 223m a x21212121xxxxxxxxz解： 用圖解法得最優(yōu)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1