規(guī)劃問(wèn)題的基本概念專題培訓(xùn)課件

規(guī)劃問(wèn)題的基本概念推薦參考書(shū)胡運(yùn)權(quán).運(yùn)籌學(xué)教程.清華大學(xué)出版社.1998韓伯棠.管理運(yùn)籌學(xué).高等教育出版社.2010謝金星等.優(yōu)化建模與Lindo/Lingo軟件.清華大學(xué)出版社.2005譚永基等.經(jīng)濟(jì)管理數(shù)學(xué)模型案例教程.高教出版社.2013譚永基.數(shù)學(xué)模型.復(fù)旦大學(xué)出版社.2005姜啟源.數(shù)學(xué)模型.高等教育出版社.2010但靜.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn).高等教育出版社.2003姜啟源等.大學(xué)數(shù)學(xué)實(shí)驗(yàn).清華大學(xué)出版社.2004[美]JoeZhu著.數(shù)據(jù)包絡(luò)分析.科學(xué)出版社.2016謝中華.Matlab統(tǒng)計(jì)分析與應(yīng)用：40個(gè)案例分析.北航出版社.2010規(guī)劃問(wèn)題及其模型

在工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究等領(lǐng)域中，決策者要求在滿足一系列條件要求下，求材料最省、重量最輕、成本最低、時(shí)間最短、路程最短、利潤(rùn)最大、誤差最小、產(chǎn)量最大等等，都稱為優(yōu)化問(wèn)題。習(xí)慣上，上述的最省、最輕、最低、最短、最大等統(tǒng)稱最優(yōu)。

對(duì)于給定的優(yōu)化問(wèn)題，決策者根據(jù)問(wèn)題的背景知識(shí)或試驗(yàn)數(shù)據(jù)，將問(wèn)題進(jìn)一步簡(jiǎn)化，用一系列數(shù)學(xué)符號(hào)(變量)來(lái)代替問(wèn)題所涉及的各種已知或未知要素，用這些符號(hào)的函數(shù)等式或者不等式來(lái)反映客觀條件或約束，并用這些符號(hào)的函數(shù)來(lái)反映決策者的訴求（欲望或目標(biāo)），這樣的約束和訴求就構(gòu)成了相應(yīng)問(wèn)題的規(guī)劃模型。一、兩個(gè)案例案例1

（生產(chǎn)決策問(wèn)題）

（一個(gè)線性規(guī)劃模型）案例2

（路燈照度問(wèn)題）

（一個(gè)非線性規(guī)劃問(wèn)題）

通過(guò)兩個(gè)案例，學(xué)習(xí)規(guī)劃模型的建立必要步驟以及書(shū)寫(xiě)的規(guī)范格式。

某工廠在計(jì)劃期內(nèi)要安排I、II兩種產(chǎn)品生產(chǎn)。生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)、A，B兩種原材料的消耗、資源的限制以及單件產(chǎn)品利潤(rùn)如表1-1所示表1-1問(wèn)工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品II，才能獲利最多？III資源限制設(shè)備原料A原料B11300臺(tái)時(shí)21400kg01250kg利潤(rùn)（元）50100案例1生產(chǎn)決策問(wèn)題（一個(gè)簡(jiǎn)單的線性規(guī)劃問(wèn)題）【問(wèn)題分析]】（1）這是一個(gè)生產(chǎn)決策問(wèn)題，決策者的目標(biāo)是生產(chǎn)利潤(rùn)最大（2）與利潤(rùn)有關(guān)的是產(chǎn)品的銷(xiāo)售量與售價(jià)（或單位利潤(rùn)）；（3）生產(chǎn)產(chǎn)品就要消耗資源（這與產(chǎn)量有關(guān)），而各種資源又受到客觀限制。經(jīng)驗(yàn)：收入與銷(xiāo)售量有關(guān)，而資源的消耗量與產(chǎn)品的產(chǎn)量有關(guān)?！締?wèn)題假設(shè)】

（1）產(chǎn)品I的產(chǎn)量等于銷(xiāo)售量；（2）產(chǎn)品II的產(chǎn)量等于銷(xiāo)售量?！痉?hào)設(shè)置】x1

