線性規(guī)劃模型ppt課件

1、線性規(guī)劃的學(xué)習(xí)要求線性規(guī)劃的學(xué)習(xí)要求 知道線性規(guī)劃模型的一般形式知道線性規(guī)劃模型的一般形式 會(huì)用圖解法求解二個(gè)變量的線性規(guī)劃問題會(huì)用圖解法求解二個(gè)變量的線性規(guī)劃問題 會(huì)利用軟件會(huì)利用軟件LindoLindo求線性規(guī)劃問題的最優(yōu)解、最優(yōu)求線性規(guī)劃問題的最優(yōu)解、最優(yōu)值值 會(huì)建立簡(jiǎn)單的線性規(guī)劃問題會(huì)建立簡(jiǎn)單的線性規(guī)劃問題一、基本概念一、基本概念nnnnnnnnnnbxaxaxabxaxaxabxaxaxa),(),(),(22112222212111212111或或或約束條件：約束條件： 線性規(guī)劃模型的一般形式可以表示為：線性規(guī)劃模型的一般形式可以表示為：目標(biāo)函數(shù)目標(biāo)函數(shù) max(或或min)=cl

2、x1+c2x2+ + cnxn。非負(fù)條件：非負(fù)條件： x10, x20, , xn0目標(biāo)函數(shù)目標(biāo)函數(shù) ： max(或或min)= njjjxc1 njjijxa1(或=，) bi，i=1，2，m約束條件：約束條件： 可簡(jiǎn)寫為可簡(jiǎn)寫為 ： 非負(fù)條件：非負(fù)條件： xj0，j=1，2，n線性規(guī)劃的特點(diǎn)：線性規(guī)劃的特點(diǎn)： 具有唯一的目標(biāo)函數(shù)。具有唯一的目標(biāo)函數(shù)。 決策變量無論在目標(biāo)函數(shù)還是在約束條件中出現(xiàn)都具決策變量無論在目標(biāo)函數(shù)還是在約束條件中出現(xiàn)都具有冪為有冪為1的指數(shù)形式，并往往和一常數(shù)相乘。的指數(shù)形式，并往往和一常數(shù)相乘。 目標(biāo)函數(shù)或約束條件中都不包括決策變量的乘積項(xiàng)。目標(biāo)函數(shù)或約束條件中都不

3、包括決策變量的乘積項(xiàng)。 目標(biāo)函數(shù)和每個(gè)約束條件中決策變量的系數(shù)均為常數(shù)。目標(biāo)函數(shù)和每個(gè)約束條件中決策變量的系數(shù)均為常數(shù)。 決策變量之值可以是任一實(shí)數(shù)。決策變量之值可以是任一實(shí)數(shù)。說明：說明： 目標(biāo)函數(shù)中的系數(shù)ci , i=1,2, ，n , 常稱為價(jià)值系數(shù)，它反映某種價(jià)值如利潤(rùn)、收益或效益）；約束條件中的右端項(xiàng)bj，j=1,2, ，m等長(zhǎng)稱為右端系數(shù)，它反映某種資源的限制如勞動(dòng)力、原材料等）；約束條件中的aij常稱為技術(shù)系數(shù)。一般，它們都是已知的常數(shù)。一個(gè)線性規(guī)劃問題有解，是指能找出一組一個(gè)線性規(guī)劃問題有解，是指能找出一組xjxjj=1j=1，2 2，n n），使其滿足所有的約束條件和非負(fù)條件

4、。），使其滿足所有的約束條件和非負(fù)條件。稱任何一組這樣的稱任何一組這樣的xjxjj=1j=1，2 2，n n是線性規(guī)劃是線性規(guī)劃問題的一個(gè)可行解。通常，線性規(guī)劃問題含有多個(gè)問題的一個(gè)可行解。通常，線性規(guī)劃問題含有多個(gè)可行解。稱全部可行解的集合為該線性規(guī)劃問題的可行解。稱全部可行解的集合為該線性規(guī)劃問題的可行域。使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為該線可行域。使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為該線性規(guī)劃問題的最優(yōu)解，最優(yōu)目標(biāo)函數(shù)值稱為該線性性規(guī)劃問題的最優(yōu)解，最優(yōu)目標(biāo)函數(shù)值稱為該線性規(guī)劃問題的最優(yōu)值。對(duì)不存在可行解的線性規(guī)劃問規(guī)劃問題的最優(yōu)值。對(duì)不存在可行解的線性規(guī)劃問題，稱該線性規(guī)劃問題無解。題，稱

5、該線性規(guī)劃問題無解。二、二、 兩個(gè)變量的線性規(guī)劃問題的圖解法兩個(gè)變量的線性規(guī)劃問題的圖解法 第第1 1步：在平面上建立直角坐標(biāo)系；步：在平面上建立直角坐標(biāo)系； 第第2 2步：圖示約束條件和非負(fù)條件，找出可行域；步：圖示約束條件和非負(fù)條件，找出可行域； 第第3 3步：圖示目標(biāo)函數(shù)，并尋找最優(yōu)解。步：圖示目標(biāo)函數(shù)，并尋找最優(yōu)解。 例：例： max z=l00 x1+80 x2 約束條件約束條件 4x1+2x2400 2x1+4x2500 非負(fù)條件：非負(fù)條件： xl0, x20 唯一最優(yōu)解求最大值示意圖唯一最優(yōu)解求最大值示意圖三、線性規(guī)劃的軟件三、線性規(guī)劃的軟件lindo實(shí)現(xiàn)實(shí)現(xiàn) LINDO 是是

6、Linear INteractive Discrete Optimizer的縮寫，是一個(gè)線性和整數(shù)規(guī)劃的軟件系的縮寫，是一個(gè)線性和整數(shù)規(guī)劃的軟件系統(tǒng)。最大規(guī)模的模型的非零系數(shù)可以達(dá)到統(tǒng)。最大規(guī)模的模型的非零系數(shù)可以達(dá)到1,000,000個(gè)，最大變量個(gè)數(shù)可以達(dá)到個(gè)，最大變量個(gè)數(shù)可以達(dá)到100,000個(gè)，最大目標(biāo)函個(gè)，最大目標(biāo)函數(shù)和約束條件個(gè)數(shù)可以達(dá)到數(shù)和約束條件個(gè)數(shù)可以達(dá)到32000個(gè)，最大整數(shù)變量個(gè)，最大整數(shù)變量個(gè)數(shù)可以達(dá)到個(gè)數(shù)可以達(dá)到100,000個(gè)。它的特點(diǎn)是采用交互方式個(gè)。它的特點(diǎn)是采用交互方式操作，而且命令簡(jiǎn)單明了，很容易掌握。用戶在輸入操作，而且命令簡(jiǎn)單明了，很容易掌握。用戶在輸入初

7、步的數(shù)學(xué)模型后，可以一邊運(yùn)行，一邊修改調(diào)試，初步的數(shù)學(xué)模型后，可以一邊運(yùn)行，一邊修改調(diào)試，直至獲得滿意的結(jié)果。直至獲得滿意的結(jié)果。 LINDO既是一個(gè)實(shí)用的求解大規(guī)模線性和整數(shù)規(guī)劃系既是一個(gè)實(shí)用的求解大規(guī)模線性和整數(shù)規(guī)劃系統(tǒng)，也很適用于訓(xùn)練的目的，用來培養(yǎng)學(xué)生面對(duì)較復(fù)統(tǒng)，也很適用于訓(xùn)練的目的，用來培養(yǎng)學(xué)生面對(duì)較復(fù)雜的實(shí)際問題，構(gòu)造線性及整數(shù)規(guī)劃模型以及求解這雜的實(shí)際問題，構(gòu)造線性及整數(shù)規(guī)劃模型以及求解這些問題的能力。限于本教材的內(nèi)容，本手冊(cè)只介紹有些問題的能力。限于本教材的內(nèi)容，本手冊(cè)只介紹有關(guān)線性規(guī)劃和整數(shù)規(guī)劃的基本內(nèi)容，省略了有關(guān)二次關(guān)線性規(guī)劃和整數(shù)規(guī)劃的基本內(nèi)容，省略了有關(guān)二次規(guī)劃、參數(shù)

8、規(guī)劃以及有關(guān)線性規(guī)劃算法的比較專門的規(guī)劃、參數(shù)規(guī)劃以及有關(guān)線性規(guī)劃算法的比較專門的內(nèi)容。內(nèi)容。1.1 LINDO 命令一覽表命令一覽表 1、查詢類(Information) HELP 求助 COM ( Command )命令列表 LOCAL 當(dāng)前版本信息 CAT ( Categories )命令分類 TIME 顯示當(dāng)前時(shí)間 DATE顯示當(dāng)前日期8、整數(shù)規(guī)劃、二次規(guī)劃和參數(shù)規(guī)劃 ( Integer, Quadratic and Parametric Programs )INT定義一個(gè)0-1變量QCP*(Quadratic Programming)定義二次規(guī)劃PARA*(Parametric Pr

9、ogramming)求解參數(shù)規(guī)劃POSD*(Positive Definiteness)檢查二次規(guī)劃矩陣的正定性TITAN*緊縮連續(xù)變量的上界以及0-1變量的系數(shù)BIP*整數(shù)規(guī)劃中給出一個(gè)剪枝的界GIN （General Integer）定義一個(gè)整數(shù)變量IPTOL*設(shè)定整數(shù)規(guī)劃最優(yōu)解的寬容度 (1)(1)模型中出現(xiàn)的關(guān)鍵詞只能是模型中出現(xiàn)的關(guān)鍵詞只能是 MAX ( MAX (或或 MIN ) MIN )， ST ( ST (或或 SUBJECT TO )SUBJECT TO )和和 END END。關(guān)鍵詞中不能含有空格。關(guān)鍵詞中不能含有空格。MAX MAX ( ( 或或 MIN ) MIN )

10、， ST ( ST (或或 SUBJECT TO ) SUBJECT TO )的右面至少要有一的右面至少要有一個(gè)空格，關(guān)鍵詞中字符大寫和小寫都合法的。個(gè)空格，關(guān)鍵詞中字符大寫和小寫都合法的。 (2)(2)變量名不超過變量名不超過8 8個(gè)字符，其中第一個(gè)字符必須定字母，個(gè)字符，其中第一個(gè)字符必須定字母，其余的可以是字母或數(shù)字。這樣就可以藉助變量表示變量其余的可以是字母或數(shù)字。這樣就可以藉助變量表示變量的實(shí)際含義。例如有的實(shí)際含義。例如有1010種燃料，可以分別記為種燃料，可以分別記為FUEL01FUEL01，F(xiàn)UEL10FUEL10等。等。 (3)(3)不等號(hào)用不等號(hào)用 表示表示，用，用 表示表

11、示。要注意的。要注意的是當(dāng)模型是當(dāng)模型( (用用 LOOK LOOK 命令命令) )輸出輸出( (到屏幕或打印機(jī)到屏幕或打印機(jī)) )時(shí)，不等時(shí)，不等號(hào)分別寫成號(hào)分別寫成 和和 。 (4)(4)目標(biāo)函數(shù)中不能出現(xiàn)常數(shù)項(xiàng)，也不能出現(xiàn)等式，例如目標(biāo)函數(shù)中不能出現(xiàn)常數(shù)項(xiàng)，也不能出現(xiàn)等式，例如: : MAX 2X1MAX 2X13X23X25 5 和和 MAX Z=2X1 MAX Z=2X13X23X2都是非法的。都是非法的。 (5)無論連目標(biāo)函數(shù)(第一行)或約束條件中，都不能出現(xiàn)括號(hào)、乘號(hào)。例如:MAX2(X1+X2)和 MIN 2*X1+3*X2都是非法的。 (6)在約束條件中，變量必須在關(guān)系符左面

12、，常數(shù)必須在關(guān)系符右邊，例如: 3X14X230 和 3X134X2 都是非法的。 (7)模型中系數(shù)必須寫成整數(shù)或小數(shù)形式而不能寫成指數(shù)形式，例如：下列系數(shù)的記法是非法的： .258E+5。 如系數(shù)是小數(shù)形式，輸入的位數(shù)限制定整數(shù)最大6位，小數(shù)最大5位。 (8) 變量的非負(fù)約束是隱含的，不需要在模型中加以意義。LINDO/PC 5.3 2019 LINDO SYSTEMS INC.1MAX 4 X1 + X2 - X3 + 2 X42ST3X1 X2 + X3 - X4 = 3043 X1 + X2 - X3 + 2 X4 = 365X1 + 2 X2 + X3 2 X4 = 206END.23 - Exit with compile - Exit without compileOBJECTIVE FUNCTION VALUE1)12737.06