吉林大學(xué)遠(yuǎn)程教育 運(yùn)籌學(xué) 李時(shí) 1.1課件

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

講授教師：李時(shí)會計(jì)學(xué)專業(yè)課程簡介

運(yùn)籌學(xué)是高等學(xué)校經(jīng)濟(jì)管理類專業(yè)本科生所必修的一門專業(yè)基礎(chǔ)課；是分析和解決經(jīng)營管理領(lǐng)域最優(yōu)化問題的一門方法論學(xué)科；是每個(gè)有志于從事現(xiàn)代經(jīng)營管理工作的同志所應(yīng)該掌握的重要數(shù)量分析工具。課程簡介

何謂“運(yùn)籌學(xué)”？它的英文名稱是OperationsResearch,直譯為“作業(yè)研究”，就是研究在經(jīng)營管理活動中如何行動，如何以盡可能小的代價(jià)，獲取盡可能好的結(jié)果，即所謂“最優(yōu)化”問題。漢語是世界上最豐富的語言，中國學(xué)者把這門學(xué)科意譯為“運(yùn)籌學(xué)”，就是取自古語“運(yùn)籌于帷幄之中，決勝于千里之外”，其意為運(yùn)算籌劃，出謀獻(xiàn)策，以最佳策略取勝。這就極為恰當(dāng)?shù)馗爬诉@門學(xué)科的精髓。課程簡介

運(yùn)籌學(xué)發(fā)展到現(xiàn)在，雖然只有五十多年的歷史，但其內(nèi)容已相當(dāng)豐富，所涉及的領(lǐng)域也十分廣泛。以《運(yùn)籌學(xué)國際文摘》收集的各國運(yùn)籌學(xué)論文的內(nèi)容為例，按技術(shù)分類就有50多種。現(xiàn)在這門新興學(xué)科的應(yīng)用已深入到國民經(jīng)濟(jì)的各個(gè)領(lǐng)域，成為促進(jìn)國民經(jīng)濟(jì)多快好省，健康協(xié)調(diào)發(fā)展的有效方法。課程簡介

我們講授這門課程的目的就是要使同學(xué)們系統(tǒng)地了解運(yùn)籌學(xué)的基本概念、基本原理、研究方法及其應(yīng)用，掌握運(yùn)籌學(xué)整體優(yōu)化的思想和定量分析的優(yōu)化技術(shù)，并能正確應(yīng)用各類模型分析和解決實(shí)際問題。這門課程共講授48學(xué)時(shí)，根據(jù)這些學(xué)時(shí)，我們安排了如下一些內(nèi)容：第一章：線性規(guī)劃與單純形法（8學(xué)時(shí)）第二章：線性規(guī)劃的對偶理論與靈敏度分析（7學(xué)時(shí)）課程簡介

第三章：運(yùn)輸問題（4學(xué)時(shí)）第四章：整數(shù)規(guī)劃（4學(xué)時(shí)）第五章：動態(tài)規(guī)劃（3學(xué)時(shí)）第六章：動態(tài)規(guī)劃應(yīng)用舉例（7學(xué)時(shí)）第七章：圖與網(wǎng)絡(luò)分析（7學(xué)時(shí)）第八章：排隊(duì)論（8學(xué)時(shí)）第一章線性規(guī)劃與

單純形法

第一章線性規(guī)劃與單純形法線性規(guī)劃是運(yùn)籌學(xué)最重要的分支。自1947年美國人丹捷格提出求解線性規(guī)劃的單純形法以來，它在理論上已趨向成熟，實(shí)際上的應(yīng)用日益廣泛與深入，現(xiàn)在幾乎各行各業(yè)都可以建立線性規(guī)劃模型。比如制定企業(yè)最佳經(jīng)營計(jì)劃、確定產(chǎn)品最優(yōu)配料比、尋找材料的最優(yōu)下料方案、研究各種資源的最優(yōu)分配方案等等。由于線性規(guī)劃模型具有應(yīng)用的廣泛性，更主要由于它的算法易于在計(jì)算機(jī)上實(shí)現(xiàn)，實(shí)際上，EXCEL的“規(guī)劃求解”即可以用來求解一般的線性規(guī)劃問題。所以，線性規(guī)劃已成為現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。線性規(guī)劃數(shù)學(xué)模型

建立該問題的數(shù)學(xué)模型設(shè)x1,x2分別表示計(jì)劃期內(nèi)產(chǎn)品Ⅰ，Ⅱ的產(chǎn)量。因?yàn)橛?jì)劃期內(nèi)生產(chǎn)用的原料和工時(shí)都是有限的，所以在確定產(chǎn)品Ⅰ，Ⅱ的產(chǎn)量時(shí)要滿足下面約束條件：

2x1+3x2≤100

4x1+2x2≤120

x1,x2≥0一般滿足上述約束方程組的解不是唯一的，根據(jù)題意我們需要的是既滿足約束條件，又使得所獲利潤最大的方案。線性規(guī)劃數(shù)學(xué)模型例2某晝夜服務(wù)的公交線路每天各時(shí)間區(qū)段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：班次

時(shí)間

所需人數(shù)16：00—10：0060210：00—14：0070314：00—18：0060418：00—22：0020522：00—2：002062：00—6：0030線性規(guī)劃數(shù)學(xué)模型目標(biāo)函數(shù)：minZ=x1+x2+x3+x4+x5+x6

約束條件：x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥20

x4+x5≥20

x5+x6≥30

x1,x2,…,x6≥0線性規(guī)劃數(shù)學(xué)模型上面兩例優(yōu)化模型，都具有下述特征：

(1)每個(gè)問題都用一組未知變量x1,…,xn表示所求方案，通常這些變量都是非負(fù)的，稱為決策變量。

(2)存在一組約束條件，這些約束條件都可以用一組線性等式或不等式表示。

(3)都有一個(gè)要求的目標(biāo)，并且這個(gè)目標(biāo)可表示為一組決策變量的線性函數(shù)，稱為目標(biāo)函數(shù)。目標(biāo)函數(shù)可以是求最大，也可以是求最小。

具有上述特征的數(shù)學(xué)模型就稱為線性規(guī)劃模型。線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型的一般形式如下：目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+‥‥+cnxn約束條件:

a11x1+a12x2+‥‥+a1nxn≤（≥，＝）b1

a21x1+a22x2+‥‥+a2nxn≤（≥，＝）b2

……

am1x1+am2x2+‥‥+amnxn≤（≥，＝）bm

x1,x2,‥‥,xn≥0

2圖解法1.2圖解法如何求解線性規(guī)劃模型是本章討論的中心問題。首先介紹只有兩個(gè)決策變量的線性規(guī)劃的圖解法，該方法能夠?qū)€性規(guī)劃的解法從幾何直觀上給我們以啟迪。對于兩個(gè)決策變量的每一組取值，都可以看作平面直角坐標(biāo)系中一個(gè)點(diǎn)的坐標(biāo)，因此，我們可以把滿足約束條件的點(diǎn)在平面直角坐標(biāo)系中表示出來。以例1的模型為例，約束條件2x1+3x2≤100，4x1+2x2≤120都代表由一條直線劃定的半個(gè)平面，考慮到x1,x2≥0，所以，滿足所有約束條件的點(diǎn)應(yīng)為坐落在第一象限的區(qū)域OQ1Q2Q3（如圖），該區(qū)域稱為可行域。圖1-1

圖1-1OX26050403020101020304050x14x1+2x2=120

2x1+3x2=100Q3Q2Q1結(jié)論從圖解法可以看出一般情況下（1）具有兩個(gè)變量的線性規(guī)劃問題的可行域是凸多