產(chǎn)品I的一個(gè)周期的產(chǎn)量（單位：件）；x2

產(chǎn)品II的一個(gè)周期的產(chǎn)量（單位：件）；z工廠一個(gè)周期內(nèi)的總利潤(rùn)（單位：元）。（其中，x1,x2稱為決策變量）III資源限制設(shè)備原料A原料B11300臺(tái)時(shí)21400kg01250kg利潤(rùn)（元）50100【建立模型】工廠一個(gè)生產(chǎn)周期的總利潤(rùn)x1x2生產(chǎn)資料約束（設(shè)備限時(shí)）（原料A限量）（原料B限量）資源的實(shí)際消耗資源的擁有量限制III資源限制設(shè)備原料A原料B11300臺(tái)時(shí)21400kg01250kg利潤(rùn)（元）50100其它約束：因?yàn)閤1和x2都是產(chǎn)品的產(chǎn)量，所以，從數(shù)學(xué)意義上，有廠家的訴求：一個(gè)周期內(nèi)利潤(rùn)z越大越好！(maxz)

以上分析，將生產(chǎn)過(guò)程的未知要素（產(chǎn)品產(chǎn)量）用x1,x2表示，各種客觀約束都表達(dá)為x1,x2的函數(shù)不等式，廠家的訴求（利潤(rùn)）也是x1,x2的函數(shù)表達(dá)式，將這些數(shù)學(xué)結(jié)構(gòu)寫(xiě)在一起，就是這個(gè)規(guī)劃問(wèn)題的數(shù)學(xué)模型：

這個(gè)規(guī)劃模型，如果拋開(kāi)這個(gè)問(wèn)題的背景，就是求在五個(gè)約束條件下，一次函數(shù)z=50x1+100x2的最大值，這是一個(gè)純數(shù)學(xué)意義上的極大值問(wèn)題?！緮?shù)學(xué)模型】目標(biāo)函數(shù)條件約束變量約束約束Subjectto受約束于，滿足于

