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

運(yùn)籌學(xué)

.舉例例（線材合理下料問題）某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？例（機(jī)器負(fù)荷分配問題）某種機(jī)器可以在高、低兩種負(fù)荷下進(jìn)行生產(chǎn)。高負(fù)荷年產(chǎn)量8，年完好率0.7；低負(fù)荷年產(chǎn)量5，年完好率0.9。現(xiàn)有完好機(jī)器1000臺，需制定一個(gè)5年計(jì)劃，以決定每年安排多少臺機(jī)器投入高、低負(fù)荷生產(chǎn)，使5年的總產(chǎn)量最大。.消防站選址問題

某城市的消防總部將全市劃分為11個(gè)防火區(qū)，設(shè)有4個(gè)消防救火站。下圖①~④表示消防站，1~11表示防火區(qū)域，圖中連線表示各地區(qū)由哪個(gè)消防站負(fù)責(zé)。問題：可否減少消防站的數(shù)目，仍能同樣負(fù)責(zé)各地區(qū)的防火任務(wù)？如果可以，應(yīng)關(guān)閉哪個(gè)消防站？12345678910111234.緒論產(chǎn)生于二戰(zhàn)時(shí)期，運(yùn)籌學(xué)（OperationalResearch)直譯為“運(yùn)作研究”。

20世紀(jì)60年代，在工業(yè)、農(nóng)業(yè)、社會(huì)等各領(lǐng)域得到廣泛應(yīng)用在我國，20世紀(jì)50年代中期由錢學(xué)森等引入

運(yùn)用數(shù)學(xué)方法，為決策者進(jìn)行最優(yōu)決策提供科學(xué)依據(jù)的一門應(yīng)用科學(xué)。運(yùn)籌學(xué)的特點(diǎn)

面向管理和工程實(shí)際問題應(yīng)用數(shù)學(xué)方法建立數(shù)學(xué)模型一定意義下的優(yōu)化一、運(yùn)籌學(xué)的產(chǎn)生與發(fā)展二、學(xué)科性質(zhì).三、運(yùn)籌學(xué)的分支線性規(guī)劃非線性規(guī)劃圖論與網(wǎng)絡(luò)分析存儲論決策論排隊(duì)論對策論（博弈論）….四、管理運(yùn)籌學(xué)的工作程序明確問題問題分類建立數(shù)學(xué)模型求解數(shù)學(xué)模型結(jié)果分析實(shí)施.五運(yùn)籌學(xué)與決策管理就是決策

從這個(gè)意義上說，運(yùn)籌學(xué)是典型的輔助決策的學(xué)科

決策的基本問題是發(fā)現(xiàn)問題和解決問題發(fā)現(xiàn)問題需要決策者豐富的經(jīng)驗(yàn)、廣博的知識和敏銳的觀察判斷能力以及深入細(xì)致的調(diào)查研究。運(yùn)籌學(xué)可提供某些輔助分析，但主要不針對此問題。解決問題首先要提出方案，方案的創(chuàng)造同樣是決策者才干的體現(xiàn)。

在解決問題中有兩類問題是值得注意的：有些問題的解決方案在既定的準(zhǔn)則下隱含在一系列限制條件中，需要一些方法“找出”這個(gè)方案；有些問題可能提出幾個(gè)（有限個(gè)）方案，需要一些方法評價(jià)和優(yōu)選這些方案；運(yùn)籌學(xué)在以上兩類問題中是很有用的。.課程教材：吳育華,杜綱，管理科學(xué)基礎(chǔ)（修訂版），天津大學(xué)出版社。主要參考書：[1]錢頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，1990；[2]胡運(yùn)權(quán)，運(yùn)籌學(xué)教程，北京：清華大學(xué)出版社，1998；[3]（加）PeterCBell,韓伯棠等譯，管理科學(xué)（運(yùn)籌學(xué)）—戰(zhàn)略角度的審視，機(jī)械工業(yè)出版社，2000；[4]丁以中主編，管理科學(xué)---運(yùn)用Spreadsheet建模和求解，北京：清華大學(xué)出版社，2003；[5][美]弗雷德里克·S·希利爾（FrederickSHillier）,任建標(biāo)譯,數(shù)據(jù)、模型與決策（原書名IntroductiontoManagementScience），北京：中國財(cái)政經(jīng)濟(jì)出版社，2004；.主要授課內(nèi)容：線性規(guī)劃*線性目標(biāo)規(guī)劃圖論與網(wǎng)絡(luò)分析*網(wǎng)絡(luò)計(jì)劃*風(fēng)險(xiǎn)型決策*庫存決策動(dòng)態(tài)規(guī)劃*矩陣對策

