1、第二章：線性規(guī)劃的圖解法，1。提出問(wèn)題2。圖解法的靈敏度分析。第二章：線性規(guī)劃的圖解法。一些典型的線性規(guī)劃在管理中的應(yīng)用使線材得到了合理的利用：如何在保證生產(chǎn)的條件下減少配料；如何在原材料供應(yīng)限制下獲得最大利潤(rùn)；投資問(wèn)題：從投資項(xiàng)目中選擇方案。投資回報(bào)最大化的產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等。以實(shí)現(xiàn)利潤(rùn)最大化。勞動(dòng)力安排：用最少的勞動(dòng)力滿足工作需要。運(yùn)輸問(wèn)題：如何制定運(yùn)輸計(jì)劃，使總運(yùn)費(fèi)最小化。2、線性規(guī)劃的構(gòu)成：目標(biāo)函數(shù)最大或最小約束滿足決策變量，可控因素用符號(hào)表示。1.問(wèn)題被提出來(lái)了。例1。工廠應(yīng)該在計(jì)劃期間安排兩種產(chǎn)品的生產(chǎn)。眾所周知，生產(chǎn)單位產(chǎn)品所需的設(shè)備以及甲、乙原料的消耗和資

2、源限制如下：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)，線性規(guī)劃模型：目標(biāo)函數(shù)：max z=50 x1 100 x2約束：s.t. x1x2300 2x1x2400x250x1，x20，1問(wèn)題提出，建模過(guò)程1。理解要解決的問(wèn)題，明確在什么條件下追求什么目標(biāo)；2.定義決策變量(x1，x2，xn)，每組值代表一個(gè)方案；3.以決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，并確定最大化或最小化目標(biāo)；4.使用一組決策變量的等式或不等式來(lái)表示在解決問(wèn)題的過(guò)程中必須遵循的約束。一般形式目標(biāo)函數(shù)：最大(最小)z=c1 x1 c2 x2 cn xn約束：s.t. a11 x1 a12 x2 a1n xn (=，)b1 a21 x1 a22 x

3、2 a2n xn (=，)b2 am1 x1 am2 x2 amn xn (=，)bm x1，x2，xn 0，4，示例1。目標(biāo)函數(shù)：max z=50 x1 100 x2約束：s . t . x1x 2300(a)2x 1x 2400(b)x2250(c)X10(d)x20(e)得到最優(yōu)解：x1=50，x2=250。最佳目標(biāo)值是z=27500。2圖解法，對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，線性規(guī)劃問(wèn)題的相關(guān)概念可以通過(guò)在平面直角坐標(biāo)系上作圖來(lái)表示和求解。該方法在下面的示例1中詳細(xì)說(shuō)明：(1)以決策變量X1和X2作為坐標(biāo)向量來(lái)建立直角坐標(biāo)系。在直角坐標(biāo)系中，圖上任意點(diǎn)的坐標(biāo)代表一組決策變量值，示例

4、1中的每個(gè)約束條件代表一個(gè)半平面。6，2圖解法，(2)對(duì)于每個(gè)不等式(約束條件)，首先把它的等式作為坐標(biāo)系中的一條直線，然后確定由不等式確定的半平面。7，x1，x1，x2，x2，2，(3)將五個(gè)圖合并成一個(gè)圖，并取每個(gè)約束條件的公共部分，如圖2-1所示。(4)目標(biāo)函數(shù)z=50 x1 100 x2，當(dāng)z取一個(gè)固定值時(shí)，得到一條直線，并且直線上的每一點(diǎn)都有相同的目標(biāo)函數(shù)值，稱為“等值線”。平行移動(dòng)等值線。當(dāng)移動(dòng)到B點(diǎn)時(shí)，Z在可行區(qū)域內(nèi)最大化。a、b、c、d和e是可行域的頂點(diǎn)，并且可行域的頂點(diǎn)對(duì)于有限數(shù)量的約束也是有限的。9，2圖解法，線性規(guī)劃的標(biāo)準(zhǔn)化內(nèi)容之一：引入松弛變量(意味著剩余資源量)s1，

5、s2，S3被建模為目標(biāo)函數(shù)：max z=50 x1 100 x2 0 s1 0 s2 0 s3約束：s . t . x1x2s 1=3002 x1 2s 2=400 x2 3=250 x1，x2，s1，s2，S3 0對(duì)于最優(yōu)解x1=50 x2=250，s1=0 s2=50 s3=0， 它表明，生產(chǎn)50個(gè)單位的產(chǎn)品和250個(gè)單位的產(chǎn)品將消耗所有可能的設(shè)備小時(shí)和原材料b，但仍然有50公斤的原材料a，10，2圖解法，重要的結(jié)論：如果線性規(guī)劃有一個(gè)最優(yōu)解，必須有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解； 無(wú)限多的最優(yōu)解。如果將示例1中的目標(biāo)函數(shù)更改為max z=50 x1 50 x2，則線段BC上的所有點(diǎn)都代表