雖然有些問(wèn)題的數(shù)學(xué)結(jié)構(gòu)很難用數(shù)學(xué)式子來(lái)表達(dá)，但習(xí)慣上我們稱決策變量、約束條件、目標(biāo)函數(shù)為規(guī)劃問(wèn)題的三要素。這個(gè)問(wèn)題的目標(biāo)和約束都是決策變量的一次表達(dá)式，稱為線性規(guī)劃。決策變量案例2路燈照度問(wèn)題(一個(gè)非線性規(guī)劃問(wèn)題）

如圖2-1所示，在一條s=20m寬的道路兩側(cè)，分別安裝了一只2kw和一只3kw的路燈，它們離地面的高度分別為h1=5m和h2=6m。（1）在漆黑的夜晚，當(dāng)兩只路燈開(kāi)啟時(shí)，兩只路燈連線路面上最暗的點(diǎn)和最亮的點(diǎn)在哪里？（2）如果3kw路燈的高度可以在3m到9m之間變化，如何求得路面上最暗和最亮的點(diǎn)的位置？（3）如果兩只路燈的高度均可以在3m到9m之間變化，結(jié)果將如何？圖2-1osxP1P2h1h2r1r2【問(wèn)題分析】經(jīng)驗(yàn)：（物理學(xué)背景知識(shí)）

光源點(diǎn)P1在點(diǎn)x處的照度（照亮強(qiáng)度）I1，I1與功率P1成正例，與距離r1的平方成反比，與照射角度α1的正弦成正比。即其中，k為比例系數(shù)，同時(shí)也是平衡量綱（單位）的量。圖2-1osxP1P2h1h2r1r2圖2-1osxP1P2h1h2r1r2【問(wèn)題假設(shè)】（1）p1,p2都可以看成點(diǎn)光源；（2）p1,p2在x的照度可以疊加（求和）；【符號(hào)設(shè)置】（符號(hào)設(shè)置如有圖2-1所示）I:某點(diǎn)處的照度（亮度）；I1：燈P1在該點(diǎn)處的照度；I2：燈P2在該點(diǎn)處的照度；（3）光源只來(lái)至兩盞燈。s:街道寬；

p1,p2:兩個(gè)光源的功率；h1,h2:兩盞燈的高度；

r1,r2:兩盞路燈到x的距離；

x:街道某點(diǎn)的坐標(biāo)，介于0和s之間；

α1,

α2:光線的入射角。圖2-1osxP1P2h1h2r1r2兩只燈在點(diǎn)x處的照度為其中，變量之間的關(guān)系【建立模型】問(wèn)題(1)：燈高度不變，求路面照度最弱最強(qiáng)的位置x。數(shù)學(xué)模型1s.t.也可以化簡(jiǎn)為代入已知參數(shù)，模型簡(jiǎn)化為即求一元函數(shù)I(x)在[0，20]上的最大值與最小值。問(wèn)題(2)：當(dāng)3kw的燈的高度在3m到9m之間變化時(shí)，路面的最暗和最亮點(diǎn)。數(shù)學(xué)模型2

即求二元函數(shù)I(x,h2)在所給矩形閉區(qū)域上的最大值與最小值。問(wèn)題(3)：兩只燈的高度都在3m到9m之間變化時(shí)，求路面的最暗和最亮點(diǎn)。數(shù)學(xué)模型3即求三元函數(shù)I(x,h1,h2)在所給條件下的上的最大值與最小值。

像這種目標(biāo)函數(shù)或者約束條件是決策變量的非一次（非線性）的規(guī)劃模型，稱為非線性規(guī)劃模型。二、規(guī)劃問(wèn)題解的概念1、線性規(guī)劃解的概念

通過(guò)具體的例子，學(xué)習(xí)線性規(guī)劃問(wèn)題的可行解、可行域、最優(yōu)解等概念；通過(guò)圖解法了解線性規(guī)劃解的情況；2、非線性規(guī)劃解的概念

通過(guò)具體的例子，學(xué)習(xí)非線性規(guī)劃的可行解、可行域、局部最優(yōu)解、全局最優(yōu)解等概念；通過(guò)例子了解非線性規(guī)劃求解的特點(diǎn)；3、小結(jié)

對(duì)比線性規(guī)劃和非線性規(guī)劃的圖解法，總結(jié)兩種規(guī)劃解的不同點(diǎn)（局部和全局）和相同點(diǎn)（迭代法）。1、線性規(guī)劃解的概念1.1線性規(guī)劃的可行解

若x1,x2滿足條件[1]~[4],則稱向量為線性規(guī)劃問(wèn)題的一個(gè)可行解。[1][2][3][4]例如其中x(1),x(2)為可行解，而x(3),x(4)不是可行解。所有可行解構(gòu)成的集合稱為該線性規(guī)劃的可行域。

在例1中，若存在x*=[x1*,x2*]T,對(duì)D中任何x=[x1,x2]T，都有稱x*為該線性規(guī)劃的最優(yōu)解（使目標(biāo)函數(shù)最大或最小的可行解）。1.2線性規(guī)劃的可行域1.3線性規(guī)劃的最優(yōu)解1.4可行解、可行域、最優(yōu)解的幾何意義可以用圖解法求解兩個(gè)決策變量的線性規(guī)劃問(wèn)題。例3用圖解法求解如下線性規(guī)劃問(wèn)題解圖解法步驟：（1）用x1，x2分別表示橫坐標(biāo)和縱坐標(biāo)，并根據(jù)x1,x2>=0，繪制坐標(biāo)系；（2）圖示各個(gè)約束條件所表達(dá)的基線及其變化方向；（3）由滿足所有條件的點(diǎn)（可行解）構(gòu)成的集合（區(qū)域）就是可行域，（4）圖示目標(biāo)函數(shù)的基線，并由變量的變化方向確定基線的平移方向，最后確定最優(yōu)解；x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4可行區(qū)域Dx2=z-2x1使得目標(biāo)函數(shù)最大的點(diǎn)Q2(3.5,1.5)Q2對(duì)應(yīng)的點(diǎn)就是線性規(guī)劃問(wèn)題的唯一最優(yōu)解：x*=[x1*=3.5,x2*=1.5]T。

例4用圖解法觀察下述問(wèn)題的最優(yōu)解情況x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4x2+x1=0可以看出，Q2Q3上的點(diǎn)全是最優(yōu)解。即問(wèn)題有無(wú)窮多最優(yōu)解。

例5判斷如下線性規(guī)劃的解情況X2=3x1x20x2+x1=0可以看出，在可行域內(nèi)，當(dāng)可行解變化時(shí)，目標(biāo)函數(shù)可以無(wú)限增大。即問(wèn)題為無(wú)界解。例6

判斷如右線性規(guī)劃問(wèn)題的解情況可以看出，該問(wèn)題兩個(gè)約束矛盾，無(wú)可行解。

綜上所述，對(duì)于線性規(guī)劃問(wèn)題，其結(jié)果不外乎下面幾種情況：（1）有最優(yōu)解：唯一最優(yōu)解或無(wú)窮多最優(yōu)解，且最優(yōu)解一定在可行域某頂點(diǎn)達(dá)到；（2）無(wú)界解；（3）無(wú)可行解。

在實(shí)際的線性規(guī)劃模型的計(jì)算中，如果遇到（2）情況，說(shuō)明漏掉了重要的約束；如果遇到（3）情況，說(shuō)明問(wèn)題有約束沖突，檢查約束條件，一般采取如下策略：要么留下主要約束，去掉與之矛盾的次要的約束；要么承認(rèn)矛盾的合理性，采用多目標(biāo)規(guī)劃。

在建立規(guī)劃模型時(shí)，若目標(biāo)函數(shù)如例2中決策變量或者約束方程（不等式）中某些變量為非一次（不是線性），則稱建立的數(shù)學(xué)模型為非線性規(guī)劃模型。[5]2、非線性規(guī)劃解的概念模型[5]為非線性規(guī)劃的標(biāo)準(zhǔn)模型(目標(biāo)最小化，所有約束都是大于等于)，很多優(yōu)化理論的推導(dǎo)和優(yōu)化程序的編譯都是按照這種模式展開(kāi)）。[6]模型[6]稱為無(wú)約束優(yōu)化。默認(rèn)[7]模型[7]稱為二次規(guī)劃(目標(biāo)是決策變量的二次型，約束都是決策變量的線性約束，它的很多性質(zhì)跟線性規(guī)劃類(lèi)似)。2.1可行集（可行域）給定非線性規(guī)劃問(wèn)題[5][10][11][12]2.1.1可行解若x1,x2滿足條件[10],[11],[12]，則稱向量x=[x1,x2]T為非線規(guī)劃[5]的可行解。[10][11][12]例如：其中x(1),x(4)不是此問(wèn)題的可行解，而x(2),x(3)是規(guī)劃問(wèn)題[5]的可行解。2.1.2可行集（可行域）稱為非線性規(guī)劃問(wèn)題[5]的可行集（域）。例8利用圖解法，求解如下非線性規(guī)劃問(wèn)題【問(wèn)題分析】:決策變量為x=(x1,x2)T。目標(biāo)函數(shù)表示決策變量ｘ=(x1,x2)T到點(diǎn)(2,1)T的距離的平方（體現(xiàn)為以(2,1)為圓心的圓周半徑變化）；第一個(gè)約束是一條拋物線（開(kāi)口朝左,x1為橫軸）；第二個(gè)約束為一次不等式；同時(shí)決策變量非負(fù)。（注意等號(hào)）解以x1和x2分別為橫軸和縱軸，建立直角坐標(biāo)系，如圖2-2：（1）繪制約束曲線；（2）標(biāo)出可行域：x1x20(右上)2.5(在拋物線上)ABCD拋物線段ABCD為可行域；圖2-2x1x20(右上)2.512ABCD如圖2-2（續(xù)）（3）繪制目標(biāo)函數(shù)曲線該問(wèn)題的目標(biāo)是在拋物線段ABCD上找一個(gè)點(diǎn)，使得這個(gè)點(diǎn)到(2,1)T的距離的平方最?。ň嚯x本身也是最小）。這樣的點(diǎn)位于以(2,1)T為圓心的圓周上。由圖示可知，點(diǎn)D到(2,1)T的距離最小。即D(4,1)T就是拋物線段ABCD上到點(diǎn)(2,1)T距離平方最小的點(diǎn)。2.2非線性規(guī)劃的解的概念2.2.1局部極?。O大）點(diǎn)如右圖所示，點(diǎn)B(2.9104,4.3275)T比附近的其它點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值都小，稱為局部極小點(diǎn)，對(duì)應(yīng)的目標(biāo)值f(B)為局部極小值；點(diǎn)C(6.25,2.5)T對(duì)應(yīng)的目標(biāo)函數(shù)值比附近的其它目標(biāo)函數(shù)值都大，稱為局部極大點(diǎn)，對(duì)應(yīng)的目標(biāo)函數(shù)f(C)稱為局部極大值。

因?yàn)閽佄锞€段ABCD上，B左右的點(diǎn)到(2,1)T的距離都大于B到(2,1)T的距離；C左右的點(diǎn)到(2,1)T的距離都小于C到(2,1)T的距離。2.2.2全局最?。ㄗ畲螅c(diǎn)如右圖所示，點(diǎn)D(4,1)T到(2,1)T的距離小于拋物線段ABCD上其它任何點(diǎn)到(2,1)T的距離，稱點(diǎn)D為此規(guī)劃的全局最小值點(diǎn)，f(D)稱為全局最小值。點(diǎn)A(0,5)T到點(diǎn)(2,1)T的距離大于拋物線段ABCD上任何點(diǎn)到(2,1)T的距離，稱點(diǎn)A為全局最大值點(diǎn)，f(A)稱為全局最大值。3.1、線性規(guī)劃求解的特點(diǎn)例3的圖解法截圖3、線性規(guī)劃與非線性規(guī)劃最優(yōu)解求解的根本區(qū)別例4圖解法截圖線性規(guī)劃最優(yōu)解的特點(diǎn)：（1）線性規(guī)劃的可行域都是直線段圍成的（凸）多邊形區(qū)域；（2）只要線性規(guī)劃存在最優(yōu)解（不管是唯一最優(yōu)解還是無(wú)窮多最優(yōu)解），就一定會(huì)在邊界的頂點(diǎn)處到達(dá)；（3）尋找線性規(guī)劃最優(yōu)解的原理：【單純形法】步驟1：在OQ1Q2Q3Q4O邊界上，任取一個(gè)頂點(diǎn)，比如O點(diǎn)，計(jì)算O的目標(biāo)函數(shù)值，比較O與相鄰的頂點(diǎn)Q1和Q4對(duì)應(yīng)的的目標(biāo)函數(shù)值，如果O點(diǎn)的目標(biāo)函數(shù)值最大（最大化目標(biāo)），O就是最優(yōu)解；步驟2：如果存在相鄰點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值比O點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值大（比如Q1)，用Q1點(diǎn)代替剛才的O點(diǎn)，重復(fù)步驟1，直到某個(gè)點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值比相鄰的點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值都大。對(duì)線性規(guī)劃解的全局性：對(duì)于線性規(guī)劃問(wèn)題，得到的任何一個(gè)最優(yōu)解都是全局最優(yōu)解。3.2、非線性規(guī)劃求解的特點(diǎn)例8圖解法截圖非線性規(guī)劃求解原理和線性規(guī)劃求解原理大致都用迭代法。步驟1：如右圖所示，在可行域ABCD拋物線段上任取一個(gè)初始點(diǎn)O（有風(fēng)險(xiǎn)），比如這個(gè)初始點(diǎn)選在AB之間的某點(diǎn)；步驟2：從O點(diǎn)分別試著朝A和朝B方向走，比較哪個(gè)方向會(huì)讓目標(biāo)函數(shù)減?。ㄗ钚』繕?biāo)，如果有多個(gè)方向，就選取目標(biāo)函數(shù)減小最快的方向），就準(zhǔn)備朝那個(gè)方向邁出步伐；步驟3：確定了朝B方向目標(biāo)函數(shù)會(huì)減小，就朝B方向跨出最大一步，到達(dá)步伐的終點(diǎn)O1；步驟4：用O1替代O點(diǎn)，重復(fù)步驟1~3，直到?jīng)]有方向可走為止。非線性規(guī)劃迭代法計(jì)算的風(fēng)險(xiǎn)：尋找最?。ɑ蜃畲螅┮蕾囉诔跏键c(diǎn)。比如剛才的迭代初始值選在AB之間，就會(huì)將B點(diǎn)誤作為全局最小值點(diǎn)。規(guī)避這種風(fēng)險(xiǎn)的方法除了從迭代方法上作改進(jìn)，就是多選幾個(gè)初始點(diǎn)計(jì)算，然后比較每次計(jì)算的最優(yōu)解，再選取你認(rèn)為最合適的一個(gè)點(diǎn)為全局最優(yōu)解。（例如：設(shè)wifi信號(hào)源在(2,1)T，你拿著手機(jī)在ABCD段上找離信號(hào)源最近的點(diǎn)）三、按照決策變量要求識(shí)別規(guī)劃模型1、整數(shù)規(guī)劃模型

