【文章內(nèi)容簡(jiǎn)介】 ji,2,11,2,1,0,2,11,2,1111????；具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行 Am+1，運(yùn)價(jià)為零。產(chǎn)量為 am+1即可。 Chapter3 整數(shù)規(guī)劃 ( Integer Programming ) 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 指配問(wèn)題與匈牙利法 本章主要內(nèi)容： Page 46 引言 整數(shù)規(guī)劃是規(guī)劃論中近幾十年才發(fā)展起來(lái)的一個(gè)重要分支，主要是由于經(jīng)濟(jì)管理中的大量問(wèn)題在抽象成模型時(shí)，人們發(fā)現(xiàn)許多量具有不可分割性，因此當(dāng)它們被作為變量引入到規(guī)劃中時(shí)，常要求滿足取整條件 . 如生產(chǎn)計(jì)劃中，生產(chǎn)機(jī)器多少臺(tái) (整數(shù) )；人力資源管理中，招聘員工多少人 (整數(shù) )；運(yùn)輸問(wèn)題中，從一個(gè)港口到另一個(gè)港口的集裝箱調(diào)運(yùn)數(shù)量 (整數(shù) )；另外，運(yùn)作管理中的決策問(wèn)題：如工廠選址、人員的工作指派、設(shè)備購(gòu)置和配置等 . Page 47 一輛車最大裝載重量為 7噸，容量為 12立方米。現(xiàn)有兩種物品，每種物品數(shù)量無(wú)限。各種物品每件的體積、重量、價(jià)格如下表： 物品 1 物品 2 體積（立方米 /件） 3 4 重量（噸 /件） 4 2 價(jià)值（萬(wàn)元 /件） 4 3 求這輛車中裝入每種物品各多少件，使物品總價(jià)值最高。 背包問(wèn)題 Page 48 設(shè)三種物品的件數(shù)各為 x1， x2件，總價(jià)值為 z max z=4x1+3x2 . 3x1+4x2≤12 4x1+2x2 ≤7 x1， x2≥0 ， x1， x2為整數(shù) Page 49 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃（簡(jiǎn)稱： IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問(wèn)題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱為該整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。若該松弛問(wèn)題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。 整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式： 11m a x ( m in )( , ) ( 1 , 2 )0 ( j 1 . 2 n ) njjjnij j ijjZ Z c xa x b i mx????? ? ? ?????????或且 部 分 或 全 部 為 整 數(shù)Page 50 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃問(wèn)題的種類： 純整數(shù)規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)規(guī)劃。 混合整數(shù)規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)規(guī)劃。 01型整數(shù)規(guī)劃：決策變量只能取值 0或 1的整數(shù)規(guī)劃。 Page 51 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃問(wèn)題解的特征： 整數(shù)規(guī)劃問(wèn)題的可行解集合是它松弛問(wèn)題可行解集合的一個(gè)子集，任意兩個(gè)可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。 整數(shù)規(guī)劃問(wèn)題的可行解一定是它的松弛問(wèn)題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。 Page 52 01整數(shù)規(guī)劃 01整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量?jī)H取值 0或者 1，我們通常稱為 01變量或邏輯變量 . 在實(shí)踐中，許多問(wèn)題只回答是或否 . 例如，對(duì)某個(gè)項(xiàng)目是否投資，對(duì)某個(gè)應(yīng)聘者是否聘用，對(duì)某種新產(chǎn)品是否研發(fā)等，這類問(wèn)題都可以用 01變量來(lái)描繪 . Page 53 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃問(wèn)題的求解方法： 分支定界法和割平面法 匈牙利法（指派問(wèn)題） 求解整數(shù)規(guī)劃模型的數(shù)學(xué)軟件有： Lindo, Lingo和 Matlab, 其中 Lindo和 Lingo是專業(yè)的優(yōu)化軟件 . Page 54 指派問(wèn)題 Assignment Problem 在生活中經(jīng)常遇到這樣的問(wèn)題，某單位需完成 n項(xiàng)任務(wù)，恰好有 n個(gè)人可以承擔(dān)這些任務(wù) .一項(xiàng)任務(wù)只能由一個(gè)人完成，一個(gè)人只能完成一項(xiàng)任務(wù)。 由于每人的專長(zhǎng)不同，每個(gè)人完成各項(xiàng)任務(wù)的效率不同 . 于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n項(xiàng)任務(wù)的總效率最高 (或所需總時(shí)間最小，費(fèi)用最低）。 Page 55 指派問(wèn)題 指派問(wèn)題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式： 設(shè) n 個(gè)人被分配去做 n 件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第 i個(gè)人去做第 j 件工作的 時(shí)間或費(fèi)用為 Cij(i=… n。j=… n)并假設(shè) Cij ≥0。問(wèn)應(yīng)如何分配才能使總效率最高？ 設(shè)決策變量 1j( , 1 , 2 , . . . , )0 i jijx i j n?????指 派 第 i 個(gè) 人 做 第 件 事不 指 派 第 個(gè) 人 做 第 件 事Page 56 指派問(wèn)題的數(shù)學(xué)模型為： ?????????????????? ???? ?)..,1(0)..( 1)..( 1m i n111 1njixnjxnixxcZijniijnjijninjijij???或取Page 57 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 例 2 指派問(wèn)題：人事部門欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表所示，如何安排他們的工作使總成績(jī)最好。 工作人員 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 Page 58 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 設(shè) ????工作時(shí)人做不分配第工作時(shí)人做分配第jijixij 01數(shù)學(xué)模型如下： 4443424134333231242322211413121188809086907983829578879590739285m a xxxxxxxxxxxxxxxxxZ??????????????????要求每人做一項(xiàng)工作，約束條件為： ???????????????????????111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage 59 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 每項(xiàng)工作只能安排一人 ， 約束條件為： ???????????????????????111144342414433323134232221241312111xxxxxxxxxxxxxxxx變量約束： 0 1 1 , 2 , 3 , 4ijx i j??或 ， 、對(duì)于指派問(wèn)題等 01 整數(shù)規(guī)劃問(wèn)題，可以直接利用Matlab 的函數(shù) bintprog 進(jìn)行求解。 Page 60 多目標(biāo)規(guī)劃模型 在許多實(shí)際問(wèn)題中，衡量一個(gè)方案的好壞標(biāo)準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高 . 這一類問(wèn)題統(tǒng)稱為多目標(biāo)最優(yōu)化問(wèn)題或多目標(biāo)規(guī)劃問(wèn)題 . 我們先來(lái)看一個(gè)生產(chǎn)計(jì)劃的例子 . Page 61 例． （生產(chǎn)計(jì)劃問(wèn)題）某廠生產(chǎn)三種布料1 2 3,A A A，該廠兩班生產(chǎn)，每周生產(chǎn)時(shí)間為 80 h ，能耗不得超過(guò)160 t 標(biāo)準(zhǔn)煤，其它數(shù)據(jù)如下表 ： 布料 生產(chǎn)數(shù)量（ /mh ） 利潤(rùn)（ / m元 ） 最大銷售量（ /m 周 ） 能耗（ /t k m ） 1A 4 0 0 0 . 1 5 4 0 0 0 0 1 . 2 2A 5 1 0 0 . 1 3 5 1 0 0 0 1 . 3 3A 3 6 0 0 . 2 0 3 0 0 0 0 1 . 4 問(wèn)每周應(yīng)生產(chǎn)三種布料各多少 m ，才能使該廠的利潤(rùn)最高，而能源消耗最少？ Page 62 解： 設(shè)該廠每周生產(chǎn)布料1 2 3,A A A的小時(shí)數(shù)為1 2 3,x x x，總利潤(rùn)為11()yf ?? x（元），總能耗為22()yf ? x（t標(biāo)準(zhǔn)煤），其中1 2 3( , , )Tx x xx=，則上述問(wèn)題的數(shù)學(xué)模型為 11221 2 31 2 31 2 3m in ( )m in ( )80. . 1 6 16 00 10 0 , 0 10 0 , 0 25 0 / 3yfyfx x xs t x x xx x x???? ? ???? ? ? ? ? ???? ? ? ? ? ??xx Page 63 有 1 1 1 2 32 2 1 2 3( ) 0. 15 40 0 0. 13 51 0 0. 20 36 0( ) 1. 2 0. 4 1. 3 0. 51 0. 36 1. 4y f x x xy f x x x? ? ? ? ? ? ? ?? ? ? ? ? ? ?xx 顯然這是一個(gè)多目標(biāo)線性規(guī)劃問(wèn)題 . 一般的多目標(biāo)規(guī)劃問(wèn)題都可寫(xiě)成如下的形式： 12m in ( )m in ( ) m in ( ). . ( ) 0 , 1 , 2 , ,pifffs t g i m??xxxx 其中，12( , , , )Tnmx x x ?x = R，2p ?. Page 64 ? ?( ) 0 , 1 , 2 , ,iR g i m? ? ?xx稱為多目標(biāo)規(guī)劃問(wèn)題的可行集或容許集， R?x 稱為可行解或容許解 .多目標(biāo)規(guī)劃問(wèn)題與前面講的規(guī)劃問(wèn)題的主要區(qū)別在于：目標(biāo)函數(shù)不止一個(gè)，而是p個(gè)（2p ?）。 多目標(biāo)規(guī)劃問(wèn)題的解法大致可分為兩類：直接解法和間接解法 . 到目前為止，常用的多為間接解法，即根據(jù)問(wèn)題的實(shí)際背景和特征，設(shè)法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，從而得到滿意解的方法 . Page 65 1) 主要目標(biāo)法 在多目標(biāo)優(yōu)化問(wèn)