6、最優(yōu)解。無(wú)界解。也就是說(shuō)，行字段的范圍擴(kuò)展到無(wú)限，并且目標(biāo)函數(shù)值可以是無(wú)限的或無(wú)限小的。一般來(lái)說(shuō)，這表明模型是錯(cuò)誤的，忽略了一些必要的約束；沒(méi)有可行的解決辦法。如果將約束條件4x1 3x21200添加到示例1的數(shù)學(xué)模型，則可行區(qū)域是空間域，并且不存在滿足約束條件的解，當(dāng)然，不存在最優(yōu)解。11，圖解法有無(wú)界解，而線性規(guī)劃有無(wú)界解，即沒(méi)有最優(yōu)解。對(duì)于下列線性規(guī)劃問(wèn)題：約束條件：最大z=x1x2X1-x2 1 -3x1 2x2 6 x1 0，x2 0，12，圖形解是無(wú)界的，結(jié)果用圖形方法求解。如圖所示，可以看出問(wèn)題的可行域是無(wú)界的，目標(biāo)函數(shù)值可以增加到無(wú)窮大，成為無(wú)界解，即沒(méi)有最優(yōu)解。13，1，2，

7、3，4，-1，-2，1，2，3，4，-1，z=0=x1x2，z=1=x1x2，z=3=x1x2，進(jìn)一步討論。但是，由于原料甲和原料乙的規(guī)格不同，它們的加工時(shí)間也不同。每噸原料甲加工2小時(shí)，每噸原料乙加工1小時(shí)，公司共有600個(gè)加工小時(shí)。我們也知道原材料甲的價(jià)格是每噸2萬(wàn)元，原材料乙的價(jià)格是每噸3萬(wàn)元。在滿足生產(chǎn)需求的前提下，在公司加工能力范圍內(nèi)，如何采購(gòu)原材料甲和乙，使采購(gòu)成本最低？14，進(jìn)一步討論，解決方案：目標(biāo)函數(shù)：min f=2x1 3 x2約束：s.t. x1 x2 350 x1 125 2 x1 x2 600 x1，x2 0采用圖解法。如下圖所示，Q點(diǎn)(250，100)的坐標(biāo)是最優(yōu)解

8、。15，3圖形方法的靈敏度分析，線性規(guī)劃目標(biāo)函數(shù)的標(biāo)準(zhǔn)化一般形式：max (min) z=c1 x1 c2 x2 cn xn約束條件：s.t. a11 x1 a12 x2 a1n xn (=，)b1 a21 x1 a22 x2 a2n xn (=，)b2 am1 x1 am2 x2 amn xn (=，)bm x1，x2， Xn 0標(biāo)準(zhǔn)目標(biāo)函數(shù)：max z=c1 x1 c2 x2 cn xn約束：s . t . a11x 1 a12x 2 a1n xn=b1a 21 xa 22x 2 a2 nxn=b2am 1x 1 a2 x2 amnxn=圖形方法bm x1，x2，xn 0，bi 0，16，

9、3的靈敏度分析表明，線性規(guī)劃的標(biāo)準(zhǔn)形式有以下四個(gè)特殊點(diǎn)：目標(biāo)最大化； 約束是等式；決策變量不是負(fù)的；右端項(xiàng)不是負(fù)數(shù)。對(duì)于各種非標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題，我們總是可以通過(guò)下面的變換把它們轉(zhuǎn)化為標(biāo)準(zhǔn)：17，3圖解法的靈敏度分析。1.最小化目標(biāo)函數(shù)：如果目標(biāo)函數(shù)是min f=c1x1c2cnxn (can) make z -f，那么最小化問(wèn)題具有與下面的最大化問(wèn)題相同的最優(yōu)解。即max z=-c1x1-c2x2 - cnxn，但必須注意的是，雖然上述兩個(gè)問(wèn)題的最優(yōu)解是相同的，但它們的最優(yōu)解的目標(biāo)函數(shù)值相差一個(gè)符號(hào)，即最小f-max z的靈敏度分析，18，3圖解法，2。約束條件不是等式的問(wèn)題：如果約束條件是a

10、i1 x1 ai2 x2 ain xn bi，可以引入一個(gè)新的變量S，使其等于約束s=bi(ai1 x1 ai2 x2 ain xn)的左右兩邊之差。顯然，S還有一個(gè)非負(fù)約束，即s0。這時(shí)，新的約束條件就變成了ai1x1ai2ainxn s=bi，19，3的圖解法的靈敏度分析。當(dāng)約束條件是ai1x1ai2ainxn bi時(shí)，類似地，s=(ai1x1ai2ainxn)-bi顯然，s也具有非負(fù)約束，即s0。此時(shí)，新的光束減少條件成為圖形方法AI1x1ai2ainxn-s=bi，20，3的靈敏度分析，并且當(dāng)不等式“小于或等于”時(shí)，為了將約束從不等式變?yōu)榈仁蕉氲淖兞縎被稱為“松弛變量”。當(dāng)不等式“

