【正文】 jijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運輸問題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。,1,0,1,1m i n111 1????? 解此問題可假想一個產(chǎn)地 Am+1，其產(chǎn)量為： am+1 = Σ bj－ Σ ai； 若用 xm+1， j表示從 Am+1到 Bj的運量，可令 cm+1， j=0或等于第 Bj產(chǎn)地每缺單位物資的損失。因為 xm+1， j實際上表示 Bj銷地所缺的物資數(shù)量。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運輸問題，其數(shù)學(xué)模型為： ?此時，可用表上作業(yè)法求解。 ???????????????????????? ?????? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。1,1,0,11,1m i n11111 1????例 某公司有 6個供貨棧（倉庫），庫存貨物總數(shù)分別為 60， 55， 51， 43， 41， 52，現(xiàn)有 8個客戶各要一批貨數(shù)量分別為 35， 37， 22， 32， 41， 32， 43， 38，各供貨棧道 8個客戶的單位貨物運輸價見表 供貨棧到客戶的單位貨物運價 客戶 貨棧 V1 V2 V3 V4 V5 V6 V7 V8 W1 6 2 6 7 4 2 5 9 W2 4 9 5 3 8 5 8 2 W3 5 2 1 9 7 4 3 3 W4 7 6 7 3 9 2 7 1 W5 2 3 9 5 7 2 6 5 W6 5 5 2 2 8 1 4 3 試確定各貨棧到各客戶處的貨物調(diào)運數(shù)量，使總的運輸費用最小。 解 引入決策變量 代表從第 個貨棧到第 個 客戶的貨物運量 . 設(shè) 表示從第 個貨棧 到第 個客戶的單位貨物運價 表示第 個貨棧的最大供貨量 , 表示第 個客戶的訂貨量 . 目標(biāo)函數(shù)是總運輸費用最少 . 約束條件有三條： 1. 各貨棧運出的貨物總量不超過其庫存數(shù) 3. 決策變量 非負 數(shù)學(xué)模型為 前面介紹的 LinGO的基本用法，其優(yōu)點是輸入模型較直觀，一般的數(shù)學(xué)表達式無需作大的變換即可直接輸入 .對于規(guī)模較小的的規(guī)劃模型，用直接輸入的方法是有利的，如果模型的變量和約束的條件個數(shù)比較多，若仍然用直接的輸入方式，雖然也能求解并得到結(jié)果，但這種做法有明顯的不足之處。模型的篇幅很長，不便于分析修改和擴展。 LinGO 建模語言引入集合的概念，為建立大規(guī)模的數(shù)學(xué)規(guī)劃模型提供了方便 . 用 LinGO 語言表達一個實際優(yōu)化問題，稱之為 LinGO模型。 一、集合定義部分 集合是一組相關(guān)對象構(gòu)成的組合，代表模型中的實際事物，并與數(shù)學(xué)變量與 常量聯(lián)系起來，是實際問題到數(shù)學(xué)的抽象。例中的 6個倉庫可以看成一個集合， 8個客戶可以看成另一個集合。 每個集合在使用之前需要預(yù)先給出定義，定義集合時要明確三方面的內(nèi)容 ： 集合 的名稱 ， 集合內(nèi)的成員（元素） 、 集合的屬性（可以看成與該集合有關(guān)的變量 或常量，相當(dāng)于數(shù)組） . 本例首先定義倉庫集合 ： WH/W1..W6/:AI。 其中 WH是集合的名稱， W1..W6是集合內(nèi)的成員， “ ..” 是特定的省略號 （如果不用該省略號，也可以把成員一一羅列出來，成員之間用逗號或 空格分開 ),表明該集合有 6個成員，分別對應(yīng)于 6個供貨棧， AI是集合的屬性， 它可以看成是一個數(shù)組，有 6個分量，分別表示各貨?，F(xiàn)有貨物的總數(shù)。 集合、成員、屬性的命名規(guī)則與變量相同，可按自己的意愿，用有一定意義 的字母數(shù)串來表示，式中“ / ”和“ /:” 是規(guī)定的語法規(guī)則 。 本例再定義客戶集合 ： VD/V1..V8/:DJ。 該集合有 8個成員， DJ 是集合的屬性（有 8個分量）表示各客戶的需求量 . 以上兩個集合稱為 初始集合（或稱基本集合、原始集合）初始集合的屬性都 相當(dāng)于一維數(shù)組。 為表示數(shù)學(xué)模型中從貨棧到客戶的運輸關(guān)系以及與此相關(guān)的運輸單價 和運量 再定義一個表示運輸關(guān)系的集合： LINKS(WH,VD): C,X。 該集合以初始集合 WH 和 VD 為基礎(chǔ)，稱為衍生集合（或稱派生集合） . C 和 X 是該衍生集合的兩個屬性，衍生集合的定義語句有如下要素組成 ： 1）集合的名稱； (2) 集合的初始集合； （ 3）集合的成員（可以省略不寫）； （ 4）集合的屬性（可以沒有） 定義衍生集合時可以用羅列的方式將衍生集合成員一一列舉出來，如果省略不寫，則 默認衍生集合的成員取它所對應(yīng)初始集合的所有可能組合，上述衍生集合 LINKS的定 以中沒有指明成員，則它對應(yīng)的初始集合 WH 有 6個成員， VD 有 8 個成員，因此 LINKS 成員取 WH和 VD的所有可能組合，即有 48個成員， 48個成員可以排列成一個矩陣。其 行數(shù)與集合 WH的成員個數(shù)相等，列數(shù)與集合 VD成員的個數(shù)相等 . 相應(yīng)地，集合 LINKS的 屬性Ｃ和Ｘ都相當(dāng)于二維數(shù)組，各有 48個分量，Ｃ表示貨棧Ｗ i 到客戶 Vj的單位貨物運價 X 表示貨棧 Wi到客戶 Vj的貨物運量 . 本 模型完整的集合定義為： SETS: WH/W1..W6/:AI。 VD/V1..V8/DJ。 LINKS(WH,VD):C,X。 ENDSETS 注：集合定義部分以語句 SETS: 開始， 以 ENDSETS語句結(jié)束，這兩個語句需單獨成一行， ENDSETS后面不加標(biāo)點符號 . 二、數(shù)據(jù)初始化（數(shù)據(jù)段） 以上集合中屬性 X（有 48個分量）是決策變量，是待求的未知數(shù)，屬性 AI、 DJ和Ｃ（分別有６ ,8,48個分量）都是已知數(shù)， LINKS 建模語言通過數(shù)據(jù)初始化部分來實現(xiàn)對已知屬性賦以初始值，格式為： DATA: AI=60,55,51,43,41,52。 DJ=35,37,22,32,41,32,43,38。 C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3。 ENDDATA 注：數(shù)據(jù)初始化部分以語句 DATA:開始，以ENDDATE語句結(jié)束，這兩個語句需單獨成一行，數(shù) 據(jù)之間的逗號和空格可以互換。 三、目標(biāo)函數(shù)和約束條件 目標(biāo)函數(shù)表達式 用 LINGO語句表示為 MIN=@SUM(LINKS(I,J):C(I,J)*X(I,J))。 式中， @SUM 是 LINGO提供的內(nèi)部函數(shù)，其作用是對某個集合的所有成員 求制定表達式的和，該函數(shù)需要兩個參數(shù)，第一個參數(shù)是 集合名稱 ，制定對該 集合的所有成員求和，如果此集合是一個初始集合，它有 m 個成員，則求和運算 對 m 個成員進行，相當(dāng)于求 ，第二個參數(shù)是一個表達式，表示求和運算對該 表達式進行，此處， @SUM的第一個參數(shù)是 LINKS（ I， J），表示求和運算 對 LINKS進行， 該集合的維數(shù)為 2，共有 48個成員，運算規(guī)則是：先對 48個成員 分別求表達式 C(I,J) *X(I,J) 的值，然后求和，相當(dāng)于求 ，表達式中的 C 和 X是集合的兩個屬性，它們各有 48個分量。 注：如果表達式中參與酸的屬性屬于同一個集合，則 語句中索引（相當(dāng)于矩陣或數(shù)組的下標(biāo)可以省略）（隱藏），假如表達式中參與運算的屬性屬于不同的集合，則不能省略屬性的索引 .本例的目標(biāo)函數(shù)可以表示成 MIN=@SUM(LINKS:C*X)。 約束條件 用Ｌ INGO 語言描述該約束條件，語句為： @FOR(WH(I): @SUM(VD(J):X(I,J))=AI(I))。 語句中的 @FOR 是 LINGO提供的內(nèi)部函數(shù)，它的作用是對某個集合的所有成員 分別生成一個約束表達式，它有兩個參數(shù)，第一個參數(shù)是集合名，表示對該集合 的所有成員生成對應(yīng)的約束表達式，上式 @ FOR 的第一個參數(shù)為ＷＨ，它表示 貨棧，共有６個成員，故應(yīng)生成６個約束表達式， @FOR 的第二個參數(shù)是約束 表達式的具體內(nèi)容，此處再調(diào)用 @SUM 函數(shù)，表示該約束的左邊是求和，是對集合 ＶＤ的８個成員，并且對表達式Ｘ (I,J) 中的第二維 J 求和，即 約束表達式的右邊是集合ＷＨ的屬性 AI，它有 6個分量，與 6個約束表達式一一對應(yīng)， 本句中的屬性分別屬于不同的集合，所以不能省略 I,J. 約束條件 表示為 @FOR(D(J)):@ SUM(VD(J):X(I,J))=DJ(J))。 完整的模型 MODEL: SETS: WH/W1..W6/:AI。 VD/V1..V8/:DJ。 LINKS(WH,VD):C,X。 ENDSETS DATA: AI=60,55,51,43,41,52。 DJ=35,37,22,32,41,32,43,38。 C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3。 ENDDATA MIN=@SUM(LINKS (I,J):C(I,J)*X(I,J))。 !目標(biāo)函數(shù) @FOR(WH(I): @SUM(VD(J):X(I,J))=AI(I))。 !約束條件 @FOR(VD(J):@SUM(VD(J):X(I,J))=DJ(J))。 END 以“ MODEL：”開始 集合定義部分從(―SETS：”到“ ENDSETS‖ )：定義集合及其屬性 ?以“ END‖結(jié)束 ?給出優(yōu)化目標(biāo)和約束 集合定義部分從(“DATA：”到“ ENDDATA” ) 整數(shù)規(guī)劃 Integer Programming, IP 整數(shù)規(guī)劃 （ Integer Programming）主要是指整數(shù)線性規(guī)劃。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個整數(shù)規(guī)劃問題。 所有變量都要求為整數(shù)的稱為 純整數(shù)規(guī)劃 （ Pure Integer Programming）或稱 全整數(shù)規(guī)劃 （ All integer Programming）； 僅有一部分變量要求為整數(shù)的稱為 混合整數(shù)規(guī)劃（ Mixed Integer Programming）； 有的變量限制其取值只能為 0或 1，這類特殊的整數(shù)規(guī)劃稱為 0－ 1規(guī)劃 (01 Integer Programming ) 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型 例 某工廠生產(chǎn)甲、乙兩種設(shè)備，已知生產(chǎn)這兩種設(shè)備需要消耗材料 A、材料 B，有關(guān)數(shù)據(jù)如下，問這兩種設(shè)備各生產(chǎn)多少使工廠利潤最大？ 設(shè)備 材 料 甲 乙 資源限量 材料 A（ kg） 2 3 14 材料 B（ kg） 1 利潤（元 /件） 3 2 解： 設(shè)生產(chǎn)甲、乙這兩種設(shè)備的數(shù)量分別為 x x2，由于是設(shè)備臺數(shù)，則其變量都要求為整數(shù)，建立模型如下 ： Maxz=3x1+2x2 2x1+3x2≤14 x1+≤ x x2≥0,且為整數(shù) 圖 4－ 1 要求該模型的解，不考慮整數(shù)約束條件，用圖解法對相應(yīng)線性規(guī)劃求解，其最優(yōu)解為： x1＝ x2＝ max z＝ 湊整得到的 （ 4， 2） 不在可行域范圍內(nèi)。 （ 3， 2） 點盡管在可行域內(nèi)，但沒有使目標(biāo)達到極大化。 （ 4， 1） 使目標(biāo)函數(shù)達到最大，即 z＝ 14。 IP可用 LINDO直接求解 max 3x1+2x2 st 2x1+3x214 x1+ end gin 2 ―gin 2‖表示 “ 前 2個變量為整數(shù) ” ，等價于： gin x1 gin x2 其中“ GIN 2”表示 2個變量都是一般整數(shù)變量。 （仍然默認為取值是非負的） LINDO可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃 (IP)， 模型的輸入與 LP問題類似 , 但需 在 END標(biāo)志后定義整型變量 。 0/1型的變量可由 INTEGER（可簡寫為 INT）命令來標(biāo)