運籌學

OperationalResearch

白華暨南大學深圳旅游學院運算、籌劃、選優(yōu)、求好實踐： 已知：

1、7：30起床，8：00到教室；

2、其中刷牙2min，接水3min，洗臉2min，早餐15分鐘，路程10分鐘，上廁所1分鐘； 問題：如何作才能準時上課？第一章緒論

運籌學是一門應用科學，至今沒有統(tǒng)一的定義。據《大英百科全書》釋義：“運籌學是一門應用于管理有組織系統(tǒng)的科學”，“運籌學為掌管這類系統(tǒng)的人提供決策目標和數量分析的工具”。

中國大百科全書的釋義為：運籌學“用數學方法研究經濟、民政和國防等部門在內外環(huán)境的約束條件下合理分配人力、物力、財力等資源，使實際系統(tǒng)有效運行的技術科學，它可以用來預測發(fā)展趨勢，制定行動規(guī)劃或優(yōu)選可行方案”。

中國管理百科全書的釋義為：運籌學是應用分析、試驗、量化的方法，對經濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據的最優(yōu)方案，以實現最有效的管理。運籌學有廣泛的應用，它的產生和發(fā)展歷史悠久。1.運籌學的產生與發(fā)展名字:“運籌學”“作業(yè)研究”或“運行研究”歐洲：OperationalResearch美國：OperationsResearchO.R.發(fā)展簡史：最早的思想起源—中國,“齊王賽馬”，“丁渭修皇宮”。運籌學的產生與發(fā)展丁謂的皇宮修復工程

北宋年間，丁謂負責修復火毀的開封皇宮。他的施工方案是：先將工程皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔繁重的運輸任務；修復工程完成后，實施大溝排水，并將原廢墟物回填，修復成原來的大街。丁謂將取材、生產、運輸及廢墟物的處理用“一溝三用”巧妙地解決了。運籌學的產生與發(fā)展1914年英國人蘭徹斯特(F.W.Lanchester)研究人與火力的優(yōu)勢與勝利之間的關系，提出軍事運籌學中著名的“蘭徹斯特戰(zhàn)斗方程”。排隊論的先驅者丹麥工程師愛爾朗(A.K.Erlang)1917年在哥本哈根電話公司研究電話通信系統(tǒng)時，提出了排隊論的一些著名公式。20世紀30年代，荷蘭人荷雷斯?列文生(Horace.C.Levenson)用運籌學思想分析商業(yè)廣告和顧客心理，提出了存儲論中著名的“經濟批量公式”。運籌學的產生與發(fā)展

運籌學的真正形成—英國,二次大戰(zhàn)期間.Bawdsey雷達站的研究（1935年）

1935年，英國科學家R.Watson-Wart發(fā)明了雷達。丘吉爾命令在英國東海岸的Bawdsey建立了一個秘密雷達站。當時，德國已擁有一支強大的空軍，起飛17分鐘即到達英國本土。在如此短的時間內，如何預警和攔截成為一大難題。

1939年由曼徹斯特大學物理學家、英國戰(zhàn)斗機司令部顧問、戰(zhàn)后獲得諾貝爾獎金的P.M.S.Blackett為首，組織了一個小組，代號“Blackett馬戲團”。這個小組包括三名心理學家、兩名數學家、兩名應用數學家、一名天文物理學家、一名普通物理學家、一名海軍軍官、一名陸軍軍官、一名測量員。

研究的問題是：設計將雷達信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；雷達與武器的最佳配置；對探測、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機與武器的協(xié)調，作了系統(tǒng)的研究，并獲得成功?！癇lackett馬戲團”在秘密報告中使用了“OperationalResearch”，即“運籌學”。

“二戰(zhàn)”范例大西洋反潛戰(zhàn)（1942年）

1942年，美國大西洋艦隊反潛戰(zhàn)官員W.D.BAKER艦長請求成立反潛戰(zhàn)運籌組，麻省理工學院的物理學家P.W.MORSE被請來擔任計劃與監(jiān)督。

MORSE出色的工作之一，是協(xié)助英國打破了德國對英吉利海峽的封鎖。1941-1942年，德國潛艇嚴密封鎖了英吉利海峽，企圖切斷英國的“生命線”。海軍幾次反封鎖，均不成功。

