《OR05目標(biāo)規(guī)劃》課件

GoalProgramming(GP)wasdevelopedbyCharnesandCooperin1961andsubsequentlystudiedbymanyresearchers.GPcanberegardedasaspecialcompromisemodelformulti-objectiveprogrammingandhasbeenappliedinawidevarietyofreal-worldproblems.1精選課件ppt

目標(biāo)規(guī)劃的數(shù)學(xué)模型2.目標(biāo)規(guī)劃的圖解法3.解目標(biāo)規(guī)劃的單純形法4.目標(biāo)規(guī)劃的案例2精選課件ppt

設(shè)桌子、椅子的產(chǎn)量分別為，則模型如右：（1）

引例：某木工小組生產(chǎn)桌子和椅子2種產(chǎn)品，每周生產(chǎn)時間為48h，生產(chǎn)1張桌子平均需要1h，生產(chǎn)1把椅子需要0.4h。根據(jù)市場預(yù)測，要求桌子的銷售量每周不少于30張，椅子每周不少于60把。每張桌子的利潤為20元，每把椅子的利潤為8元。問1周生產(chǎn)桌子、椅子各多少使總利潤最大？3精選課件ppt分析：上述約束互相矛盾，不可能同時滿足，要滿足工人必須加班。于是此問題需要改變。這是一個只有2個變量的線性規(guī)劃問題，可用圖解法或單純形法求解。可是，這個問題有可行解嗎？4精選課件ppt從線性規(guī)劃問題可看出：線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問題，如擬訂生產(chǎn)計劃時，不僅考慮總產(chǎn)值，同時要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的重要程度（即優(yōu)先順序）也不相同，有些目標(biāo)之間往往相互發(fā)生矛盾。5精選課件ppt線性規(guī)劃致力于某個目標(biāo)函數(shù)的最優(yōu)解，這個最優(yōu)解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。6精選課件ppt求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進(jìn)行，這將給人們進(jìn)一步應(yīng)用線性規(guī)劃方法帶來困難。7精選課件ppt為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標(biāo)之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。8精選課件ppt9精選課件ppt10精選課件ppt產(chǎn)品甲乙擁有量原材料(kg)2111設(shè)備(hr)1210利潤(元/件)81011精選課件ppt12精選課件ppt甲產(chǎn)品乙產(chǎn)品可利用資源原材料23100噸加工時間42120時單位利潤64百元

例2某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，數(shù)據(jù)見下表：13精選課件ppt14精選課件ppt

項目品種工時消耗（時/臺）AB庫存費用（元/臺月）利潤（元/臺）MP3錄音機(jī)21135030250150總工時/月180200生產(chǎn)費用/時1005015精選課件ppt16精選課件ppt17精選課件ppt18精選課件pptx+d--d+=b若決策目標(biāo)中規(guī)定x

b(要求不超過目標(biāo)值),d+取最小。若決策目標(biāo)中規(guī)定x

b(要求超過目標(biāo)值),d-取最小。若決策目標(biāo)中規(guī)定x=b(要求恰好達(dá)到目標(biāo)值),d-+d+取最小。絕對約束（硬約束）：必須嚴(yán)格滿足的等式約束和不等式約束。目標(biāo)約束（軟約束）：含正負(fù)偏差的約束。bd+

d-

19精選課件ppt20精選課件ppt產(chǎn)品甲乙擁有量原材料(kg)2111設(shè)備(hr)1210利潤(元/件)81021精選課件ppt22精選課件ppt23精選課件ppt甲產(chǎn)品乙產(chǎn)品可利用資源原材料23100噸加工時間42120時單位利潤64百元

例2某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，數(shù)據(jù)見下表：24精選課件ppt解：設(shè)生產(chǎn)甲、乙產(chǎn)品各25精選課件ppt26精選課件ppt27精選課件ppt

項目品種工時消耗（時/臺）AB庫存費用（元/臺月）利潤（元/臺）MP3錄音機(jī)21135030250150總工時/月180200生產(chǎn)費用/時1005028精選課件ppt29精選課件ppt30精選課件ppt31精選課件ppt32精選課件ppt1086422x1+x2

11BA△OABO①MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

246810x1x233精選課件ppt1086422x1+x2

11MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

d1+d1-BDA△OAB△ODBO①②x1x234精選課件ppt1086422x1+x2

11MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11①

X1-X2+d1--d1+=0②

X1+2X2+d2--d2+=10③

8X1+10X2+d3--d3+=56④X1,X2,di-,di+,

0(i=1,2,3,)

