運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問題-在線瀏覽
2025-07-17 22:11本頁面
【正文】 解為（ , ） 如果不考慮整數(shù)約束（稱為整數(shù)規(guī)劃問題的 松弛問題 ） 最優(yōu)解為（ 4 , 1）， z*= 14。 (4,1) 主要內(nèi)容 一、整數(shù)規(guī)劃的特點(diǎn)及作用 二、分配問題與匈牙利法 三、分枝定界法 四、應(yīng)用舉例 第一節(jié) 整數(shù)規(guī)劃的特點(diǎn)及作用 第四章 整數(shù)規(guī)劃及分配問題 一、整數(shù)規(guī)劃的特點(diǎn)及作用 整數(shù)規(guī)劃的概念 ? 整數(shù)規(guī)劃 (Integer Programming) ：決策變量要求取整數(shù)的線性規(guī)劃。 ?如果所有的決策變量都是非負(fù)整數(shù)，技術(shù)系數(shù)和右端項(xiàng)為有理數(shù)，稱為 全整數(shù)規(guī)劃。 ?如果變量取值僅限于 0或 1，稱為 01整數(shù)規(guī)劃 。擬議中有 7個(gè)位置（點(diǎn)） Ai供選擇。 ? 如選用 Ai點(diǎn)，設(shè)備投資估計(jì)為 bi元，每年可獲利潤估計(jì)為 ci元，但投資總額不能超過 B元。 一、整數(shù)規(guī)劃的特點(diǎn)及作用 整數(shù)規(guī)劃的作用 ? 01整數(shù)規(guī)劃在管理領(lǐng)域具有重要作用 1. m個(gè)約束條件中只有 k個(gè)起作用； 2. 約束條件的右端項(xiàng)可能是 r個(gè)值 (b1, b2, … b r)中的某一個(gè)； 3. 兩組條件中滿足一組； 4. 用以表示含固定費(fèi)用的函數(shù)。 ? 安排工作（ 派工 ）：有 n項(xiàng)加工任務(wù)，怎樣指派到 n臺機(jī)床上完成； ? 有 n條航線，怎樣指定 n艘船去航行的； ? … … 二、分配問題與匈牙利法 分配問題 (2) ? 如果完成任務(wù)的效率表現(xiàn)為 資源消耗 ，考慮的是如何分配任務(wù)使得目標(biāo)函數(shù) 極小化 ； ? 如果完成任務(wù)的效率表現(xiàn)為 生產(chǎn)效率的高低 ，則考慮的是如何分配使得目標(biāo)函數(shù) 最大化 。 二、分配問題與匈牙利法 分配問題實(shí)例 (1) ? 例：有一份中文說明書，需要譯成英、日、德、俄四種文字。 aij 0 ( i,j = 1,2,…,n )表示指派第 j人去完成第 i項(xiàng)任務(wù)時(shí)的效率 (時(shí)間 、 成本等 )。,1( 1 0),1( 1),1( 1m i n111 1mjmixmjxmixxazijmiijmjijmimjijij????或? 某項(xiàng)任務(wù)只能由 1人完成； ? 某人只能完成 1項(xiàng)任務(wù)。 二、分配問題與匈牙利法 匈牙利法 ? 分配問題可以用單純形法或運(yùn)輸表求解。 這個(gè)解法稱為 匈牙利法 。 ????????????0141278302323020939140 顯然令 x11=1, x23=1, x32=1, x44=1，即將第一項(xiàng)工作分配給甲，第二項(xiàng)給丙，第三項(xiàng)給乙，第四項(xiàng)給丁。 如何尋找這組位于不同行不同列的零元素？ 二、分配問題與匈牙利法 匈牙利法的基本定理 ? 定理 1 如果從分配問題效率矩陣 [aij]的每一行元素中分別減去 (或加上 )一個(gè)常數(shù) ui(被稱為該行的位勢 )，從每一列分別減去 (或加上 )一個(gè)常數(shù) vj(被稱為該 列的位勢 )，得到一個(gè)新的效率矩陣 [bij]，若其中 bij = aij – ui– vj， 則 [bij]的最優(yōu)解等價(jià)于 [aij]的最優(yōu)解。 ?????????????????????????5911005324100115780411429131541116141381441579102 二、分配問題與匈牙利法 匈牙利法實(shí)例 (1) ???????????????9131541116141381441579102][ija 人員 任務(wù) 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 第一步： 找出每行的最小元素，每行對應(yīng)減去這個(gè)元素。 必定滿足： bij = aij– ui– vj 0 5 0 0 541100032450115280591100532410011
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1