1.優(yōu)化問題(w6nti)及其數(shù)學模型

假設有一個問題，它有幾個因素來決定，當這些因素處于某個狀態(tài)時，可

以使問題得到我們最想要的結果。優(yōu)化問題就是尋求(xOnqi①這個狀態(tài)的過程。

例如:

某工廠(gongchmng)生產A,B兩種產品，所用原料均為甲、乙、丙三種(s2

nzhong);生產一件產品所需原料和所獲利潤以及庫存原料情況如下所示：

原料甲原料乙原料丙利潤(元)

產品A8447000

產品B68610000

庫存構熊在工々型程獨庫存原料「鐘§80單位，眉能300單位)泵料丙220單

位的情況下如何(舊帕)安排A,B兩種產品的生產數(shù)量可以獲得最大的利潤？

設生產A中產品件，生產B中產品件，z為所獲得的利潤，于是有關

系式：

我們稱它為目標函數(shù)。生產的條件我們可以表示為：

我們把上面的不等式稱為約束條件。

產品A的產量x和B的產量*是優(yōu)化問題的變量。在滿足約束條件的前提

12

下使目標函數(shù)得到最優(yōu)的值成為最優(yōu)解。根據(jù)以上定義，也可以說優(yōu)化運算是

通過某種計算尋求最優(yōu)解的過程。

以上這個用等式或者不等式來表達我們要解決的問題的過程就是優(yōu)化問題

的建模過程。我們平時遇到的問題往往不是上面的這幾個數(shù)學表達式就能表

達得

清清晰楚的，但是建立像上面類似的數(shù)學模型卻是優(yōu)化求解的第一步。優(yōu)化問

題往往表現(xiàn)為在多約束條件下求某一函數(shù)的極值問題，例如上面的這個例子。

Matlab有一個優(yōu)化工具箱，可以匡助我們方便的解決好這種問題。

2優(yōu)化工具箱

Matlab的優(yōu)化工具箱有一些對普通非線性函數(shù)求解最小化或者最大化(求

極值)的函數(shù)組成，此外還包括一些解決諸如線性規(guī)劃等標準矩陣問題的函數(shù)

o所有的優(yōu)化函數(shù)都是用Matlab語言編寫的m文件，我們可以通過在命令窗

口里輸入typefunction_name來查看這些函數(shù)。

優(yōu)化工具箱的優(yōu)化功能包括：

(1)求無約束非線性最小化；

(2)求有約束非線性最小化；

(3)二次和線性規(guī)劃問題；

(4)非線性最小二乘法和曲線擬合問題；

(5)非線性等式的求解；

(6)約束線性最小二乘法；

(7)稀疏和結構化大尺度問題。

工具箱中求非線性函數(shù)極小值的命令函數(shù)如下表所示：

函數(shù)用法

線性規(guī)劃問題x=linprog(f,A,k))

無限定標量問題x=fminuncf^jx),x為標量

無限定條件矩陣

x=fminunc^r,x),X為矩陣

問題

minf(x)，條件為

有限定條件x=fnd.ncon^f(f1x)

目標條件x=fgoa2attain(4^,x,goal,w),條件為

，汆ItN

最小最大極值x=fminmax^坷,x)

G(X)<0

非線性二次平

x=lsqnonneg(if

方極值

非線性方程x=fsolved

半無窮條件x=fsemimf^ft\n,x)，條件為任意給定v值

上面表中函數(shù)(MnshCi)可以對標量、向量和矩陣進行運算；我們普通用大寫

字母表示矩陣，用小寫字母表示向量和標量。在Matlab中用符號表示矩