應英國要求，美國派MORSE率領一個小組去協(xié)助。MORSE經過多方實地考察，最后提出了兩條重要建議：將反潛攻擊由反潛潛艇投擲水雷，改為飛機投擲深水炸彈。起爆深度由100米左右改為25米左右。即當潛艇剛下潛時攻擊效果最佳。(提高效率4-7倍)運送物資的船隊及護航艦隊編隊，由小規(guī)模多批次，改為加大規(guī)模、減少批次，這樣，損失率將減少。（25%下降到10%）。丘吉爾采納了MORSE的建議，最終成功地打破封鎖，并重創(chuàng)了德國潛艇。MORSE同時獲得英國和美國的最高勛章。運籌學的產生與發(fā)展“二戰(zhàn)”后,運籌學的思想開始由軍用轉為民用。市場銷售生產計劃運輸問題庫存管理資源分配人事管理財政與會計工程的優(yōu)化設計城市管理……運籌學的產生與發(fā)展

運籌學本身也在不斷發(fā)展。運籌數學：新算法運籌科學：新方法運籌應用：新對象50年代初期，運籌學被引入我國.運籌學《史記》：“運籌于帷幄之中，決勝于千里之外”孫武：運籌為計，知人善用，應敵為變；80年代初，運籌學在我國開始發(fā)展起來。目前國際國內著名的運籌學刊物有ManagementScienceOperationsResearchInterfacesJournalofOperationalResearchSocietyEuropeanJournalofOperationsResearchComputers&OperationsResearch運籌學學報、運籌與管理2.

運籌學的含義首先，運籌學是一種思維方式其次，運籌學是一個解決問題的工具第三，運籌學是一種科學方法學科性質

應用學科

Morse&Kimball定義：運籌學是為決策機構在對其控制的業(yè)務活動進行決策時提供的數量化為基礎的科學方法。

Churchman定義：運籌學是應用科學的方法、技術和工具，來處理一個系統(tǒng)運行中的問題，使系統(tǒng)控制得到最優(yōu)的解決方法。我國學者給出的定義：運籌學是應用分析、試驗、量化的方法，對經濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據的最優(yōu)方案，以實現最有效的管理運籌學的含義3.

運籌學的模型模型的種類：形象模型、仿真模型、數學模型運籌學的模型主要是數學模型，即用數學符號表達變量之間的相互關系，在邏輯結構上揭示事物的內在規(guī)律。它拋棄了事物的規(guī)模、形態(tài)、質地等物理性狀，專注于描述研究對象的邏輯結構和數量關系，在“質”的意義上描述研究對象的主要特征定性與定量兩者都是常用的決策方法定性是基礎，定量是工具，定量為定性服務。定性有主觀性也有有效性，定量有科學性也有局限性。管理科學的發(fā)展，定量越來越多。但定量不可替代定性。4.運籌學的學科體系規(guī)劃論：線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃圖論與網絡存儲論排隊論決策論對策論（博弈論）計算機仿真

如果把運籌學及相關內容比作一棵大樹，則大樹的主干就是“最優(yōu)化”。

大樹的根系是其基礎科學，大樹的分枝是在各個角度和方向上的最優(yōu)化，大樹的茂密枝葉是其豐富的內容，而大樹的果實則是運籌學在各個領域中的應用成果。5.

運籌學軟件6.

什么是運籌學？有限資源的優(yōu)化配置專業(yè)基礎課工具性，關于精明的學問如何聰明起來？學會運籌學背后的哲學7.運籌學的工作步驟確定問題搜集數據建立模型檢驗模型求解模型結果分析結果實施運籌學與計算機計算機為運籌學提供解題工具。本書有現成的程序可以利用要學會解題的思路與方法，建立模型很重要。8.運籌學在工商管理中的應用生產計劃：生產作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存量等

運輸問題：確定最小成本的運輸線路、物資的調撥、運輸工具的調度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產品開發(fā)與銷售計劃制定等財務會計：預測、貸款、成本分析、定價、證券管理、現金管理等*設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等9.如何學習運籌學

學習運籌學要把重點放在結合實際的應用上，不要被一些概念、理論的困難嚇倒，要用好計算機這個強有力的工具。學習運籌學要把注意力放在“入口”和“出口”兩頭，中間過程盡可能讓計算機軟件去完成：“入口”即結合實際問題建立運籌學模型；“出口”即解決問題的方案或模型的解。本書附有運籌學教學軟件，使用方法很簡單。學會使用這個運籌學教學軟件，并借助它來學好本課程.參考書《管理運籌學》，薛聲家主編，暨南大學出版社，2010《運籌學》,李清泉主編，清華大學出版社，2012《運籌學》,胡運權主編，清華大學出版社，2011《運籌學應用案例集》，胡運權主編，清華大學出版社，2005/xjjpkc/2009/ycx//special/cuvocw/yunchouxue.html/movie/2014/11/A/7/MA9RMHE25_MAA3HMCA7.html考核課堂參與10%個人作業(yè)20%小組作業(yè)10%期末考試60%第二章線性規(guī)劃與單純形法2.1LP(linearprogramming)的基本概念

