運籌學線性規(guī)劃1

運籌學（線性規(guī)劃）模式識別與智能系統(tǒng)研究所韓延彬Email:HYB309@復習前述內容:1、運籌學的基本概念和發(fā)展簡史2、運籌學研究的基本特征與基本方法3、運籌學主要分支4、運籌學與管理科學特別強調的內容是考試的重點。寫出運籌學的基本概念運籌學是運用科學的方法(如分析、試驗、量化等)來決定如何最佳地運營和設計各種系統(tǒng)的一門學科.其研究的基本特征和方法系統(tǒng)的整體觀念，多學科的綜合，應用模型技術.分析和表述問題,建立模型,求解模型和優(yōu)化方案,對模型和由模型導出的解進行檢驗,對解的有效控制,方案的實施主要分支線性規(guī)劃,非線性規(guī)劃,動態(tài)規(guī)劃,圖與網絡分析,存儲論,排隊論,對策論,決策論1.線性規(guī)劃的定義當變量連續(xù)取值，且目標函數和約束條件均為線性時，稱這類模型為線性規(guī)劃的模型。目標函數：問題的目標通過用變量的函數形式表示約束條件：對問題的限制條件用有關的等式或不等式的表示。其典型問題為：運輸問題，生產計劃問題，下料問題，混合配料問題，許多非線性的問題往往采用某些問題轉化成為線性問題。本章主要內容線性規(guī)劃問題及其數學模型圖解法單純形法原理單純形法計算步驟單純形法的進一步討論應用舉例這一章的內容都非常的重要，所以要注意！原理，計算1.線性規(guī)劃問題及其數學模型怎樣根據現實問題搭建線性規(guī)劃的數學模型線性規(guī)劃的標準模型是什么怎樣將一般的線性規(guī)劃模型轉化為標準模型1.線性規(guī)劃問題及其數學模型問題：在現有各項資源條件的限制下，如何確定方案，使預期目標達到最優(yōu)。例1：公司S計劃制造Ⅰ,Ⅱ兩種產品，已知制造一件所占用的A，B兩臺設備的臺時，調試時間，調試工序，每天可制造的能力，以及每種產品的利潤如下：

ⅠⅡ每天的可用能力設備A設備B調試工序06152115245利潤21

問題分析可控因素：每天生產兩種產品的數量，分別設為x1,x2,目標：每天的生產利潤最大利潤函數maxz=2x1+x2（1）受制條件：每天原料的需求量不超過可用量：設備A：5x2≤15（2）

設備B：6x1+2x2≤24（3）

工序：x1+x2≤5（4）蘊含約束：產量為非負數x1,x2≥0（5）

其中（1）為目標函數，（2）～（5）約束條件例2：某工廠用三種原料生產三種產品，已知的條件如表2.1.1所示，試制訂總利潤最大的生產計劃單位產品所需原料數量（公斤）產品Q1產品Q2產品Q3原料可用量公斤/日原料P12301500原料P2024800原料P33252000單位產品的利潤（千元）354問題分析規(guī)劃問題的三個要素變量（決策變量）：問題中要確定的未知量，用以明確規(guī)劃中的用數量表示方案，措施，可有決策者制定和控制目標函數：決策變量的函數，按優(yōu)化目標分別為max和min約束條件：決策變量收到各種資源條件的限制，通常為等式和不等式。線性規(guī)劃的一般模型假定線性規(guī)劃問題中含有n個變量，分別用xj（j=1,...,n）表示，在目標函數當中xj的系數為cj（價值系數），xj的取值受到m項資源的限制，用bi（I=1,...,m）表示第i中資源的數量，ai,j為技術系數或工藝系數。則上述線性問題的數學模型可以表示為：max(min)z=c1x1+c2x2+...+cnxna11x1+a12x2+...+a1nxn

≤（＝，≥）b1a21x1+a22x2+...+a2nxn

≤（＝，≥）b2...am1x1+am2x2+...+amnxn

≤（＝，≥）bmx1,x2,...,xn≥0線性規(guī)劃的一般模型(其他形式)向量模式矩陣模式Max(min)z=CXAX≤(=,≥)BX≥0線性規(guī)劃的一般模型(其他形式)線性規(guī)劃問題的標準形式對于非標準形式，我們可以通過一下的形式進行標準化：(1)(2)圖1(3)約束條件(4)無約束條件x沒有約束，可以轉化為x＝x1－x2(5)對于x≤0的情況x`=-x圖解法了解圖解法的一些基本概念會用圖解法求解簡單題目了解圖解法解的情況對模型中只含2個變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解。一個線性規(guī)劃問題有解，是指能找出一組xj(j＝1,...,n)，滿足約束條件，稱這組xj為問題的可行解。通常線性規(guī)劃問題總是含有多個可行解，稱全部可行解的集合為可行域．可行域中使目標函數值達到最優(yōu)的可行解稱為最優(yōu)解。對不存在可行解的線性規(guī)劃問題，稱該問題無解。圖解法求解的目：一、判別線性規(guī)劃問題的求解結果，二、在存在最優(yōu)解的條件下，把問題的最優(yōu)解找出來。理論上講，圖解法是不存在變量限制的，但是在實際情況中，我們最多能描述的是空間模型，所以圖解法要求變量的個數≤3，一般是兩個變量?？尚杏颍ㄔ搮^(qū)域中的任何一個解即為可行解）最優(yōu)解區(qū)域（該區(qū)域中的任何一個解，都是最優(yōu)解）最優(yōu)解，也是可行解線性規(guī)劃的圖解（步驟）例3：max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標函數等值線最優(yōu)解64-860x1x2圖解法的步驟（1）以變量x1為橫坐標軸，x2為縱坐標軸畫出直角平面坐標系，并適當選取單位坐標長度。（2）圖示約束條件，找出可行域（根據約束條件）。（3）圖示目標函數，由于目標函數值逐漸增大，這樣得到一組平行的直線。（4）最后解的確定，找到使得目標函數值最大的點或者是點集。線性規(guī)劃問題求解的幾種情況惟一解圖解線性規(guī)劃問題求解的幾種情況無窮解圖解平行目標函數同某一約束條件平行圖解無界解，缺少約束條件無界解線性規(guī)劃問題求解的幾種情況無解無解，沒有可行解區(qū)域線性規(guī)劃問題求解的幾種情況由圖解法得到的啟示

1．求解線性規(guī)劃問題時，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解。

2．若線性規(guī)劃問題的可行域存在，則可行域是一個凸集。

3．若線性規(guī)劃問題的最