規(guī)劃基本知識(shí)課件

1、第六章 數(shù)學(xué)規(guī)劃模型 §6.1 數(shù)學(xué)規(guī)劃模型的基本知識(shí)6.1.1 數(shù)學(xué)規(guī)劃模型的一般形式簡(jiǎn)單的優(yōu)化模型往往是一元或者多元，無(wú)約束或者等式約束的最值問(wèn)題。而在工程技術(shù)、經(jīng)濟(jì)金融管理、科學(xué)研究和日常生活等諸多領(lǐng)域中，人們常常遇到如下問(wèn)題：結(jié)構(gòu)設(shè)計(jì)要在滿足強(qiáng)度要求的條件下選擇材料的尺寸，使其總重量最輕；資源分配要在有限資源約束條件下制定各用戶的分配數(shù)量，使資源產(chǎn)生的總效益最大；生產(chǎn)計(jì)劃要按照產(chǎn)品的工藝流程和顧客需求，制定原料、零部件等訂購(gòu)、投產(chǎn)的日程和數(shù)量，盡量降低成本使利潤(rùn)最高。上述一系列問(wèn)題的實(shí)質(zhì)是：在一系列客觀或主觀限制條件下，尋求使所關(guān)心的某個(gè)或多個(gè)指標(biāo)達(dá)到最大（或最?。?。用數(shù)學(xué)建

2、模的方法對(duì)這類問(wèn)題進(jìn)行研究，產(chǎn)生了在一系列等式與不等式約束條件下，使某個(gè)或多個(gè)目標(biāo)函數(shù)達(dá)到最大（或最小）的數(shù)學(xué)模型，即數(shù)學(xué)規(guī)劃模型。建立數(shù)學(xué)規(guī)劃模型一般需要考慮以下三個(gè)要素：（1）決策變量：它通常是所研究問(wèn)題要求解的那些未知量，一般用維向量表示，其中表示問(wèn)題的第個(gè)決策變量。當(dāng)對(duì)賦值后它通常稱為該問(wèn)題的一個(gè)解。（2）目標(biāo)函數(shù)：它通常是所研究問(wèn)題要求達(dá)到最大（或最?。┑哪莻€(gè)（那些）指標(biāo)的數(shù)學(xué)表達(dá)式，它是決策變量的函數(shù)，記為。（3）約束條件：由所研究問(wèn)題對(duì)決策變量的限制條件給出，允許取值的范圍記為，即，稱為可行域。常用一組關(guān)于決策變量的等式（）和不等式（）來(lái)界定，分別稱為等式約束和不等式約束。數(shù)學(xué)規(guī)

3、劃模型可表達(dá)成如下一般形式： 其中是對(duì)目標(biāo)函數(shù)求最大值或最小值的意思，是“受約束于”的意思。由于等式約束總可以轉(zhuǎn)化為不等式約束，大于等于約束總可以轉(zhuǎn)化為小于等于約束，于是數(shù)學(xué)規(guī)劃模型的一般形式又可簡(jiǎn)化為：6.1.2 數(shù)學(xué)規(guī)劃模型的可行解與最優(yōu)解由數(shù)學(xué)規(guī)劃模型的一般形式，可行域可表達(dá)為： 滿足約束條件的解即可行域中的點(diǎn)稱為數(shù)學(xué)規(guī)劃模型的可行解；使目標(biāo)函數(shù)達(dá)到最大值或最小值的可行解，即可行域中使目標(biāo)函數(shù)達(dá)到最大值或最小值的點(diǎn)稱為數(shù)學(xué)規(guī)劃模型的最優(yōu)解。數(shù)學(xué)規(guī)劃模型的求解本質(zhì)就是在可行域中選擇使得目標(biāo)函數(shù)達(dá)到最優(yōu)的點(diǎn)，在運(yùn)籌學(xué)中對(duì)數(shù)學(xué)規(guī)劃模型的求解進(jìn)行了大量的研究和求解方法介紹，但總體來(lái)說(shuō)數(shù)學(xué)規(guī)劃模型

4、的求解比較復(fù)雜和繁瑣，有些問(wèn)題的求解非常困難。根據(jù)實(shí)際問(wèn)題建立的數(shù)學(xué)規(guī)劃模型，其結(jié)構(gòu)往往非常復(fù)雜且數(shù)據(jù)量大，不能使用普通方法求解，目前數(shù)學(xué)軟件已發(fā)展得比較成熟，可借助LINGO或MATLAB軟件進(jìn)行求解。6.1.3 數(shù)學(xué)規(guī)劃模型的基本類型數(shù)學(xué)規(guī)劃模型的分類方法較多，這里將數(shù)學(xué)規(guī)劃模型按照下列方式劃分：（1）線性規(guī)劃模型：目標(biāo)函數(shù)和約束條件都是線性函數(shù)的數(shù)學(xué)規(guī)劃模型； （2）整數(shù)規(guī)劃模型：決策變量要求取整數(shù)值的線性規(guī)劃模型； （3）非線性規(guī)劃模型：目標(biāo)函數(shù)或者約束條件中有非線性函數(shù)的數(shù)學(xué)規(guī)劃模型；（4）多目標(biāo)規(guī)劃模型：具有多個(gè)目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃模型。 本章主要介紹上述四類數(shù)學(xué)規(guī)劃模型。此外還有如

5、動(dòng)態(tài)規(guī)劃模型等，可查閱清華大學(xué)編運(yùn)籌學(xué)教材。§6.2 線性規(guī)劃模型6.2.1 線性規(guī)劃模型的一般形式線性規(guī)劃模型所解決的問(wèn)題具有以下共同特征：（1）每個(gè)問(wèn)題都可用一組決策變量 表示某一方案，決策變量的一組定值就代表一個(gè)具體方案。通常決策變量取值是非負(fù)的。（2）存在一定的限制條件（即約束條件），這些約束條件可用關(guān)于決策變量的一組線性等式或線性不等式來(lái)表示。（3）有一個(gè)目標(biāo)要求（即目標(biāo)函數(shù)），目標(biāo)函數(shù)可表示為關(guān)于決策變量的線性函數(shù)。根據(jù)問(wèn)題的需要，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。線性規(guī)劃模型的一般形式如下： 目標(biāo)函數(shù)： 約束條件： 用矩陣向量符號(hào)，可更簡(jiǎn)潔地表示線性規(guī)劃模型的一般形式：

6、目標(biāo)函數(shù)： 約束條件： 這里系數(shù)矩陣是矩陣，約束向量是列向量，價(jià)值向量是行向量。即：， ，關(guān)于線性規(guī)劃模型的求解，目前已有相當(dāng)完善的單純形算法（詳細(xì)參見(jiàn)清華大學(xué)編運(yùn)籌學(xué)教材）。在實(shí)際建模中，由于數(shù)據(jù)龐大，借助于LINGO、MATLAB等數(shù)學(xué)軟件進(jìn)行求解是完全可以實(shí)現(xiàn)的。6.2.2 線性規(guī)劃建模示例例6.1 貨機(jī)裝載問(wèn)題 一架貨機(jī)有三個(gè)貨艙：前艙、中艙和后艙。三個(gè)貨艙所能裝載貨物的最大重量和體積限制如表6-1所示。并且為了飛機(jī)的平衡，三個(gè)貨艙共裝載的貨物重量必須與其最大的容許量成比例。 表6-1 重量、體積限制 前艙 中艙 后艙 重量限制（噸） 10 16 8 體積限制（立方米） 6800 87

