運(yùn)籌學(xué)第一講

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

(OperationsResearch)

鄒江

413625505@管理學(xué)核心課程教材、參考書及刊物選用教材《運(yùn)籌學(xué)》運(yùn)籌學(xué)教材編寫組清華大學(xué)出版社參考教材《運(yùn)籌學(xué)教程》胡運(yùn)權(quán)主編第四版

清華大學(xué)出版社刊物

《Managementscience》《Interfaces》《EuropeanJournalofOperationsResearch》《運(yùn)籌與管理》本課程授課方式與考核學(xué)科總成績(jī)平時(shí)成績(jī)（30％）課堂考勤（100％）點(diǎn)名5次平時(shí)作業(yè)（無(wú)）期末成績(jī)（70％）1：講授為主，結(jié)合課堂習(xí)題作業(yè)2：開卷考試緒論（1）運(yùn)籌學(xué)簡(jiǎn)述（2）運(yùn)籌學(xué)的主要分支（3）本課程的特點(diǎn)及學(xué)習(xí)方法（4）運(yùn)籌學(xué)在工商管理、工程管理、物流管理中的應(yīng)用本章主要內(nèi)容：運(yùn)籌學(xué)簡(jiǎn)述一:運(yùn)籌學(xué)的概念

目前并沒(méi)有一個(gè)統(tǒng)一的概念。1：譯為“運(yùn)作研究”。運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法來(lái)決定如何最佳地運(yùn)營(yíng)和設(shè)計(jì)各種系統(tǒng)的一門學(xué)科。2：在美國(guó)有人把運(yùn)籌學(xué)稱之為管理科學(xué)(ManagementScience)。3：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故又名最優(yōu)化理論（現(xiàn)代最優(yōu)化理論）。因其有統(tǒng)籌優(yōu)化的含義，借鑒史記“運(yùn)籌于帷幄之中，決勝于千里之外”，我國(guó)取名為運(yùn)籌學(xué)。4：在分析研究問(wèn)題的基礎(chǔ)上，建立數(shù)學(xué)模型描來(lái)述所研究的問(wèn)題，求解并檢驗(yàn)該模型，從而得出最優(yōu)解，用于指導(dǎo)現(xiàn)實(shí)問(wèn)題的決策。（補(bǔ)充）真實(shí)系統(tǒng)系統(tǒng)分析問(wèn)題描述模型建立與修改模型求解與檢驗(yàn)結(jié)果分析與實(shí)施數(shù)據(jù)準(zhǔn)備例：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示，問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

目標(biāo)函數(shù)Maxz=1500x1+2500x2

約束條件s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

運(yùn)籌學(xué)簡(jiǎn)述運(yùn)籌學(xué)的歷史（略）1：運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早—“田忌賽馬”、孫子兵法等都體現(xiàn)了博弈論的思想2：第二次世界大戰(zhàn)期間——美、英等國(guó)家的作戰(zhàn)研究小組解決作戰(zhàn)中所遇到的許多錯(cuò)綜復(fù)雜的戰(zhàn)略、戰(zhàn)術(shù)問(wèn)題而對(duì)運(yùn)籌學(xué)做了進(jìn)一步的研究。3：1947年，丹齊格在研究美國(guó)空軍配置時(shí)，提出了求解線性規(guī)劃問(wèn)題的單純型法（里程碑式的發(fā)現(xiàn)解決了算法的問(wèn)題，使得運(yùn)籌學(xué)得到飛速的發(fā)展）4：康托洛維奇《最佳資源利用的經(jīng)濟(jì)計(jì)算》運(yùn)籌學(xué)的主要分支簡(jiǎn)介規(guī)劃問(wèn)題（線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、多目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等）圖論（橫道圖、雙代號(hào)網(wǎng)絡(luò)圖、最短路、最大流）和工程管理中的進(jìn)度控制結(jié)合尤其緊密庫(kù)存論（econimicorderquantity和newsvendorsproblem）排隊(duì)論（隨機(jī)理論）對(duì)策論（gametheroy）排序與統(tǒng)籌方法決策分析（決策論）本課程的特點(diǎn)及學(xué)習(xí)方法先修課：高等數(shù)學(xué)，概率論與數(shù)理統(tǒng)計(jì)、線性代數(shù)特點(diǎn)：應(yīng)用數(shù)學(xué)、交叉科學(xué)系統(tǒng)整體優(yōu)化模型方法的應(yīng)用，以定量研究為主，定性研究為輔（運(yùn)籌學(xué)、博弈論、計(jì)量經(jīng)濟(jì)學(xué)）學(xué)習(xí)方法建議：

