期末復(fù)習(xí)考試及評分標(biāo)準(zhǔn)考試成績＝60分平時＝40分內(nèi)容概要第2章線性規(guī)劃的圖解法

2.圖解法的靈敏度分析1.圖解法例1.某工廠在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2

約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0例1.目標(biāo)函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標(biāo)值z=27500§2圖解法

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例1詳細(xì)講解其方法：取各約束條件的公共部分，如圖2-1所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1§2圖解法x1x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2CBADE內(nèi)容概要第2章線性規(guī)劃的圖解法

2.圖解法的靈敏度分析1.圖解法圖解法的靈敏度分析Ci假設(shè)產(chǎn)品Ⅱ的利潤100元不變，即c2=100，代到式（*）并整理得

0c1

100假設(shè)產(chǎn)品Ⅰ的利潤50元不變，即c1=50，代到式（*）并整理得

50c2

+假若產(chǎn)品Ⅰ、Ⅱ的利潤均改變，則可直接用式（*）來判斷。假設(shè)產(chǎn)品Ⅰ、Ⅱ的利潤分別為60元、55元，則

-2-(60/55)

-1

那么，最優(yōu)解為

z=x1+x2

和

z=2x1+x2

的交點(diǎn)x1=100，x2=200。

當(dāng)約束條件右邊系數(shù)bj變化時，其線性規(guī)劃的可行域也將變化，這樣就可能引起最優(yōu)解的變化。為了說明這方面的靈敏度分析，不妨假設(shè)例1中的設(shè)備臺時數(shù)增加了10個臺時，共有臺時數(shù)310個，這樣例1中的設(shè)備臺時數(shù)的約束條件就變?yōu)椋?/p>

x1+x2≤310,

增加了10個臺時，擴(kuò)大了可行域。二、約束條件中右邊系數(shù)bj的靈敏度分析第三章線性規(guī)劃問題的計算機(jī)求解§1“管理運(yùn)籌學(xué)”軟件的操作方法§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析例1.目標(biāo)函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)§1

“管理運(yùn)籌學(xué)”軟件的操作方法1.軟件使用演示：（演示例1）第一步：點(diǎn)擊“開始”->“程序”->“管理運(yùn)籌學(xué)2.5”，彈出主窗口。§1

“管理運(yùn)籌學(xué)”軟件的操作方法第四步：點(diǎn)擊“解決”按鈕，得出計算結(jié)果。本題的運(yùn)行結(jié)果界面如下。§2

“管理運(yùn)籌學(xué)”軟件的輸出信息分析第五步：分析運(yùn)行結(jié)果。本題中目標(biāo)函數(shù)的最優(yōu)值是27500，x1=50,x2=250。相差值表示相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量，使得決策變量為正值，當(dāng)決策變量已為正數(shù)時，相差數(shù)為零。松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零，則表示與之相對應(yīng)的資源已經(jīng)全部用上。對偶價格表示其對應(yīng)的資源每增加一個單位，將增加多少個單位的最優(yōu)值。目標(biāo)函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下，目標(biāo)函數(shù)的決策變量系數(shù)的變化范圍。當(dāng)前值是指當(dāng)前的最優(yōu)解中的系數(shù)取值。常數(shù)項范圍是指約束條件的右端常量。上限值和下限值是指當(dāng)約束條件的右端常量在此范圍內(nèi)變化時，與其對應(yīng)的約束條件的對偶價格不變。當(dāng)前值是指現(xiàn)在的取值。

以上計算機(jī)輸出的目標(biāo)函數(shù)系數(shù)和約束條件右邊值的靈敏度分析都是在其他系數(shù)值不變，只有一個系數(shù)變化的基礎(chǔ)上得出的！

2.當(dāng)有多個系數(shù)變化時，需要進(jìn)一步討論。百分之一百法則：對于所有變化的目標(biāo)函數(shù)決策系數(shù)（約束條件右邊常數(shù)值），當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。*允許增加量=上限-現(xiàn)在值

c1的允許增加量為100-50=50

b1的允許增加量為325-300=25*允許減少量=現(xiàn)在值-下限

c2的允許減少量為100-50=50

b3的允許減少量為250-200=50*允許增加的百分比=增加量/允許增加量*允許減少的百分比=減少量/允許減少量第四章線性規(guī)劃在工商管理中的應(yīng)用§1人力資源分配的問題§2生產(chǎn)計劃的問題§3套裁下料問題§4配料問題§5投資問題§1

人力資源分配的問題

例1．某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?§1

人力資源分配的問題

解：設(shè)xi

表示第i班次時開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0§3

套裁下料問題

例5．某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？第七章運(yùn)輸問題§1運(yùn)輸模型§2運(yùn)輸問題的計算機(jī)求解§3運(yùn)輸問題的應(yīng)用§4*運(yùn)輸問題的表上作業(yè)法生產(chǎn)問題某機(jī)床廠定下一年合同分別于各季度末交貨。已知各季度生產(chǎn)成本不同，允許存貨，存儲費(fèi)0.12萬元/臺季，三、四季度可以加班生產(chǎn)，加班生產(chǎn)能力8臺/季，加班費(fèi)用3萬元/臺問如何安排生產(chǎn)使得總費(fèi)用最低？季度正常生產(chǎn)能力單位成本（萬元）交貨臺數(shù)12343032202810.5510.81111.125301545建模：

