管理運(yùn)籌學(xué)復(fù)習(xí)

管理運(yùn)籌學(xué)復(fù)習(xí)第1頁(yè)/共40頁(yè)2線性規(guī)劃問(wèn)題線性規(guī)劃主要解決有限資源的最佳分配問(wèn)題決策變量決策變量的取值要求非負(fù)。約束條件存在一組決策變量構(gòu)成的線性等式或不等式的約束條件。目標(biāo)函數(shù)存在唯一的線性目標(biāo)函數(shù)（極大或極小）。求解方法：圖解法單純形解法第2頁(yè)/共40頁(yè)3線性規(guī)劃的一般模型例1.生產(chǎn)計(jì)劃問(wèn)題

某廠生產(chǎn)甲乙兩種產(chǎn)品，各自的零部件分別在A、B車間生產(chǎn)，最后都需在C車間裝配，相關(guān)數(shù)據(jù)如表所示：

問(wèn)如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤(rùn)為最大。線性規(guī)劃模型的構(gòu)建

產(chǎn)品資源工時(shí)單耗甲乙生產(chǎn)能力ABC10023481236單位產(chǎn)品獲利35第3頁(yè)/共40頁(yè)4線性規(guī)劃的一般模型(1)決策變量：設(shè)x1為甲產(chǎn)品產(chǎn)量，x2為乙產(chǎn)品產(chǎn)量。(2)約束條件：A車間能力約束x1≤8B車間能力約束2x2≤12C車間能力約束

3x1+4x2≤36(3)目標(biāo)函數(shù)：

maxZ=

3x1+5x2

(4)非負(fù)約束：

x1

≥0，x2

≥0線性規(guī)劃數(shù)學(xué)模型為

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0建立模型第4頁(yè)/共40頁(yè)5某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示

產(chǎn)品原料甲乙丙原料擁有量AB6334554530單件利潤(rùn)415

第5頁(yè)/共40頁(yè)6目標(biāo)規(guī)劃建模某工廠計(jì)劃生產(chǎn)A、B兩種產(chǎn)品，每噸產(chǎn)品的耗電量指標(biāo)、原材料消耗、單位產(chǎn)品利潤(rùn)及資源限量如表所示。廠長(zhǎng)首先考慮要充分利用供電部門分配的電量限額66，然后考慮利潤(rùn)不低于100元；據(jù)市場(chǎng)調(diào)查結(jié)果，希望B產(chǎn)品的產(chǎn)量不低于A產(chǎn)品的產(chǎn)量，問(wèn)應(yīng)如何制定產(chǎn)品A、B的產(chǎn)量。

產(chǎn)品資源AB資源限量

電力101266原材料218單位產(chǎn)品利潤(rùn)

1020第6頁(yè)/共40頁(yè)7目標(biāo)規(guī)劃解：設(shè)x1、x2分別表示A、B兩種產(chǎn)品的產(chǎn)量，則目標(biāo)規(guī)劃模型如下：

minZ=P1(d1-

+d1+

)

+P2d2-

+P3d3-2x1+x2≤8

10x1+12x2+d1-

-d1+

=6610x1+20x2+d2-

-d2+

=100-x1+x2+d3-

-d3+

=0x1,x2

,d1-

,d1+

,d2-

,d2+

,d3-

,d3+

