運(yùn)籌學(xué)-整數(shù)規(guī)劃與分配問(wèn)題

第四章整數(shù)規(guī)劃與分配問(wèn)題運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!對(duì)于線性規(guī)劃問(wèn)題，最優(yōu)解可能是分?jǐn)?shù)或小數(shù)。但是對(duì)于某些問(wèn)題，會(huì)要求解答必須是整數(shù)（稱(chēng)為整數(shù)解）。對(duì)于所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)、裝貨的車(chē)數(shù)、集裝箱數(shù)量等；對(duì)于一些決策變量必須取Boolean值時(shí)，如要不要在某地建工廠，可選用一個(gè)邏輯變量x，令x=0表示不在該地建廠，x=1表示在該地建廠。

這時(shí)，分?jǐn)?shù)或小數(shù)的解就不合要求，我們稱(chēng)這樣的問(wèn)題為整數(shù)規(guī)劃。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!例：某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如下表：貨物體積米3/箱重量百斤/箱利潤(rùn)百元/箱

甲乙54252010托運(yùn)限制2413問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得的利潤(rùn)為最大？能否先不考慮對(duì)變量的整數(shù)約束，作為一般線性規(guī)劃來(lái)求解，當(dāng)解為非整數(shù)的時(shí)候可以用“四舍五入”或“湊整”方法尋找最優(yōu)解？運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!對(duì)于變量取值很大時(shí)，用上述方法得到的解與最優(yōu)解差別不大；但當(dāng)變量取值較小時(shí)，得到的解就可能與實(shí)際整數(shù)最優(yōu)解差別很大。當(dāng)問(wèn)題規(guī)模較大（決策變量較多）時(shí)，用“湊整”方法來(lái)算工作量很大。例：某線性規(guī)劃問(wèn)題最優(yōu)解為(x1,x2)=(4.6,5.5)，用湊整法需要比較與上述數(shù)據(jù)最接近的幾種組合：(4,5),(4,6),(5,5),(5,6)，共四種組合。若問(wèn)題中有10個(gè)整數(shù)變量，則解組合達(dá)到210=1024個(gè)整數(shù)組合。且最優(yōu)解未必在這些組合中。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!主要內(nèi)容一、整數(shù)規(guī)劃的特點(diǎn)及作用二、分配問(wèn)題與匈牙利法三、分枝定界法四、應(yīng)用舉例運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!一、整數(shù)規(guī)劃的特點(diǎn)及作用

1.1整數(shù)規(guī)劃的概念整數(shù)規(guī)劃(IntegerProgramming)：決策變量要求取整數(shù)的線性規(guī)劃。如果所有的決策變量、技術(shù)系數(shù)和右端項(xiàng)都是非負(fù)整數(shù)，就稱(chēng)為純整數(shù)規(guī)劃。如果所有的決策變量都是非負(fù)整數(shù)，技術(shù)系數(shù)和右端項(xiàng)為有理數(shù)，稱(chēng)為全整數(shù)規(guī)劃。如果僅一部分決策變量為整數(shù)，則稱(chēng)為混合整數(shù)規(guī)劃。如果變量取值僅限于0或1，稱(chēng)為0-1整數(shù)規(guī)劃。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!一、整數(shù)規(guī)劃的特點(diǎn)及作用

1.2

0-1整數(shù)規(guī)劃0-1整數(shù)規(guī)劃的一般形式:0-1整數(shù)規(guī)劃一般都是純整數(shù)規(guī)劃。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!第二節(jié)分配問(wèn)題與匈牙利法第四章整數(shù)規(guī)劃及分配問(wèn)題運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!二、分配問(wèn)題與匈牙利法

2.1分配問(wèn)題(2)如果完成任務(wù)的效率表現(xiàn)為資源消耗，考慮的是如何分配任務(wù)使得目標(biāo)函數(shù)極小化；如果完成任務(wù)的效率表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目標(biāo)函數(shù)最大化。在分配問(wèn)題中，利用不同資源完成不同計(jì)劃活動(dòng)的效率，通常用表格形式表示為效率表，表格中數(shù)字組成效率矩陣。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!二、分配問(wèn)題與匈牙利法