成本交貨生產(chǎn)

12345（虛擬）產(chǎn)量1季度正常生產(chǎn)2季度正常生產(chǎn)3季度正常生產(chǎn)3季度加班生產(chǎn)4季度正常生產(chǎn)4季度加班生產(chǎn)10.5510.6710.7910.910M10.810.9211.040MM1111.120MM1414.120MMM11.10MMM14.103032208288

需求量2530154511126126§4運(yùn)輸問題的表上作業(yè)法例10.喜慶食品公司有三個生產(chǎn)面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價的單位為百元/噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020第八章整數(shù)規(guī)劃§3整數(shù)規(guī)劃的應(yīng)用

§4整數(shù)規(guī)劃的分枝定界法§3整數(shù)規(guī)劃的應(yīng)用

一、投資場所的選擇例2、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

，A3三個點(diǎn)至多選擇兩個；在西區(qū)由A4

，A5兩個點(diǎn)中至少選一個；在南區(qū)由A6

，A7兩個點(diǎn)中至少選一個；在北區(qū)由A8

，A9

，A10

三個點(diǎn)中至少選兩個。

Aj

各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測情況見表所示(單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點(diǎn)，可使年利潤為最大?二、固定成本問題例7．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機(jī)器有100臺/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號是l00萬元，中號為150萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計劃，使獲得的利潤為最大。

27指派問題

有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時間為最少如果把工作時間看成創(chuàng)造的效益，那么又該如何指派，才能獲得最大效益？如果再增加一項工作E，四人完成的時間分別是17,20,15,16分鐘，那么又該如何指派使得所花時間最少？29第九章目標(biāo)規(guī)劃§1目標(biāo)規(guī)劃概述§2目標(biāo)規(guī)劃圖解法§3復(fù)雜情況下的目標(biāo)規(guī)劃§4加權(quán)目標(biāo)規(guī)劃

30§3復(fù)雜情況下的目標(biāo)規(guī)劃例7．一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費(fèi)人力2工時，生產(chǎn)一件產(chǎn)品B需要耗費(fèi)人力3工時。A、B產(chǎn)品的單位利潤分別為260元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費(fèi)人力資源不能低于600工時，但也不能超過680工時的極限；次要任務(wù)是要求每周的利潤超過70000元；在前兩個任務(wù)的前提下，為了保證庫存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因為B產(chǎn)品比A產(chǎn)品更重要，不妨假設(shè)B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的2倍。試求如何安排生產(chǎn)？31§3復(fù)雜情況下的目標(biāo)規(guī)劃采用簡化模式，最終得到目標(biāo)線性規(guī)劃如下：

MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.

2x1+3x2-d1++d1-=680對應(yīng)第1個目標(biāo)

2x1+3x2-d2++d2-=600對應(yīng)第2個目標(biāo)

250x1+125x2-d3-+d3+＝70000對應(yīng)第3個目標(biāo)

x1-d4++d4-=200對應(yīng)第4個目標(biāo)

x2-d5++d5-=120對應(yīng)第5個目標(biāo)

x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0

第十一章圖與網(wǎng)絡(luò)模型§1圖與網(wǎng)絡(luò)的基本概念§2最短路問題§3最小生成樹問題§4最大流問題§5最小費(fèi)用最大流問題

例1求下圖中v1到v6的最短路v23527531512v1v6v5v3v4

例2設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是否購買新的設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。公司原來沒有此設(shè)備。已知：設(shè)備每年年初的價格表設(shè)備維修費(fèi)如下表年份12345年初價格1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用568111864686865505061456054例6：如下圖G，求最小生成樹：一、最小費(fèi)用最大流的數(shù)學(xué)模型例7由于輸油管道的長短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用bij，cij的單位為萬加侖/小時，bij的單位為百元/萬加侖。如圖。從采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流量和最小費(fèi)用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)第十四章排隊論§1引言§2單服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間的排隊模型§3多服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間的排隊模型§4排隊系統(tǒng)的經(jīng)濟(jì)分析§5單服務(wù)臺泊松到達(dá)、任意服務(wù)時間的排隊模型§6單服務(wù)臺泊松到達(dá)、定長服務(wù)時間的排隊模型§7多服務(wù)臺泊松到達(dá)、任意的服務(wù)時間、損失制排隊模型§8顧客來源有限制排隊模型§9單服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間、系統(tǒng)容量有限制的排隊模型§10多服務(wù)臺泊松到達(dá)、負(fù)指數(shù)服務(wù)時間、系統(tǒng)容量有限制的排隊模型37損失制系統(tǒng)服務(wù)機(jī)構(gòu)被占用時新到的顧客將離開等待制系統(tǒng)先來先服務(wù)(FirstComeFirstServe,FCFS)后來先服務(wù)(LastComeFirstServe,LCFS)具有優(yōu)先權(quán)的服務(wù)(Priority,PR)隨機(jī)選擇服務(wù)混合制系統(tǒng)損失制與等待制的混合排隊及排隊規(guī)則：M/M/1/∞/∞單位時間顧客平均到達(dá)數(shù)，單位平均服務(wù)顧客數(shù)(<)數(shù)量指標(biāo)公式:1.系統(tǒng)中無顧客的概率