下部分2015本科線性規(guī)劃

1、1案例1：偉恩德公司的組合zP26z兩種性能極佳的新y門與木框窗z市場需求與定價調(diào)研z是否安排生產(chǎn)？z各生產(chǎn)多少為最優(yōu)？第二章線性LinearProgramming雷 明OPERATIONS RESEARCH(運籌學/管理科學)光華管理學院雷 明leiming21.1.2線性問題的一般數(shù)學模型1.相關概念（1）決策變量：（2）目標函數(shù)：（3）約束條件： 模型結構的三要素。1.1一般線性問題及數(shù)學模型1 1 1 問題的提出例：某企業(yè)計劃生產(chǎn)甲、乙兩種 ，該兩種 均需經(jīng)A、B、C、D四種不同設備上 ，按工藝資料規(guī)定，在各種不同設備上的 時間及設備 能力、 利潤如表中所示。問:如何安排 的生產(chǎn)計劃,

2、才能使企業(yè)獲利最大?設 備 ABCD利潤甲乙2212400423能力1281612生產(chǎn)條件生產(chǎn)能力、所需、利潤：4hr/wk12hr/wk18hr/wk工廠1工廠2工廠31hr3hr2hr2hr門窗利潤：300/unit利潤：500/unit3例1：某工廠在生產(chǎn)過程中需要使用濃度為80%的硫酸100 噸，而市面上只有濃度為30%，45%，73%，85%，92%的硫酸出售， 每噸的價格分別為400、700、1400、1900和2500元。 問：采用怎樣的方案，才能使所需總費用最?。?.1.3 簡單線性模型的建立步驟：（1） 分析問題：（2） 具體構造模型：2.線性模型的一般要求（1）變量：（2）

3、目標函數(shù)：（3）約束條件：4例4：有A、B兩種，都需要經(jīng)過前、后兩到化學反應過程。每種產(chǎn)品需要的反應時間及其可供使用的總時間如表示。每生產(chǎn)一個B的同時，會產(chǎn)生2個的副C，且不需外加任何費用。副C的一部分可以出售，其余的只能加以銷毀。副C每賣出一個可獲利3元，但是如果賣不出去，則每需銷毀費用2元。表明，最多可售出5個的副C。要求確定使利潤最大的生產(chǎn)計劃。過程AB可利用時間前道過程后道過程23341624利潤410例3：一家晝夜服務的飯店，24小時中需要的服務員數(shù)如下表所示。每個服務員每天連續(xù)工作8小時，且在時段開始時上班。問： 最少需要多少名服務員？試建立該問題的線性模型。起迄時 間服務員 人

4、數(shù)2- - - - 6 時6- - - 10 時10 - - 1 4 時14 - - 1 8 時18 - - 2 2 時22 - - - 2 時4810 712 4例2：設有下面四個投資機會：甲：在三年內(nèi)，投資人應在每年年初投資，每年每元投資可獲利0 2元，每年取息后可重新將本息用于投資。乙：在三年內(nèi)，投資人應在第一年年初投資，每兩年每元投資可獲利0 5元，兩年后取息，取息后可重新將本息用于投資。這種投資最多不得超過20,000元。丙：在三年內(nèi)，投資人應在第二年年初投資，兩年后每元投資可獲利0 6元。這種投資最多不得超過15,000元。?。涸谌陜?nèi)，投資人應在第三年年初投資，一年后每元投資可獲

5、利0 4元。這種投資最多不得超過10,000元。假定在這三年為一期的投資中，每期的開始有30,000元資金可供使用，問：采取怎樣的投資計劃，才能在第三年年底獲得最大 ？5（3） 矩陣: max z=CXs.t. AXbX0n（4） 向量: max z=åcjxjj=1ns.t å pjxjb （i=1,2,m）j=1xj0（j=1,2,n)n(2) 和式： max z=å cjxjj=1ns.t.å aijxjbi （i=1,2,m)j=1xj 0（j=1,2,n)其中：cj表示目標函數(shù)系數(shù)aij表示約束條件系數(shù)bi表示約束右端項3 .線性問題的一般表示

6、方法（1）一般式：max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1 ,x2, ,xn0s.t.-subject to6例：將下述LP模型標準化：obj.Min z=2x1- x2+3x3 st.x1+2 x2+4x3 £ 63x1- 2x2+ x3 = 42x1- x2 - 3x3 ³5 x1 ³ 0, x3 £ 0LP的標準化：（1）變量：（2） 目標函數(shù)：（3） 約束方程：；（4） 約束右端項：4. 線性模型的標準形式（1）變量

7、：（2） 目標函數(shù)：（3） 約束條件：（4） 約束右端項： 非標準形式情況有變量：目標函數(shù)：約束條件約束右端項：7各解之間的關系：最優(yōu)解（如果存在）解集·可行解基解不可行解基可行解（4）基：（5） 基變量：（6） 非基變量：（7） 基本解（基解）：（8） 基本可行解（基可行解）：（9） 可行基：1.1.4線性問題解的有關概念設模型nmax z=åcjxjj 1ns t åaijxj=bi （i=1,2,m)j 1xj0（j=1,2,n)（1） 可行解：（2） 可行域：（3） 最優(yōu)解：8唯一解無窮多解AA=B解無可行解x2642(4,2)zmax02468x1Z=6

8、Z=01.2 線性問題的圖解方法* 利用作圖方法求解。例：max z=2x1+3x2s.t 2x1+2x2£12x1+2x2£ 84x1£164x2 £12x1³0, x2³091.4.2 單純形法計算：Cj 2300iCB XB bx1x2x3x40 x330 x44111012013/1=34/2= 2cj - zj23000 x313 x221/201-1/21/2101/224cj - zj1/200-3/22 x123 x21102-101-11cj - zj00-1-11.4 單純形法的計算及程序求解例： max z=2x1+3x2s t x1+x2+x3=3x1+2x2+x4=4 xj³0, (j=1,2,3,4)1.3 單純形法的基本原理（Simplex Method）1.3.1 兩個概念：（1）凸集：對于集合C中任意兩點連線上的點，若也在C內(nèi)， 則稱C為凸集。（2）頂點：凸集中不成為任意兩點連線上的點，稱為凸集頂點。1.3.2 三個基本定理：定理一：若線性LP模型存在可行解，則可行域為凸集。定理二：LP模型的基本可