第一章-線性規(guī)劃問題及其數(shù)學(xué)模型10頁

1、第一章 線性規(guī)劃問題及其數(shù)學(xué)模型一、問題的提出在生產(chǎn)管理和經(jīng)營活動(dòng)中經(jīng)常提出一類問題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。例1 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)及A、B兩種原材料的消耗，如表1-1所示。表1-1III該工廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元，問應(yīng)如何安排計(jì)劃設(shè) 備原材料A原材料B1402048臺時(shí)16kg12kg使該工廠獲利最多？這問題可以用以下的數(shù)學(xué)模型來描述，設(shè)x1、x2分別表示在計(jì)劃期內(nèi)產(chǎn)品I、II的產(chǎn)量。因?yàn)樵O(shè)備的有效臺時(shí)是8，這是一個(gè)限制產(chǎn)量的條件，所以在確定產(chǎn)品I、II

2、的產(chǎn)量時(shí)，要考慮不超過設(shè)備的有效臺時(shí)數(shù)，即可用不等式表示為：x1+2x28同理，因原材料A、B的限量，可以得到以下不等式4x1164x212該工廠的目標(biāo)是在不超過所有資源限量的條件下，如何確定產(chǎn)量x1、x2以得到最大的利潤。若用z表示利潤，這時(shí)z=2x1+3x2。綜合上述，該計(jì)劃問題可用數(shù)學(xué)模型表示為：目標(biāo)函數(shù) max z=2x1+3x2滿足約束條件 x1+2x284x1164x212 x1、x20例2 某鐵路制冰廠每年1至4季度必須給冷藏車提供冰各為15，20，25，10kt。已知該廠各季度冰的生產(chǎn)能力及冰的單位成本如表6-26所示。如果生產(chǎn)出來的冰不在當(dāng)季度使用，每千噸冰存貯一個(gè)季度需存貯

3、費(fèi)4千元。又設(shè)該制冰廠每年第3季度末對貯冰庫進(jìn)行清庫維修。問應(yīng)如何安排冰的生產(chǎn)，可使該廠全年生產(chǎn)費(fèi)用最少？季 度生產(chǎn)能力（kt）單位成本（千元）IIIIIIIV251816155785解：由于每個(gè)季度生產(chǎn)出來的冰不一定當(dāng)季度使用，設(shè)xij為第i季度生產(chǎn)的用于第j季度的冰的數(shù)量。按照各季度冷藏車對冰的需要量，必須滿足： 又每個(gè)季度生產(chǎn)的用于當(dāng)季度和以后各季度的冰的數(shù)量不可能超過該季度的生產(chǎn)能力，故又有 第i季度生產(chǎn)用于第j季度的冰的實(shí)際成本cij應(yīng)該是該季度冰的生產(chǎn)成本加上存貯費(fèi)用。對不可能的用冰方案，例如第一季度生產(chǎn)的冰存貯到第四季度用，其xij=0，cij=M（充分大的正數(shù)）。同時(shí)注意到這是

4、一個(gè)產(chǎn)銷不平衡問題，總的生產(chǎn)能力大于總的銷量，應(yīng)該增加一個(gè)虛銷點(diǎn)，并令cij=0（i=1，2，3，4）。這樣就可以把這個(gè)問題變成一個(gè)產(chǎn)銷平衡的運(yùn)輸問題模型，如表6-27所示。表6-27銷地產(chǎn)地IIIIIIIV虛銷點(diǎn)產(chǎn)量IIIIIIIV5 x11M x21M x319 x410 x120 x220 x320 x420 x130 x230 x330 x43M x14M x24M x245 x440 x150 x250 x850 x4525181615銷量152025104從以上兩例可以看出，它們都是屬于一類優(yōu)化問題。它們的共同特征：（1）每一個(gè)問題都用一組決策變量（x1，x2，xn）表示某一方案；

5、這組決策變量的值就代表一個(gè)具體方案。一般這些變量取值是非負(fù)的。（2）存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。（3）都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。滿足約束條件： （1.1）、（1.2）稱為約束條件。二、線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型可一般表示為 其中，（1.3.1）為目標(biāo)函數(shù)，（1.3.2）和（1.3.3）為約束條件，（1.3.3）為非負(fù)條件。上述數(shù)學(xué)模型，也可借助于求和符號寫成如下的“壓縮”形式： 若引用下述記號：C=（c

6、1，c2，cn）=（A1，A2，An）則可將線性規(guī)劃的數(shù)學(xué)模型寫成矩陣形式如下： 其中，0為n維零向量。在上述各式中，cj（j=1，2，n）稱為價(jià)值系數(shù)，aij（i=1，2，m；j=1，2，n）為約束條件的系數(shù)，bi（i=1，2，m）為約束條件的右側(cè)常數(shù)，xj（j=1，2，n）為未知數(shù)（變量），C為價(jià)值系數(shù)（行）向量，b為限定向量，X為未知數(shù)向量，A為約束條件的系數(shù)矩陣，Aj（j=1，2，n）為約束條件的系數(shù)列向量。三、線性規(guī)劃問題的標(biāo)準(zhǔn)型式由前節(jié)可知，線性規(guī)劃問題有各種不同的形式。目標(biāo)函數(shù)有的要求max，有的要求min；約束條件可以是“”，也可以是“”形式的不等式，還可以是等式。決策變量一般