d1+d1-d2+BEDA△OAB△ODBDEO①②③d2-246810x1x235精選課件ppt1086422x1+x2

50MinZ=P1d1++P2(d2-+d2+)+P3d3-約束方程：2X1+X2≤11

X1-X2+d1--d1+=0

X1+2X2+d2--d2+=10

8X1+10X2+d3--d3+=56

X1,X2,di-,di+,

0(i=1,2,3,)

2468x110d1+d1-d2+d2-d3+d3-BFEGDJA△OAB△OCBDEDGOx236精選課件ppt結(jié)果：可求得G的坐標(biāo)是（2，4），D的坐標(biāo)是（10/3,10/3），G、D的凸線性組合都是該目標(biāo)規(guī)劃問題的解。注意：目標(biāo)規(guī)劃問題求解時，把絕對約束作為最高優(yōu)先級考慮，在本例中能依先后次序都滿足d1+=0

、d2--d2+=0

、d3-＝0

，因而Z＝0。但在大多數(shù)問題中并非如此，會出現(xiàn)某些約束得不到滿足，故將目標(biāo)規(guī)劃問題的最優(yōu)解稱為滿意解。37精選課件ppt彩電

黑白擁有量裝配線（小時）1140銷量2430利潤（元/件）8040例6：某工廠生產(chǎn)彩電、黑白兩種電視機(jī)，數(shù)據(jù)如下38精選課件ppt解：P1:充分利用裝配線每周計劃開動40小時；X1+X2+d1--d1+=40P2:允許裝配線加班；但加班時間每周盡量不超過10小時；X1+X2+d2--d2+=50P3:電視機(jī)的數(shù)量盡量滿足市場要求，權(quán)系數(shù)為利潤比。X1+d3--d3+=24；X2+d4--d4+=30目標(biāo)函數(shù)：MinZ=P1d1-+P2d2++

P3(2d3-+d4-)39精選課件pptMinZ=P1d1-+P2d2++P3（2d3-+d4-

）約束方程：X1+X2+d1--d1+=40①X1+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④X1,X2,di-,di+,

0(i=1,2,3,)

第一：充分利用裝配線每周計劃開動40小時；第二：允許加班，但盡量不超過10小時；第三：電視機(jī)要滿足市場要求，彩電權(quán)系數(shù)取2。40精選課件pptO①MinZ=P1d1-+P2d2++P3（2d3-+d4-

）約束方程：X1+X2+d1--d1+=40①X1+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④X1,X2,di-,di+,

0(i=1,2,3,)

BCDHGEF②③④d1-d1+d2-d2+d3-d3+d4+d4-無法滿足d4－＝0，只能在ABEF中取一點，使得d4－盡可能小，這就是E點，坐標(biāo)為（24，26）。Ax1x241精選課件ppt42精選課件ppt43精選課件ppt44精選課件ppt45精選課件ppt46精選課件ppt47精選課件ppt48精選課件ppt49精選課件ppt50精選課件ppt51精選課件ppt52精選課件ppt53精選課件ppt54精選課件ppt解目標(biāo)規(guī)劃問題的單純形法的計算步驟：Step1.

建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成K行，令k=1；Step2.

檢查該行中是否存在負(fù)數(shù)，且對應(yīng)的前k－1行的系數(shù)是零。若有負(fù)數(shù)取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)3。若無負(fù)數(shù)，則轉(zhuǎn)5；Step3.

按最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。Step4.

按單純形法進(jìn)行基變換運算，建立新的計算表，返回2。Step5.

令k=k+1，若k＝K，算法結(jié)束。否則轉(zhuǎn)2，進(jìn)行下一優(yōu)先級的優(yōu)化。55精選課件ppt(一)56精選課件ppt57精選課件ppt58精選課件ppt59精選課件ppt60精選課件ppt61精選課件ppt62精選課件ppt63精選課件ppt64精選課件ppt65精選課件ppt66精選課件ppt67精選課件ppt68精選課件ppt69精選課件ppt70精選課件ppt71精選課件ppt72精選課件ppt73精選課件ppt74精選課件ppt75精選課件ppt第四節(jié)目標(biāo)規(guī)劃的案例76精選課件ppt77精選課件ppt78精選課件ppt79精選課件ppt80精選課件ppt81精選課件ppt已知三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品,供需量與單位運價表如下表:900/1000250450100200銷量4003254A32006453A23007625A1產(chǎn)量B4B3B2B1

