《運(yùn)籌學(xué)》教學(xué)案卷

1、運(yùn)籌學(xué)教學(xué)案卷對(duì)象：交通運(yùn)輸、農(nóng)業(yè)工程、環(huán)境工程 時(shí)間：2010/08-2011/01沈陽(yáng)農(nóng)業(yè)大學(xué) 工程學(xué)院趙 秀 榮7/21/2022Associate Prof Xiurong Zhao,Shenyang Agriculture University,China第五章目標(biāo)規(guī)劃（講課3學(xué)時(shí)）5-1 目標(biāo)規(guī)劃數(shù)學(xué)模型5-2 目標(biāo)規(guī)劃的圖解法5-3 解目標(biāo)規(guī)劃的單純形法7/21/2022本章重點(diǎn) 掌握目標(biāo)規(guī)劃的數(shù)學(xué)模型7/21/2022緒： 前面討論的線性規(guī)劃問題，都涉及一個(gè)目標(biāo)函數(shù)，稱單目標(biāo)數(shù)學(xué)規(guī)劃。在實(shí)際中，所遇到的問題，往往難以用一個(gè)目標(biāo)來衡量。將具有兩個(gè)或兩個(gè)以上目標(biāo)函數(shù)的規(guī)劃問題叫做多

2、目標(biāo)規(guī)劃。 7/21/2022緒： 多目標(biāo)問題在經(jīng)濟(jì)中、科學(xué)研究和工程設(shè)計(jì)上經(jīng)常遇到。例如，設(shè)計(jì)導(dǎo)彈，既要射程遠(yuǎn)，又要省燃料，還必須要精度高；確定一個(gè)新橡膠配方，往往同時(shí)考察八、九個(gè)指標(biāo)，如強(qiáng)力、硬度、變形、伸長(zhǎng)等；再如選一個(gè)新廠址，除考慮運(yùn)輸費(fèi)用、造價(jià)、燃料等費(fèi)用外，還要考慮環(huán)境污染等社會(huì)因素。7/21/2022 5-1 目標(biāo)規(guī)劃數(shù)學(xué)模型 為了使同學(xué)們更好理解和掌握目標(biāo)規(guī)劃，下面通過例子來介紹其有關(guān)概念及數(shù)學(xué)模型。例1：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)如表5-1。試求該工廠獲利最大的生產(chǎn)方案。7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型 產(chǎn)品原料甲乙資源擁有量原材料（kg）2111設(shè)備（

3、hr）1210利潤(rùn)（元/件）810根據(jù)LP問題所學(xué)知識(shí)，可列出其線性規(guī)劃數(shù)學(xué)模型如下： 解：可得最優(yōu)解：7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型 如果實(shí)際上工廠在決策時(shí)，要考慮市場(chǎng)等一系列條件，如：（1）根據(jù)市場(chǎng)信息，產(chǎn)品甲的銷量有下降趨勢(shì)，故考慮產(chǎn)品甲的產(chǎn)量不大于產(chǎn)品乙；（2）超過計(jì)劃供應(yīng)的原材料時(shí)，需用高價(jià)采購(gòu)，這就使成本增加；（3）應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班（4）應(yīng)盡可能達(dá)到并超過計(jì)劃利潤(rùn)指標(biāo)56元。 在考慮上述問題決策時(shí)，便是多目標(biāo)決策問題。目標(biāo)規(guī)劃方法是解決這類決策問題的方法之一。 下面介紹有關(guān)概念：7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型（1）偏差變量設(shè) 為決策變量

4、，此外引入正負(fù)偏差變量 。 表示決策值超過目標(biāo)的部分； 表示決策值未達(dá)到目標(biāo)值的部分。因?yàn)闆Q策值不可能既超過目標(biāo)值，同時(shí)又未達(dá)到目標(biāo)值，即 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型（2）絕對(duì)約束和目標(biāo)約束 絕對(duì)約束是指必須嚴(yán)格滿足的等式約束和不等式約束；如線性規(guī)劃問題的所有約束條件。不能滿足這些約束條件的解稱為非可行解，所以這些約束就是硬約束。 目標(biāo)約束是目標(biāo)規(guī)劃特有的，可以把約束右端項(xiàng)看作要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時(shí)發(fā)生正或負(fù)的偏差，因此在這些約束中加入正或負(fù)偏差變量，則這些約束是軟約束。7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型（3）優(yōu)先因子 一個(gè)規(guī)劃問題通常有多個(gè)目標(biāo)，但決策者在要

