運(yùn)籌學(xué)線性規(guī)劃1

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

ⅠⅡ每天的可用能力設(shè)備A設(shè)備B調(diào)試工序06152115245利潤(rùn)21

問(wèn)題分析可控因素：每天生產(chǎn)兩種產(chǎn)品的數(shù)量，分別設(shè)為x1,x2,目標(biāo)：每天的生產(chǎn)利潤(rùn)最大利潤(rùn)函數(shù)maxz=2x1+x2（1）受制條件：每天原料的需求量不超過(guò)可用量：設(shè)備A：5x2≤15（2）

設(shè)備B：6x1+2x2≤24（3）

工序：x1+x2≤5（4）蘊(yùn)含約束：產(chǎn)量為非負(fù)數(shù)x1,x2≥0（5）

其中（1）為目標(biāo)函數(shù)，（2）～（5）約束條件例2：某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表2.1.1所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原料數(shù)量（公斤）產(chǎn)品Q1產(chǎn)品Q2產(chǎn)品Q3原料可用量公斤/日原料P12301500原料P2024800原料P33252000單位產(chǎn)品的利潤(rùn)（千元）354問(wèn)題分析規(guī)劃問(wèn)題的三個(gè)要素變量（決策變量）：?jiǎn)栴}中要確定的未知量，用以明確規(guī)劃中的用數(shù)量表示方案，措施，可有決策者制定和控制目標(biāo)函數(shù)：決策變量的函數(shù)，按優(yōu)化目標(biāo)分別為max和min約束條件：決策變量收到各種資源條件的限制，通常為等式和不等式。線性規(guī)劃的一般模型假定線性規(guī)劃問(wèn)題中含有n個(gè)變量，分別用xj（j=1,...,n）表示，在目標(biāo)函數(shù)當(dāng)中xj的系數(shù)為cj（價(jià)值系數(shù)），xj的取值受到m項(xiàng)資源的限制，用bi（I=1,...,m）表示第i中資源的數(shù)量，ai,j為技術(shù)系數(shù)或工藝系數(shù)。則上述線性問(wèn)題的數(shù)學(xué)模型可以表示為：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ī)劃問(wèn)題的標(biāo)準(zhǔn)形式對(duì)于非標(biāo)準(zhǔn)形式，我們可以通過(guò)一下的形式進(jìn)行標(biāo)準(zhǔn)化：(1)(2)圖1(3)約束條件(4)無(wú)約束條件x沒(méi)有約束，可以轉(zhuǎn)化為x＝x1－x2(5)對(duì)于x≤0的情況x`=-x圖解法了解圖解法的一些基本概念會(huì)用圖解法求解簡(jiǎn)單題目了解圖解法解的情況對(duì)模型中只含2個(gè)變量的線性規(guī)劃問(wèn)題，可以通過(guò)在平面上作圖的方法求解。一個(gè)線性規(guī)劃問(wèn)題有解，是指能找出一組xj(j＝1,...,n)，滿足約束條件，稱這組xj為問(wèn)題的可行解。通常線性規(guī)劃問(wèn)題總是含有多個(gè)可行解，稱全部可行解的集合為可行域．可行域中使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為最優(yōu)解。對(duì)不存在可行解的線性規(guī)劃問(wèn)題，稱該問(wèn)題無(wú)解。圖解法求解的目：一、判別線性規(guī)劃問(wèn)題的求解結(jié)果，二、在存在最優(yōu)解的條件下，把問(wèn)題的最優(yōu)解找出來(lái)。理論上講，圖解法是不存在變量限制的，但是在實(shí)際情況中，我們最多能描述的是空間模型，所以圖解法要求變量的個(gè)數(shù)≤3，一般是兩個(gè)變量?？尚杏颍ㄔ搮^(qū)域中的任何一個(gè)解即為可行解）最優(yōu)解區(qū)域（該區(qū)域中的任何一個(gè)解，都是最優(yōu)解）最優(yōu)解，也是可行解線性規(guī)劃的圖解（步驟）例3：max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x2圖解法的步驟（1）以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸畫出直角平面坐標(biāo)系，并適當(dāng)選取單位坐標(biāo)長(zhǎng)度。（2）圖示約束條件，找出可行域（根據(jù)約束條件）。（3）圖示目標(biāo)函數(shù)，由于目標(biāo)函數(shù)值逐漸增大，這樣得到一組平行的直線。（4）最后解的確定，找到使得目標(biāo)函數(shù)值最大的點(diǎn)或者是點(diǎn)集。線性規(guī)劃問(wèn)題求解的幾種情況惟一解圖解線性規(guī)劃問(wèn)題求解的幾種情況無(wú)窮解圖解平行目標(biāo)函數(shù)同某一約束條件平行圖解無(wú)界解，缺少約束條件無(wú)界解線性規(guī)劃問(wèn)題求解的幾種情況無(wú)解無(wú)解，沒(méi)有可行解區(qū)域線性規(guī)劃問(wèn)題求解的幾種情況由圖解法得到的啟示

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

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

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