銷地產(chǎn)地82精選課件ppt考慮調(diào)運方案時,依次考慮以下七項指標(biāo):P1:B4是重點保證單位，必須全部滿足其要求;P2:A3向B1提供的產(chǎn)量不少于100;P3:每個銷地的供應(yīng)量不小于其需要量的80%;P4:所訂調(diào)運方案的總費用不超過最小調(diào)運方案的10%;P5:因路段的問題,盡量避免安排A2的產(chǎn)品運往B4;P6:給B1和B3的供應(yīng)率要相同;P7:力求總運費最省;試求滿意的調(diào)運方案。83精選課件ppt解:由于產(chǎn)量小于銷量,假想一個產(chǎn)地A4,其產(chǎn)量為100.用表上作業(yè)法求得最優(yōu)解如下,最小運費為2950元.100100

A4400150250A3200

200

A2300

100200A1產(chǎn)量B4B3B2B1

銷地產(chǎn)地1000/1000250450100200銷量84精選課件ppt分析:供應(yīng)約束:x11+x12+x13+x14≤300x21+x22+x23+x24≤200x31+x32+x33+x34≤400

需求約束:x11+x21+x31+d1--d1+=200x12+x22+x32+d2--d2+=100x13+x23+x33+d3--d3+=450

x14+x24+x34+d4--d4+=250P1:

B4是重點保證單位必須全部滿足其要求,P1d4-P2:A3向B1提供的產(chǎn)量不少于100,P2d5-x31+d5--d5+=10085精選課件ppt

P3:每個銷地的供應(yīng)量不小于需要量的80%,

P3(d6-+d7-+d8-+d9-)x11+x21+x31+d6--d6+=200×0.8x12+x22+x32+d7--d7+=100×0.8x13+x23+x33+d8--d8+=450×0.8

x14+x24+x34+d9--d9+=250×0.8P4:

所訂調(diào)運方案的總費用不超過最小調(diào)運方案的

10%,P4d10+86精選課件ppt

P5:因路段的問題,盡量避免安排A2運往B4,P5d11+x24+d11--d11+=0P6:給B1和B3的供應(yīng)率要相同,P6(d12-+d12+)

