運籌學(xué)緒論069的課件

系統(tǒng)工程A第一講緒論一、運籌學(xué)的形成與發(fā)展二、運籌學(xué)模型及分析步驟三、運籌學(xué)的定義及學(xué)科體系學(xué)習(xí)目的學(xué)習(xí)本章要了解運籌學(xué)的形成和發(fā)展歷史、典型案例，以及運籌學(xué)研究的主要內(nèi)容等。第一節(jié)運籌學(xué)的形成和發(fā)展運籌學(xué)（OperationsResearch）是系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)(ManagementScience)。運籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”，故有人稱之為最優(yōu)化技術(shù)。1938年英國最早出現(xiàn)了軍事運籌學(xué)，命名為“OperationalResearch”,1942年，美國從事這方面工作的科學(xué)家命其名為“OperationsResearch”，這個名字一直延用至今。一、中國古代的運籌學(xué)思想中國《史記》中的“運籌帷幄之中，決勝千里之外”表達了中國古代運籌學(xué)思想，在古代中國有許多運籌學(xué)思想的應(yīng)用案例，如丁謂修宮、田忌賽馬等，都蘊藏著神奇的運籌學(xué)思想，這些案例至今仍有很高的參考和借鑒價值。1．丁謂修宮宋朝《夢溪筆談》中記載了這樣一個故事：北宋真宗年間，皇宮失火，皇帝召各大臣商議如何在很短的時間內(nèi)修復(fù)好皇宮，而修復(fù)皇宮包括取土燒磚，運輸建筑材料，清理廢墟三大工程，但在當(dāng)時的條件下，這是相當(dāng)繁重的工程，大家都無以言答。當(dāng)時有個叫丁謂的大臣，他提出了一個一舉三得的方案丁謂修宮工程問題示意圖取土問題

木材和石料運輸問題建筑垃圾處理問題挖溝引水入溝填溝2．田忌賽馬

戰(zhàn)國時期齊王和田忌賽馬,各從自己上等馬、中等馬、下等馬中選送一匹進行比賽，每輸一局，輸銀千兩，齊王的馬都比田忌的好，但田忌的下等馬與齊王的上等馬賽，用上等馬對中等馬，用中等馬對下等馬，這樣田忌非但沒有輸，反而嬴了一千兩銀子，這便是系統(tǒng)中從整體出發(fā)，選最優(yōu)方案，到最后實施的對策策略。二、運籌學(xué)學(xué)科的形成

現(xiàn)在普遍認為，運籌學(xué)的研究是從第二次世界大戰(zhàn)初期的軍事任務(wù)開始的，以英國為代表的科學(xué)家做了奠基性的工作。當(dāng)時迫切需要把各項稀少的資源以有效的方式分配給各種不同的軍事經(jīng)營及在每一經(jīng)營內(nèi)的各項活動，所以美國及隨后美國的軍事管理當(dāng)局都號召大批科學(xué)家運用科學(xué)手段來處理戰(zhàn)略與戰(zhàn)術(shù)問題，實際上這便是要求他們對種種（軍事）經(jīng)營進行研究，這些科學(xué)家小組正是最早的運籌小組（O.R.小組）。第二次世界大戰(zhàn)期間，運籌學(xué)（OR）成功地解決了許多重要作戰(zhàn)問題，顯示了科學(xué)的巨大物質(zhì)威力，為“OR”后來的發(fā)展鋪平了道路。

1935年，英國科學(xué)家R.Watson-Wart發(fā)明了雷達。丘吉爾命令在英國東海岸的Bawdsey建立了一個秘密雷達站。

1939年由P.M.S.Blackett（著名物理學(xué)家）為首，組織了一個小組，代號“Blackett馬戲團”。研究的問題是：設(shè)計將雷達信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；雷達與武器的最佳配置；對探測、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機與武器的協(xié)調(diào)，作了系統(tǒng)的研究，并獲得成功?！癇lackett馬戲團”在秘密報告中使用了“OperationalResearch”，即“運籌學(xué)”。1．模型運籌學(xué)模型是用一些數(shù)學(xué)關(guān)系（數(shù)學(xué)方程、邏輯關(guān)系等）來描述被研究對象的實際關(guān)系（技術(shù)關(guān)系、物理定律、外部環(huán)境等）。運籌學(xué)模型的一個顯著特點是它們大部分為最優(yōu)化模型。一般來說，運籌學(xué)模型都有一個目標(biāo)函數(shù)和一系列的約束條件，模型的目標(biāo)是在滿足約束條件的前提下使目標(biāo)函數(shù)最大化或最小化。第二節(jié)、運籌學(xué)模型及分析步驟Max（Min）z＝7x1+5x23x1+2x2