7、是非負(fù)約束，但也允許在（）范圍內(nèi)取值，即無約束。將這種多種形式的數(shù)學(xué)模型統(tǒng)一變換為標(biāo)準(zhǔn)形式。這里規(guī)定的標(biāo)準(zhǔn)型式為：max z = c1x1+c2x2+cnxn簡寫為max z = 在標(biāo)準(zhǔn)型式中規(guī)定各約束條件的右端項(xiàng)bi0，否則等式兩端乘以“1”。用向量和矩陣符號表述時(shí)為：max z =CX 其中：C=（c1,c2cn）； ； ；向量pj對應(yīng)的決策變量是xi。用矩陣描述時(shí)為：max z =CXAX=bX0其中 稱A為約束條件的mn維系數(shù)矩陣，一般mn；m，n0；b為資源向量；C為價(jià)值向量；X為決策變量向量。實(shí)際碰到各種線性規(guī)劃問題的數(shù)學(xué)模型都應(yīng)變換為標(biāo)準(zhǔn)型式后求解。以下討論如何化標(biāo)準(zhǔn)型的問題。（

8、1）若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化，即min z =CX。這時(shí)只需將目標(biāo)函數(shù)數(shù)量小化變換求目標(biāo)函數(shù)最大化，即令，于是得到max 。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了。（2）約束方程為不等式。這里有兩種情況：一種是約束方程為不等式，則可在不等式的左端加入非負(fù)松弛變量，把原不等式變?yōu)榈仁?；另一種是約束方程為不等式，則可在不等式的左端減去一個(gè)非負(fù)剩余變量（也可稱松弛變量），把不等式約束條件變?yōu)榈仁郊s束條件。下面舉例說明。例3 將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。例1的數(shù)學(xué)模型為（簡稱模型M2）模型M2max z =2x1+3x2在各不等式中分別加上一個(gè)松弛變量x3，x4，x5，使不等式變?yōu)榈仁健＿@時(shí)得到標(biāo)準(zhǔn)型：m

9、ax z =2x1+3x2+0x3+0x4+0x5所加松弛變量x3、x4、x5表示沒有被利用的資源。當(dāng)然也沒有利潤，在目標(biāo)函數(shù)中其系數(shù)應(yīng)為零；即c3，c4，c5=0。（3）若存在取值無約束的變量xk，可令，其中，0。以上討論說明，任何形式的數(shù)學(xué)模型都可化為標(biāo)準(zhǔn)型，下面舉例說明。例4 將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型x1+x2+x37x1x2+x323x1+x2+2x3=5 x1，x20，x3為無約束解：步驟為：1用x1x5替換x3，其中x4，x50；2在第一個(gè)約束不等式號的左端加入松弛變量x6；3在第二個(gè)約束不等式號的左端減去剩余變量x7；4令，把求min z 改為求max ；即可得到該問題的標(biāo)準(zhǔn)

10、型max = x12x2+3（x4x5）+0x6+0x1x1+x2+(x4x5)+ x6 =7x1x2+(x4x5) x7 =23x1+x2+2（x4x5）=5x1，x2，x4，x5，x6，x7 2四、圖解法圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理?，F(xiàn)對上述例1進(jìn)行圖解。在以x1、x2為坐標(biāo)軸的直角坐標(biāo)系中，非負(fù)條件x1，x20是指第一象限。例1的每個(gè)約束條件都代表一個(gè)半平面。如約束條件x1+2x28是代表以直線x1+2x2=8為邊界的左下方的半平面，若同時(shí)滿足x1，x20，x1+2x28，4x116和4x212的約束條件的點(diǎn)，必然落在由這三個(gè)半平面交成的區(qū)域內(nèi)。由例1的所有約束條

11、件為半平面交成的區(qū)域見圖1-2中的陰影部分。陰影區(qū)域中的每一個(gè)點(diǎn)（包括邊界點(diǎn)）都是這個(gè)線性規(guī)劃問題的解（稱可行解），因而此區(qū)域是例1的線性規(guī)劃問題的解集合，稱它為可行域。再分析目標(biāo)函數(shù)z =2x1+3x2，在這坐標(biāo)平面上，它可表示以z為參數(shù)、2/3為斜率的一族平行線：x2=(2/3)x1+z/3位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值，因而稱它為“等值線”。當(dāng)z值由小變大時(shí)，直線x2=(2/3)x1+z/3沿其法線方向向右上方移動(dòng)。當(dāng)移動(dòng)到Q2點(diǎn)時(shí)，使z值在可行域邊界上實(shí)現(xiàn)最大化（見圖1-3），這就得到了例1的最優(yōu)解Q2，Q2點(diǎn)的坐標(biāo)為（4，2）。于是可計(jì)算出z =14。這說明該廠的最優(yōu)生產(chǎn)計(jì)

12、劃方案是：生產(chǎn)產(chǎn)品I 4件，生產(chǎn)產(chǎn)品II 2件，可得最大利潤為14元。上例中求解得到2到的最優(yōu)解是唯一的，但對一般線性規(guī)劃問題，求解結(jié)果還可能出現(xiàn)以下幾種情況：圖1-3（1）無窮多最優(yōu)解（多重解）。若將例1中的目標(biāo)函數(shù)變?yōu)榍髆ax z=2x1+4x2，則表示目標(biāo)函數(shù)中以參數(shù)z的這族平行直線與約束條件x1+2x28的邊界線平行。當(dāng)z值由小變大時(shí)，將與線段Q2Q3重合（見圖1-4）。線段Q2Q3上任意一點(diǎn)都使z取得相同的最大值，這個(gè)線性規(guī)劃問題有無窮多最優(yōu)解（多重解）。（2）無界解。對下述線性規(guī)劃問題max z = x1+x22x1+x24x1x22x1，x20用圖解法求解結(jié)果見圖1-5，從圖中可以看到，該問題可行域無界，目標(biāo)函數(shù)值可以增大到無窮大。稱這種情況為無界解或無最優(yōu)解。0 （3）無可行解。如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件2x1+x24，該