第1章 線性規(guī)劃和單純形法

上課須知理論課每周4節(jié)，實踐課每周上機；考查，五級分制：優(yōu)、良、中、及格、不及格；課后及時復習與預習；獨立自主作業(yè)，課代表在上課前收取，按學號整理；平時成績=作業(yè)+課堂考查；聽到下課鈴聲才能離開教室。參考教材第1章線性規(guī)劃模型和單純形法§1.1什么是線性規(guī)劃§1.2線性規(guī)劃的圖解法§1.3單純形法§1.4人工變量法第1章線性規(guī)劃模型和單純形法§1.1什么是線性規(guī)劃線性的約束線性的目標函數(shù)例1：達能公司生產(chǎn)I、II兩種餅干，需用A、B、C三種類型的設(shè)備。每噸餅干在生產(chǎn)中需要占用設(shè)備的工時數(shù)，每噸餅干可以獲得的利潤以及三種設(shè)備可利用的工時數(shù)如下表所示：

餅干I餅干II工時數(shù)設(shè)備A（攪拌機）3515設(shè)備B（成形機）215設(shè)備C（烘箱）2211利潤（百元/噸）54

§1.1什么是線性規(guī)劃

§1.1什么是線性規(guī)劃

問題：公司應如何安排生產(chǎn)可獲得最大的利潤？解：設(shè)變量xi為第i種產(chǎn)品的每天的生產(chǎn)量（i＝1,2）。根據(jù)前面分析，可以建立如下的線性規(guī)劃模型：

一般形式

目標函數(shù)：

約束條件：

§1.1什么是線性規(guī)劃標準形式目標函數(shù)：

約束條件：§1.1什么是線性規(guī)劃線性規(guī)劃的標準形式有四個特點：§1.1

什么是線性規(guī)劃目標最小化、等式約束、非負決策變量、非負右端項一般形式四類變換標準形式

§1.1什么是線性規(guī)劃例1（續(xù)）將例1化為標準式。（怎樣化為標準形？教材第14-16頁有四點?。?.1什么是線性規(guī)劃例2：服裝廠應如何安排生產(chǎn)可獲得最大的總利潤？

男式女式生產(chǎn)能力（小時）裁剪12/3900縫紉1/21/3300檢驗1/81/4100利潤（元/件）58

解：（1）決策變量

§1.1什么是線性規(guī)劃設(shè)變量x1

為男式童裝的生產(chǎn)件數(shù)，變量x2

為女式童裝的生產(chǎn)件數(shù)。（2）約束條件（3）目標函數(shù)

LP（LinearProgramming）模型§1.1什么是線性規(guī)劃（標準化）Return

§1.1

什么是線性規(guī)劃

§1.2線性規(guī)劃的圖解法

對于只有兩個變量的線性規(guī)劃問題，可以在二維直角坐標平面上用圖解法求解。

用圖解法求解時不必化成標準形。

§1.2線性規(guī)劃的圖解法

圖解法求解步驟：

第(1)步以決策變量為坐標建立直角坐標系。

§1.2線性規(guī)劃的圖解法

第（2）步

確定每個約束條件決定的半平面，并繪出各約束半平面交集