LP是在有限資源的條件下，利用線性方程建立模型，合理分配和利用資源，以期取得最佳的經濟效益的優(yōu)化方法。LP特征：一組有待決策的變量，一個線性的目標函數，一組線性的約束條件。2.1.1LP的數學模型

例題1—生產計劃問題某廠生產兩種產品，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數如下表：產品A產品B資源限量勞動力設備原材料1434510360200300利潤元/kg70120例題1建模問題：如何安排生產計劃，使得獲利最多？步驟：1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數：maxZ=70X1+120X23、確定約束條件：人力約束9X1+4X2≤360

設備約束4X1+5X2

≤200

原材料約束3X1+10X2

≤300

非負性約束X1≥0X2≥0

線性規(guī)劃問題是在一組線性等式或不等式的約束之下，求一個線性函數的最大值或最小值的問題。它由以下部分組成：目標函數:max

z

或min

z

約束條件:s.t.(subjectto)

滿足于決策變量:用符號xj等來表示可控制的因素

線性規(guī)劃模型特點決策變量：向量(x1…xn)T決策人要考慮和控制的因素非負約束條件：線性等式或不等式目標函數：Z=?(x1

…xn)線性式，求Z極大或極小例題2——配方問題養(yǎng)海貍鼠飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養(yǎng)要求70030200例題2建模設抓取飼料Ix1kg;飼料IIx2kg;飼料IIIx3kg……目標函數：最省錢minZ=2x1+7x2+4x3+9x4+5x5約束條件營養(yǎng)要求：

3x2+2x2+x3+6x4+18x5≥700x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非負性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0例題3：人員安排問題醫(yī)院護士24小時值班，每次值班8小時。不同時段需要的護士人數不等。據統(tǒng)計：

序號時段最少人數安排人數106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6例題3建模目標函數：minZ=x1+x2+x3+x4+x5+x6約束條件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30

X6+X1≥60非負性約束：xj

≥0,j=1,2,…6線性規(guī)劃模型一般形式目標函數:

max（min）z=c1

x1+c2

x2+…+cnxn

約束條件：

s.t.

a11

x1+a12

x2+…+a1nxn

≤（=,≥）b1

a21

x1+a22

x2+…+a2nxn

≤（=,≥）b2…………am1

x1+am2

x2+…+amnxn≤（=,≥）bm

x1，x2，…，xn≥0.2.1.2

線性規(guī)劃的圖解法例1.

目標函數：

max

z=50x1+100x2

約束條件：

s.t.

x1+x2≤300(E)2x1+x2≤400(G)

x2≤250(F)

x1≥0，x2≥0一個線性不等式確定一個半平面如不等式(E)

x1+x2≤300確定的半平面為x1x2100300300100200200x1+x2=300x1+x2≤300Ex1x2x2≥0x2=0x1x2x1≥0x1=05個半平面的交得到可行域考查目標函數等值線EF100200300100200300GABCz=50x1+100x2=275000Dz=50x1+100x2=10000z=50x1+100x2=20000解聯(lián)立方程組

x1+x2=300(E)

x2=250(F)得最優(yōu)解為：

x1=50，x2=250，最優(yōu)目標值為：

z=27500。例、maxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20解：(1)、確定可行域

X10X1=0(縱)X20X2=0(橫)X1+2X230X1+2X2=30(0,15)(30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)

2X2=24(2)、求最優(yōu)解解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC可行域目標函數等值線最優(yōu)解64-860x1x2max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0線性規(guī)劃圖解法的步驟

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標系上作圖表示線性規(guī)劃問題的有關概念，并求解，其步驟如下：

(1)

分別取決策變量x1

，x2

為坐標向量建立直角坐標系。(2)