7、00 5300 現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，貨物的規(guī)格以及裝運(yùn)后獲得的利潤(rùn)如表6-2所示。表6-2 規(guī)格、利潤(rùn) 重量（噸） 空間（立方米/噸） 利潤(rùn)（元/噸） 貨物1 18 480 3100 貨物2 15 650 3800 貨物3 23 580 3500 貨物4 12 390 2850 問(wèn)應(yīng)如何安排裝運(yùn)，使得貨機(jī)本次飛行獲利最大？ 1. 模型假設(shè)（1）每種貨物可以無(wú)限細(xì)分； （2）每種貨物可以分布在一個(gè)或者多個(gè)貨艙內(nèi)； （3）不同的貨物可以放在同一個(gè)貨艙內(nèi)，并且可以保證不留空隙。 2. 模型建立（1）決策變量本問(wèn)題需要確定各種貨物放在每個(gè)貨艙內(nèi)的重量，于是用表示第種貨物放在第個(gè)貨艙內(nèi)的重

8、量，：分別表示貨物1，貨物2，貨物3和貨物4；：分別表示前艙、中艙和后艙。 以作為決策變量。（2）目標(biāo)函數(shù)需要實(shí)現(xiàn)總利潤(rùn)的最大化，于是目標(biāo)函數(shù)即為總利潤(rùn)函數(shù)： （3）約束條件供裝載的四種貨物的總重量約束： 三個(gè)貨艙的空間限制約束： 三個(gè)貨艙的重量限制約束： 三個(gè)貨艙裝入重量的平衡約束：綜合上述分析，貨機(jī)裝載問(wèn)題的數(shù)學(xué)模型為如下線性規(guī)劃模型： 3. 模型求解使用數(shù)學(xué)軟件MATLAB中的Linprog命令求解，求解結(jié)果為： 即使得貨機(jī)本次飛行獲利最大的裝運(yùn)安排為：貨物1不裝運(yùn)；貨物2在前艙裝載10噸，在后艙裝載5噸；貨物3在中艙裝載12.947噸，在后艙裝載3噸；貨物4在中艙裝載3.053噸。貨機(jī)

9、本次飛行獲利為：121516元。例6.2 連續(xù)投資問(wèn)題某部門在今后五年內(nèi)考慮給下列項(xiàng)目投資，已知：項(xiàng)目A，從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項(xiàng)目B，第三年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過(guò)4萬(wàn)元；項(xiàng)目C，第二年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過(guò)3萬(wàn)元；項(xiàng)目D，五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6% 。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)應(yīng)如何確定這些項(xiàng)目每年的投資額，使到第五年末擁有的資金本利總額為最大？這個(gè)連續(xù)投資問(wèn)題，與時(shí)間有關(guān)，屬于多階段決策問(wèn)題，我們也可設(shè)法建立其線性規(guī)劃模型。1. 模型假設(shè)（1）

10、該部門現(xiàn)有資金10萬(wàn)元可以完全用于投資；（2）每年產(chǎn)生的投資收益也可完全用于投資。2. 模型建立（1）決策變量設(shè)（）分別表示第年年初給項(xiàng)目A，B，C，D的投資額，以它們?yōu)槟Ｐ偷臎Q策變量。根據(jù)給定的條件，將決策變量列于表 6-3中。表6-3 決策變量 項(xiàng)目第一年 第二年第三年 第四年第五年A 0B 00 00C 00 00D （2）約束條件由于項(xiàng)目D每年都可以投資，且當(dāng)年末即能回收本息。所以該部門每年應(yīng)把資金全部投出去，手中不應(yīng)當(dāng)有剩余的呆滯資金。因此第一年：該部門年初擁有10萬(wàn)元，可投資項(xiàng)目A與項(xiàng)目D，于是應(yīng)有第二年：第二年初擁有的資金額僅為項(xiàng)目D在第一年回收的本息。而第二年年初可投資A、C、

11、 D三個(gè)項(xiàng)目，于是第二年的投資分配應(yīng)為第三年：第三年初擁有的資金額是從項(xiàng)目A第一年投資及項(xiàng)目D第二年投資中回收的本利總和及。而第三年年初可投資A、B、 D三個(gè)項(xiàng)目，于是第三年的投資分配應(yīng)為第四年與第五年：同以上分析，可得此外，對(duì)項(xiàng)目B、C的投資有限額規(guī)定，即：，（3）目標(biāo)函數(shù)要求第五年末該部門手中擁有的資金額達(dá)到最大，于是目標(biāo)函數(shù)可表示為：綜合上述分析，這個(gè)連續(xù)投資問(wèn)題的數(shù)學(xué)模型為如下線性規(guī)劃模型： 3. 模型求解使用數(shù)學(xué)軟件MATLAB中的Linprog命令求解，其結(jié)果可表示為表 6-4。 表6-4 求解結(jié)果項(xiàng)目第一年第二年第三年第四年第五年A3.47833.91304.50B00400C0

12、3000D6.52170000到第五年末，該部門擁有的資金總額為14.375萬(wàn)元，即盈利43.75% 。§6.3 整數(shù)規(guī)劃模型6.3.1 整數(shù)規(guī)劃模型的基本知識(shí)線性規(guī)劃模型的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問(wèn)題的建模中，只有當(dāng)決策變量的取值為整數(shù)時(shí)才有意義。例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。要求全部或部分決策變量的取值為整數(shù)的線性規(guī)劃模型，稱為整數(shù)規(guī)劃模型。全部決策變量的取值都為整數(shù)的整數(shù)規(guī)劃模型，稱為純整數(shù)規(guī)劃模型；僅要求部分決策變量的取值為整數(shù)的整數(shù)規(guī)劃模型，稱為混合整數(shù)規(guī)劃模型；要求決策變量只能取0或1值的整數(shù)規(guī)劃

13、模型，則稱為0-1規(guī)劃模型。 純整數(shù)規(guī)劃模型的一般形式為： 0-1規(guī)劃模型的一般形式為： 整數(shù)規(guī)劃模型的求解比線性規(guī)劃模型的求解要難得多，整數(shù)規(guī)劃模型求解的困難在于模型的維數(shù)（決策變量與約束條件的個(gè)數(shù)）增加時(shí)，計(jì)算量將爆炸性（即按指數(shù)規(guī)律）增加。下面是一些有關(guān)整數(shù)規(guī)劃模型常用的求解方法。（1）枚舉法與隱枚舉法：常用于0-1規(guī)劃模型的求解，但模型的維數(shù)高時(shí)不可行。（2）分枝定界法：對(duì)純整數(shù)規(guī)劃模型和混合整數(shù)規(guī)劃模型的求解均適用，比較可行。（3）割平面法：對(duì)純整數(shù)規(guī)劃模型和混合整數(shù)規(guī)劃模型的求解均適用，比較可行。以上求解整數(shù)規(guī)劃模型的詳細(xì)算法，請(qǐng)參見(jiàn)清華大學(xué)編運(yùn)籌學(xué)教材。在實(shí)際建模中，可借助于LI