2.2分配問(wèn)題實(shí)例(2)效率矩陣用[aij]表示。aij>0(i,j=1,2,…,n)表示指派第j人去完成第i項(xiàng)任務(wù)時(shí)的效率(時(shí)間、成本等)。

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!二、分配問(wèn)題與匈牙利法

2.3匈牙利法分配問(wèn)題可以用單純形法或運(yùn)輸表求解。庫(kù)恩(W.W.Kuhn)于1955年提出了指派問(wèn)題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.K?nig)一個(gè)關(guān)于矩陣中零元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。這個(gè)解法稱(chēng)為匈牙利法。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!二、分配問(wèn)題與匈牙利法

2.3匈牙利法的基本定理定理1如果從分配問(wèn)題效率矩陣[aij]的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui(被稱(chēng)為該行的位勢(shì))，從每一列分別減去(或加上)一個(gè)常數(shù)vj(被稱(chēng)為該列的位勢(shì))，得到一個(gè)新的效率矩陣[bij]，若其中bij=aij

–ui–vj，則[bij]的最優(yōu)解等價(jià)于[aij]的最優(yōu)解。定理2若矩陣A的元素可分為“0”和非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素的最大個(gè)數(shù)。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(2)第二步：找出矩陣每列的最小元素，再分別從各列中減去。必定滿足：bij=aij–ui–vj運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(4)第三步：從列開(kāi)始，若該列只有一個(gè)零元素，對(duì)零元素打上()括號(hào)(同樣不考慮已劃去的零元素)，再用直線劃去其所在行；若該列沒(méi)有零元素或有兩個(gè)零元素，則轉(zhuǎn)下一列，依次進(jìn)行到最后一列為止。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(6)順著閉回路的走向，對(duì)每個(gè)間隔的零元素打()，然后對(duì)所有打()的零元素或所在行或所在列畫(huà)一條直線，同樣得到最優(yōu)解。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(8)第五步：回到第三步，迭代運(yùn)算，直到矩陣的每一行都有一個(gè)打()的零元素為止。最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。所需時(shí)間為：4

+

4

+

9

+

11=28h運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!二、分配問(wèn)題與匈牙利法

2.6目標(biāo)函數(shù)最大化的分配問(wèn)題令

bij

=

M

-

aij標(biāo)準(zhǔn)化

M為充分大的常數(shù)，可以得到bij≥0。根據(jù)定理1，這種轉(zhuǎn)換是等價(jià)的。bij

=?aij

–ui–vj

=?aij

+

M若aij≥0，轉(zhuǎn)換后的效率矩陣不符合匈牙利法的條件。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!第三節(jié)分枝定界法第四章整數(shù)規(guī)劃及分配問(wèn)題運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!三、分枝定界法

3.2分枝定界法實(shí)例(1)求解B：其最優(yōu)解為x1=3.25，x2=2.5，最優(yōu)目標(biāo)函數(shù)值為z*

=14.75松弛問(wèn)題定界：令x1=0，x2=0作為初始整數(shù)解，其z=0，因此。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!定界：

用圖解法可得B1的最優(yōu)解為(3.5,2),z1=14.5；B2的最優(yōu)解為(2.5,3),z2=13.5。沒(méi)有整數(shù)最優(yōu)解，上界其下界沒(méi)有整數(shù)解，

z1>z2，對(duì)B1再次分枝。

三、分枝定界法

3.2分枝定界法實(shí)例(3)運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!三、分枝定界法

3.2分枝定界法—剪枝Bx1=3.25

x2=2.5Z

=14.75B1x1=3.5x2=2Z

=

14.5B2x1=2.5

x2=3Z

=13.5B11x1=3