數(shù)學(xué)建模能力的培養(yǎng)+模型求解能力的訓(xùn)練運(yùn)籌學(xué)的應(yīng)用運(yùn)籌學(xué)在工商管理、工程管理、物流管理中的應(yīng)用涉及幾個(gè)方面：生產(chǎn)計(jì)劃安排運(yùn)輸問(wèn)題人事管理庫(kù)存管理市場(chǎng)營(yíng)銷財(cái)務(wù)和會(huì)計(jì)其他，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項(xiàng)目的選擇與評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)等。Interface上發(fā)表的部分獲獎(jiǎng)項(xiàng)目組織應(yīng)用效果聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排每年節(jié)約成本600萬(wàn)美元Citgo石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營(yíng)銷每年節(jié)約成本7000萬(wàn)AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本4.06億美元，銷售額大幅增加標(biāo)準(zhǔn)品牌公司控制成本庫(kù)存（制定最優(yōu)再定購(gòu)點(diǎn)和定購(gòu)量確保安全庫(kù)存）每年節(jié)約成本380萬(wàn)美元法國(guó)國(guó)家鐵路公司制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量每年節(jié)約成本1500萬(wàn)美元，年收入大幅增加。TacoBell優(yōu)化員工安排，以最低成本服務(wù)客戶每年節(jié)約成本1300萬(wàn)美元Delta航空公司優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來(lái)實(shí)現(xiàn)利潤(rùn)最大化每年節(jié)約成本1億美元運(yùn)籌學(xué)在工商管理中的運(yùn)用——生產(chǎn)計(jì)劃安排優(yōu)化例：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤(rùn)（元/件）15002500

問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)前面分析，可以建立如下的線性規(guī)劃模型：

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65

2x1+x2

≤40

3x2

≤75

x1,x2

≥0

運(yùn)籌學(xué)在物流管理中的運(yùn)用——運(yùn)輸問(wèn)題例：某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？解：設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表

Minf=6x11+4x12+6x13+6x21+5x22+5x23

s.t.

x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1,2；j=1,2,3）運(yùn)籌學(xué)在物流管理中的運(yùn)用——報(bào)童模型經(jīng)典報(bào)童模型是描述零售商的兩難決策行為的模型。零售商所面臨的是隨機(jī)需求，當(dāng)零售商訂購(gòu)量大于顧客的需求時(shí)，會(huì)剩余一部分產(chǎn)品。這部分剩余的產(chǎn)品會(huì)帶來(lái)相應(yīng)的管理費(fèi)用以及還具有一定的殘值，而當(dāng)零售商訂購(gòu)量小于顧客需求量時(shí)，會(huì)由于訂貨量不足而產(chǎn)生缺貨損失x----零售商所面臨的隨機(jī)需求；f(x)----隨機(jī)需求的概率密度函數(shù)；F(X)----隨機(jī)需求的累積分布函數(shù)；P----產(chǎn)品單位銷售價(jià)格；W----產(chǎn)品單位購(gòu)買價(jià)格；V----產(chǎn)品殘值；S----產(chǎn)品缺貨損失；q----訂貨量；Cs----供應(yīng)商產(chǎn)品生產(chǎn)成本。零售商利潤(rùn)函數(shù)為：零售商期望利潤(rùn)函數(shù)為線性規(guī)劃在工程管理中的應(yīng)用

下料問(wèn)題例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取2.5米長(zhǎng)的毛坯100根，長(zhǎng)1.3米的毛坯200根。問(wèn)如何才能既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出4種下料方案以裁用ⅠⅡⅢⅣ2.5m32101.3m0246料頭0.2設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數(shù)分別為xj

(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：例某辦公樓工程，建筑面積5500m２，框架結(jié)構(gòu)，獨(dú)立柱基礎(chǔ)，上設(shè)承臺(tái)梁，獨(dú)立柱基礎(chǔ)埋深為1.5m，地質(zhì)勘察報(bào)告中地基基礎(chǔ)持力層為中砂層，基礎(chǔ)施工鋼材由建設(shè)單位供應(yīng)。基礎(chǔ)工程施工分為兩個(gè)施工流水段，組織流水施工，根據(jù)工期要求編制了工程基礎(chǔ)項(xiàng)目的施工進(jìn)度計(jì)劃，并繪出施工雙代號(hào)網(wǎng)絡(luò)計(jì)劃圖，如下圖所示：在工程施工中發(fā)生如下