(或=

）。若

存在（

稱為可行集或可行域，點x

稱為線性規(guī)劃的可行解）轉(zhuǎn)第（3）步；若不存在，該線性規(guī)劃問題無可行解。

§1.2線性規(guī)劃的圖解法

第（3）步

作一條目標函數(shù)的等值線，確定目標值增加（或減少）的方向；平移等值線，達到既與

有交點又不可能使值再增加（或減少）的位置(或交于無窮遠處，稱無有限最優(yōu)解）。若有交點時，此等值線與

的交點即最優(yōu)解（一個或多個），目標函數(shù)的值即最優(yōu)值。

§1.2線性規(guī)劃的圖解法目標函數(shù)等值線的確定例1（續(xù)）目標函數(shù)

的等值線用下列方法來確定：

在坐標平面上找出點方向OM是目標函數(shù)z增加的方向

OM的直線是目標函數(shù)z的等值線

§1.2

線性規(guī)劃的圖解法

對求最大的問題把等值線向目標函數(shù)增加的方向推；

對求最小的問題把等值線向目標函數(shù)減少的方向推。例1（續(xù)）

§1.2線性規(guī)劃的圖解法§1.2

線性規(guī)劃的圖解法最優(yōu)解:§1.2

線性規(guī)劃的圖解法最優(yōu)值:例2（續(xù)）

§1.2

線性規(guī)劃的圖解法§1.2

線性規(guī)劃的圖解法§1.2

線性規(guī)劃的圖解法最優(yōu)解:最優(yōu)值:

§1.2

線性規(guī)劃的圖解法例3

§1.2

線性規(guī)劃的圖解法

§1.2

線性規(guī)劃的圖解法例4

§1.2

線性規(guī)劃的圖解法

§1.2

線性規(guī)劃的圖解法例5

§1.2

線性規(guī)劃的圖解法

§1.2

線性規(guī)劃的圖解法例6

§1.2

線性規(guī)劃的圖解法多個最優(yōu)解：在例6中，線段上的每一點都是最優(yōu)解，最優(yōu)解的全體可以表示為：

極點(端點)是和

最優(yōu)值:§1.2

線性規(guī)劃的圖解法線性規(guī)劃的可行域和最優(yōu)解有以下幾種情況：

1.可行域為封閉的有界區(qū)域

有唯一的最優(yōu)解；

有無窮多個最優(yōu)解；

2.可行域為封閉的無界區(qū)域

有唯一的最優(yōu)解；

§1.2

線性規(guī)劃的圖解法

有無窮多個最優(yōu)解；

無有限的最優(yōu)解

（目標值無界）

3.可行域為空集

無可行解§1.2

線性規(guī)劃的圖解法§1.2

線性規(guī)劃的圖解法可行域和最優(yōu)解

Return§1.3

單純形法

例1（續(xù)）

變量x3

,x4,x5稱為基本變量，基本變量的全體（用B表示）稱為一個（組）基；其它的變量稱為非基本變量（用N表示）。

（1）基本變量：x3=15,x4=5/2,x5=11/2

（2）非基本變量：x1=0,x2=0

目標值：z1=0§1.3

單純形法

§1.3

單純形法

例1（續(xù)）將例1化為標準式?！?.3

單純形法

x1x2x3x4x5右端z1540000x33510015x4210105x52200111“單純形表”

單純形法步驟：（1）化為標準形；（2）找出一個基；（3）檢驗數(shù)（目標函數(shù)的系數(shù)）都是≤0時，已經(jīng)得到最優(yōu)解；（4）檢驗數(shù)有>0時，由最大的檢驗數(shù)計算比值；（5）由最小的比值換基，直到檢驗數(shù)都是≤0，從而得到最優(yōu)解?！?.3

單純形法

在計算比值時要注意兩點：（1）檢驗數(shù)有

>0時，由最大的檢驗數(shù)計算比值時，只對正的系數(shù)計算；（2）如果最大的檢驗數(shù)相應的系數(shù)都是≤

0，那么不能計算比值。這時無最優(yōu)解，即最優(yōu)解不存在。這是對應圖解法中“可行域無界——目標函數(shù)無界”的情況?！?.3

單純形法

§1.3

單純形法

x1x2x3x4x5右端比z1540000x3251001515/3=5x42101055/2x5220011111/2§1.3

單純形法

x1x2x3x4x5右端比z103/20-5/20-25/2x307/21-3/2015/215/7x111/201/205/25x5010-1166基本變量:

非基本變量:

目標值:§1.3

單純形法

§1.3

單純形法

x1x2x3x4x5右端z100-3/7-13/70-110/7x2012/7-3/7015/7x110-1/75/7010/7x5001-2/7-4/7127/7最優(yōu)解、最優(yōu)值:原問題的最優(yōu)解、最優(yōu)值:

§1.3

單純形法

例7用單純形求下列線性規(guī)劃。§1.3

單純形法

轉(zhuǎn)化為標準形

§1.3

單純形法

§1.3

單純形法

x1x2x3x4x5x6右端比z16-330000x421010084x5-4-2301014*x61-210011818§1.3

單純形法

x1x2x3x4x5x6右端比z10-63-300-24x111/201/2004*x50032103010x60-5/21-1/2011414§1.3

單純形法

x1x2x3x4x5x6右端z10-60-5-10-54x111/201/2004x30012/31/3010x60-5/20-7/6-1/314最優(yōu)解、最優(yōu)值:原問題的最優(yōu)解、最優(yōu)值:

§1.3

單純形法

§1.3

單純形法例8

某工廠有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示。問：工廠應如何安排生產(chǎn)可獲得最大的總利潤？請用圖解法和單純形兩種方法解這個問題。

產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500

解：x1-甲產(chǎn)品數(shù)量，x2-乙產(chǎn)品數(shù)量

§1.3

單純形法

§1.3

單純形法

轉(zhuǎn)化為標準形：§1.3

單純形法

§1.3

單純形法

x1x2x3x4x5右端比z1150025000000x3321006565/2x4210104040/1x5030017575/3§1.3

單純形法

x1x2x3x4x5右端比z11500000-2500/3-62500x33010-2/31515/3x42001-1/31515/2x201001/325*§1.3

單純形法

x1x2x3x4x5右端z100-5000-500-70000x1101/30-2/95x400-2/311/95x201001/325最優(yōu)解、最優(yōu)值:原問題的最優(yōu)解、最優(yōu)值:

§1.3

單純形法

可行解、可行域最優(yōu)解、最優(yōu)值基、基變量、非基變量注意復習下列概念：§1.3

單純形法

兩個習題：1.

均無符號限制

§1.3

單純形法

參考答案：化標準形設(shè)z1=-zx1=y1-y2，

x2=y3-y4，x3=y5-y6

所以z1=-(y1-y2)-2(y3-y4)+(y5-y6)再加入三個松弛變量y7,y8,y9

§1.3

單純形法

（標準形）

最優(yōu)解：§1.3

單純形法

2

§1.3

單純形法

參考答案：（標準形）最優(yōu)解：（0,0,1.5,0,8,0）

Return§1.3

單純形法

人工變量法基本思想（見下例）例9§1.4

人工變量法

首先標準化§1.4

人工變量法

第一階段:輔助問題

增加人工變量R1和R2

，用單純形法求解。§1.4

人工變量法

輔助問題最優(yōu)解及最優(yōu)值:x1*=2,x2*=0,S2*=0,S3*=1R1*=0,R2*=0,f*=0

原來問題的可行解:

x1*=2,x2*=0,S2*=0,S3*=1§1.4

人工變量法第二階段:把第一階段最后的一張（最優(yōu)）單純形表的目標函數(shù)f-行換成原來的目標函數(shù)z-行，用單純形法求解。§1.4

人工變量法例10§1.4

人工變量法解：標準形§1.4

人工變量法第一階段:輔助問題增加人工變量R1和R3§1.4

人工變量法§1.4

人工變量法x1x2x3S1S2R1R3右端f00000-1-1015-3-101015S25-61001002011100015§1.4

人工變量法x1x2x3S1S2R1R3右端

比f2-2-100020R11-3-1010153S25-610010020*R311100015565§1.4

人工變量法x1x2x3S1S2R1R3右端

比f4/501/50-6/502x21/51-3/5-1/501/503*S231/5032/5-6/516/50385.9R34/501/50-1/5121.28/58/5§1.4

人工變量法x1x2x3S1S2R1R3右端

f00000-1-10x21/210-1/801/83/815/4S2300-212-430x31/2011/80-1/85/85/4最優(yōu)解、最優(yōu)值:原問題的最優(yōu)解、最優(yōu)值:

§1.4

人工變量法

輔助問題最優(yōu)解:輔助問題最優(yōu)值:

f*=0原來問題的可行解:x1=0,x2=15/4,x3=5/4,S1=0,S2=30§1.4

人工變量法第二階段:把第一階段最后的一張（最優(yōu)）單純形表的目標函數(shù)f-行換成原來的目標函數(shù)z-行?！?.4

人工變量法§1.4

人工變量法x1x2x3S1S2右端

z-23/200-1/80-125/4x21/210-1/8015/4S2300-2130x31/2011/805/4

最優(yōu)解:

x1*=0,x2*=15/4,x3*=5/4

最優(yōu)值:

z*=-125/4§1.4

人工變量法例11§1.4

人工變量法解：標準形§1.4

人工變量法第一階段:輔助問題