≥0第7頁(yè)/共40頁(yè)題例：一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費(fèi)人力2工時(shí)，生產(chǎn)一件產(chǎn)品B需要耗費(fèi)人力3工時(shí)。A、B產(chǎn)品的單位利潤(rùn)分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費(fèi)人力資源不能低于600工時(shí)，但也不能超過(guò)680工時(shí)的極限；次要任務(wù)是要求每周的利潤(rùn)超過(guò)70000元；在前兩個(gè)任務(wù)的前提下，為了保證庫(kù)存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因?yàn)锽產(chǎn)品比A產(chǎn)品更重要，不妨假設(shè)B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的1倍。試求如何安排生產(chǎn)？8第8頁(yè)/共40頁(yè)9第9頁(yè)/共40頁(yè)10線性規(guī)劃標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項(xiàng)bi≥0，決策變量非負(fù)。maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)簡(jiǎn)記第10頁(yè)/共40頁(yè)11線性規(guī)劃標(biāo)準(zhǔn)型目標(biāo)函數(shù)極小化問(wèn)題只需將目標(biāo)等式兩端乘以-1即變?yōu)闃O大化問(wèn)題。右端常數(shù)項(xiàng)非正將約束等式兩端同乘以-1約束條件為不等式當(dāng)約束方程為“≤”時(shí)，左端加入一個(gè)非負(fù)的松弛變量；當(dāng)約束條件為“≥”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱松弛變量)即可。

決策變量xk沒(méi)有非負(fù)性要求令xk=xk′-xk〃，xk=xk′，xk〃≥0，用xk′、xk〃

取代模型中xk非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化

第11頁(yè)/共40頁(yè)12線性規(guī)劃解的概念基m個(gè)線性無(wú)關(guān)的約束方程，稱為一個(gè)基，用B表示。稱基矩陣的列為基向量，用Pj表示(j=1,2,…,m)?；兞颗c基向量Pj相對(duì)應(yīng)的m個(gè)變量xj稱為基變量其余的m-n個(gè)變量為非基變量。線性規(guī)劃解的概念

x1x2x3x4x5單位矩陣基解令所有非基變量等于零，求出基變量的值，基解是各約束方程及坐標(biāo)軸之間交點(diǎn)的坐標(biāo)。基可行解：滿足非負(fù)性約束的基解。最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。第12頁(yè)/共40頁(yè)13表格單純形法maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

單純形法計(jì)算Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第13頁(yè)/共40頁(yè)14表格單純形法81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x535000檢驗(yàn)數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最優(yōu)解:X*=(4,6,4,0,0)T，Z*=42第14頁(yè)/共40頁(yè)15表格單純形法最優(yōu)基

Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3檢驗(yàn)數(shù)j-42000-1/2-1x3x2x1最優(yōu)基的逆

最優(yōu)基和最優(yōu)基的逆第15頁(yè)/共40頁(yè)擴(kuò)展題16第16頁(yè)/共40頁(yè)17第17頁(yè)/共40頁(yè)18對(duì)偶理論對(duì)偶問(wèn)題的最優(yōu)解對(duì)應(yīng)于原問(wèn)題最優(yōu)單純型法表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。對(duì)偶問(wèn)題的最優(yōu)解：y1=0，y2=1/2，y3=1，W*=42例1的對(duì)偶問(wèn)題的數(shù)學(xué)模型min=8y1+12y2+36y3

y1+0y2+3y3≥3

0y1+2y2+3y3≥5y1，y2，y3≥0S.t.maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.第18頁(yè)/共40頁(yè)19對(duì)偶理論這說(shuō)明yi是右端項(xiàng)bi每增加一個(gè)單位對(duì)目標(biāo)函數(shù)Z的貢獻(xiàn)。對(duì)偶變量的值yi*所表示的第i種資源的邊際價(jià)值，稱為影子價(jià)值。若原問(wèn)題的價(jià)值系數(shù)Cj表示單位產(chǎn)值，則yi稱為影子價(jià)格。若原問(wèn)題的價(jià)值系數(shù)Cj表示單位利潤(rùn)，則yi稱為影子利潤(rùn)。影子價(jià)格不是資源的實(shí)際價(jià)格，而是資源配置結(jié)構(gòu)的反映，是在其它數(shù)據(jù)相對(duì)穩(wěn)定的條件下某種資源增加一個(gè)單位導(dǎo)致的目標(biāo)函數(shù)值的增量變化。對(duì)資源i總存量的評(píng)估：購(gòu)進(jìn)or出讓對(duì)資源i當(dāng)前分配量的評(píng)估：增加or減少對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋第19頁(yè)/共40頁(yè)靈敏度分析20第20頁(yè)/共40頁(yè)最優(yōu)單純形表為：21XBb'X1X2X3X4X5X220-11310X510160-2-41-Z-10000abc第21頁(yè)/共40頁(yè)(1)求出a、b、c的值；（2）寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)基B和它的逆B-1