部分決策變量要求取整數(shù)，這個(gè)要求人能識(shí)別，智能機(jī)器能識(shí)別，同時(shí)要求軟件能識(shí)別；2、0-1規(guī)劃

對(duì)于“是”與“非”的選擇問(wèn)題，多用0-1變量來(lái)實(shí)現(xiàn)，同樣要求人、機(jī)器、軟件都能識(shí)別；3、通過(guò)案例學(xué)習(xí)，了解不同變量之間的交叉約束的線性約束表達(dá)。1、整數(shù)規(guī)劃模型例9貨物托運(yùn)問(wèn)題（一般整數(shù)規(guī)劃）

某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤(rùn)以及托運(yùn)限制如表1-2貨物每件體積/英尺3每件重量/100kg每件利潤(rùn)/百元甲19542乙273403托運(yùn)限制1365140表1-2

且甲種貨物最多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可獲利最大?！締?wèn)題假設(shè)】（1）甲乙兩種貨物不可分割，即按整數(shù)計(jì)件；（2）甲乙兩貨物的體積可以直接相加（軟體積）。比如水的體積，就是所占空間的體積（軟體積）；碎石的體積就比所占空間的體積?。ㄓ搀w積）?！痉?hào)設(shè)置】x1

甲貨物裝運(yùn)的件數(shù)；x2