供應(yīng)率=實際供應(yīng)量/銷量,即:(x11+x21+x31)/200=(x13+x23+x33)/450,目標(biāo)約束為:(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0P7:力求總運費最省,P7d13+87精選課件ppt

供應(yīng)約束:x11+x12+x13+x14≤300x21+x22+x23+x24≤200x31+x32+x33+x34≤400

需求約束:x11+x21+x31+d1--d1+=200x12+x22+x32+d2--d2+=100x13+x23+x33+d3--d3+=450P1

x14+x24+x34+d4--d4+=250P2x31+d5--d5+=100

88精選課件pptP3x11+x21+x31+d6--d6+=200×0.8x12+x22+x32+d7--d7+=100×0.8x13+x23+x33+d8--d8+=450×0.8

x14+x24+x34+d9--d9+=250×0.8P4P5x24+d11--d11+=0P6(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0P7minz=P1d4-+P2d5-+P3(d6-+d7+-+d8-+d9-)+P4d10++P5d11++P6(d12-+d12+)+P7d13+89精選課件ppt計算得滿意調(diào)運方案?？傎M用為3360。100

9010A440050250100A3200

110

90A2300200

100

A1產(chǎn)量B4B3B2B1

銷地產(chǎn)地1000/1000250450100200銷量90精選課件ppt一、重載運輸簡介（一）概念（二）組織形式（三）現(xiàn)狀（四）重載運輸技術(shù)裝備（五）重載運輸組織91精選課件ppt（一）重載運輸概念◆重載運輸是除高速鐵路以外，鐵路現(xiàn)代化的又一重要標(biāo)志。◆重載運輸是在先進(jìn)的鐵路技術(shù)裝備條件下，擴(kuò)大列車編組，提高列車重量的一種運輸方式。

◆國際重載協(xié)會認(rèn)為，重載鐵路必須滿足以下三條標(biāo)準(zhǔn)中的至少兩條：

1、經(jīng)常、定期開行或準(zhǔn)備開行總重至少為5000噸的單元列車或組合列車；

2、在長度至少為150公里的線路區(qū)段上，年計費貨運量至少達(dá)2000萬噸；

3、經(jīng)常、正常開行或準(zhǔn)備開行軸重25噸及其以上的列車。

92精選課件ppt◆重載鐵路的最新界定重載鐵路是指同時具備以下三條中的任意兩條的線路：

1、單機(jī)牽引重量達(dá)到8000噸；

2、軸重達(dá)到或超過27噸；

3、在長度至少為150公里的線路區(qū)段上，年運量至少達(dá)到4000萬噸。

我國滿足這種條件的線路極少，軸重達(dá)不到，總重8000t以上的列車也很少。所以，我們還是按5000t考慮。主要是研究目標(biāo)規(guī)劃在實際問題中的應(yīng)用。93精選課件ppt（二）重載運輸組織形式組合式重載列車——將2列普通列車首尾相接連在一起，機(jī)車分別掛于列車頭部和中部，在運行圖上占用1條運行線，運行到前方某站再分解的列車。單元式重載列車——固定發(fā)、到站，固定運行線，固定機(jī)車車輛，運輸單一品種貨物，在裝車地和卸車地之間往返循環(huán)運行，途中不進(jìn)行改編、摘掛作業(yè)的列車。整列式重載列車——由大功率機(jī)車（單機(jī)或多機(jī)）牽引，機(jī)車掛于列車頭部，作業(yè)組織方法與普通貨物列車一樣，只是列車重量和編組輛數(shù)有顯著增加的列車。94精選課件ppt（三）重載運輸現(xiàn)狀

澳大利亞、加拿大、中國、南非、美國、俄羅斯、巴西等，特點：國土幅員遼闊、資源豐富、鐵路較為發(fā)達(dá)、大宗貨物運輸較多。1、世界上開展重載運輸?shù)闹饕獓?、重載運輸技術(shù)水平軸重：美、加、澳等國達(dá)32.5t~35.7t，積極研究39t，巴西、瑞典達(dá)30t，南非26t，俄羅斯25~27t。我國目前23~25t。列車重量：一般1萬t~2萬t，南非、澳大利亞已超過2萬t。我國大秦線開行2萬t成功，一般線路5千~1萬t。95精選課件ppt3、世界上最長、最重的重載列車4、運量一條重載運輸線路年貨運量（貨流量）較普通線路大得多，但各國情況不同。大秦線2007年已實現(xiàn)3億t，朔黃線近1億t，世界其他國家因列車密度較小，大多不超過1億t。但巴西卡拉斯加礦山鐵路（單線）年運量實現(xiàn)1.08億t，列車編組達(dá)312輛，列車長度達(dá)3200m，軸重30.5t，4臺機(jī)車牽引。列車總重：10萬t，載重8.23萬t礦石。列車長度：7400m，編成輛數(shù)682輛。牽引機(jī)車：8臺。創(chuàng)造者：澳大利亞BHP公司，2001年6月。96精選課件ppt（四）重載運輸技術(shù)裝備機(jī)車——大功率，如SS4，DF8B等。車輛——大載重（70t,80t以上），大軸重（23t,25t以上），輕型縮短型。線路——60kg/m以上的高強度鋼軌，鋼筋混凝土軌枕，坡度不應(yīng)>8‰。站場——站線有效長1050~1700m，大秦線達(dá)2800m。通信信號——自動閉塞，移動通信。調(diào)度指揮——自動化，信息化。97精選課件ppt（五）重載運輸組織中的待研問題▲集疏運系統(tǒng)的合理規(guī)劃▲不同運輸方式的合理銜接與協(xié)調(diào)▲列車重量的合理組合▲列車重量、速度、密度的合理匹配▲重載運輸線路車流組織優(yōu)化▲客貨混運線路重載列車開行方案▲固定車底循環(huán)直達(dá)運輸?shù)倪m應(yīng)性問題▲重去空回方式與重來重去方式的比較分析98精選課件ppt三、問題描述與模型建立（一）問題的描述（二）優(yōu)化目標(biāo)（三）模型推導(dǎo)（四）模型的基本形式99精選課件ppt（一）問題的描述1、研究背景

（1）重載運輸線路一般設(shè)計為雙線自動閉塞電氣化鐵路，以運送煤炭、礦石等大宗物資為主，采用大功率機(jī)車單機(jī)或多機(jī)牽引，使用專用的大載重車輛裝運貨物。

（2）為了加速機(jī)車車輛周轉(zhuǎn)，常采取固定車底循環(huán)直達(dá)運輸方式組織列車重去空回，有的線路甚至努力實現(xiàn)“班列化”。

（3）重載運輸線上開行的重載列車往往不只一種，而是有多種不同的重量級別。100精選課件ppt

（4）在實際的運輸生產(chǎn)中，一般會提出多個優(yōu)化目標(biāo)，如運量最大，資源消耗最小。有的目標(biāo)是決策者規(guī)定的硬性指標(biāo)，必須重點保證，有的則相對弱化一些。針對這一特點，采用目標(biāo)規(guī)劃模型來加以描述并求解。2、問題的表述