；

(3)求此線性規(guī)劃的對(duì)偶問(wèn)題及其最優(yōu)解；

(4)試求c2在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；

(5)若b1=20變?yōu)?5，最優(yōu)解及最優(yōu)值是什么？22第22頁(yè)/共40頁(yè)整數(shù)規(guī)劃——重點(diǎn)掌握匈牙利算法指派問(wèn)題23第23頁(yè)/共40頁(yè)22四月2023【題例】某汽車公司擬將四種新產(chǎn)品配置到四個(gè)工廠生產(chǎn)，四個(gè)工廠的單位產(chǎn)品成本（元/件）如表5-35所示．求最優(yōu)生產(chǎn)配置方案．表5-35產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠27550150230工廠36570170250工廠48255200280【解】問(wèn)題求最小值。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有指派問(wèn)題assignmentproblem

第24頁(yè)/共40頁(yè)22四月2023第二步：找出矩陣每列的最小元素，再分別從每列中減去，有指派問(wèn)題assignmentproblem

第25頁(yè)/共40頁(yè)22四月2023第三步：用最少的直線覆蓋所有“0”，得第四步：這里直線數(shù)等于3（等于4時(shí)停止運(yùn)算），要進(jìn)行下一輪計(jì)算．從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小數(shù)k并且減去k，矩陣中k＝5．直線相交處的元素加上k，被直線覆蓋而沒(méi)有相交的元素不變，得到下列矩陣指派問(wèn)題assignmentproblem

第四步等價(jià)于第2、3行減去5，同時(shí)第1列加上5得到的結(jié)果第26頁(yè)/共40頁(yè)22四月2023第五步：覆蓋所有零最少需要4條直線，表明矩陣中存在4個(gè)不同行不同列的零元素．容易看出4個(gè)“0”的位置()××()×()()或()××()×()()指派問(wèn)題assignmentproblem

第27頁(yè)/共40頁(yè)22四月2023得到兩個(gè)最優(yōu)解有兩個(gè)最優(yōu)方案第一種方案：第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品3，第三個(gè)工廠加工產(chǎn)品4，第四個(gè)工廠加工產(chǎn)品2；第二種方案：第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個(gè)工廠加工產(chǎn)品3，第四個(gè)工廠加工產(chǎn)品2；單件產(chǎn)品總成本Z＝58＋150＋250＋55＝513指派問(wèn)題assignmentproblem

第28頁(yè)/共40頁(yè)22四月2023【題例】求表5－6所示的運(yùn)輸問(wèn)題的初始基可行解。表5－6

銷地產(chǎn)地B1B2B3產(chǎn)量A1A2A3847634758304525銷量603010100運(yùn)輸單純形法

TransportationSimplexMethod第29頁(yè)/共40頁(yè)22四月2023

BjAiB1B2B3產(chǎn)量A186730A243545A374825銷量603010100表5－7【解】30××15×10×25205.2運(yùn)輸單純形法

TransportationSimplexMethod第30頁(yè)/共40頁(yè)22四月2023【例】求表5-10給出的運(yùn)輸問(wèn)題的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj510251050表5-105.2運(yùn)輸單純形法

TransportationSimplexMethod第31頁(yè)/共40頁(yè)22四月2023表5-11BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×10105.2運(yùn)輸單純形法

TransportationSimplexMethod第32頁(yè)/共40頁(yè)22四月2023初始基本可行解可用下列矩陣表示表5－11中，基變量恰好是3+4－1=6個(gè)且不包含閉回路，是一組基變量，其余標(biāo)有符號(hào)×的變量是非基變量5.2運(yùn)輸單純形法

TransportationSimplexMeth