5、達(dá)到這些目標(biāo)時(shí)，有主次和輕重緩急之分；凡要求第一位的目標(biāo)賦予優(yōu)先因子 ；第二位賦予優(yōu)先因子 ；以此類推，令 注意：優(yōu)先因子不代表具體數(shù)，只代表目標(biāo)的優(yōu)先次序。 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型（4）目標(biāo)規(guī)劃的目標(biāo)函數(shù) 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是按各目標(biāo)約束的正負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)成的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是 其基本形式有三種： 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型（1）要求恰好達(dá)到目標(biāo)值，即正負(fù)偏差變量都要極可能的小。這時(shí)（2）要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，正偏差的變量要盡可能小。這時(shí) （3）要求超過

6、目標(biāo)值，即超過量不限，但必須是負(fù)偏差變量要盡可能的小。這時(shí) 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型 對(duì)于每一個(gè)目標(biāo)規(guī)劃問題，其目標(biāo)函數(shù)是根據(jù)決策者的要求和規(guī)定的優(yōu)先因子來構(gòu)造的。7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型例2：例1中，決策者在原料供應(yīng)受價(jià)格限制基礎(chǔ)上考慮：首先是乙的產(chǎn)量不低于產(chǎn)品甲的產(chǎn)量；其次是充分利用設(shè)備有效臺(tái)時(shí)，不加班；再次是利潤(rùn)額不小于56元，求決策方案。G P那么該目標(biāo)規(guī)劃的目標(biāo)函數(shù)是什么呢？要考慮的目標(biāo)有三個(gè)，分別賦優(yōu)先因子：P1，P2，P3L P臺(tái)時(shí)原材料首先要確定該目標(biāo)規(guī)劃的約束條件最先要考慮有無硬約束？請(qǐng)大家分析原材料約束即為硬約束，即考慮所有硬約束以后，開

7、始考慮目標(biāo)約束，按照目標(biāo)先后，則有按照第一個(gè)目標(biāo)要求（現(xiàn)不考慮其下級(jí)目標(biāo)）應(yīng)該符合？再按照第二個(gè)目標(biāo)要求（不考慮其上、下級(jí)目標(biāo)）最后按照第三個(gè)目標(biāo)要求（不考慮其上級(jí)目標(biāo)）應(yīng)該符合？把三個(gè)應(yīng)滿足的目標(biāo)合成一個(gè)目標(biāo)函數(shù)即為該問題目標(biāo)函數(shù)7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型解：按決策者所要求的，分別賦予這三個(gè)目標(biāo)、優(yōu)先因子，則其數(shù)學(xué)模型為： 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型解：按決策者所要求的，分別賦予這三個(gè)目標(biāo)、優(yōu)先因子，則其數(shù)學(xué)模型為： 7/21/20225-1 目標(biāo)規(guī)劃數(shù)學(xué)模型目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為： 7/21/20225-2 目標(biāo)規(guī)劃的圖解法 對(duì)只具有兩個(gè)決策變量的目標(biāo)規(guī)劃