14、NGO、MATLAB等數(shù)學(xué)軟件對(duì)整數(shù)規(guī)劃模型進(jìn)行求解。6.3.2 指派問(wèn)題問(wèn)題：設(shè)有項(xiàng)任務(wù)要派個(gè)人去完成，但由于任務(wù)的性質(zhì)和個(gè)人專長(zhǎng)不同，每個(gè)人去完成不同任務(wù)的效率（或所用時(shí)間）有所不同。試問(wèn)應(yīng)當(dāng)派哪個(gè)人去完成哪項(xiàng)任務(wù)，使總的效率最高（或所用的總時(shí)間最少）？這類問(wèn)題稱為指派問(wèn)題。設(shè)表示第人完成第項(xiàng)任務(wù)所需的時(shí)間，表示所用總時(shí)間。決策變量設(shè)置如下：由于問(wèn)題的要求，每項(xiàng)任務(wù)均要有人去完成，即有又每人均要被分派任務(wù)，即有 以所用總時(shí)間作為目標(biāo)函數(shù)，指派問(wèn)題的解決歸結(jié)為如下0-1規(guī)劃模型： 對(duì)于指派問(wèn)題的求解，已有較成熟的匈牙利算法（參見(jiàn)清華大學(xué)編運(yùn)籌學(xué)教材）。在實(shí)際建模中，可用LINGO、MATLA

15、B等數(shù)學(xué)軟件進(jìn)行求解。6.3.3 整數(shù)規(guī)劃建模示例例6.3 兩輛平板車裝載問(wèn)題有七種規(guī)格的包裝箱要裝到兩節(jié)鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以cm 計(jì)）及重量（w，以kg計(jì)）是不同的。表6-5給出了每種包裝箱的厚度、重量以及數(shù)量。每節(jié)平板車有10.2m 長(zhǎng)的地方可用來(lái)裝包裝箱（像面包片那樣），載重為40噸。由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)于C5, C6, C7 類包裝箱的總數(shù)有一個(gè)特別的限制：這類箱子所占的空間（厚度）不能超過(guò)302.7cm。 試設(shè)計(jì)一種裝車方案，使得浪費(fèi)的空間最小。 表6-5 厚度、重量及數(shù)量包裝箱類型C1C2C3C4C5C6C7厚度t/cm48.752.061.37

16、2.048.752.064.0重量w/kg200030001000500400020001000數(shù)量/件87966481. 模型假設(shè)（1）各種規(guī)格的包裝箱的寬和高是一樣的，且滿足裝車的寬、高要求，平板車能裝包裝箱的數(shù)量只與包裝箱的厚度與重量有關(guān)；（2）每件包裝箱不能拆分裝車；（3）每種包裝箱可以分布在不同的平板車上； （4）不同的包裝箱可以放在同一個(gè)平板車上，并且可以保證不留空隙。2. 模型建立（1）決策變量設(shè)（）表示在第節(jié)車上裝載第種包裝箱的數(shù)量，以為決策變量，只能取非負(fù)整數(shù)值。（2）約束條件以表示第種包裝箱可用裝車的件數(shù)，兩節(jié)車的裝箱數(shù)不能超過(guò)可用裝車的件數(shù)，故有：以表示第節(jié)車可用裝箱的長(zhǎng)

17、度，表示第種包裝箱的厚度，每節(jié)車可裝的長(zhǎng)度不能超過(guò)車能提供的長(zhǎng)度，故有：以表示第種包裝箱的重量，表示第節(jié)車的載重量，每節(jié)車可裝的重量不能超過(guò)車能夠承受的載重量，故有：對(duì)于C5, C6, C7類包裝箱的總數(shù)的特別限制記為（），故有：（3）目標(biāo)函數(shù)浪費(fèi)的空間最小，即所裝包裝箱的總厚度最大。以所裝包裝箱的總厚度為目標(biāo)函數(shù)，所裝包裝箱的總厚度表達(dá)式為：綜合上述分析，兩輛平板車裝載問(wèn)題的數(shù)學(xué)模型為如下整數(shù)規(guī)劃模型： 3. 模型求解運(yùn)用LINGO軟件得到最優(yōu)解：，最優(yōu)目標(biāo)值，即按此最優(yōu)裝車方案兩輛平板車共剩余空間。另外，此模型完全適用于兩輛平板車的載重量和可用裝載空間不同的情形。例6.4 DVD在線租賃分

18、配問(wèn)題某網(wǎng)站有種DVD，每種DVD的數(shù)量有限。需在該網(wǎng)站租賃DVD的顧客只要在線提交訂單，網(wǎng)站就會(huì)通過(guò)快遞的方式盡可能滿足要求。網(wǎng)站規(guī)定顧客提交訂單時(shí)，顧客應(yīng)在訂單上填寫10種愿意觀看的DVD，并且基于對(duì)這些DVD的偏愛(ài)程度，用1，2，10的數(shù)字對(duì)填寫的10種DVD進(jìn)行排序預(yù)定，其余種類的DVD填寫數(shù)字0，表示不愿意觀看。網(wǎng)站會(huì)根據(jù)手頭現(xiàn)有的DVD數(shù)量和顧客的訂單進(jìn)行分發(fā)DVD，并且每位顧客每次只能獲得3張DVD。表6-6中列出了網(wǎng)站手上20種DVD的現(xiàn)有張數(shù)和當(dāng)前需要處理的100位顧客的在線訂單，網(wǎng)站如何對(duì)這些DVD進(jìn)行分配，才能使顧客獲得最大的滿意度？試建立其數(shù)學(xué)模型。表6-6 現(xiàn)有DVD

19、張數(shù)和當(dāng)前需要處理的會(huì)員的在線訂單（表格格式示例）DVD編號(hào)D001D002D003D004DVD現(xiàn)有數(shù)量812210顧客在線訂單C00010020C00021090C000336100C000480541. 模型假設(shè)（1）網(wǎng)站對(duì)其顧客分配DVD時(shí)，只能向其提供已經(jīng)預(yù)定的DVD，即訂單中填寫數(shù)字為0的DVD不分配給顧客；（2）每位顧客每次租賃只能獲得3張或0張DVD；（3）顧客訂單中對(duì)已預(yù)定DVD的排序數(shù)字1，2，10越小，表示顧客獲得該種DVD的滿意度越大，顧客獲得沒(méi)有預(yù)定DVD的滿意度為0。2. 模型建立（1）決策變量定義如下0-1變量作為決策變量：（2）目標(biāo)函數(shù)設(shè)有位顧客，網(wǎng)站共有種DV

20、D，則顧客在線訂單中的偏愛(ài)排序數(shù)字1，2，10和0形成階矩陣，記為，稱為偏愛(ài)排序矩陣。表示第個(gè)顧客不愿意觀看第種DVD；為1，2，10中數(shù)字之一時(shí)，數(shù)字越小表示第個(gè)顧客對(duì)第種DVD越偏愛(ài)，相應(yīng)第個(gè)顧客獲得第種DVD時(shí)，其滿意度越高。為此按下列方式定義第個(gè)顧客獲得第種DVD時(shí)的滿意度指標(biāo)：表示第個(gè)顧客不愿意觀看第種DVD，其滿意度為0；為1，2，10中數(shù)字之一時(shí)，數(shù)字越大表示第個(gè)顧客獲得第種DVD時(shí)，其滿意度越高。稱為滿意度矩陣。所有顧客獲得各種DVD的總體滿意度指標(biāo)由下式表達(dá)：我們的目標(biāo)即為實(shí)現(xiàn)總體滿意度指標(biāo)的最大化。（3）約束條件以表示第j種DVD的現(xiàn)有數(shù)量。顯然，對(duì)每種DVD，要求分配的總