乙貨物裝運(yùn)的件數(shù)；z一次運(yùn)輸?shù)睦麧?rùn)（單位：百元）【建立模型】根據(jù)問(wèn)題描述，則總利潤(rùn)為【問(wèn)題分析】（此問(wèn)題已高度簡(jiǎn)化，[問(wèn)題分析]略去）運(yùn)輸體積約束運(yùn)輸重量約束貨物要求約束貨物分割要求x1,x2要求取整數(shù)；非負(fù)約束【數(shù)學(xué)模型】x1,x2取整（或x1,x2∈Z）線性規(guī)劃整數(shù)線性規(guī)劃

這種要求所有決策變量的線性規(guī)劃就稱為線性整數(shù)規(guī)劃；要求部分變量取整的稱為混合線性整數(shù)規(guī)劃。例10投資場(chǎng)所的選擇（一般0-1規(guī)劃）

某公司計(jì)劃在市區(qū)的東、南、西、北四個(gè)區(qū)建立銷(xiāo)售門(mén)面。擬議中有10個(gè)位置Ai(i=1,2,…,10)可供選擇，考慮到各個(gè)地區(qū)居民消費(fèi)水平以及居民的居住密度，規(guī)定：在東區(qū)A1,A2,A3三個(gè)點(diǎn)中至少選擇兩個(gè)；在西區(qū)A4,A5兩個(gè)點(diǎn)中至少選擇一個(gè)；在南區(qū)A6,A7兩個(gè)點(diǎn)中至少選擇一個(gè)；在北區(qū)A8,A9,A10三個(gè)點(diǎn)中至少選擇2個(gè)。Ai各個(gè)點(diǎn)的設(shè)備投資以及每年可獲利潤(rùn)由于地點(diǎn)不同都不一樣，預(yù)測(cè)情況如下表A1A2A3A4A5A6A7A8A9A10投資額10012015080709080140160180利潤(rùn)36405022203025485861