排隊(duì)論課程基本要求：掌握好基本概念、主要模型形式及其特點(diǎn)、必要的算法原理及簡單的計(jì)算。所需基礎(chǔ)知識：微積分、矩陣、線性方程組、概率基礎(chǔ)等.班級公共郵箱guanliyunchou@密碼：6個(gè)6.第一章線性規(guī)劃（LinearProgramming，簡稱LP）§1線性規(guī)劃的模型與圖解法一、LP問題及其數(shù)學(xué)模型例1某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。127單價(jià)300103油(C)20054電(B)36049煤(A)資源限制乙甲產(chǎn)品資源....結(jié)構(gòu)約束條件非負(fù)約束條件目標(biāo)函數(shù)資源向量（右端項(xiàng)）.Max（Min）Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

≤（=,≥）b1……am1x1+am2x2+…+amnxn

≤（=,≥）bmx1，x2，…，xn≥0s.t.

LP模型的一般形式.......課堂練習(xí)某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費(fèi)最小的購買方案。（列出模型）ABCD價(jià)格M0300N0.2200每頭日需10587養(yǎng)分飼料.課堂練習(xí)某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的A、B、C、D四種養(yǎng)分。有關(guān)數(shù)據(jù)如下表，現(xiàn)飼料可從市場上出售的M、N兩種飼料中選擇，試決定總花費(fèi)最小的購買方案。（列出模型）ABCD價(jià)格M0300N0.2200每頭日需10587養(yǎng)分飼料答案：設(shè)購買M飼料x1，N飼料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2.二、線性規(guī)劃的圖解法1.步驟（1）作約束的圖形——可行域可行解的集合①先作非負(fù)約束②再作資源約束9x1+4x2=3604x1+5x2=2003x1+10x2=300公共部分，即為可行域例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.x1x240206080100204060801000.（2）作目標(biāo)函數(shù)的等值線①給z不同的值，作相應(yīng)直線，判斷出z增大時(shí)，直線的移動(dòng)方向②將直線向增大方向移動(dòng)，直至可行域邊界，交點(diǎn)X*即為最優(yōu)解。7x1+12x2=847x1+12x2=168如：令7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000X*=（20，24），Z*=428.最優(yōu)解：x1=0，x2=1最優(yōu)目標(biāo)值z=6練習(xí)（自學(xué)）圖解法求解線性規(guī)劃012341234x1x2O-1-2(1)(2)(3).2.LP解的幾種情況（1）唯一解（2）多重最優(yōu)解（3）無可行解注：出現(xiàn)（3）、（4）情況時(shí)，建模有問題（4）無有限最優(yōu)解.圖解法的結(jié)論：線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點(diǎn)獲得若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無窮多最優(yōu)解凸集不是凸集極點(diǎn).三線性規(guī)劃應(yīng)用舉例例1（線材合理下料問題）某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？.2x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1++x3+3x4++2x6+3x7+4x8=100x1,x2,x3,x4,x5,x6,x7,x8≥0設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上述8種方案下料的原材料根數(shù)，建立如下的LP模型：最優(yōu)解為：

x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0minZ=x1+x2+x3+x4+x5+x6+x7+x8s.t.解：共有下列8種下料方案.一、線性規(guī)劃的標(biāo)準(zhǔn)型MaxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

=b1…………am1x1+am2x2+…+amnxn