x2=2Z

=13B12x1=4x2=1Z

=14××x2≤2x2≥3x1≤3x1≥4將各子問(wèn)題邊界值與保留的可行解的值進(jìn)行比較。把邊界值劣于可行解的分支減去。若除保留的可行解外，其他的分支均被減去，則得到最優(yōu)解。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!三、分枝定界法

3.4分枝定界法的解題步驟(1)解松馳問(wèn)題B：B沒(méi)有可行解，這時(shí)A也沒(méi)有可行解，停止。B有最優(yōu)解，并符合問(wèn)題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，停止。B有最優(yōu)解，但不符合問(wèn)題A的整數(shù)條件，將B的目標(biāo)函數(shù)值為問(wèn)題A的上界。用觀察法找問(wèn)題A的一個(gè)整數(shù)可行解，一般可取xj=0，j=1,…,n，求得其目標(biāo)函數(shù)值，作為A的下界，開(kāi)始迭代運(yùn)算。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!三、分枝定界法

3.4分枝定界法的解題步驟(3)比較與剪枝：各分支的最優(yōu)目標(biāo)函數(shù)若小于第三步得到的下界，則剪掉此分枝(用打×表示)，以后不再考慮。若大于下界，且不符合整數(shù)條件，則重復(fù)第三步，選取所有邊界值最優(yōu)的分枝進(jìn)行分枝與定界，一直到最后得到z*=

A的下界為止，此時(shí)得到最優(yōu)解。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!例：求整數(shù)規(guī)劃問(wèn)題的最優(yōu)解解：用圖解法得最優(yōu)解為（3.25,2.5）如果不考慮整數(shù)約束（稱(chēng)為整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題）最優(yōu)解為（4,1），z*=14。湊整法求解：比較四個(gè)點(diǎn)（4,3）,（4,2）,（3,3）,（3,2），前三個(gè)都不是可行解，第四個(gè)雖然是可行解，但z=13不是最優(yōu)解。(4,1)運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!節(jié)整數(shù)規(guī)劃的特點(diǎn)及作用第四章整數(shù)規(guī)劃及分配問(wèn)題運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!一、整數(shù)規(guī)劃的特點(diǎn)及作用

1.2

0-1整數(shù)規(guī)劃某公司擬在市東、西、南三區(qū)建立門(mén)市部。擬議中有7個(gè)位置（點(diǎn)）Ai供選擇。規(guī)定在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過(guò)B元。問(wèn)：應(yīng)如何選址，可使年利潤(rùn)為最大？運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!一、整數(shù)規(guī)劃的特點(diǎn)及作用

1.3整數(shù)規(guī)劃的作用0-1整數(shù)規(guī)劃在管理領(lǐng)域具有重要作用m個(gè)約束條件中只有k個(gè)起作用；約束條件的右端項(xiàng)可能是r個(gè)值(b1,b2,…br)中的某一個(gè)；兩組條件中滿足一組；用以表示含固定費(fèi)用的函數(shù)。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!二、分配問(wèn)題與匈牙利法

2.1分配問(wèn)題(1)指派n個(gè)人去完成n項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高(或所需總時(shí)間最少)，這類(lèi)問(wèn)題稱(chēng)為指派問(wèn)題或分配問(wèn)題。安排工作（派工）：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上完成；有n條航線，怎樣指定n艘船去航行的；……運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!二、分配問(wèn)題與匈牙利法

2.2分配問(wèn)題實(shí)例(1)例：有一份中文說(shuō)明書(shū)，需要譯成英、日、德、俄四種文字?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下，問(wèn)應(yīng)指派何人去完成工作，使所需總時(shí)間最少?

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!二、分配問(wèn)題與匈牙利法

2.2分配問(wèn)題實(shí)例(3)某項(xiàng)任務(wù)只能由1人完成；某人只能完成1項(xiàng)任務(wù)。