21、量不超過(guò)相應(yīng)的現(xiàn)有數(shù)量。即有：又根據(jù)假設(shè)，網(wǎng)站只向會(huì)員提供其預(yù)定的DVD，即只有當(dāng)滿意度指標(biāo)不為0時(shí)，才可以進(jìn)行分配。故引入約束：進(jìn)一步，對(duì)每個(gè)顧客每次租賃只能獲得3張其預(yù)定的DVD或不能得到DVD，于是有：引人0-1變量，上述約束條件又可表達(dá)為：綜合上述分析，DVD在線租賃分配問(wèn)題的數(shù)學(xué)模型為如下0-1規(guī)劃模型： 3. 模型求解引用2005年全國(guó)數(shù)模競(jìng)賽所給數(shù)據(jù)，利用LINGO軟件對(duì)上述0-1規(guī)劃模型進(jìn)行求解是完全可以實(shí)現(xiàn)的，這里求解結(jié)果略。§6.4 非線性規(guī)劃模型6.4.1 非線性規(guī)劃模型的基本知識(shí)在數(shù)學(xué)規(guī)劃模型中，如果目標(biāo)函數(shù)或約束條件、中包含非線性函數(shù)，就稱這種規(guī)劃模型為非線

22、性規(guī)劃模型。稱為非線性規(guī)劃模型的可行域。定義6.1 若有，使得，均有（或）則稱為非線性規(guī)劃模型的全局最優(yōu)解。定義6.2 稱為點(diǎn)的鄰域，其中，為向量的模；若有，使得均有（或）則稱為非線性規(guī)劃模型的局部最優(yōu)解。一般說(shuō)來(lái)，求解非線性規(guī)劃模型要比求解線性規(guī)劃模型困難得多。而且，也不像線性規(guī)劃模型的求解有單純形法這一通用算法，非線性規(guī)劃模型目前還沒(méi)有適于各種問(wèn)題的一般算法，各種算法都有自己特定的適用范圍。由于非線性規(guī)劃模型的復(fù)雜性，在求解非線性規(guī)劃模型的過(guò)程中，有時(shí)只能找到模型的局部最優(yōu)解，局部最優(yōu)解還不一定是全局最優(yōu)解。特別，若某非線性規(guī)劃模型的目標(biāo)函數(shù)為決策變量的二次函數(shù)，約束條件與線性規(guī)劃模型一樣

23、全是線性等式和線性不等式，稱這種特殊形式的非線性規(guī)劃模型為二次規(guī)劃模型。二次規(guī)劃模型的一般形式為： 這里系數(shù)矩陣是矩陣，約束向量是列向量，是實(shí)對(duì)稱矩陣，是列向量。 二次規(guī)劃模型有成熟的求解算法，特別當(dāng)是正定或半正定矩陣時(shí)，可得到全局最優(yōu)解。用LINGO、MATLAB等數(shù)學(xué)軟件進(jìn)行求解也較為方便，二次規(guī)劃模型有著非常廣泛的應(yīng)用。6.4.2 非線性規(guī)劃模型的常用解法介紹非線性規(guī)劃模型在工程計(jì)算和經(jīng)濟(jì)管理中經(jīng)常遇到，近二十年來(lái)對(duì)非線性規(guī)劃模型求解算法的研究有了很大發(fā)展，其求解方法大體可分為以下幾類：（1）利用問(wèn)題的最優(yōu)性條件來(lái)求解的方法。（2）利用線性規(guī)劃或二次規(guī)劃來(lái)逐次逼近求解的方法，例如線性逼近

24、法、二次逼近法等。（3）把約束非線性規(guī)劃模型轉(zhuǎn)化為一個(gè)或一系列無(wú)約束非線性規(guī)劃模型來(lái)求解的方法，例如懲罰函數(shù)法、精確懲罰函數(shù)法、乘子法等。（4）對(duì)約束非線性規(guī)劃模型不預(yù)先進(jìn)行轉(zhuǎn)換，直接進(jìn)行處理的分析方法，例如可行方向法、梯度投影法、廣義既約梯度法等。（5）對(duì)約束非線性規(guī)劃模型不預(yù)先進(jìn)行轉(zhuǎn)換的直接求解方法，例如復(fù)形法、隨機(jī)試驗(yàn)法等。對(duì)于上述一系列關(guān)于非線性規(guī)劃模型的求解方法，可詳細(xì)參見(jiàn)清華大學(xué)編運(yùn)籌學(xué)教材等參考文獻(xiàn)。目前，如乘子法、精確懲罰函數(shù)法、廣義既約梯度法、二次逼近法等方法都已開(kāi)發(fā)成計(jì)算機(jī)軟件，并在實(shí)際應(yīng)用中獲得成功。6.4.3 非線性規(guī)劃建模示例例6.5 股票組合投資問(wèn)題現(xiàn)有一筆資金決定

25、進(jìn)行股票投資，以一年為一個(gè)投資周期。市場(chǎng)上有種股票（）可供選擇，投資這種股票在過(guò)去年份的收益率情況可統(tǒng)計(jì)得到。對(duì)各種股票按適當(dāng)?shù)馁Y金比例進(jìn)行投資稱為組合投資。一般組合投資能夠滿足達(dá)到一定的總體預(yù)期收益率，同時(shí)有效降低總體風(fēng)險(xiǎn)。（1）試設(shè)計(jì)一種組合投資方案，即確定投資各種股票的資金比例，使總體收益率至少達(dá)到，并且總體風(fēng)險(xiǎn)盡量小。（2）表6-7中給出了三種股票過(guò)去十二年的投資收益情況，試就只有表6-7中三種股票可供選擇時(shí)進(jìn)行計(jì)算。表6-7 三種股票過(guò)去十二年的投資收益情況股票第1年1.3001.2251.149第2年1.1031.2901.260第3年1.2161.2161.419第4年0.954

26、0.7280.922第5年0.9291.1441.169第6年1.0561.1070.965第7年1.0381.3211.133第8年1.0891.3051.732第9年1.0901.1951.021第10年1.0831.3901.131第11年1.0350.9281.006第12年1.1761.7151.908注：表6-7中的第一個(gè)數(shù)據(jù)1.300的含義是股票在第1年年末價(jià)值是其年初價(jià)值的1.300倍，即收益率為，其余數(shù)據(jù)的含義依次類推。1. 問(wèn)題分析人們投資某股票時(shí)的收益率是不確定的，可將收益率視為一個(gè)隨機(jī)變量，因此用收益率的平均值即數(shù)學(xué)期望值來(lái)表達(dá)投資某股票時(shí)的期望收益率。除了考慮期望收益