8、的數(shù)學(xué)模型，可以用圖解法來分析求解。首先在平面直角坐標(biāo)系中作約束條件直線注意不包含 作目標(biāo)約束時(shí)，限令作相應(yīng)的直線，然后在該直線旁，標(biāo)上 如下個(gè)幻燈圖，這表明目標(biāo)約束可以沿二者所示的方向平移。 7/21/20225-2 目標(biāo)規(guī)劃的圖解法BCDEFGO首先在平面直角坐標(biāo)系中作約束條件直線，不含步驟如下：在所做直線旁，標(biāo)上表明目標(biāo)約束可以沿二者所示的方向平移分析d+，d-的方向？作目標(biāo)約束時(shí)，限令先考慮滿足所有硬約束后，考慮滿足第一目標(biāo)，即要使 d1+=0 （這時(shí)只能在OBC范圍內(nèi)取值）接著考慮第二優(yōu)先因子目標(biāo)的實(shí)現(xiàn)。在目標(biāo)函數(shù)中要求實(shí)現(xiàn)則只有在ED線段上的點(diǎn)才符合最后考慮具有第三優(yōu)先因子的目標(biāo)的

9、實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)則把最優(yōu)解定在了？GD上可求得G的坐標(biāo)值為（2，4）、D（10/3，10/3），G、D的凸線性組合都是該目標(biāo)規(guī)劃問題的解。7/21/20225-2 目標(biāo)規(guī)劃的圖解法 注意目標(biāo)規(guī)劃問題求解時(shí)，把絕對(duì)約束作為最高的優(yōu)先級(jí)考慮。在前例中能以先后次序都得到了滿足，即 因而但在大多問題中并非如此，還可能出現(xiàn)非可行解，故將目標(biāo)規(guī)劃問題的最優(yōu)解稱為滿意解。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃數(shù)學(xué)模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，所以可用單純形法求解。但要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型的一些特點(diǎn)作以下規(guī)定：（1）因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小，所以 ，以 為

10、最優(yōu)判斷的準(zhǔn)則。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法（2）非基變量的檢驗(yàn)數(shù)中含有不同級(jí)別的優(yōu)先因子，須按優(yōu)先因子先后依次判斷；對(duì)下級(jí)進(jìn)行判斷迭代時(shí)，以不破壞上一級(jí)以及其以前各級(jí)的達(dá)成值為標(biāo)準(zhǔn)。解目標(biāo)規(guī)劃問題單純形法的計(jì)算步驟：第一步：建立初始單純形表，在表中將檢驗(yàn)數(shù)行按照優(yōu)先因子的個(gè)數(shù)分別排成k行，含k=1。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法第二步：檢查k=1行中是否存在負(fù)數(shù)，且對(duì)應(yīng)的前k-1行的系數(shù)是零。若有負(fù)數(shù)，取其中最小者對(duì)應(yīng)的變量為換入變量轉(zhuǎn)第三步；若無負(fù)數(shù)，則轉(zhuǎn)第五步。第三步：按最小比值規(guī)定確定換出變量，當(dāng)存在兩個(gè)或兩個(gè)以上相同最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的

11、變量為換出變量。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法第四步：按單純形法進(jìn)行迭代換算，建立新的計(jì)算表，返第二步。第五步:當(dāng)所有k行都判斷完畢后，表中的解即為滿意解。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法例3：試用單純形法來求解例2： 7/21/20225-3 解目標(biāo)規(guī)劃的單純形法因?yàn)樗袡z驗(yàn)數(shù)都大于或等于零，故已滿足第一優(yōu)先指標(biāo)，應(yīng)往下進(jìn)行，即判斷第二優(yōu)先指標(biāo)將主元化為1，主元所在列其它元素化為零。注意不包含下級(jí)指標(biāo)，同時(shí)不破壞上級(jí)已達(dá)成指標(biāo)。結(jié)果見下幻燈片。7/21/20225-3 解目標(biāo)規(guī)劃的單純形法因?yàn)榈谝?、第二行所有檢驗(yàn)數(shù)都大于或等于零，故均已滿足，應(yīng)往下進(jìn)行，即判斷第三優(yōu)先指標(biāo)如果選擇該列，則會(huì)影響前面的二級(jí)指標(biāo)，所以不選擇該列。試試看其它列，如第一列“-3”，其前面兩行檢驗(yàn)數(shù)均為零，故不會(huì)影響上級(jí)指標(biāo)達(dá)成值。將主元化為1，主元所在列其它元素化為零。進(jìn)行單純形迭代。結(jié)果見下個(gè)幻燈片。7/21/20225-3