在一定的資源約束（線路能力和機(jī)車車輛數(shù)量）條件下，如何合理確定各種不同重量級別的列車的開行數(shù)量，使得決策者期望的年運量目標(biāo)能夠?qū)崿F(xiàn)？101精選課件ppt（二）優(yōu)化目標(biāo)主要目標(biāo)能力約束機(jī)車車輛約束1、重車方向年輸送貨物不得少于億噸；

2、考慮日常列車運行調(diào)整的需要，線路通過能力利用率不得超過線路技術(shù)負(fù)荷水平0.87；

3、由于機(jī)車數(shù)量的限制，機(jī)車使用臺數(shù)日均不超過臺；

4、由于車輛數(shù)量的限制，運用貨車輛數(shù)日均不超過輛。102精選課件ppt（三）模型推導(dǎo)

設(shè)某重載運輸線路計劃開行3種重量級別（多種類推）的貨物列車：2萬t、1萬t和5千t，每天開行的數(shù)量分別記作。針對4個優(yōu)化目標(biāo)建立4個約束方程。要求年貨流量不少于億噸，則日均貨流量不應(yīng)少于（萬t）

通常重載貨運通道的貨源充足，貨流波動極小，故可忽略。1、運量目標(biāo)103精選課件ppt由此得對應(yīng)目標(biāo)1的約束方程為

設(shè)2萬t、1萬t和5千t級列車的平均載重系數(shù)（指列車載重與總重之比，主要與貨車類型及靜載重有關(guān)）分別為，則重車方向日均輸送貨流量為（萬t）104精選課件ppt

設(shè)2萬t、1萬t和5千t級列車的追蹤間隔時間分別為。

研究表明，追蹤列車間隔時間與列車長度有一定關(guān)系，列車長度越大，追蹤間隔時間會相應(yīng)地有所增加，因而一般有。

在接觸網(wǎng)及線路設(shè)備綜合維修施工天窗為min，技術(shù)負(fù)荷水平為0.87的條件下，一晝夜可利用的時間為min。于是對應(yīng)目標(biāo)2的約束方程為2、能力約束105精選課件ppt

設(shè)機(jī)車平均全周轉(zhuǎn)時間為小時，則機(jī)車需要系數(shù)牽引1對列車所需要的機(jī)車臺數(shù)由此得第3個約束方程為

因2萬噸列車由4臺機(jī)車牽引，1萬噸和5千噸列車分別由2臺和1臺機(jī)車牽引，故有3、機(jī)車約束106精選課件ppt4、車輛約束

設(shè)2萬t、1萬t和5千t級列車的車底周轉(zhuǎn)時間分別為，因裝、卸作業(yè)停留時間與列車中編掛的車輛數(shù)呈正相關(guān)關(guān)系，而且2萬t列車和部分1萬t列車采取組合列車方式，在始發(fā)站（基地站）和終到站還會有合并作業(yè)和分解作業(yè)，故一般有。但若從裝車站直接組織2萬t（或1萬t）列車，在基地站不進(jìn)行合并作業(yè)而直接無改編通過，則可以使大為縮短。

設(shè)3種列車的編成輛數(shù)分別為，得第4個約束方程為107精選課件ppt（四）模型的基本形式

說明：若考慮機(jī)車車輛處于同一優(yōu)先級，則目標(biāo)函數(shù)可寫成108精選課件ppt三、案例分析（一）參數(shù)標(biāo)定（二）模型建立（三）模型求解（四）結(jié)果分析109精選課件ppt（一）參數(shù)標(biāo)定

以大秦線為例進(jìn)行具體分析。經(jīng)查有關(guān)資料，并作簡單計算，得各項參數(shù)如下：◆期望年運量億t?！袅熊囕d重系數(shù)大秦線開行的3種重量級別的列車使用的貨車車型有所不同：2萬噸列車使用專用的C80型貨車，1萬噸和5千噸列車主要使用C63型車，少量使用C76型車。重載列車輸送重質(zhì)貨物，車輛載重力均可得到充分利用，故可認(rèn)為列車載重系數(shù)等于車輛載重系數(shù)。取值如下：110精選課件ppt◆設(shè)備綜合養(yǎng)護(hù)維修施工天窗min?！?/p>

列車追蹤間隔時間分別按10,12,15min取值。◆機(jī)車平均全周轉(zhuǎn)時間估計為21h