≤904x1+6x2

≤2007x2

≤

210

x1≥0，x2≥0

數(shù)學(xué)模型舉例：2．研究方法

①從現(xiàn)實生活場合抽出本質(zhì)的要素來構(gòu)造數(shù)學(xué)模

型；②探索求解的結(jié)構(gòu)并導(dǎo)出系統(tǒng)的求解過程；③從可行方案中尋求系統(tǒng)的最優(yōu)解法。0102033．運籌學(xué)解決問題的方法步驟明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果明確問題建立模型設(shè)計算法整理數(shù)據(jù)求解模型評價結(jié)果簡化？滿意？YesNoNoOperationsResearch含義

Operations漢語翻譯工作、操作、行動、手術(shù)、運算OperationsResearch

日本——運用學(xué)港臺——作業(yè)研究

中國大陸——運籌學(xué)第三節(jié)運籌學(xué)的定義及學(xué)科體系運籌學(xué)的定義

Morse&Kimball（運籌學(xué)界元老）運籌學(xué)是為決策機構(gòu)在對其控制的業(yè)務(wù)活動進行決策時，提供的數(shù)量化為基礎(chǔ)的科學(xué)方法。

英國人運籌學(xué)會（世界上最早的運籌學(xué)會）運籌學(xué)是運用科學(xué)方法（特別是數(shù)學(xué)方法）來解決工業(yè)、商業(yè)、政府、國防等部門里有關(guān)人力、機器、物資、金錢等大型系統(tǒng)的指揮和管理中出現(xiàn)的復(fù)雜問題的一門學(xué)科。由一支綜合性的隊伍，采用科學(xué)的方法，為一些涉及到有機系統(tǒng)（人-機）的控制系統(tǒng)問題提供解答，為該系統(tǒng)的總目標(biāo)服務(wù)的學(xué)科。

——錢學(xué)森等學(xué)科體系

運籌學(xué)已經(jīng)形成了一個龐大的學(xué)科體系，其具體內(nèi)容主要包括：規(guī)劃論（包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動態(tài)規(guī)劃）、決策論、對策論、排隊論、存儲論、網(wǎng)絡(luò)分析等。線性規(guī)劃對偶理論運輸問題整數(shù)規(guī)劃動態(tài)規(guī)劃圖與網(wǎng)絡(luò)方法網(wǎng)絡(luò)計劃技術(shù)矩陣決策決策分析緒論-思考題1．什么是運籌學(xué)？列舉我國古代運籌學(xué)思想的應(yīng)用案例。2．在第二次世界大戰(zhàn)中，有哪些運用運籌學(xué)的戰(zhàn)例？3．我國的運籌學(xué)研究和應(yīng)用情況如何？4．主要分支有哪些？5．簡述運籌學(xué)分析的步驟。第一章線形規(guī)劃

本章學(xué)習(xí)重點

線性規(guī)劃是運籌學(xué)中比較成熟的一個分支，它具有成熟而有效的求解方法，可以借助于計算機進行求解，在軍事、經(jīng)濟等領(lǐng)域中具有廣泛的應(yīng)用。學(xué)習(xí)本章，要掌握線性規(guī)劃的數(shù)學(xué)模型（建模以及把不同形式的線性規(guī)劃問題化為標(biāo)準形式的方法）、求解方法。

線性規(guī)劃問題的提出線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的基本概念線性規(guī)劃問題的標(biāo)準形式繼續(xù)返回第一節(jié)線性規(guī)劃問題

及其數(shù)學(xué)模型問題的提出引例:生產(chǎn)計劃問題產(chǎn)品甲產(chǎn)品乙如何安排生產(chǎn)使利潤最大？線性規(guī)劃研究的內(nèi)容在現(xiàn)有的資源條件下，如何充分利用資源，使任務(wù)或目標(biāo)完成得最好（求極大化問題）。在給定目標(biāo)下，如何以最少的資源消耗，實現(xiàn)這個目標(biāo)（求極小化問題）。是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——甲的產(chǎn)量