27、率外，還要考慮風(fēng)險(xiǎn)，一般投資某股票的收益率越不穩(wěn)定即波動(dòng)幅度越大，就認(rèn)為其風(fēng)險(xiǎn)越大，因此可用收益率的方差來(lái)衡量投資某股票的風(fēng)險(xiǎn)：方差越大，則認(rèn)為其風(fēng)險(xiǎn)越大；方差越小，則認(rèn)為其風(fēng)險(xiǎn)越小。同時(shí)還應(yīng)考慮股票間的相關(guān)性，由概率論的知識(shí)可知，兩種股票收益率的協(xié)方差表示的則是它們之間的相關(guān)程度：（1）協(xié)方差為時(shí)，兩者不相關(guān)；（2）協(xié)方差為正數(shù)時(shí)，表示兩者正相關(guān)，協(xié)方差越大則正相關(guān)性越強(qiáng)，即越有可能一賺皆賺，一賠皆賠；（3）協(xié)方差為負(fù)數(shù)時(shí)，表示兩者負(fù)相關(guān)，即越有可能一個(gè)賺，另一個(gè)賠。2. 模型假設(shè)（1）影響投資決策的主要因素為期望收益率和風(fēng)險(xiǎn)兩項(xiàng)，不受意外因素影響；（2）用收益率的方差來(lái)衡量風(fēng)險(xiǎn)，用收益率的

28、協(xié)方差來(lái)衡量股票間的相關(guān)程度；（3）遵守占優(yōu)原則：同一收益率水平下，選擇風(fēng)險(xiǎn)低的投資方案；（4）不考慮交易費(fèi)用；（5）手上現(xiàn)有資金全部用于股票投資。3. 模型建立（1）決策變量以，分別表示投資于，這種股票的資金比例，則向量表示一個(gè)投資組合，以其作為決策變量。（2）目標(biāo)函數(shù)設(shè)，分別為投資，這種股票的收益率，則其期望收益率分別為，。按投資組合進(jìn)行投資時(shí)，其組合收益率為，也是一個(gè)隨機(jī)變量，期望組合收益率為：組合風(fēng)險(xiǎn)（即組合收益率的方差）為：注：符號(hào)表示數(shù)學(xué)期望，表示方差，表示與的協(xié)方差。我們的目標(biāo)是希望組合風(fēng)險(xiǎn)盡量小，因此目標(biāo)函數(shù)即為：（3）約束條件手上現(xiàn)有資金全部用于這種股票的投資，因此有：根據(jù)題

29、設(shè)要求，期望組合收益率應(yīng)大于等于給定的預(yù)期收益率（），于是有：綜合上述分析，股票組合投資問(wèn)題的數(shù)學(xué)模型為如下二次規(guī)劃模型： 4. 模型求解（1）數(shù)據(jù)準(zhǔn)備根據(jù)概率論的知識(shí)和表6-7中給出的數(shù)據(jù)，計(jì)算出三種股票的期望收益率和三種股票收益率的協(xié)方差矩陣如下：，即： ，。（2）求解取和，將上述數(shù)據(jù)代入股票組合投資問(wèn)題的二次規(guī)劃模型，利用LINGO軟件進(jìn)行求解，其最優(yōu)解為：，即投資三種股票的資金比例大致是：占，占，占，相應(yīng)的風(fēng)險(xiǎn)值為。 此外，股票組合投資問(wèn)題還有：（1）存在（例如可買國(guó)庫(kù)券等）無(wú)風(fēng)險(xiǎn)資產(chǎn)；（2）考慮交易成本等情形。這些情形下的股票組合投資問(wèn)題的數(shù)學(xué)模型請(qǐng)讀者思考。例6.6 節(jié)水洗衣機(jī)問(wèn)題

30、我國(guó)淡水資源有限，節(jié)約用水人人有責(zé)。洗衣機(jī)在家庭用水中占有相當(dāng)大的份額，目前洗衣機(jī)已非常普及，節(jié)約洗衣機(jī)用水十分重要。假設(shè)在放入衣物和洗滌劑后洗衣機(jī)的運(yùn)行過(guò)程為：加水漂洗脫水加水漂洗脫水加水漂洗脫水（稱“加水漂洗脫水”為運(yùn)行一輪）。請(qǐng)為洗衣機(jī)設(shè)計(jì)一種程序（包括運(yùn)行多少輪、每輪加多少水等），使得在滿足一定洗滌效果的條件下，總用水量最少。1. 問(wèn)題分析（1）洗衣的基本原理與過(guò)程洗衣的基本原理就是將吸附在衣物上的污物溶于水中，通過(guò)脫去污水而帶走污物?！叭芪畚锩撐鬯笔怯蓛蓚€(gè)基本要素構(gòu)成的“元操作”，無(wú)論是如何精心設(shè)計(jì)的洗衣方式和程序都是以此為基礎(chǔ)的。洗衣的過(guò)程就是通過(guò)加水來(lái)實(shí)現(xiàn)上述“溶污物脫污水”操

31、作的反復(fù)執(zhí)行，使得殘留在衣物上的污物越來(lái)越少，直到滿意的程度。通常洗衣要加入洗滌劑，它幫助衣物上原有的污物溶解。但應(yīng)注意，洗滌劑本身也是不希望留在衣物上的東西。因此“污物”應(yīng)是衣物上原有污物與洗滌劑的總和。有了這種認(rèn)識(shí)后，就可以統(tǒng)一地處理“洗滌”過(guò)程（即通常加洗滌劑的首輪洗衣）和“漂洗”過(guò)程（即通常的以后各輪洗衣，不再加洗滌劑，但水中還有剩余洗滌劑），把二者都看作“溶污物”環(huán)節(jié)?！懊撐鬯痹谙匆聶C(jī)中稱為“脫水”，一般是由“排水”和“甩干”兩個(gè)步驟組成。（2）節(jié)水洗衣機(jī)問(wèn)題要點(diǎn)分析 立足于“溶污物脫污水”這種基本原理，我們可以找出節(jié)水洗衣機(jī)問(wèn)題的基本要點(diǎn)如下：1）污物的溶解情況如何？我們將用“溶

32、解特征”來(lái)刻畫；2）每輪脫去污水后，污物減少情況如何？這將由系統(tǒng)的動(dòng)態(tài)方程表示；3）如何設(shè)計(jì)由一系列“溶污物脫污水”構(gòu)成的節(jié)水洗衣機(jī)程序？這將通過(guò)用水程序來(lái)反映，也是我們最終需要的結(jié)果。 2. 模型假設(shè)（1）僅考慮離散的洗衣方案，即“加水溶污物脫污水”（以下稱為“加水漂洗脫水”）三個(gè)環(huán)節(jié)是分離的，這三個(gè)環(huán)節(jié)構(gòu)成一個(gè)洗衣周期，稱為一輪；（2）每輪用水量不能低于高度，否則洗衣機(jī)無(wú)法轉(zhuǎn)動(dòng)；用水量高度不能高于，否則會(huì)溢出，設(shè)；（3）每次洗漂的時(shí)間是足夠的，以便衣物上的污物充分溶入水中，從而使每輪所加的水被充分利用；（4）脫水時(shí)間也是足夠的，以使污水充分脫出，即讓衣物所含的污水量達(dá)到一個(gè)低限，設(shè)這個(gè)低限