另外，投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)該選擇哪幾家銷(xiāo)售點(diǎn)，可使得年利潤(rùn)為最大？【問(wèn)題分析】

根據(jù)問(wèn)題的敘述，每個(gè)點(diǎn)最多建立一個(gè)銷(xiāo)售網(wǎng)點(diǎn)，若設(shè)xi為第i小區(qū)建立的銷(xiāo)售網(wǎng)點(diǎn)數(shù)，則在第i個(gè)點(diǎn)建立銷(xiāo)售網(wǎng)點(diǎn)在第i個(gè)點(diǎn)不建銷(xiāo)售網(wǎng)點(diǎn)i=1,2,…,10這樣的0-1決策變量，有如下性質(zhì)：

即對(duì)每個(gè)點(diǎn)xi來(lái)說(shuō)，要么取0，要么取1，這樣的變量就稱為0-1變量，因此，變量也可以設(shè)成（1）xi+xj=1：xi和xj有且只有一個(gè)取1，另外一個(gè)取0；（2）xi+xj<=1：xi和xj最一個(gè)多取1；（3）xi+xj>=1：xi和xj至少一個(gè)取1；（4）kxj：要么取k，要么取0；（5）x1+x2+…+xm=p(p<=m)：m個(gè)中恰好取p個(gè)；（6）x1+x2+…+xm<=p：m個(gè)中至多取p個(gè)；（7）x1+x2+…+xm>=p：m個(gè)中至少取p個(gè)；（8）xi>=xj：若第j個(gè)被選中，則第i個(gè)也被選中。思考：xi+xj>=xk表達(dá)的意思？？？【問(wèn)題假設(shè)】（1）每個(gè)點(diǎn)最多建立一個(gè)門(mén)面?！痉?hào)設(shè)置】xi

