運籌學知識點總結

運籌學：應用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。線性規(guī)劃的圖解法基本概念線性規(guī)劃：是一種解決在線性約束條件下追求最大或最小的線性目標函數(shù)的方法。線性規(guī)劃的三要素：變量或決策變量、目標函數(shù)、約束條件。目標函數(shù)：是變量的線性函數(shù)。約束條件：變量的線性等式或不等式?？尚薪猓簼M足所有約束條件的解稱為該線性規(guī)劃的可行解?？尚杏颍嚎尚薪獾募戏Q為可行域。最優(yōu)解：使得目標函數(shù)值最大的可行解稱為該線性規(guī)劃的最優(yōu)解。唯一最優(yōu)解、無窮最優(yōu)解、無界解（可行域無界）或無可行解（可行域為空域）。凸集：要求集合中任意兩點的連線段落在這個集合中。等值線：目標函數(shù)z，對于z的某一取值所得的直線上的每一點都具有相同的目標函數(shù)值，故稱之為等值線。松弛變量：對于“≤”約束條件，可增加一些代表沒使用的資源或能力的變量，稱之為松弛變量。剩余變量：對于“≥”約束條件，可增加一些代表最低限約束的超過量的變量，稱之為剩余變量。線性規(guī)劃的標準形式約束條件為等式（=）約束條件的常數(shù)項非負（bj決策變量非負（xj靈敏度分析：是在建立數(shù)學模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)的變化對最優(yōu)解產(chǎn)生什么影響。目標函數(shù)中的系數(shù)ci目標函數(shù)的斜率在形成最優(yōu)解頂點的兩條直線的斜率之間變化時，最優(yōu)解不變。約束條件中常數(shù)項bi對偶價格：約束條件常數(shù)項中增加一個單位而使最優(yōu)目標函數(shù)值得到改進的數(shù)量。當某約束條件中的松弛變量（或剩余變量）不為零時，這個約束條件的對偶價格為零。線性規(guī)劃問題在工商管理中的應用人力資源分配問題（P41）設xi為第i班次開始上班的人數(shù)生產(chǎn)計劃問題（P44）套材下料問題（P48）下料方案表（P48）設xi為按各下料方式下料的原材料數(shù)量配料問題（P49）設xij為第i種產(chǎn)品需要第j投資問題（P53）設xij為第i年初投資于項目j運輸問題產(chǎn)銷平衡問題（P133）產(chǎn)銷平衡運價表產(chǎn)大于銷：假想倉庫，轉化為產(chǎn)銷平衡問題求解（P141）對于貨物必須運出的產(chǎn)地，假想倉庫的單位儲存費用為M（是一個足夠大的正數(shù)），對于貨物非必須運出的產(chǎn)地，假想倉庫的單位儲存費用為給定值。對于貨物非必須全部運出的銷地，需將其拆分為“貨物必須運出”和“貨物非必須運出”兩個產(chǎn)地。銷大于產(chǎn)：假想產(chǎn)地，轉化為產(chǎn)銷平衡問題求解（P139）對于需求必須滿足的銷地，假想產(chǎn)地的單位運價為M（是一個足夠大的正數(shù)），對于需求非必須滿足的銷地，假想產(chǎn)地的單位運價為0。對于需求非必須全部滿足的銷地，需將其拆分為“需求必須滿足”和“需求非必須滿足”兩個銷地。生產(chǎn)與儲存問題（P142）法一：線性規(guī)劃，設xij為第i時間點生產(chǎn)的第j時間點交貨的產(chǎn)品數(shù)目法二：轉化為運輸問題（M的作用：迫使運量為0）轉運問題（P146）法一：線性規(guī)劃（約束條件：起點節(jié)點的約束、轉運節(jié)點的約束、終點節(jié)點的約束）法二：轉化為擴大的運輸問題（P148）對擴大的運輸問題建立運價表，將表中不可能的運輸方案用M代替。將原產(chǎn)地、銷地、中轉站的產(chǎn)量和銷量同時加上原產(chǎn)量或銷量的值。計算機求解運輸問題的方法是表上作業(yè)法，其實質是單純形法。整數(shù)規(guī)劃整數(shù)規(guī)劃的分類純整數(shù)規(guī)劃：如果所有的變量都為非負整數(shù)，則稱為純整數(shù)規(guī)劃?；旌险麛?shù)規(guī)劃：如果只有一部分變量為非負整數(shù)，則稱為混合整數(shù)規(guī)劃。0-1規(guī)劃：如果所有變量都是0,1變量，則稱為0-1規(guī)劃。整數(shù)規(guī)劃的性質任何求最大目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值；任何求最小目標函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值。整數(shù)規(guī)劃的圖解法（P173）、整數(shù)規(guī)劃的計算機求解（P175）投資場所的選擇（P177）0-1規(guī)劃固定成本問題（P178）產(chǎn)品的固定費用只有生產(chǎn)該產(chǎn)品時才投入，為說明固定成本的性質，需引入0-1變量yi為避免不投入固定費用就生產(chǎn)，有約束條件xi≤yi指派問題（P179）每項任務均有一人擔任，有約束條件i每人承擔的任務不超過自己的承擔能力（ai是第i個人至多承擔的任務數(shù)）j人少任務多且一人只能擔任一項任務時，需假設一人，其完成所有任務的時間為0。分布系統(tǒng)設計（P181）附帶選址問題的運輸問題，需引入0-1變量yi，有j投資問題（P183）當項目有最低投資額要求時，需引入0-1變量yij最低投資額要求其他約束條件為“第i年投資額=可動資產(chǎn)”。目標規(guī)劃目標規(guī)劃：是解決存在多個目標的最優(yōu)化問題的方法，它把多目標決策問題轉化為線性規(guī)劃來求解。偏差變量：實際值與目標值的差距。偏差變量的作用是允許約束條件不被精確滿足。有優(yōu)先權的目標規(guī)劃，首先考慮優(yōu)先權高的目標（P206）目標規(guī)劃模型的標準化（P208）復雜情況下的有優(yōu)先權的目標規(guī)劃（P209）加權目標規(guī)劃（P211）罰數(shù)權重：表示偏離各目標的嚴重程度?；痉椒ㄊ峭ㄟ^量化的方法分配給每個目標偏離的嚴重程度一個罰數(shù)權重，建立總的目標函數(shù)，該目標函數(shù)表示的目標是要使每個目標與各自目標的加權偏差之和最小。動態(tài)規(guī)劃基本概念動態(tài)規(guī)劃：是解決多階段決策過程最優(yōu)化問題的一種方法。階段：根據(jù)時間與空間的自然特征劃分階段。狀態(tài)si：指每個階段開始時所處的自然狀況或客觀條件決策xi：某一階段內的抉擇指標函數(shù)ri(si,xi)：表示指標函數(shù)是衡量全過程策略或k子過程策略優(yōu)劣的數(shù)量指標，指標函數(shù)的最優(yōu)值稱之為最優(yōu)指標函數(shù)，記作fi狀態(tài)轉移方程s動態(tài)規(guī)劃表sfxrfx0123012最優(yōu)化原理：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構成最優(yōu)子策略。也就是說最優(yōu)策略的任一子策略都是最優(yōu)的。最短路徑問題（P217）si為階段初始位置，xi為階段決策資源分配問題（P222）sk為階段初始剩余量，x設sk=分配給第k個目標到第n設xi背包問題（P225）法一：動態(tài)規(guī)劃（si為階段初始剩余量，x法二：整數(shù)規(guī)劃生產(chǎn)與儲存問題（P230）si為階段初始儲存量，xi為階段決策生產(chǎn)量，d機器負荷分配問題（235）設sk=第k階段初擁有的設xi=第k圖與網(wǎng)絡模型無向圖：G由點和邊構成，V是點的集合，E是邊的集合。鏈：(v1,圈：(連通圖：對一個無向圖G，若任意兩個不同點之間，至少存在一條鏈，則稱G是連通圖。有向圖：D由點和弧構成，V是點的集合，A是弧的集合。路：(v回路：v賦權圖對于無向圖G的每一條邊(vi,vj)，如果相應的有一個數(shù)wij，則稱這樣的圖G為賦權圖對于有向圖D的每一條弧(vi,vj)，如果相應的有一個數(shù)cij，則稱這樣的圖D為賦權圖網(wǎng)絡在賦權的有向圖D中指定一點，稱為發(fā)點（記為vs），指定另一點為收點（記為vt），其余的點稱為中間點，并把D中的每一條弧的賦權數(shù)cij稱之為弧(viDijkstra算法（P249）I={sij=l最小生成樹問題：在一個賦權的連通的無向圖G找出一個生成樹，并使得這個生成樹的所有邊的權數(shù)之和為最小。樹：無圈的連通圖。生成子圖：給了一個無向圖G=(V,E)，我們保留G的所有點，而刪除部分G的邊或者說保留一部分G生成樹：如果圖G的一個生成子圖是一個樹，則稱這個生成子圖為生成樹。破圈算法（P257）最大流問題：給了一個帶收發(fā)點的網(wǎng)絡，其每條弧的賦權稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。（P261）最小費用最大流問題（P264）排序與統(tǒng)籌方法一臺機器、n個零件的排序問題（求使各零件平均停留時間最少的加工次序）各零件平均停留時間為1即按照加工時間排出加工順序，加工時間越短的零件排在越前面，加工時間越長的零件排在越后面，可使各個零件的平均停留時間為最少（按加工時間升序排列）。兩臺機器、n個零件的排序問題加工時間的延長主要是由于第二臺機器的停工待料造成的為減少第二臺機器的停工待料，應把在第一臺機器上加工時間越短的零件越早加工，把在第二臺機器上加工時間越短的零件越晚加工。步驟（P278）計劃網(wǎng)絡圖點表示一個事件，是一個工序的開始或結束，是相鄰工序在事件上的分界點?；”硎疽粋€工序，在弧的上面標工序代號，在弧的下面標權數(shù)。緊前工序：緊接某項工序的先行（前道）工序。緊后工序：緊接某項工序的后續(xù)工序。虛工序計劃網(wǎng)絡圖中不能有缺口和回路。關鍵路線：計劃網(wǎng)絡圖中最長的路線，用雙線