33、為一個(gè)大于0的常數(shù)，設(shè)。3. 模型建立（1）決策變量設(shè)共進(jìn)行輪“加水漂洗脫水”的過(guò)程，依次為第0輪，第1輪，第輪。第輪用水量（單位：高度）為（），以為模型的決策變量。（2）目標(biāo)函數(shù)輪總用水量，根據(jù)要求我們以為目標(biāo)函數(shù)，實(shí)現(xiàn)其最小化。（3）溶解特性、動(dòng)態(tài)方程、約束條件設(shè)衣物上的初始污物量為，在第輪脫水之后仍吸附在衣物上的污物量為。在第輪洗漂之后和脫水之前，第輪脫水之后的污物量已變成了兩部分：，（）其中表示已溶入水中的污物量，表示尚未溶入水中的污物量。與第輪的加水量有關(guān)，總的規(guī)律應(yīng)是，越大越大，且當(dāng)時(shí)，最?。ǎ?yàn)榇藭r(shí)洗衣機(jī)處于轉(zhuǎn)動(dòng)臨界點(diǎn)，有可能無(wú)法轉(zhuǎn)動(dòng)，該輪洗衣無(wú)效）；當(dāng)時(shí)，最大（ 這里假設(shè)，其

34、中稱為“溶解率”），因此簡(jiǎn)單地選擇線性關(guān)系表示這種溶解特性則有： （6.1）在第輪脫水之后，衣物上尚有污物。有污水，其中污水中含有污物量為，于是第輪完成之后衣物上尚存的污物總量為： （6.2）將（6.1）代入（6.2）式，并整理后得系統(tǒng)動(dòng)態(tài)方程：，（） （6.3）由于是洗衣全過(guò)程結(jié)束后衣物上最終殘存的污物量，而是初始污物量，故反映了洗滌效果，越小，洗滌效果越好，我們?cè)O(shè)定適當(dāng)小的正數(shù)（ ），用來(lái)表示達(dá)到設(shè)定的洗滌效果。由系統(tǒng)動(dòng)態(tài)方程（6.3）可得： （6.4）于是達(dá)到設(shè)定的洗滌效果可用下列約束條件表示： （6.5）同時(shí)每輪的用水量還應(yīng)滿足不小于，不超過(guò)。于是應(yīng)有約束條件：，（） （6.6）綜合上

35、述分析，節(jié)水洗衣機(jī)問(wèn)題的數(shù)學(xué)模型為如下非線性規(guī)劃模型： 若令：，即。則上述節(jié)水洗衣機(jī)問(wèn)題的非線性規(guī)劃模型變成為如下更簡(jiǎn)潔的形式： 其中：，4. 模型求解（1）最少洗衣輪數(shù)定義函數(shù)：，（）。易知： ，（）可見(jiàn)是區(qū)間上的單調(diào)減函數(shù)，所以在區(qū)間上的最小值為：第輪的洗滌效果為： ，（）由此不難得出輪洗完后洗凈效果最多可達(dá)到： 給定洗凈效果的要求，則應(yīng)有：于是， （6.7）設(shè)為滿足（6.7）式的最小正整數(shù)，則最少洗衣輪數(shù)即為。（2）算法可選用一種求解非線性規(guī)劃模型的算法，例如精確懲罰函數(shù)法，對(duì)于， ，（憑常識(shí)洗衣的輪數(shù)不應(yīng)太多，比如可取已足夠）進(jìn)行枚舉求解，然后選出最好的結(jié)果。其中是滿足（6.7）式的最

36、小正整數(shù)。注意不必使用求解混合整數(shù)非線性規(guī)劃問(wèn)題的算法，那將使問(wèn)題復(fù)雜化。 5. 注記（1）模型中的乘積約束可化為：；（2）在實(shí)際中，無(wú)論是參數(shù)，以及洗凈效果要求，還是溶解特性，均應(yīng)在各種不同條件下（比如針對(duì)衣物量的多少、衣物的各種質(zhì)地以衣物的臟污程度）通過(guò)試驗(yàn)確定。§6.5 多目標(biāo)規(guī)劃模型6.5.1 多目標(biāo)規(guī)劃模型的基本知識(shí)前面介紹的線性規(guī)劃模型、整數(shù)規(guī)劃模型、非線性規(guī)劃模型中的目標(biāo)函數(shù)都只有一個(gè)。而在許多實(shí)際問(wèn)題中，衡量一個(gè)方案好壞的標(biāo)準(zhǔn)往往不止一個(gè)，例如設(shè)計(jì)導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高。這一類問(wèn)題稱為多目標(biāo)規(guī)劃問(wèn)題。對(duì)多目標(biāo)規(guī)劃問(wèn)題建立其具有多個(gè)目標(biāo)函數(shù)的數(shù)學(xué)

37、規(guī)劃模型稱為多目標(biāo)規(guī)劃模型。具有個(gè)目標(biāo)的多目標(biāo)規(guī)劃模型的一般形式為：目標(biāo)函數(shù) 由于等式約束總可以轉(zhuǎn)化為不等式約束，大于等于約束總可以轉(zhuǎn)化為小于等于約束，同時(shí)目標(biāo)函數(shù)的最大化總可以轉(zhuǎn)化為目標(biāo)函數(shù)的最小化，于是多目標(biāo)規(guī)劃模型的一般形式又可簡(jiǎn)化為：稱為多目標(biāo)規(guī)劃模型的可行域。多目標(biāo)規(guī)劃模型的一般形式又可表達(dá)為：其中表示對(duì)個(gè)目標(biāo)，以追求最小為目的。設(shè)有兩向量，。規(guī)定以下幾個(gè)有關(guān)向量比較的符號(hào)。（1）符號(hào)“”：若，則意味著的每個(gè)分量都要小于或等于的對(duì)應(yīng)的分量；（2）符號(hào)“”：若，則意味著的每個(gè)分量都要嚴(yán)格小于的對(duì)應(yīng)的分量；（3）符號(hào)“”：若，則意味著的每個(gè)分量都要小于或等于的對(duì)應(yīng)的分量，并且存在的某一個(gè)

38、分量嚴(yán)格的小于的對(duì)應(yīng)的分量。定義6.3 設(shè)，若對(duì)于任意，均有，即對(duì)于，均有，則稱為多目標(biāo)規(guī)劃模型的絕對(duì)最優(yōu)解。定義6.4 設(shè)，若不存在，使得，則稱為多目標(biāo)規(guī)劃模型的有效解。定義6.5 設(shè)，若不存在，使得，則稱為多目標(biāo)規(guī)劃模型的弱有效解。在多目標(biāo)規(guī)劃模型的個(gè)目標(biāo)中，有的相互聯(lián)系，有的相互制約，有的相互沖突。多目標(biāo)規(guī)劃模型除了目標(biāo)函數(shù)不只一個(gè)這一明顯的特點(diǎn)外，最顯著的還有以下兩點(diǎn)：目標(biāo)間的不可公度性和目標(biāo)間的矛盾性。目標(biāo)間的不可公度性：是指各個(gè)目標(biāo)沒(méi)有統(tǒng)一的度量標(biāo)準(zhǔn)，因而難以直接進(jìn)行比較。例如房屋設(shè)計(jì)問(wèn)題中，造價(jià)目標(biāo)的單位是元/平方米，建造時(shí)間目標(biāo)的單位是年，而結(jié)構(gòu)、造型等目標(biāo)則為定性指標(biāo)；目標(biāo)間