陣的元素乘。固然，上述運算是在定義好了一個(yig?最小化函數(shù)的前提下進

行的，也就是說要先建立數(shù)學模型。

注：Matlab自身提供了一個(yig?優(yōu)化演示示例，其命令為。ptdemo。

3.線性規(guī)劃(xi6nxingguThu臺)問題

前面6-1中所舉的例子就是一個典型的線性規(guī)劃問題。線性規(guī)劃數(shù)學模型的

特點伯di*n)是：在線性不等式或者線性等式的約束條件下，求能滿足目標函數(shù)

取得最大值或者最小值的一組變量的值，目標函數(shù)也要求是線性函數(shù)。

命令:linprog

格式:X=linprog(f,A,b)

[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,optio

ns)

功能：計算使目標函數(shù)取得最小值的一組變量的值。

說明：這里f為由目標函數(shù)的系數(shù)組成的向量。A是一個矩陣，b是一個向

量，A和b構成為了線性規(guī)劃的不等式約束條件0X是一個向量，為返

回的滿足目標函數(shù)取得極小值的一組變量的值。Aeq是一個矩陣，Beq是一個

向量，Aeq和Beq構成為了線性規(guī)劃的等式約束條件oLB和UB分

②在優(yōu)化問題中，涉及到優(yōu)化結果只能取整數(shù)值的情況時，如果我們對優(yōu)

化結果隨意的進行取整，可能導致最后結果不是最優(yōu)，這一點需要注意。

例2中國石油天然氣集團公司天然氣的運送(yCinsdng)案例分析

中國(zhonggu6)石油天然氣集團公司在東海有一個(yigV)油氣田(節(jié)點

),該公司要將開采的天然氣通過管道運送(pinsbng)到上海的一個配送中心

(節(jié)點),天然氣在運送途中(tUZhong)要經過兩次管道換接點(節(jié)點B和

C).換接先后管道長短不一，而且不同的管道對應不同的單位流量運費。如

圖，天然氣運送的管道網絡圖，弧線表示管道，弧旁的數(shù)字為(，)，其中

b表示管道上的單位流量費用，c表示管道上的容量。公司希翼選擇一個經濟

巧ij

實惠的管道路線運送天然氣，既運送最多的天然氣又使總的運輸費用至少。

(4,2

這是一個最小費用最大流問題。為了建立該問題的數(shù)學模型，首先設每段

管道(gumnd臺o)上的流量作為問題的決策變量，分別記為

,稱分段(fendgn)流量。

從始點u處，可得流量(同冶ng)函數(shù)，

S

且有約束條件：(1);

(2)

(3)；

一方面要使流量(I血詒ng)最大，另一方面要是(yaoshi)費用最小。

所以分兩部份計算，先求出最大流，再求最小費用最大流。

對應matlab程序如下：

f=-[1,1,0,0,0,0,0,0,0];

aeq=[l,0,-1,-1,1,0,0,0,0;

0,1,1,0,0,-1,0,0,0;

0,0,0,1,0,0,1,-1,0;

0,0,0,0,-1,1,-1,0,-1];

beq=zeros(4,1);

lb=zeros(9,1);

ub=[4;5;1;3;1;2;3;5;2];

Lx,fvalj=linprog(aeq,beq,lb,ub)

%求出最大流

fl=[1,3,1,3,2,4,1,2,4];

aeql=[1,1,0,0,0,0,0,0,0;

1,0,-1,-14,0,0,0,0;

0,1,1,0,0,-1,0,0,0;

0,0,0,1,0,0,1,-1,0;

0,0,0,0,-1,1,-1,0,-1]；

beql=[-fval;beq];

[z,fvall]=linprog(fl,[],[],aeql,beql,lb,ub)

程序執(zhí)行后，結果為：

Z=

4.0000

1.0000

1.0000

3.0000

0.0000

2.0000

2.0000

5.0000

0.0000

fvall=

37.0000

練習(I詒nx。

某快餐店一周中每天需要不同數(shù)目的雇員(gCiy陷n),設周一至少人，周二

至少(zhisl?諂o)人，周三至少(zhish*o)人，周四至少(zhishmo)人，周五至

少人，周六至少人，周日至少人，又規(guī)定雇員需連續(xù)工作5天，每人每

天的工資為C元。問快餐店怎樣聘用雇員才干滿足需求，又能使總聘用費用最

少。

提示：由于每一個雇員需連續(xù)工作5天，故快餐店聘用的總人數(shù)不一定是每

天聘用人數(shù)之和。我們定義周一開始工作的雇員數(shù)為，周日開始工作的雇

員數(shù)

為，則一周的聘用總費用為：，由于

除了周二和周三開始工作的雇員之外，其余的雇員都會在周一工作，所以周一

至少應有a人的約束應表示為：

1

類似地可以得出其他的約束條件。

現(xiàn)給定元，人'a?=15人y16人宣19人y14

人，a=12人，a=18人，請給出問題的數(shù)學模型，并用matlab求解。

67

內容總