建立整數(shù)規(guī)劃模型分配問(wèn)題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例；n=m,aj=bj=1。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!二、分配問(wèn)題與匈牙利法

2.3匈牙利法的基本思想如果效率矩陣的所有元素aij≥0,而其中存在一組位于不同行不同列的零元素，則只要令對(duì)應(yīng)于這些零元素位置的xij=1，其余的xij=0，則所得到的可行解就是問(wèn)題的最優(yōu)解。顯然令x11=1,x23=1,x32=1,x44=1，即將項(xiàng)工作分配給甲，第二項(xiàng)給丙，第三項(xiàng)給乙，第四項(xiàng)給丁。這時(shí)完成總工作的時(shí)間為最少。如何尋找這組位于不同行不同列的零元素？運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(1)

人員任務(wù)甲乙丙丁譯成英文譯成日文譯成德文譯成俄文2151341041415914161378119步：找出每行的最小元素，每行對(duì)應(yīng)減去這個(gè)元素。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(3)第三步：從行開(kāi)始，若該行只有一個(gè)零元素，對(duì)零元素打上()括號(hào)，表示行所代表的任務(wù)已指派。用直線劃去其所在列；若該行沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi))，則轉(zhuǎn)下一行，依次進(jìn)行到最后一行為止。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(5)效率矩陣每行都有一個(gè)打()的零元素，這些零元素都位于不同行不同列，令對(duì)應(yīng)打()零元素的xij=1

就得到最優(yōu)解；矩陣中所有零元素或被劃去，或被打上()，但打()的零元素少于m個(gè)，這時(shí)轉(zhuǎn)第四步。打()的零元素小于m，但未被劃去的零元素之間存在閉回路。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!二、分配問(wèn)題與匈牙利法

2.4匈牙利法實(shí)例(7)第四步：繼續(xù)按照定理1，對(duì)矩陣進(jìn)行變換。從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)k；對(duì)矩陣的每行，當(dāng)該行有直線覆蓋時(shí)，令ui=0，無(wú)直線覆蓋的，令ui=k；對(duì)矩陣中有直線覆蓋的列，令vj=

-k，對(duì)無(wú)直線覆蓋的列，令vj=0。只有一條直線覆蓋的元素保持不變運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!二、分配問(wèn)題與匈牙利法

2.5人數(shù)和任務(wù)數(shù)不相等的分配問(wèn)題有四項(xiàng)工作分配給六個(gè)人去完成，每個(gè)人分別完成各項(xiàng)工作的時(shí)間如下，依然規(guī)定每個(gè)人完成一項(xiàng)工作。每項(xiàng)工作只交給一個(gè)人去完成。即六個(gè)人中挑選哪四個(gè)人去完成，花費(fèi)時(shí)間最少。

工作人IIIIIIIV123456373655616427245346648732

工作人IIIIIIIVVVI123456373655616427245346648732000000000000運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!第四章整數(shù)規(guī)劃及分配問(wèn)題

作業(yè)一求下面指派問(wèn)題的最優(yōu)解運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!三、分枝定界法

3.1分枝定界法的基本思想分枝定界法可用于全部類(lèi)型的整數(shù)規(guī)劃問(wèn)題。設(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*的下界。分支定界法就是將B的可行域分成子區(qū)域(稱(chēng)為分枝)的方法，逐步減小和增大上、下界，最終得到整數(shù)規(guī)劃問(wèn)題A的z*。運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!分枝：在B的最優(yōu)解中，任取一個(gè)非整數(shù)變量，如x2=2.5；因x2的最近鄰整數(shù)解為x2=2或x2=3，其最優(yōu)整數(shù)解區(qū)間只能是x2≥3或x2≤2。對(duì)B分別加上約束條件x2≥3和x2≤2，可得到兩個(gè)子問(wèn)題B1和B2。三、分枝定界法

3.2分枝定界法實(shí)例(2)運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題共43頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!三、分枝定界法

3.2分枝定