11、大于或等于”時(shí)，稱為“剩余變量”。如果原問(wèn)題中有幾個(gè)不相等的約束，那么當(dāng)每個(gè)約束轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須引入不同的松弛變量或剩余變量。21，3。右端項(xiàng)具有負(fù)值的問(wèn)題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)的每個(gè)組成部分都必須是非負(fù)值。當(dāng)某個(gè)右端項(xiàng)的系數(shù)為負(fù)時(shí)，如bi0，將等式約束的兩端同時(shí)乘以-1，得到：-ai1x1-ai2x2-ainxn=-bi。3靈敏度分析的圖解法，例如：將下面的線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式min f=2x 1-3x 24 x3 s . t . 3x 14 x2-5x 36 2x 1 x3 8 x1x 2 x3=-9x 1，x2，x3 0解：首先，將目標(biāo)函數(shù)轉(zhuǎn)化為最大化：讓z=-f=-2x

12、1 3x2-4x3考慮約束條件，有兩個(gè)不等式約束條件，并引入松弛變量或剩余變量x4，x5 0。第三個(gè)約束的右端是負(fù)的，在等式的兩邊乘以-1。22，3，通過(guò)上面的變換，我們可以得到下面的標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題：max z=-2x 13 x2-4x 3s . t . 3x 14 x2-5x 3 x4=62x 1x 3-X5=8-x1-x2-x3=9 x1，x2，x3，x4，x50 * * *。當(dāng)變量xj沒(méi)有非負(fù)約束時(shí)，xj=xj- xj 其中xj0，xj 0表示一個(gè)無(wú)符號(hào)的受限變量，由兩個(gè)非負(fù)變量之差決定。當(dāng)然，xj的符號(hào)取決于xj和XJ的大小?！保?3，3圖解法靈敏度分析：在建立數(shù)學(xué)模型并找到最優(yōu)解后

13、，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)(系數(shù))ci、aij、bj對(duì)最優(yōu)解產(chǎn)生的影響。3.1目標(biāo)函數(shù)中系數(shù)ci的靈敏度分析考慮例1中的情況，ci的變化只影響目標(biāo)函數(shù)等值線的斜率。當(dāng)目標(biāo)函數(shù)z=50 x1 100 x2在z=x2 (x2=z斜率為0)和z=x1 x2 (x2=-x1 z傾角為-1)之間時(shí)，原來(lái)的最優(yōu)解x1=50，x2=100仍然是最優(yōu)解。一般情況：z=c1 x1 c2 x2寫成截?cái)鄕2=-(c1/c2) x1 z/c2。目標(biāo)函數(shù)等值線的斜率為-(c1/c2)。當(dāng)-1-(c1/c2) 0 (*)時(shí)，原來(lái)的最優(yōu)解仍然是最優(yōu)解。24，3圖形靈敏度分析，假設(shè)產(chǎn)品的利潤(rùn)100元不變，即c2=100，

14、用公式(*)代替，整理為0 c1 100，假設(shè)產(chǎn)品的利潤(rùn)50元不變，即c1=50，用公式(*)代替，整理為50 c2，如果產(chǎn)品和利潤(rùn)都發(fā)生變化，可以直接用公式(*)來(lái)判斷。假設(shè)產(chǎn)品利潤(rùn)和利潤(rùn)分別為60元和55元，那么-2-(60/55)-1，那么最優(yōu)解是z=x1 x2和z=2 x1 x2的交集，其中x1=100，x2=200。25，3圖解法的靈敏度分析，3.2約束條件下右系數(shù)bj的靈敏度分析當(dāng)約束條件下的右系數(shù)bj改變時(shí)，線性規(guī)劃的可行域也改變，這可能導(dǎo)致最優(yōu)解的改變?？紤]示例1的情況：當(dāng)添加10個(gè)站點(diǎn)時(shí)，即b1變?yōu)?10，則可行區(qū)域擴(kuò)展，并且最優(yōu)解是x2=250和x1 x2=310，x1=60，x2=250的交集。變更后總利潤(rùn)-變更前總利潤(rùn)=增加利潤(rùn)(5060 100250)-(50 50 100 250)=500，500/10=50元表明，當(dāng)設(shè)備容量在一定范圍內(nèi)增加(減少)一個(gè)單位時(shí)，50元利潤(rùn)可以增加(減少)，這就是這個(gè)約束條件的雙重價(jià)格。26，3。假設(shè)當(dāng)原料A增加10千克時(shí)，即b2變?yōu)?10，則可行區(qū)域擴(kuò)大，但是最優(yōu)解仍然是x2=250和x1