——乙的產(chǎn)量

MaxZ=x1+x2決策變量第2步--定義目標(biāo)函數(shù)——利潤

MaxZ=2x1+3x2系數(shù)第2步--定義目標(biāo)函數(shù)對我們有何限制?第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0該計劃的數(shù)學(xué)模型

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2決策變量（Decisionvariables）目標(biāo)函數(shù)（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數(shù)指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標(biāo)函數(shù)達到最優(yōu)的決策變量的值線性規(guī)劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標(biāo)函數(shù)是線性的。求目標(biāo)函數(shù)最大化或最小化

例2(書)

某廠生產(chǎn)甲乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需用資源A3噸，資源B4m3；制成一噸產(chǎn)品乙需用資源A2噸，資源B6m3，資源c7個單位。若一噸產(chǎn)品甲和乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源的限制量分別為90噸、200m3和210個單位，試決定應(yīng)生產(chǎn)這兩種產(chǎn)品各多少噸才能使創(chuàng)造的總經(jīng)濟價值最高?建模步驟：第一步：確定決策變量

x1：生產(chǎn)產(chǎn)品甲的數(shù)量（噸）

x2：生產(chǎn)產(chǎn)品乙的數(shù)量（噸）上述變量為由決策者決定的未知量，稱為決策變量。第二步：確定目標(biāo)函數(shù)

以Z

表示生產(chǎn)甲和乙兩種產(chǎn)品各為x1和x2（噸）時產(chǎn)生的經(jīng)濟價值，總經(jīng)濟價值最高的目標(biāo)可表示為：

maxz＝7x1十5x2

這就是該問題的目標(biāo)函數(shù)。

第三步：確定約束條件本例的約束條件為三種資源的限制用量。對各個限制條件逐一加以分析，寫出反映其限制關(guān)系的表達式（等式或不等式），從而得到約束條件。

資源A限制：3x1十2x2

≤90

資源B限制；4x1十6x2

≤200

資源C限制：7x2

≤

210

此外，產(chǎn)量x1和x2不能為負，只能取正值非負條件：x1

≥0，x2

≥0經(jīng)上述分析，可將該問題表示為：

maxz＝7x1十5x23x1十2x2

≤904x1十6x2

≤2007x2

≤

210

x1

≥

0，x2

≥0這種數(shù)學(xué)表達方式，稱為該問題的一種數(shù)學(xué)模型。線性規(guī)劃三要素線性規(guī)劃(LinearProgramming，LP)有：一組有待決策的變量（指模型中要求解的未知量）一個線性的目標(biāo)函數(shù)（指模型中要達到的目標(biāo)的數(shù)學(xué)表達式）一組線性的約束條件（指模型中的變量取值所需要滿足的一切限制條件）

線性規(guī)劃模型的一般形式線性規(guī)劃問題的標(biāo)準形式標(biāo)準形式為:目標(biāo)函數(shù)最大約束條件等式?jīng)Q策變量非負右端常數(shù)項非負

用矩陣表示A—系數(shù)矩陣C—價值向量b—資源向量X—決策變量向量一般線性規(guī)劃問題的標(biāo)準形化線型規(guī)劃問題的數(shù)學(xué)模型有各種不同的形式，為了便于討論和求解，需要將線型規(guī)劃問題的數(shù)學(xué)模型寫成一個統(tǒng)一的格式，稱為線型規(guī)劃問題的標(biāo)準型。統(tǒng)一格式規(guī)定如下：1、目標(biāo)函數(shù)取最大化2、所有約束條件用等式來表示3、所有決策變量取非負值4、每一約束條件的右端常數(shù)（資源限量）為非負值

minZ=CX等價于maxZ’=-CX“”

約束：加入非負松馳變量一般線性規(guī)劃問題的標(biāo)準形化例：

目標(biāo)函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0

minZ=CX等價于maxZ’=-CX“”

約束：加入非負松馳變量一般線性規(guī)劃問題的標(biāo)準形化例：

“”

約束：減去非負剩余變量；

Max例：可正可負（即無約束）；

解：標(biāo)準形為復(fù)習(xí)思考