二章線性基本概念

1Data,ModelandDecisions數(shù)據(jù)、模型與決策Session2-1LinearProgramming:BasicConcepts線性規(guī)劃：基本概念2SessionTopicsAnClassWorkingExample一個(gè)課堂操作舉例

BasicConceptsofLinearProgramming線性規(guī)劃的基本概念TheGraphicalMethodforSolvingLP

線性規(guī)劃的圖解法

UsingExcelSolvertoSolving

用微軟ExcelSolver求解

KeyCategoriesofLPProblems

線性規(guī)劃問題的主要類型ThreeClassicApplicationsofLP

三個(gè)經(jīng)典的線性規(guī)劃應(yīng)用3TheLegoProductionProblem

拼裝玩具生產(chǎn)(1/3)你怎么去分析呢？想想看！每個(gè)小組都有一組拼裝玩具(8個(gè)小塊和6大塊)，這些是你們的原材料（rawmaterials），你們要用這些原材料去生產(chǎn)桌和椅（tablesandchairs）這兩種產(chǎn)品（products），具體拼裝圖如下一個(gè)幻燈片。自己動手4TheLegoProductionProblem

拼裝玩具生產(chǎn)(2/3)原材料6大塊8小塊產(chǎn)品

桌

椅Profit=$20/Table Profit=$15/Chair5TheLegoProductionProblem

拼裝玩具生產(chǎn)(3/3)為了最小化成本或最大化利潤的目的需要對一些稀缺資源進(jìn)行配置你的答案是什么？6MathematicalStatementofLP

Problem

線性規(guī)劃的數(shù)學(xué)描述線性規(guī)劃要確定決策變量x1,x2,…,xn

使得已知參數(shù)

c1,…,cn;a11,…,amn;b1,…,bm.7ComponentsoftheModel

模型的組成部分Decisionvariables決策變量Objectivefunction目標(biāo)函數(shù)Constraints約束8AssumptionsofLinearProgramming

線性規(guī)劃的假設(shè)Linearity線性Divisibility可分性Certainty確定性Non-negativity非負(fù)性9WhyUseLinearProgramming?

為什么要使用線性規(guī)劃線性規(guī)劃很容易而有效率地被求解如果存在最優(yōu)解，則肯定能夠找到功能強(qiáng)大的敏感性分析（sensitivityanalysis）許多實(shí)際問題是線性的10StepsinFormulatingLPProblem

線性規(guī)劃問題建模步驟

需要做哪些決策？決策變量是什么問題的目標(biāo)是什么？寫出目標(biāo)函數(shù)資源和需求之間的情況如何？確定約束條件11TheGraphicalMethodforSolvingLP

線性規(guī)劃的圖解法12TheSimpleMethodforSolvingLP

線性規(guī)劃的單純形法13UsingExcelSolvertoSolving

用微軟Excel的規(guī)劃求解來解決14SolvingLegoProblem

求解玩具拼裝問題

用易理解方式輸入數(shù)據(jù)和構(gòu)筑數(shù)據(jù)之間的聯(lián)系定義目標(biāo)單元格（目標(biāo)函數(shù)）確定可變單元（決策變量）添加約束變量（AddingConstraints）15TheSolution

求解結(jié)果16KeyCategoriesofLPProblems

線性規(guī)劃問題主要類型

資源分配問題（resource-allocation）成本收益平衡問題（cost-benefit-trade-off）網(wǎng)絡(luò)配送問題（distribution-network）混合問題（mixedProblem）17ModelingfromManagerialPerspective

管理視角的建模總績效測度必須是管理層想獲得的現(xiàn)實(shí)目標(biāo)準(zhǔn)確細(xì)致地描述資源約束管理科學(xué)小組與管理層的有效溝通模型往往要不斷地修改和擴(kuò)展要進(jìn)行what-if分析18ThreeClassicalApplicationsofLP

線性規(guī)劃問題的三個(gè)經(jīng)典應(yīng)用潘得羅索工業(yè)公司的產(chǎn)品組合考慮有限資源，確定產(chǎn)品的最佳組合公司的總利潤增加了20%.聯(lián)合航空公司的員工排程為最有效率地滿足服務(wù)要求為所有地雇員設(shè)計(jì)工作日程安排.每年節(jié)約$6,000,000.Citgo石油公司供應(yīng)、配送與營銷規(guī)劃SDM系統(tǒng)使用線性規(guī)劃協(xié)調(diào)全美的Citgo的主要產(chǎn)品的供應(yīng)，配送和營銷.庫存減少導(dǎo)致Citgo公司每年利潤增加$14,000,000.19PonderosaIndustrial

潘德羅索工業(yè)公司潘德羅索應(yīng)用成功的因素：以自然語言為用戶界面的財(cái)務(wù)計(jì)劃系統(tǒng)，使用自然語言而不是數(shù)學(xué)符號來顯示線性規(guī)劃模型各個(gè)組成部分以及輸出的結(jié)果，使得做決策的管理者能夠很容易看懂整個(gè)過程。最優(yōu)化系統(tǒng)是互動的（interactive），管理者在從一個(gè)版本的模型中獲得一組最優(yōu)解之后，可以提出一系列的what-if問題，并能立即得到回應(yīng)。

公司經(jīng)驗(yàn)20PersonnelSchedulingatUA.

聯(lián)合航空公司人員排程聯(lián)合航空公司利用線性規(guī)劃，來為其在主要的機(jī)場和定票點(diǎn)的上萬個(gè)工作人員安排每周的工作時(shí)間表。目標(biāo)是為了能夠在滿足客戶的服務(wù)需要的同時(shí)，將一周內(nèi)每天每半個(gè)小時(shí)的人員成本最小化。聯(lián)合航空公司一些地點(diǎn)的規(guī)劃模型包括20，000個(gè)決策變量。應(yīng)用成功最主要的因素是因?yàn)榈玫搅诉\(yùn)營經(jīng)理以及其它員工的大力支持。公司經(jīng)驗(yàn)21CitgoPetroleumCorporation

Citgo石油集團(tuán)公司經(jīng)驗(yàn)Citgo石油集團(tuán)運(yùn)用管理科學(xué)的技術(shù)，特別是線性規(guī)劃，建立供應(yīng)、配送與營銷的建模系統(tǒng)將公司主要產(chǎn)品的供應(yīng)、配送與營銷通過公司龐大的銷售與配送網(wǎng)絡(luò)得到很好的協(xié)調(diào)。在90年代中期創(chuàng)造了大量的財(cái)富。公司每種主要產(chǎn)品的模型都含有大約1，500個(gè)決策量以及3