=bmx1，x2，…，xn≥0s.t.1、標(biāo)準(zhǔn)形式矩陣表示MaxZ=CXAX=bX≥0s.t.注：標(biāo)準(zhǔn)型中要求bi≥0§2單純形法.2、非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型（1）MinZ=CXMaxZ'=-CX（2）約束條件例如：9x1+4x2≤3609x1+4x2+x3=360松弛變量“≤”型約束，加松弛變量；“≥”型約束，減松弛變量；（3）自由變量xj進(jìn)行變量替換：xj=xj'

-xj''，其中xj'

、xj''≥0.例、將如下問題化為標(biāo)準(zhǔn)型解：令、第一個(gè)約束加松弛變量第二個(gè)約束減松弛變量、、得標(biāo)準(zhǔn)型：.二、單純形法的基本方法基本方法：確定初始基可行解檢驗(yàn)是否最優(yōu)？轉(zhuǎn)到另一更好的基可行解停YN方法前提：模型化為標(biāo)準(zhǔn)型..并保證其他的基變量非負(fù)...基變量和非基變量....三、單純形法的步驟1.初始可行基B0的確定若A中含有I：B0=I若A中不含I：人工變量法.2.最優(yōu)性檢驗(yàn)（1）計(jì)算每個(gè)xj的檢驗(yàn)數(shù)（2）若所有σj≤0，則當(dāng)前解為最優(yōu)；否則，至少有σk>0，轉(zhuǎn)3。注:（1）基變量的檢驗(yàn)數(shù)必為0；（2）非基變量σ的經(jīng)濟(jì)含義：非基變量取值由0變正，每增加一個(gè)單位，使目標(biāo)值的增加量。.3.換基迭代（基變換）（1）進(jìn)基：取對應(yīng)的Pk進(jìn)基。（2）出基：取對應(yīng)的Pl出基。得新基，計(jì)算新的基可行解，轉(zhuǎn)2。保證新解的可行性.σ的計(jì)算:XBCBB-1bx1x2x3x4x5θσ四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7.σθx5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:790θ的計(jì)算:4030.σθx5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7904030[]樞紐元素.σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2.σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.230.820100.σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.230.820100[].x3x1x2071224010-0.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]以為主元進(jìn)行初等行變換2.5.x3x1x2071224010-0.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]∴X*=(20,24,84,0,0)TZ*=428.9x1+4x2=3604x1+5x2=2003x1+10x2=300x1x240206080100204060801000(0,0)(40,0)(36.5,10.8)(20,24)(0,30).課堂練習(xí)用單純形法求解MinS=-x1+2x2x1-x2≥

-2x1+2x2≤6x1,x2≥0s.t.化為標(biāo)準(zhǔn)型MaxS′=x1-2x2-x1+x2+x3=

2x1+2x2+x4=

6x1,…,x4≥0s.t.XBCBB-1bx1x2x3x4θx302-1110不考慮x406[1]2016σ1-2x3080311x1161201σ0-40-1∴X*=(6,0,8,0)TZ*=-6..

聯(lián)系用矩陣表示的單純形法原理，單純形表各部分內(nèi)容可如下表示..§3線性規(guī)劃的對偶問題（DualProgramming）一、對偶問題的提出和模型1、問題的提出煤電油例今有另廠要購買三種資源，在原廠可接受的條件下，單價(jià)多少可使另廠付費(fèi)最低？MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.設(shè)煤電油“價(jià)格”分別為y1,y2,y3MinW=360y1+200y2+300y3s.t.9y1+4y2+3y3≥74y1+5y2+10y3≥12y1,y2,y3≥0DUAL以后將特別討論這一“價(jià)格”的含義.2、原問題與對偶問題的對應(yīng)關(guān)系MaxZ=CXAX≤bX≥0s.t.原問題（P）：對偶問題（D）：MinW=bTYATY≥CTY≥0s.t.MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MinW=360y1+200y2+300y3s.t.9y1+4y2+3y3≥74y1+5y2+10y3≥12y1,y2,y3≥0（Y為行向量）

