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

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

2、才能使企業(yè)獲利最大?設(shè) 備 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%的硫酸出售， 每噸的價(jià)格分別為400、700、1400、1900和2500元。 問：采用怎樣的方案，才能使所需總費(fèi)用最小？1.1.3 簡單線性模型的建立步驟：（1） 分析問題：（2） 具體構(gòu)造模型：2.線性模型的一般要求（1）變量：（2）

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

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

5、利0 4元。這種投資最多不得超過10,000元。假定在這三年為一期的投資中，每期的開始有30,000元資金可供使用，問：采取怎樣的投資計(jì)劃，才能在第三年年底獲得最大 ？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表示目標(biāo)函數(shù)系數(shù)aij表示約束條件系數(shù)bi表示約束右端項(xiàng)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模型標(biāo)準(zhǔn)化：obj.Min z=2x1- x2+3x3 st.x1+2 x2+4x3 £ 63x1- 2x2+ x3 = 42x1- x2 - 3x3 ³5 x1 ³ 0, x3 £ 0LP的標(biāo)準(zhǔn)化：（1）變量：（2） 目標(biāo)函數(shù)：（3） 約束方程：；（4） 約束右端項(xiàng)：4. 線性模型的標(biāo)準(zhǔn)形式（1）變量

7、：（2） 目標(biāo)函數(shù)：（3） 約束條件：（4） 約束右端項(xiàng)： 非標(biāo)準(zhǔn)形式情況有變量：目標(biāo)函數(shù)：約束條件約束右端項(xiàng)：7各解之間的關(guān)系：最優(yōu)解（如果存在）解集·可行解基解不可行解基可行解（4）基：（5） 基變量：（6） 非基變量：（7） 基本解（基解）：（8） 基本可行解（基可行解）：（9） 可行基：1.1.4線性問題解的有關(guān)概念設(shè)模型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 單純形法計(jì)算：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 單純形法的計(jì)算及程序求解例： 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 兩個(gè)概念：（1）凸集：對于集合C中任意兩點(diǎn)連線上的點(diǎn)，若也在C內(nèi)， 則稱C為凸集。（2）頂點(diǎn)：凸集中不成為任意兩點(diǎn)連線上的點(diǎn)，稱為凸集頂點(diǎn)。1.3.2 三個(gè)基本定理：定理一：若線性LP模型存在可行解，則可行域?yàn)橥辜?。定理二：LP模型的基本可