對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。若各半平面交出來的公共區(qū)域存在，顯然，其中的點滿足所有的約束條件，稱這樣的點為此線性規(guī)劃的可行解，全體可行解的集合稱為可行集或可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問題無可行解。（3）任意給定目標函數一個確定的值，作出對應的目標函數等值線，并確定該族等值線平行移動時目標函數值增加的方向。然后平移目標函數的等值線，使其達到既與可行域有交點又不可能使值再增加的位置(有時交于無窮遠處，此時稱無有限最優(yōu)解）。此時，目標函數等值線與可行域的交點即此線性規(guī)劃的最優(yōu)解（一個或多個），此目標函數的值即最優(yōu)值。啟示:(1)、LP問題的約束集合(可行域)是凸集(凸多邊形)。(2)、若有最優(yōu)解，定可在凸多邊形的頂點得到。凸集凸集不是凸集頂點解的幾種情況:唯一最優(yōu)解．多個最優(yōu)解．有可行解，無最優(yōu)解（無界解）．無可行解．解的討論：最優(yōu)解是唯一解；無窮多組最優(yōu)解：例maxz=40x1+30x2

s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x1可行域目標函數是同約束條件：4x1+3x2

120平行的直線x2=

z/30-（4/3）x1x2504030201010203040x1可行域當z的值增加時，目標函數同約束條件：4x1+3x2

120重合，Q1與Q2之間都是最優(yōu)解。Q1（25，0）Q2（15，20）解的討論：無界解：例：maxz=x1+x2s.t.-2x1+x2

40x1-x2

20x1,x2

0x2504030201010203040x1該可行域無界，目標函數值可增加到無窮大，稱這種情況為無界解或無最優(yōu)解。解的討論：無可行解：例：maxz=2x1+3x2

s.t.x1+2x2

8x1

4x2

3-2x1+x2

4x1,x2

0該問題可行域為空集，即無可行解，也不存在最優(yōu)解。解的情況：有可行解

有唯一最優(yōu)解

有無窮最優(yōu)解

無最優(yōu)解無可行解例maxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X200Z=40X1+80X2=0

X1+2X2=30DABCX2X1最優(yōu)解：BC線段maxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20無界無有限最優(yōu)解例、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X1例、maxZ=3X1+2X2-X1-X21X1,X20無解無可行解-1X2-1X10線性規(guī)劃的標準形式目標函數：

maxz=c1

x1+c2

x2+…+cnxn

約束條件：

s.t.a11

x1+a12

x2+…+a1nxn

=b1

a21

x1+a22

x2+…+a2nxn

=b2…………

am1

x1+am2

x2+…+amnxn=bm

x1，x2，…，xn≥0.線性規(guī)劃的標準形式有如下四個要求：目標最大化約束方程為等式決策變量為非負右端項為非負對于各種非標準形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉化為標準形式:1.極小化目標函數的問題：設目標函數為

minf=c1x1+c2x2+…+cnxn

(可以)令

z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

maxz=-c1x1-c2x2

-…-cnxn

。

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標函數值卻相差一個符號，即

minf

＝-maxz

。目標函數xoZ-Z2.

約束條件不是等式的問題：設約束條件為

ai1

x1+ai2

x2+…+ainxn

≤bi可以引進一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1

x1+ai2

x2+…+ainxn

)。顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1

x1+ai2

x2+…+ainxn+s=bi

。當約束條件為

ai1

x1+ai2

x2+…+ainxn

≥bi時，類似地令

s=(ai1

x1+ai2

x2+…+ainxn)-bi

。顯然，s

也具有非負約束，即s≥0，這時新的約束條件成為

ai1

x1+ai2

x2+…+ainxn-s=bi

。

為了使約束由不等式成為等式而引進的變量s

當不等式為“小于等于”時稱為“松弛變量”當不等式為“大于等于”時稱為“剩余變量”如果原問題中有若干個非等式約束，則將其轉化為標準形式時，必須對各個約束引進不同的變量，有時也將它們統(tǒng)稱為松弛變量。

例：將以下線性規(guī)劃問題轉化為標準形式

minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x3≤15.74.1x1+3.3x3≥8.9

x1+x2+x3=38

x1，x2，x3

≥0

解：首先,將目標函數轉換成極大化：令z=-f=-3.6x1

+5.2x2

-1.8x3

其次考慮約束，有2

個不等式約束，引進松弛變量和剩余變量x4，x5≥0。于是，我們可以得到以下標準形式的線性規(guī)劃問題：

maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5

=8.9

x1+x2+x3

=38

x1，x2，x3，x4，x5≥0。3.變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。4.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：

-ai1

x1-ai2

x2-…-ainxn

=-bi

例:將以下線性規(guī)劃問題轉化為標準形式

minf=-3x1+5x2+8x3-7x4

s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58

x1，x3，x4≥0解：首先，將目標函數轉換成極大化：令

z=-f=3x1–5x2–8x3+7x4

；其次考慮約束，有3個不等式約束，引進2個松弛變量和1

個剩余變量

x5,x6

,x7≥0；由于x2

無非負限制，引入兩個非負變量，可令x2=x2’-x2”,其中x2’≥0，x2”≥0

；由于第3個約束右端項系數為-58，于是把該式兩端乘以-1

。于是，我們可以得到以下標準形式的線性規(guī)劃問題：maxz=3x1–5x2’+5x2”–8x3

+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=