對稱的對偶問題原問題與對偶問題形式上的對應(yīng)關(guān)系原問題（P）對偶問題（D）目標(biāo)max型目標(biāo)min型有n個(gè)變量（非負(fù)）有n個(gè)約束（大于等于）有m個(gè)約束（小于等于）有m個(gè)變量（非負(fù)）價(jià)格系數(shù)資源向量資源向量價(jià)格系數(shù)技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣的轉(zhuǎn)置.1、對稱性二、對偶性質(zhì)與定理2、弱對偶性設(shè)X、Y分別為（P）、（D）的任一可行解，則一個(gè)線性規(guī)劃的對偶問題的對偶問題恰是原問題；即（P）與（D）互為對偶3、無界性若原問題（P）無上界，則對偶問題（D）無可行解；同樣，若對偶問題（D）無下界，則原問題（P）無可行解；

（注意：該命題的逆命題不成立。）.4、解的最優(yōu)性設(shè)

、

分別為（P）與（D）的可行解，且則、分別是原問題（P）和對偶問題（D）的最優(yōu)解。

5、對偶定理（強(qiáng)對偶性）若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且二者最優(yōu)值相等.

由該性質(zhì)的證明中可以得到一個(gè)有用的結(jié)論：

若原問題（P）有最優(yōu)解，設(shè)最優(yōu)基為B，則CBB-1是對偶問題（D）的最優(yōu)解。

6、互補(bǔ)松弛定理

若是原問題（P）的可行解，是對偶問題（D）的可行解，那么和分別是原問題（P）和對偶問題（D）的最優(yōu)解的充要條件是：

.可以看出，在原問題（P）最優(yōu)解單純型表中，松弛變量檢驗(yàn)數(shù)為

它的負(fù)值CBB-1剛好是對偶問題（D）的最優(yōu)解。

對于性質(zhì)5，進(jìn)一步聯(lián)系單純型表的矩陣表示，

.三、對偶問題最優(yōu)解的經(jīng)濟(jì)解釋——影子價(jià)格設(shè)DP其最優(yōu)值為Z*(注：與LP最優(yōu)值同），則根據(jù)Z*=bTy*=b1y1*+b2y2*++bmym*Z/bi=

yi*

簡單推導(dǎo)：Y*=(y1*,y2*,……，ym*）為對偶問題的最優(yōu)解，，則yi*

表示在原問題LP模型最有解基礎(chǔ)上，資源（右端項(xiàng)）bi對目標(biāo)函數(shù)的邊際貢獻(xiàn)。即bi變化1個(gè)單位對目標(biāo)函數(shù)產(chǎn)生的影響，稱yi*為bi的影子價(jià)格（shadowprice)。例如：煤電油例的對偶問題的最優(yōu)解為Y*=(01.360.52),即煤電油三種資源的影子價(jià)格分別為0、1.36、0.52，它表明：在所求出的最優(yōu)生產(chǎn)方案（甲生產(chǎn)20，乙生產(chǎn)24，資源煤剩余84，資源電和油無剩余，總收入428）基礎(chǔ)上，資源煤增加1單位，目標(biāo)函數(shù)值不變；資源電增加1單位，目標(biāo)函數(shù)值相應(yīng)增加1.36；資源油增加1單位，目標(biāo)函數(shù)值相應(yīng)增加0.52。.由原問題所做推導(dǎo)：注意：對偶解（影子價(jià)格）的所有應(yīng)用都是基于這一基本概念。

.影子價(jià)格在管理決策中的作用：（1）影子價(jià)格≠市場價(jià)格在以本章引例為代表的目標(biāo)函數(shù)最大化毛收入這類模型中若影子價(jià)格＞市場價(jià)格，則應(yīng)買進(jìn)該資源影子價(jià)格＜市場價(jià)格，則應(yīng)賣出該資源（2）影子價(jià)格反映了當(dāng)前優(yōu)化模型中資源的稀缺性，影子價(jià)格越高，則越稀缺。例如：煤的影子價(jià)格為0，則表明有剩余；電的影子價(jià)格為1.36，是三種資源中最大的，則表明電是相對重要的。（3）在資源不變條件下，增加新產(chǎn)品是否合算的評價(jià)（見靈敏性分析）.§4線性規(guī)劃的靈敏性分析（sensitivityanalysis）1．右端項(xiàng)b變化的分析（先看后兩頁圖示）

對于線性規(guī)劃在其最優(yōu)解基礎(chǔ)上，設(shè)B為最優(yōu)基，則

由單純形法b的變化直接影響右端項(xiàng)（可行性）而不直接影響檢驗(yàn)數(shù)（最優(yōu)性）

.右端項(xiàng)變化示意1，某個(gè)右端項(xiàng)在一定范圍變化，可能不影響最優(yōu)解7x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=2003x1+10x2=300x1x2402060801002040608010009x1+4x2=320.X*=（20，24），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200x1x2402060801002040608010004x1+5x2=170右端項(xiàng)變化示意2，某個(gè)右端項(xiàng)在一定范圍變化，影響最優(yōu)解,但可能不影響最優(yōu)基。...2．價(jià)格系數(shù)C變化的分析3x1+10x2=300X*=（20，24），Z*=4287x1+12x2=847x1+12x2=1689x1+4x2=3604x1+5x2=200x1x240206080100204060801000目標(biāo)函數(shù)系數(shù)變化示意，目標(biāo)函數(shù)系數(shù)在一定范圍變化，可能不影響最優(yōu)解.....§5（線性）整數(shù)規(guī)劃IntegerProgramming(簡稱IP)一、整數(shù)規(guī)劃的一般模型LP:maxz=CXAX=bX≥0IP:maxz=CXAX=bX≥0X為整數(shù).整數(shù)規(guī)劃的解法：分枝定界法或割平面法基本思想是把一個(gè)整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來求解整數(shù)規(guī)劃的分類：純整數(shù)規(guī)劃：所有變量都限制為整數(shù)混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù)

