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

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

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

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

產(chǎn)品資源工時單耗甲乙生產(chǎn)能力ABC10023481236單位產(chǎn)品獲利354線性規(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建立模型5某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示

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

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

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

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

10207目標(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題例：一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費人力2工時，生產(chǎn)一件產(chǎn)品B需要耗費人力3工時。A、B產(chǎn)品的單位利潤分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費人力資源不能低于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件的重要性的1倍。試求如何安排生產(chǎn)？8910線性規(guī)劃標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型目標(biāo)函數(shù)極大化，約束條件為等式，右端常數(shù)項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)簡記11線性規(guī)劃標(biāo)準(zhǔn)型目標(biāo)函數(shù)極小化問題只需將目標(biāo)等式兩端乘以-1即變?yōu)闃O大化問題。右端常數(shù)項非正將約束等式兩端同乘以-1約束條件為不等式當(dāng)約束方程為“≤”時，左端加入一個非負(fù)的松弛變量；當(dāng)約束條件為“≥”時，不等式左端減去一個非負(fù)的剩余變量(也可稱松弛變量)即可。

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

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

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

x1x2x3x4x5單位矩陣基解令所有非基變量等于零，求出基變量的值，基解是各約束方程及坐標(biāo)軸之間交點的坐標(biāo)?；尚薪猓簼M足非負(fù)性約束的基解。最優(yōu)基：最優(yōu)解對應(yīng)的基矩陣，稱為最優(yōu)基。13表格單純形法maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

單純形法計算Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=914表格單純形法81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000檢驗數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最優(yōu)解:X*=(4,6,4,0,0)T，Z*=4215表格單純形法最優(yōu)基

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

最優(yōu)基和最優(yōu)基的逆擴展題161718對偶理論對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗數(shù)的負(fù)值。對偶問題的最優(yōu)解：y1=0，y2=1/2，y3=1，W*=42例1的對偶問題的數(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.19對偶理論這說明yi是右端項bi每增加一個單位對目標(biāo)函數(shù)Z的貢獻。對偶變量的值yi*所表示的第i種資源的邊際價值，稱為影子價值。若原問題的價值系數(shù)Cj表示單位產(chǎn)值，則yi稱為影子價格。若原問題的價值系數(shù)Cj表示單位利潤，則yi稱為影子利潤。影子價格不是資源的實際價格，而是資源配置結(jié)構(gòu)的反映，是在其它數(shù)據(jù)相對穩(wěn)定的條件下某種資源增加一個單位導(dǎo)致的目標(biāo)函數(shù)值的增量變化。對資源i總存量的評估：購進or出讓對資源i當(dāng)前分配量的評估：增加or減少對偶問題的經(jīng)濟解釋靈敏度分析20最優(yōu)單純形表為：21XBb'X1X2X3X4X5X220-11310X510160-2-41-Z-10000abc(1)求出a、b、c的值；（2）寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)基B和它的逆B-1

；

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

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

(5)若b1=20變?yōu)?5，最優(yōu)解及最優(yōu)值是什么？22整數(shù)規(guī)劃——重點掌握匈牙利算法指派問題2304二月2023【題例】某汽車公司擬將四種新產(chǎn)品配置到四個工廠生產(chǎn)，四個工廠的單位產(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【解】問題求最小值。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有指派問題assignmentproblem

04二月2023第二步：找出矩陣每列的最小元素，再分別從每列中減去，有指派問題assignmentproblem

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

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

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

04二月2023【題例】求表5－6所示的運輸問題的初始基可行解。表5－6

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

TransportationSimplexMethod04二月2023

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

TransportationSimplexMethod04二月2023【例】求表5-10給出的運輸問題的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj510251050表5-105.2運輸單純形法

TransportationSimplexMethod04二月2023表5-11BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×10105.2運輸單純形法

TransportationSimplexMethod04二月2023初始基本可行解可用下列矩陣表示表5－11中，基變量恰好是3+4－1=6個且不包含閉回路