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

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

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

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

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

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

一般形式

目標(biāo)函數(shù)：

約束條件：

§1.1什么是線性規(guī)劃標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：

約束條件：§1.1什么是線性規(guī)劃線性規(guī)劃的標(biāo)準(zhǔn)形式有四個(gè)特點(diǎn)：§1.1

什么是線性規(guī)劃目標(biāo)最小化、等式約束、非負(fù)決策變量、非負(fù)右端項(xiàng)一般形式四類變換標(biāo)準(zhǔn)形式

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

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

解：（1）決策變量

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

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

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

LP（LinearProgramming）模型§1.1什么是線性規(guī)劃（標(biāo)準(zhǔn)化）Return

§1.1

什么是線性規(guī)劃

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

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

用圖解法求解時(shí)不必化成標(biāo)準(zhǔn)形。

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

圖解法求解步驟：

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

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

第（2）步

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

(或=

）。若

存在（

稱為可行集或可行域，點(diǎn)x

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

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

第（3）步

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

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

的交點(diǎn)即最優(yōu)解（一個(gè)或多個(gè)），目標(biāo)函數(shù)的值即最優(yōu)值。

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

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

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

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

§1.2

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

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

對(duì)求最小的問題把等值線向目標(biāo)函數(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ī)劃的圖解法多個(gè)最優(yōu)解：在例6中，線段上的每一點(diǎn)都是最優(yōu)解，最優(yōu)解的全體可以表示為：

極點(diǎn)(端點(diǎn))是和

最優(yōu)值:§1.2

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

1.可行域?yàn)榉忾]的有界區(qū)域

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

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

2.可行域?yàn)榉忾]的無界區(qū)域

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

§1.2

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

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

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

（目標(biāo)值無界）

3.可行域?yàn)榭占?/p>

無可行解§1.2

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

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

Return§1.3

單純形法

例1（續(xù)）

變量x3

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

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

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

目標(biāo)值：z1=0§1.3

單純形法

§1.3

單純形法

例1（續(xù)）將例1化為標(biāo)準(zhǔn)式?！?.3

單純形法

x1x2x3x4x5右端z1540000x33510015x4210105x52200111“單純形表”

單純形法步驟：（1）化為標(biāo)準(zhǔn)形；（2）找出一個(gè)基；（3）檢驗(yàn)數(shù)（目標(biāo)函數(shù)的系數(shù)）都是≤0時(shí)，已經(jīng)得到最優(yōu)解；（4）檢驗(yàn)數(shù)有>0時(shí)，由最大的檢驗(yàn)數(shù)計(jì)算比值；（5）由最小的比值換基，直到檢驗(yàn)數(shù)都是≤0，從而得到最優(yōu)解。§1.3

單純形法

在計(jì)算比值時(shí)要注意兩點(diǎn)：（1）檢驗(yàn)數(shù)有

>0時(shí)，由最大的檢驗(yàn)數(shù)計(jì)算比值時(shí)，只對(duì)正的系數(shù)計(jì)算；（2）如果最大的檢驗(yàn)數(shù)相應(yīng)的系數(shù)都是≤

0，那么不能計(jì)算比值。這時(shí)無最優(yōu)解，即最優(yōu)解不存在。這是對(duì)應(yīng)圖解法中“可行域無界——目標(biāo)函數(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基本變量:

非基本變量:

目標(biāo)值:§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)化為標(biāo)準(zhǔ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è)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示。問：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？請(qǐng)用圖解法和單純形兩種方法解這個(gè)問題。

產(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)化為標(biāo)準(zhǔ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)值基、基變量、非基變量注意復(fù)習(xí)下列概念：§1.3

單純形法

兩個(gè)習(xí)題：1.

均無符號(hào)限制

§1.3

單純形法

參考答案：化標(biāo)準(zhǔn)形設(shè)z1=-zx1=y1-y2，

x2=y3-y4，x3=y5-y6

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

§1.3

單純形法

（標(biāo)準(zhǔn)形）

最優(yōu)解：§1.3

單純形法

2

§1.3

單純形法

參考答案：（標(biāo)準(zhǔn)形）最優(yōu)解：（0,0,1.5,0,8,0）

Return§1.3

單純形法

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

人工變量法

首先標(biāo)準(zhǔn)化§1.4

人工變量法

第一階段:輔助問題

增加人工變量R1和R2

，用單純形法求解?！?.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)）單純形表的目標(biāo)函數(shù)f-行換成原來的目標(biāo)函數(shù)z-行，用單純形法求解。§1.4

人工變量法例10§1.4

人工變量法解：標(biāo)準(zhǔn)形§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)）單純形表的目標(biāo)函數(shù)f-行換成原來的目標(biāo)函數(shù)z-行。§1.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

人工變量法解：標(biāo)準(zhǔn)形§1.4

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