0-1整數(shù)規(guī)劃：變量的取值僅限于0或1.[例]人力資源分配的問題某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?班次時(shí)間所需人數(shù)16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030.解：設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),于是LP模型為:x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0且為整數(shù)minz=x1+x2+x3+x4+x5+x6

最優(yōu)解：X*=(60，10，50，0，30，0）T，Z*=150.二、0-1整數(shù)規(guī)劃選址問題指派問題固定費(fèi)用問題背包問題.1.投資場所的選址問題

某城市擬在東、西、南三區(qū)設(shè)立商業(yè)網(wǎng)點(diǎn)，備選位置有A1~A7共7個(gè)，如果選Ai，估計(jì)投資為bi元，利潤為ci元，要求總投資不超過B元，規(guī)定東區(qū)：A!、A2、A3中至多選2個(gè)西區(qū)：A4、A5中至少選一個(gè)南區(qū)：A6、A7中至少選一個(gè)問如何設(shè)點(diǎn)使總利潤最大？1，Ai被選中

0，Ai沒被選中解：令xi=maxz=xi=0或1，i=1,…,7∑bixi≤Bi=17x1+x2+x3≤2x4+x5≥1x6+x7≥1s.t..課堂練習(xí)1:

某鉆井隊(duì)要從S1~S10共10個(gè)井位中確定五個(gè)鉆井探油，如果選Si，估計(jì)鉆探費(fèi)用為ci元，并且井位選擇上要滿足下列條件：（1）或選擇S1和S7，或選擇S8;

（2）選擇了S3或S4就不能選擇S5，反過來也一樣;（3）在S5，S6，S7，S8中最多只能選兩個(gè)。問如何選擇井位使總費(fèi)用最?。?課堂練習(xí)1:某鉆井隊(duì)要從S1~S10共10個(gè)井位中確定五個(gè)鉆井探油，如果選Si，估計(jì)鉆探費(fèi)用為ci元，并且井位選擇上要滿足下列條件：（1）或選擇S1和S7，或選擇S8（2）選擇了S3或S4就不能選擇S5，反過來也一樣（3）在S5，S6，S7，S8中最多只能選兩個(gè)問如何選擇井位使總費(fèi)用最小？1，Si被選中

0，Si沒被選中解：令xi=minz=s.t.或1，i=1,…,10.某籃球隊(duì)有8名隊(duì)員，其身高和專長如下表，現(xiàn)要選拔5名球員上場參賽，要求：（1）中鋒只有1人上場（2）后衛(wèi)至少有一人上場（3）只有2號上場，6號才上場要求平均身高最高，應(yīng)如何選拔隊(duì)員？課堂練習(xí)2:.1，隊(duì)員i被選中

0，隊(duì)員i沒被選中解：令xi=maxz=或1，i=1,…,8s.t.某籃球隊(duì)有8名隊(duì)員，其身高和專長如下表，現(xiàn)要選拔5名球員上場參賽，要求：（1）中鋒只有1人上場（2）后衛(wèi)至少有一人上場（3）只有2號上場，6號才上場要求平均身高最高，應(yīng)如何選拔隊(duì)員？.2.指派問題

例：有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作任務(wù)E、J、G、R，現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種說明書所需的時(shí)間如下表所示，問應(yīng)指派何人去完成何項(xiàng)任務(wù)，使所需總時(shí)間最少？問題描述：n項(xiàng)任務(wù)可由n個(gè)人完成，由于專長不同，各人完成各任務(wù)的時(shí)間也不同，求最優(yōu)安排。要求：每人只能完成一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。.x11+x12+x13+x14=1(甲只能干一項(xiàng)工作)

x21+x22+x23+x24=1(乙只能干一項(xiàng)工作)x31+x32+x33+x34=1(丙只能干一項(xiàng)工作)x41+x42+x43+x44=1(丁只能干一項(xiàng)工作)x11+x21+x31+x41=1(E任務(wù)只能一人干)

x12+x22+x32+x42=1(J任務(wù)只能一人干)x13+x23+x33+x43=1(G任務(wù)只能一人干)x14+x24+x34+x44=1(R任務(wù)只能一人干)xij=0或1，i,j=1,2,3,4minz=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24+9x31+14x32+16x33+13x34+7x41+8x42+11x43+9x441，指派第i人去完成第j項(xiàng)任務(wù)

0，不指派第i人去完成第j項(xiàng)任務(wù)解：令

xij=課堂練習(xí):P57例2.23.指派問題可以一般化表述為有n個(gè)人n項(xiàng)工作，已知第i個(gè)人做第j項(xiàng)工作的費(fèi)用為cij，現(xiàn)如何分派任務(wù)，使一個(gè)人只做一項(xiàng)工作，一項(xiàng)工作只由一個(gè)人完成，而且總費(fèi)用最小。以4個(gè)人4項(xiàng)工作的指派問題為例，該問題需用4×4＝16個(gè)0－1變量，即設(shè)

把這些變量和已知費(fèi)用系數(shù)分別排成一4×4矩陣，分別稱為解矩陣和費(fèi)用矩陣，

....3.固定費(fèi)用問題最基本的帶有固定費(fèi)用的費(fèi)用函數(shù)一般表示為：

若引入0－1變量

則帶有固定費(fèi)用的費(fèi)用函數(shù)可表示為：

.固體廢物處理規(guī)劃例（教材P52例2.20）示意圖：...固定費(fèi)用問題另例例、生產(chǎn)三種型號的防寒服，其消耗資源及單件成本如表。此外，每種防寒服不管生產(chǎn)多少，都要支付一定的固定費(fèi)用。型號資源小中大資源限制尼龍綢1500尼龍棉1000勞動(dòng)力44.553500設(shè)備2800單件成本131210固定費(fèi)用120150180今要生產(chǎn)500件防寒服，確定總費(fèi)用最低的生產(chǎn)方式。.一般描述：已知：生產(chǎn)某產(chǎn)品有m種方式，設(shè)第j種生產(chǎn)方式的固定成本為kj，可變成本為cj。問題：應(yīng)選擇哪幾種生產(chǎn)方式、分別生產(chǎn)多少產(chǎn)量可使總成本最低？分析：這是一個(gè)混合0-1規(guī)劃問題：1，選擇第j種方式，即xj>0時(shí)0，不選擇第j種方式，即xj=0時(shí)令yj=設(shè)第j種生產(chǎn)方式的產(chǎn)量為xj于是該問題可表示為：

xj≤M

yj.例、生