39、的矛盾性：是指如果選擇一種方案以改進(jìn)某一目標(biāo)的值，可能會(huì)使另一目標(biāo)的值變壞，如房屋設(shè)計(jì)中造型、抗震性能目標(biāo)的提高可能會(huì)使房屋建造成本目標(biāo)提高。正是由于目標(biāo)間的矛盾性，解決實(shí)際問(wèn)題所建立的多目標(biāo)規(guī)劃模型常常沒(méi)有絕對(duì)最優(yōu)解，只能尋找其有效解或弱有效解。6.5.2 多目標(biāo)規(guī)劃模型的常用解法介紹多目標(biāo)規(guī)劃模型的解法大致可分為兩類：直接解法和間接解法。到目前為止，常用的多為間接解法，即根據(jù)問(wèn)題的實(shí)際背景和特征，設(shè)法將多目標(biāo)規(guī)劃模型轉(zhuǎn)化為單目標(biāo)規(guī)劃模型，從而得到多目標(biāo)規(guī)劃模型的滿意解。 1主要目標(biāo)法在多目標(biāo)規(guī)劃模型中，若能從個(gè)目標(biāo)中，確定一個(gè)目標(biāo)為主要目標(biāo)，例如，而把其余目標(biāo)作為次要目標(biāo)，并根據(jù)實(shí)際情況，

40、確定適當(dāng)?shù)慕缦拗?，這樣就可以把次要目標(biāo)作為約束來(lái)處理，而將多目標(biāo)規(guī)劃模型轉(zhuǎn)化為求解如下的單目標(biāo)線性或非線性規(guī)劃模型：其中界限值取為，則此單目標(biāo)規(guī)劃模型的最優(yōu)解必為原多目標(biāo)規(guī)劃模型的弱有效解。因此，用主要目標(biāo)法求得的解必是多目標(biāo)規(guī)劃模型的弱有效解或有效解。2分層序列法把多目標(biāo)規(guī)劃模型中的個(gè)目標(biāo)按其重要程度排一個(gè)次序，假設(shè)最重要，次之 ，再次之， ，最后一個(gè)目標(biāo)為。先求出以第一個(gè)目標(biāo)為目標(biāo)函數(shù)，而原模型中的約束條件不變的問(wèn)題：其最優(yōu)解為，最優(yōu)值為。再求解問(wèn)題：其最優(yōu)解為，最優(yōu)值為。再求解問(wèn)題：其最優(yōu)解為，最優(yōu)值為， ，如此繼續(xù)下去，直到求解第個(gè)問(wèn)題：其最優(yōu)解為，最優(yōu)值為。則就是原多目標(biāo)規(guī)劃模型在分

41、層序列意義下得最優(yōu)解，為其最優(yōu)值。常將分層序列法修改如下：選取一組適當(dāng)小的正數(shù)成為寬容值，把上述的問(wèn)題修改如下：再按上述方法依次求解各問(wèn)題， ， 。3線性加權(quán)求和法對(duì)多目標(biāo)規(guī)劃模型中的個(gè)目標(biāo)按其重要程度給以適當(dāng)?shù)姆秦?fù)權(quán)系數(shù)，且，然后用作為新的目標(biāo)函數(shù)，成為評(píng)價(jià)（目標(biāo)）函數(shù)，再求解單目標(biāo)規(guī)劃問(wèn)題：其最優(yōu)解為，取作為多目標(biāo)規(guī)劃模型的解。6.5.3 多目標(biāo)規(guī)劃建模示例例6.7 選課策略問(wèn)題某學(xué)校規(guī)定，運(yùn)籌學(xué)專業(yè)的學(xué)生畢業(yè)時(shí)必須至少學(xué)習(xí)兩門數(shù)學(xué)課程、三門運(yùn)籌學(xué)課程和兩門計(jì)算機(jī)課程。這些課程的編號(hào)、名稱 、學(xué)分、所屬類別和先修課程要求如表6-8所示。一般學(xué)生選課時(shí)要考慮總的課程門數(shù)和所獲得的學(xué)分。試設(shè)計(jì)

42、選課策略，在滿足畢業(yè)要求的同時(shí)，使得所修課程門數(shù)盡量少，所獲得的學(xué)分盡量多。表6-8 課程情況課程編號(hào)課程名稱學(xué)分所屬類別先修課程要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)6計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)8預(yù)測(cè)理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代數(shù)1. 模型假設(shè)（1）各個(gè)同學(xué)在選課時(shí)不受其他因素影響，只受學(xué)分和選課門數(shù)影響；（2）各門課程沒(méi)有人數(shù)限制；（3）僅考慮表6-8所列9門課程。2. 模型建立（1）決策變量定義如下0-1變量作為決策

43、變量：（2）約束條件至少選兩門數(shù)學(xué)課程、三門運(yùn)籌學(xué)課程和兩門計(jì)算機(jī)課程，根據(jù)表6-8中對(duì)各門課程所屬類別的劃分，這一約束可以表示為：某些課程有先修課程的要求。例如“數(shù)據(jù)結(jié)構(gòu)”的先修課是“計(jì)算機(jī)編程”，這意味著如果，必須，這個(gè)條件可以表示為（注意：時(shí)對(duì)沒(méi)有限制）?！白顑?yōu)化方法”的先修課是“微積分”和“線性代數(shù)”這一條件可以表示為，而這兩個(gè)不等式可以合并為。這樣，所有課程的先修課要求可以表達(dá)為：（3）目標(biāo)函數(shù)根據(jù)本問(wèn)題的假設(shè)，我們考慮課程門數(shù)和學(xué)分兩個(gè)目標(biāo)。所選課程門數(shù)可表達(dá)為：我們希望課程門數(shù)盡量少，即希望對(duì)目標(biāo)函數(shù)實(shí)現(xiàn)最小化。所選課程的總學(xué)分可表達(dá)為：其中為課程編號(hào)為的課程的學(xué)分，這里，。我們

44、希望學(xué)分盡量多，即希望對(duì)目標(biāo)函數(shù)實(shí)現(xiàn)最大化。綜合上述分析，選課策略問(wèn)題的數(shù)學(xué)模型為如下多目標(biāo)規(guī)劃模型：3. 模型求解記上述多目標(biāo)規(guī)劃模型的可行域?yàn)?。?）如果以課程門數(shù)作為主要目標(biāo)，不考慮學(xué)分的多少，由主要目標(biāo)法將上述多目標(biāo)規(guī)劃模型轉(zhuǎn)化為如下的單目標(biāo)規(guī)劃模型：運(yùn)用LINGO軟件求解得到：，即選微積分、線性代數(shù)、最優(yōu)化方法、計(jì)算機(jī)模擬、計(jì)算機(jī)編程、數(shù)學(xué)實(shí)驗(yàn)這門課，可滿足畢業(yè)要求并使課程門數(shù)最少，此時(shí)總學(xué)分為。（2）如果以課程門數(shù)作為最重要目標(biāo)，總學(xué)分作為次重要目標(biāo)，即在課程門數(shù)達(dá)到最少的前提下使總學(xué)分達(dá)到最多。于是利用分層序列法在上述的基礎(chǔ)上，再次求解如下的單目標(biāo)規(guī)劃模型：運(yùn)用LINGO軟件求解