點(diǎn)Ai建立的門(mén)面數(shù)，i=1,2,…,10，其中z表示年總利潤(rùn)。根據(jù)問(wèn)題敘述，總利潤(rùn)為總投資額約束【建立模型】選擇約束：東區(qū)A1,A2,A3三個(gè)點(diǎn)至少選擇兩個(gè):西區(qū)A4,A5兩個(gè)點(diǎn)至少選擇一個(gè)：南區(qū)A6,A7兩個(gè)點(diǎn)至少選擇一個(gè)：北區(qū)A8,A9,A10三個(gè)點(diǎn)至少選擇兩個(gè)：變量約束：【數(shù)學(xué)模型】s.t.

像這種決策變量只取0和1的線性規(guī)劃，稱為0-1線性規(guī)劃，屬于特殊的整數(shù)線性規(guī)劃，在實(shí)際問(wèn)題中應(yīng)用廣泛。軟件也能識(shí)別??！例11固定成本問(wèn)題(變量交叉約束）

高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器的各種資源的數(shù)量如表1-3所示表1-3資源小號(hào)容器中號(hào)容器大號(hào)容器金屬板/t勞動(dòng)力/（人/月）機(jī)器設(shè)備/（臺(tái)/月）221432843

不考慮固定費(fèi)用，每種容器出售一只的利潤(rùn)分別為4萬(wàn)元，5萬(wàn)元，6萬(wàn)元，可使用的金屬板有500t，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月。

此外，只要生產(chǎn)，不管每種容器的制造數(shù)量是多少，都要支付一筆固定的費(fèi)用，小號(hào)為100萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元?，F(xiàn)在要制定一個(gè)月生產(chǎn)計(jì)劃，使