45、得到：，即將上述（1）中學(xué)分的“計(jì)算機(jī)模擬”換成學(xué)分的“應(yīng)用統(tǒng)計(jì)”，同樣這門課，可使總學(xué)分由增至。（3）如果認(rèn)為課程門數(shù)和總學(xué)分這兩個(gè)目標(biāo)的重要程度之間的差異不十分明顯，這時(shí)可由線性加權(quán)求和法取權(quán)系數(shù)和，將原多目標(biāo)規(guī)劃模型轉(zhuǎn)化為如下的單目標(biāo)規(guī)劃模型：運(yùn)用LINGO軟件求解得到：，即選微積分、線性代數(shù)、最優(yōu)化方法、數(shù)據(jù)結(jié)構(gòu)、應(yīng)用統(tǒng)計(jì)、計(jì)算機(jī)模擬、計(jì)算機(jī)編程、數(shù)學(xué)實(shí)驗(yàn)這門課。此時(shí)雖然課程門數(shù)增加了兩門課，但總學(xué)分也增加到了。例6.8 露天礦生產(chǎn)的車輛安排問(wèn)題許多現(xiàn)代化鐵礦是露天開(kāi)采的，它的生產(chǎn)主要是由電動(dòng)鏟車（以下簡(jiǎn)稱電鏟）裝車、電動(dòng)輪自卸卡車（以下簡(jiǎn)稱卡車）運(yùn)輸來(lái)完成。某露天礦里有10個(gè)爆破生成

46、的石料堆，每堆稱為一個(gè)鏟位，每個(gè)鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來(lái)說(shuō)，平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的，見(jiàn)表6-9。每個(gè)鏟位至多能安置一臺(tái)電鏟，現(xiàn)有電鏟7臺(tái)，電鏟的平均裝車時(shí)間為5分鐘。卸貨地點(diǎn)（以下簡(jiǎn)稱卸點(diǎn)）有卸礦石的礦石漏、2個(gè)鐵路倒裝場(chǎng)（以下簡(jiǎn)稱倒裝場(chǎng)）和卸巖石的巖石漏、巖場(chǎng)5個(gè)。各卸點(diǎn)一個(gè)班次的產(chǎn)量要求：礦石漏1.2萬(wàn)噸、倒裝場(chǎng)1.3萬(wàn)噸、倒裝場(chǎng)1.3萬(wàn)噸、巖石漏1.9萬(wàn)噸、巖場(chǎng)1.3萬(wàn)噸。從保護(hù)國(guó)家資源的角度及礦山的經(jīng)濟(jì)效益考慮，應(yīng)該盡量把礦石按礦石卸點(diǎn)需要的鐵含量（假設(shè)要求都為29.5%1

47、%，稱為品位限制）搭配起來(lái)送到卸點(diǎn)，搭配的量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。從長(zhǎng)遠(yuǎn)看，卸點(diǎn)可以移動(dòng)，但一個(gè)班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r(shí)間為3分鐘。所用卡車載重量為154噸，平均時(shí)速28?？ㄜ嚨暮挠土亢艽螅總€(gè)班次每臺(tái)車消耗近1噸柴油。發(fā)動(dòng)機(jī)點(diǎn)火時(shí)需要消耗相當(dāng)多的電瓶能量，故一個(gè)班次中只在開(kāi)始工作時(shí)點(diǎn)火一次?？ㄜ囋诘却龝r(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運(yùn)輸。每個(gè)鏟位到每個(gè)卸點(diǎn)的道路都是專用的寬60的雙向車道，不會(huì)出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的，見(jiàn)表6-10。一個(gè)班次的生產(chǎn)計(jì)劃應(yīng)該包含以

48、下內(nèi)容：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；卡車分別在哪些路線上各運(yùn)輸多少次（只求出各條路線上的車次數(shù)即可）。一個(gè)合格的計(jì)劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個(gè)好的計(jì)劃還應(yīng)該考慮：利用現(xiàn)有卡車20輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量?jī)?yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解）。試就上述問(wèn)題建立數(shù)學(xué)模型，并給出算法。表6-9 各鏟位礦石、巖石數(shù)量(萬(wàn)噸)和礦石的平均鐵含量鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0.951.051.001.051.101.251.051.301.351.25巖石量1.251.101.351.051.151.351.051.15

49、1.351.25鐵含量30%28%29%32%31%33%32%31%33%31%表6-10 各鏟位和各卸點(diǎn)之間的距離（公里）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場(chǎng)1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝場(chǎng)4.423.863.723.162.252.810.781.62

50、1.270.50圖6-1 鏟位和卸點(diǎn)位置的二維示意圖1. 問(wèn)題分析 本題可以看成是經(jīng)典運(yùn)輸問(wèn)題的一種變形和擴(kuò)展，它與經(jīng)典運(yùn)輸問(wèn)題明顯有以下不同：（1）這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；（2）屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；（3）為了完成品位約束，礦石要搭配運(yùn)輸；（4）產(chǎn)地、銷地均有單位時(shí)間的流量限制；（5）運(yùn)輸車輛只有一種，每次都是滿載運(yùn)輸，每車次154噸；（6）鏟位數(shù)多于電鏟數(shù)，意味著要選擇不多于7個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地。 根據(jù)題目要求的原則：獲得最大的總產(chǎn)量（巖石產(chǎn)量?jī)?yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解），主要目標(biāo)應(yīng)有：（1）總產(chǎn)量最大；（2）巖石產(chǎn)量最大；（3）總運(yùn)量（噸公里

51、）最小。 三個(gè)目標(biāo)之間的優(yōu)先關(guān)系應(yīng)該理解為字典序。2. 模型假設(shè)（1）電鏟在一個(gè)班次中，位置不能移動(dòng)；（2）卡車在一個(gè)班次中，不發(fā)生等待或熄火后再啟動(dòng)的情況；（3）卡車空載與重載的速度都是28；（4）運(yùn)輸車輛只有一種，每次都是滿載運(yùn)輸，每車次154噸；（5）電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)；（6）不會(huì)出現(xiàn)堵車現(xiàn)象。3. 模型建立（1）決策變量設(shè)為從號(hào)鏟位到號(hào)卸點(diǎn)路線上所需的車次數(shù)，其中：分別代表個(gè)鏟位；分別代表礦石漏、倒裝場(chǎng)、巖場(chǎng)、巖石漏、倒裝場(chǎng)。只能取非負(fù)整數(shù)值。設(shè)為0-1變量，其意義為：以上述定義的和作為決策變量。令，則決策變量又可表示為向量形式：。（2）約束條件 1）道路能力約束 由于一臺(tái)電鏟與一個(gè)卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)，所以一條路線上最多能同時(shí)運(yùn)行的卡車數(shù)是有限的。設(shè)卡車在第號(hào)鏟位到號(hào)卸點(diǎn)路線上運(yùn)行一個(gè)周期平均所需的時(shí)間為，可以由下式計(jì)算：由于裝車時(shí)間分鐘大于卸車時(shí)間分鐘，所以可以分析出這條路線上在卡車不等待條件下最多能同時(shí)運(yùn)行的卡車數(shù)，由下式計(jì)算： 同樣可分析出每輛卡車一個(gè)班次中在這條路線上最多可以運(yùn)行的次數(shù)，由下式計(jì)算： 其中是開(kāi)始裝車時(shí)最后一輛車的延時(shí)時(shí)間。設(shè)一個(gè)班次中在這條路線上最多可以運(yùn)行的總車次數(shù)為，由下式大約計(jì)算：