最優(yōu)裝載問題及最優(yōu)化方法在資源配置方面的應(yīng)用

問題描述

有一批共個(gè)集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。

容易證明：如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。

(1)首先將第一艘輪船盡可能裝滿；

(2)將剩余的集裝箱裝上第二艘輪船。

1、隊(duì)列式分支限界法求解

在算法的循環(huán)體中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中(右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn))。2個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄。

活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記-1，故在取隊(duì)首元素時(shí)，活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是-1時(shí)，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列非空，則將尾部標(biāo)記-1加入活結(jié)點(diǎn)隊(duì)列，算法開始處理下一層的活結(jié)點(diǎn)。

節(jié)點(diǎn)的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量。則當(dāng)ew+r<bestw時(shí)，可將其右子樹剪去，因?yàn)榇藭r(shí)若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。另外，為了確保右子樹成功剪枝，應(yīng)該在算法每一次進(jìn)入左子樹的時(shí)候更新bestw的值。

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲(chǔ)相應(yīng)子集樹中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)志。

找到最優(yōu)值后，可以根據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。

算法具體代碼實(shí)現(xiàn)如下：

1、Queue.h[cpp]

\o"viewplain"viewplain

\o"copy"copy#include<iostream>

using

namespace

std;

template

<class

T>

class

Queue

{

public:

Queue(int

MaxQueueSize=50);

~Queue(){delete

[]

queue;}

bool

IsEmpty()const{return

front==rear;}

bool

IsFull(){return

(

(

(rear+1)

%MaxSize==front

)?1:0);}

T

Top()

const;

T

Last()

const;

Queue<T>&

Add(const

T&

x);

Queue<T>&

AddLeft(const

T&

x);

Queue<T>&

Delete(T

&x);

void

Output(ostream&

out)const;

int

Length(){return

(rear-front);}

private:

int

front;

int

rear;

int

MaxSize;

T

*queue;

};

template<class

T>

Queue<T>::Queue(int

MaxQueueSize)

{

MaxSize=MaxQueueSize+1;

queue=new

T[MaxSize];

front=rear=0;

}

template<class

T

>

T

Queue<T>::Top()const

{

if(IsEmpty())

{

cout<<"queue:no

element,no!"<<endl;

return

0;

}

else

return

queue[(front+1)

%

MaxSize];

}

template<class

T>

T

Queue<T>

::Last()const

{

if(IsEmpty())

{

cout<<"queue:no

element"<<endl;

return

0;

}

else

return

queue[rear];

}

template<class

T>

Queue<T>&

Queue<T>::Add(const

T&

x)

{

if(IsFull())cout<<"queue:no

memory"<<endl;

else

{

rear=(rear+1)%

MaxSize;

queue[rear]=x;

}

return

*this;

}

template<class

T>

Queue<T>&

Queue<T>::AddLeft(const

T&

x)

{

if(IsFull())cout<<"queue:no

memory"<<endl;

else

{

front=(front+MaxSize-1)%

MaxSize;

queue[(front+1)%

MaxSize]=x;

}

return

*this;

}

template<class

T>

Queue<T>&

Queue<T>

::Delete(T

&

x)

{

if(IsEmpty())cout<<"queue:no

element(delete)"<<endl;

else

{

front=(front+1)

%

MaxSize;

x=queue[front];

}

return

*this;

}

template<class

T>

void

Queue

<T>::Output(ostream&

out)const

{

for(int

i=rear%MaxSize;i>=(front+1)%MaxSize;i--)

out<<queue[i];

}

template<class

T>

ostream&

operator

<<

(ostream&

out,const

Queue<T>&

x)

{x.Output(out);return

out;}

2、6d3-1.cpp[cpp]

\o"viewplain"viewplain

\o"copy"copy//裝載問題

隊(duì)列式分支限界法求解

#include

"stdafx.h"

#include

"Queue.h"

#include

<iostream>

using

namespace

std;

const

int

N

=

4;

template<class

Type>

class

QNode

{

template<class

Type>

friend

void

EnQueue(Queue<QNode<Type>*>&Q,Type

wt,int

i,int

n,Type

bestw,QNode<Type>*E,QNode<Type>

*&bestE,int

bestx[],bool

ch);

template<class

Type>

friend

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[]);

private:

QNode

*parent;

//指向父節(jié)點(diǎn)的指針

bool

LChild;

//左兒子標(biāo)識(shí)

Type

weight;

//節(jié)點(diǎn)所相應(yīng)的載重量

};

template<class

Type>

void

EnQueue(Queue<QNode<Type>*>&Q,Type

wt,int

i,int

n,Type

bestw,QNode<Type>*E,QNode<Type>

*&bestE,int

bestx[],bool

ch);

template<class

Type>

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[]);

int

main()

{

float

c

=

70;

float

w[]

=

{0,20,10,26,15};//下標(biāo)從1開始

int

x[N+1];

float

bestw;

cout<<"輪船載重為："<<c<<endl;

cout<<"待裝物品的重量分別為："<<endl;

for(int

i=1;

i<=N;

i++)

{

cout<<w[i]<<"

";

}

cout<<endl;

bestw

=

MaxLoading(w,c,N,x);

cout<<"分支限界選擇結(jié)果為:"<<endl;

for(int

i=1;

i<=4;

i++)

{

cout<<x[i]<<"

";

}

cout<<endl;

cout<<"最優(yōu)裝載重量為："<<bestw<<endl;

return

0;

}

//將活節(jié)點(diǎn)加入到活節(jié)點(diǎn)隊(duì)列Q中

template<class

Type>

void

EnQueue(Queue<QNode<Type>*>&Q,Type

wt,int

i,int

n,Type

bestw,QNode<Type>*E,QNode<Type>

*&bestE,int

bestx[],bool

ch)

{

if(i

==

n)//可行葉節(jié)點(diǎn)

{

if(wt

==

bestw)

{

//當(dāng)前最優(yōu)裝載重量

bestE

=

E;

bestx[n]

=

ch;

}

return;

}

//非葉節(jié)點(diǎn)

QNode<Type>

*b;

b

=

new

QNode<Type>;

b->weight

=

wt;

b->parent

=

E;

b->LChild

=

ch;

Q.Add(b);

}

template<class

Type>

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[])

{//隊(duì)列式分支限界法，返回最優(yōu)裝載重量，bestx返回最優(yōu)解

//初始化

Queue<QNode<Type>*>

Q;

//活節(jié)點(diǎn)隊(duì)列

Q.Add(0);

//同層節(jié)點(diǎn)尾部標(biāo)識(shí)

int

i

=

1;

//當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層

Type

Ew

=

0,

//擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量

bestw

=

0,

//當(dāng)前最優(yōu)裝載重量

r

=

0;

//剩余集裝箱重量

for(int

j=2;

j<=n;

j++)

{

r

+=

w[j];

}

QNode<Type>

*E

=

0,

//當(dāng)前擴(kuò)展節(jié)點(diǎn)

*bestE;

//當(dāng)前最優(yōu)擴(kuò)展節(jié)點(diǎn)

//搜索子集空間樹

while(true)

{

//檢查左兒子節(jié)點(diǎn)

Type

wt

=

Ew

+

w[i];

if(wt

<=

c)//可行節(jié)點(diǎn)

{

if(wt>bestw)

{

bestw

=

wt;

}

EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);

}

//檢查右兒子節(jié)點(diǎn)

if(Ew+r>bestw)

{

EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);

}

Q.Delete(E);//取下一擴(kuò)展節(jié)點(diǎn)

if(!E)//同層節(jié)點(diǎn)尾部

{

if(Q.IsEmpty())

{

break;

}

Q.Add(0);

//同層節(jié)點(diǎn)尾部標(biāo)識(shí)

Q.Delete(E);

//取下一擴(kuò)展節(jié)點(diǎn)

i++;

//進(jìn)入下一層

r-=w[i];

//剩余集裝箱重量

}

Ew

=E->weight;

//新擴(kuò)展節(jié)點(diǎn)所對(duì)應(yīng)的載重量

}

//構(gòu)造當(dāng)前最優(yōu)解

for(int

j=n-1;

j>0;

j--)

{

bestx[j]

=

bestE->LChild;

bestE

=

bestE->parent;

}

return

bestw;

}

程序運(yùn)行結(jié)果如圖：

2、優(yōu)先隊(duì)列式分支限界法求解

解裝載問題的優(yōu)先隊(duì)列式分支限界法用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表?；罱Y(jié)點(diǎn)x在優(yōu)先隊(duì)列中的優(yōu)先級(jí)定義為從根結(jié)點(diǎn)到結(jié)點(diǎn)x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。

優(yōu)先隊(duì)列中優(yōu)先級(jí)最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。以結(jié)點(diǎn)x為根的子樹中所有結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過它的優(yōu)先級(jí)。子集樹中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同。

在優(yōu)先隊(duì)列式分支限界法中，一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。

算法具體代碼實(shí)現(xiàn)如下：

1、MaxHeap.h[cpp]

\o"viewplain"viewplain

\o"copy"copytemplate<class

T>

class

MaxHeap

{

public:

MaxHeap(int

MaxHeapSize

=

10);

~MaxHeap()

{delete

[]

heap;}

int

Size()

const

{return

CurrentSize;}

T

Max()

{

//查

if

(CurrentSize

==

0)

{

throw

OutOfBounds();

}

return

heap[1];

}

MaxHeap<T>&

Insert(const

T&

x);

//增

MaxHeap<T>&

DeleteMax(T&

x);

//刪

void

Initialize(T

a[],

int

size,

int

ArraySize);

private:

int

CurrentSize,

MaxSize;

T

*heap;

//

element

array

};

template<class

T>

MaxHeap<T>::MaxHeap(int

MaxHeapSize)

{//

Max

heap

constructor.

MaxSize

=

MaxHeapSize;

heap

=

new

T[MaxSize+1];

CurrentSize

=

0;

}

template<class

T>

MaxHeap<T>&

MaxHeap<T>::Insert(const

T&

x)

{//

Insert

x

into

the

max

heap.

if

(CurrentSize

==

MaxSize)

{

cout<<"no

space!"<<endl;

return

*this;

}

//

尋找新元素x的位置

//

i——初始為新葉節(jié)點(diǎn)的位置，逐層向上，尋找最終位置

int

i

=

++CurrentSize;

while

(i

!=

1

&&

x

>

heap[i/2])

{

//

i不是根節(jié)點(diǎn)，且其值大于父節(jié)點(diǎn)的值，需要繼續(xù)調(diào)整

heap[i]

=

heap[i/2];

//

父節(jié)點(diǎn)下降

i

/=

2;

//

繼續(xù)向上，搜尋正確位置

}

heap[i]

=

x;

return

*this;

}

template<class

T>

MaxHeap<T>&

MaxHeap<T>::DeleteMax(T&

x)

{//

Set

x

to

max

element

and

delete

max

element

from

heap.

//

check

if

heap

is

empty

if

(CurrentSize

==

0)

{

cout<<"Empty

heap!"<<endl;

return

*this;

}

x

=

heap[1];

//

刪除最大元素

//

重整堆

T

y

=

heap[CurrentSize--];

//

取最后一個(gè)節(jié)點(diǎn)，從根開始重整

//

find

place

for

y

starting

at

root

int

i

=

1,

//

current

node

of

heap

ci

=

2;

//

child

of

i

while

(ci

<=

CurrentSize)

{

//

使ci指向i的兩個(gè)孩子中較大者

if

(ci

<

CurrentSize

&&

heap[ci]

<

heap[ci+1])

{

ci++;

}

//

y的值大于等于孩子節(jié)點(diǎn)嗎？

if

(y

>=

heap[ci])

{

break;

//

是，i就是y的正確位置，退出

}

//

否，需要繼續(xù)向下，重整堆

heap[i]

=

heap[ci];

//

大于父節(jié)點(diǎn)的孩子節(jié)點(diǎn)上升

i

=

ci;

//

向下一層，繼續(xù)搜索正確位置

ci

*=

2;

}

heap[i]

=

y;

return

*this;

}

template<class

T>

void

MaxHeap<T>::Initialize(T

a[],

int

size,int

ArraySize)

{//

Initialize

max

heap

to

array

a.

delete

[]

heap;

heap

=

a;

CurrentSize

=

size;

MaxSize

=

ArraySize;

//

從最后一個(gè)內(nèi)部節(jié)點(diǎn)開始，一直到根，對(duì)每個(gè)子樹進(jìn)行堆重整

for

(int

i

=

CurrentSize/2;

i

>=

1;

i--)

{

T

y

=

heap[i];

//

子樹根節(jié)點(diǎn)元素

//

find

place

to

put

y

int

c

=

2*i;

//

parent

of

c

is

target

//

location

for

y

while

(c

<=

CurrentSize)

{

//

heap[c]

should

be

larger

sibling

if

(c

<

CurrentSize

&&

heap[c]

<

heap[c+1])

{

c++;

}

//

can

we

put

y

in

heap[c/2]?

if

(y

>=

heap[c])

{

break;

//

yes

}

//

no

heap[c/2]

=

heap[c];

//

move

child

up

c

*=

2;

//

move

down

a

level

}

heap[c/2]

=

y;

}

}

2、6d3-2.cpp[cpp]

\o"viewplain"viewplain

\o"copy"copy//裝載問題

優(yōu)先隊(duì)列式分支限界法求解

#include

"stdafx.h"

#include

"MaxHeap.h"

#include

<iostream>

using

namespace

std;

const

int

N

=

4;

class

bbnode;

template<class

Type>

class

HeapNode

{

template<class

Type>

friend

void

AddLiveNode(MaxHeap<HeapNode<Type>>&

H,bbnode

*E,Type

wt,bool

ch,int

lev);

template<class

Type>

friend

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[]);

public:

operator

Type()

const{return

uweight;}

private:

bbnode

*ptr;

//指向活節(jié)點(diǎn)在子集樹中相應(yīng)節(jié)點(diǎn)的指針

Type

uweight;

//活節(jié)點(diǎn)優(yōu)先級(jí)(上界)

int

level;

//活節(jié)點(diǎn)在子集樹中所處的層序號(hào)

};

class

bbnode

{

template<class

Type>

friend

void

AddLiveNode(MaxHeap<HeapNode<Type>>&

H,bbnode

*E,Type

wt,bool

ch,int

lev);

template<class

Type>

friend

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[]);

friend

class

AdjacencyGraph;

private:

bbnode

*parent;

//指向父節(jié)點(diǎn)的指針

bool

LChild;

//左兒子節(jié)點(diǎn)標(biāo)識(shí)

};

template<class

Type>

void

AddLiveNode(MaxHeap<HeapNode<Type>>&

H,bbnode

*E,Type

wt,bool

ch,int

lev);

template<class

Type>

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[]);

int

main()

{

float

c

=

70;

float

w[]

=

{0,20,10,26,15};//下標(biāo)從1開始

int

x[N+1];

float

bestw;

cout<<"輪船載重為："<<c<<endl;

cout<<"待裝物品的重量分別為："<<endl;

for(int

i=1;

i<=N;

i++)

{

cout<<w[i]<<"

";

}

cout<<endl;

bestw

=

MaxLoading(w,c,N,x);

cout<<"分支限界選擇結(jié)果為:"<<endl;

for(int

i=1;

i<=4;

i++)

{

cout<<x[i]<<"

";

}

cout<<endl;

cout<<"最優(yōu)裝載重量為："<<bestw<<endl;

return

0;

}

//將活節(jié)點(diǎn)加入到表示活節(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆H中

template<class

Type>

void

AddLiveNode(MaxHeap<HeapNode<Type>>&

H,bbnode

*E,Type

wt,bool

ch,int

lev)

{

bbnode

*b

=

new

bbnode;

b->parent

=

E;

b->LChild

=

ch;

HeapNode<Type>

N;

N.uweight

=

wt;

N.level

=

lev;

N.ptr

=

b;

H.Insert(N);

}

//優(yōu)先隊(duì)列式分支限界法，返回最優(yōu)載重量，bestx返回最優(yōu)解

template<class

Type>

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[])

{

//定義最大的容量為1000

MaxHeap<HeapNode<Type>>

H(1000);

//定義剩余容量數(shù)組

Type

*r

=

new

Type[n+1];

r[n]

=

0;

for(int

j=n-1;

j>0;

j--)

{

r[j]

=

r[j+1]

+

w[j+1];

}

//初始化

int

i

=

1;//當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層

bbnode

*E

=

0;//當(dāng)前擴(kuò)展節(jié)點(diǎn)

Type

Ew

=

0;

//擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量

//搜索子集空間樹

while(i!=n+1)//非葉子節(jié)點(diǎn)

{

//檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的兒子節(jié)點(diǎn)

if(Ew+w[i]<=c)

{

AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);

}

//右兒子節(jié)點(diǎn)

AddLiveNode(H,E,Ew+r[i],false,i+1);

//取下一擴(kuò)展節(jié)點(diǎn)

HeapNode<Type>

N;

H.DeleteMax(N);//非空

i

=

N.level;

E

=

N.ptr;

Ew

=

N.uweight

-

r[i-1];

}

//構(gòu)造當(dāng)前最優(yōu)解

for(int

j=n;

j>0;

j--)

{

bestx[j]

=

E->LChild;

E

=

E->parent;

}

return

Ew;

}

程序運(yùn)行結(jié)果如圖：本科畢業(yè)設(shè)計(jì)（論文）最優(yōu)化方法在資源配置方面的應(yīng)用學(xué)院應(yīng)用數(shù)學(xué)學(xué)院專業(yè)信息與計(jì)算科學(xué)（信息計(jì)算方向）年級(jí)班別學(xué)號(hào)學(xué)生姓名指導(dǎo)教師摘要數(shù)學(xué)與我們?nèi)粘Ｉ钕⑾⑾嚓P(guān)，如何將數(shù)學(xué)最優(yōu)化問題有效的結(jié)合到生活實(shí)際中，是當(dāng)今面臨的最熱門話題。最優(yōu)化方法是一門應(yīng)用相當(dāng)廣泛的學(xué)科，它主要研究在眾多方案中選擇最佳方案，因而被廣泛而深入的應(yīng)用于生活中生產(chǎn)、管理等領(lǐng)域，例如，資源配置、生產(chǎn)計(jì)劃等。因此，對(duì)最優(yōu)化方法在生活中的應(yīng)用研究具有重要的意義。本論文主要研究最優(yōu)化方法在生活中生產(chǎn)、管理資源配置方面問題中的應(yīng)用，具體介紹了最優(yōu)化方法中的線性規(guī)劃模型和動(dòng)態(tài)規(guī)劃模型及其它們?cè)谫Y源配置方面的應(yīng)用。本文的主要內(nèi)容和成果就是介紹了線性規(guī)劃模型在生活中生產(chǎn)計(jì)劃制定的應(yīng)用以及多階段的動(dòng)態(tài)規(guī)劃模型在生活中資源分配問題上的應(yīng)用，并用相應(yīng)的數(shù)學(xué)軟件Lindo及算法解決對(duì)應(yīng)的實(shí)例。本文所建立的數(shù)學(xué)模型有成熟的理論基礎(chǔ)，又有相應(yīng)的生活實(shí)例的支持，可信度高，對(duì)最優(yōu)化方法在資源配置方面的應(yīng)用研究具有重要參考意義。關(guān)鍵字：最優(yōu)化方法，線性規(guī)劃，動(dòng)態(tài)規(guī)劃，資源配置AbstractMathematicsiscloselyrelatedtoourdailylife.Howwillthemathematicaloptimizationproblemeffectivelycombinedtoreallife,isthemostpopulartopictodayisfacing.Theoptimizationmethodisawidelyuseddiscipline,itmainlystudiestheselectionoftheoptimumschemeinmanyschemes,soithasbeenwidelyanddeeplyusedinlifeintheproduction,managementandotherfields,forexample,theallocationofresources,productionplan.Therefore,hasthevitalsignificancetotheresearchonApplicationofoptimizationmethodinlife.Applicationofmanagementresourcesallocationproblemthisthesismainlystudiestheoptimizationmethodofproduction,inlife,andintroducestheapplicationofoptimizationmethodinthelinearprogrammingmodelandadynamicprogrammingmodelandintheallocationofresources.Themaincontentsandresultsinthispaperisintroducedtheapplicationoflinearprogrammingmodelinthelifeoftheproductionplanninganddynamicplanningmodelofmulti-stageinliferesourceallocationproblems,examplesandbyusingmathematicalsoftwareLindoandcorrespondingalgorithmtosolvethecorresponding.Themathematicalmodelproposedinthispaperhasthematuretheories,andrelevantexamplesfromreallifesupport,highreliability,isanimportantapplicationintheallocationofresourcestotheoptimizationmethod.Keyword:Optimizationmethod,Linearprogramming,Dynamicprogramming,Resourceallocation目錄1緒論12線性規(guī)劃模型及其應(yīng)用32.1線性規(guī)劃32.2對(duì)偶線性規(guī)劃及其影子價(jià)格42.3線性規(guī)劃的靈敏度分析52.4線性規(guī)劃模型在生產(chǎn)中資源配置方面的應(yīng)用舉例72.5本章小結(jié)93多階段的動(dòng)態(tài)規(guī)劃模型103.1資源分配問題上的動(dòng)態(tài)規(guī)劃模型103.2動(dòng)態(tài)規(guī)劃模型在資源分配問題的應(yīng)用舉例113.3本章小結(jié)15結(jié)論16參考文獻(xiàn)18致謝191緒論最優(yōu)化方法[1,3,5]（也稱做運(yùn)籌學(xué)方法）是近幾十年形成的，它主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問題，是系統(tǒng)工程的基礎(chǔ)理論之一，最優(yōu)化方法強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的主要研究對(duì)象是各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營(yíng)活動(dòng)。最優(yōu)化方法的目的在于針對(duì)所研究的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物力和財(cái)力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。最優(yōu)化方法在工業(yè)、農(nóng)業(yè)、物流、經(jīng)濟(jì)計(jì)劃、人力資源、軍事等行業(yè)都有著非常廣泛的應(yīng)用。有人曾對(duì)世界上500家著名的企業(yè)集團(tuán)或跨國(guó)公司進(jìn)行過調(diào)查，發(fā)現(xiàn)其中95%曾使用過線性規(guī)劃，75%使用過運(yùn)輸模型，90%使用過網(wǎng)絡(luò)計(jì)劃技術(shù)，43%使用過動(dòng)態(tài)規(guī)劃。由此可見最優(yōu)化方法是一門應(yīng)用性很強(qiáng)的學(xué)科。特別是隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，最優(yōu)化方法各種優(yōu)化模型的求解過程都可以通過專門的應(yīng)用軟件來(lái)完成，因此，最優(yōu)化方法越來(lái)越顯示出其廣泛的使用價(jià)值。資源配置(resourceallocation)是指對(duì)相對(duì)稀缺的資源在各種不同用途上加以比較作出的選擇。資源是指社會(huì)經(jīng)濟(jì)活動(dòng)中人力、物力和財(cái)力的總和，是社會(huì)經(jīng)濟(jì)發(fā)展的基本物質(zhì)條件。在社會(huì)經(jīng)濟(jì)發(fā)展的一定階段上，相對(duì)于人們的需求而言，資源總是表現(xiàn)出相對(duì)的稀缺性，從而要求人們對(duì)有限的、相對(duì)稀缺的資源進(jìn)行合理配置，以便用最少的資源耗費(fèi)，生產(chǎn)出最適用的商品和勞務(wù)，獲取最佳的效益。資源配置合理與否，對(duì)一個(gè)國(guó)家經(jīng)濟(jì)發(fā)展的成敗有著極其重要的影響。對(duì)于如今競(jìng)爭(zhēng)非常激烈的現(xiàn)實(shí)生活中，如何最合理地配置生活中生產(chǎn)、管理中的有限資源，取得最好的經(jīng)濟(jì)效益，當(dāng)今面臨的最熱門話題。這也是生活中各類決策者所要考慮到的，首先，要先制定一個(gè)最優(yōu)化的模型，然而，這些模型不是一成不變的，由于市場(chǎng)需求的不確定因素，針對(duì)不同的最優(yōu)化問題，我們要具體問題具體分析，根據(jù)具體情況，制定一個(gè)最適合的最優(yōu)化模型。因此，自最優(yōu)化方法提出后，國(guó)內(nèi)外對(duì)資源配置方面進(jìn)行了大量的研究，并提出了一系列算法解決此問題。當(dāng)然，我們的研究受到各種因素的影響，存在著非結(jié)構(gòu)性的復(fù)雜問題，僅用數(shù)學(xué)模型是很難加以描述和解決的?？傊?，隨著社會(huì)的不斷發(fā)展和進(jìn)步，實(shí)踐將對(duì)最優(yōu)化方法提出更新更多的研究課題，最優(yōu)化方法正處于不斷發(fā)展、不斷進(jìn)步的時(shí)期。本文將介紹最優(yōu)化方法模型的建立和模型的分析、求解，探討其在生活中生產(chǎn)、管理資源配置方面問題中的應(yīng)用。主要是線性規(guī)劃問題的模型、求解（線性規(guī)劃問題的單純形解法）及其應(yīng)用——生產(chǎn)計(jì)劃；以及動(dòng)態(tài)規(guī)劃的模型、求解、應(yīng)用――資源分配問題。2線性規(guī)劃模型及其應(yīng)用隨著國(guó)際經(jīng)濟(jì)貿(mào)易的發(fā)展，國(guó)際社會(huì)的競(jìng)爭(zhēng)越來(lái)越劇烈，如何最合理地配置企業(yè)有限資源，取得最佳經(jīng)濟(jì)效益，已經(jīng)成為我們目前急需解決的一大問題。在現(xiàn)實(shí)生產(chǎn)管理的經(jīng)營(yíng)活動(dòng)中，通常需要對(duì)“有限的資源”尋求“最佳”的利用或分配方式。任何資源，如勞動(dòng)力、原材料、設(shè)備或資金等都是有限的。因此，必須進(jìn)行合理的配置，尋求最佳的利用方式。所謂的最佳的方式，必須有一個(gè)標(biāo)準(zhǔn)或目標(biāo)，這個(gè)標(biāo)準(zhǔn)或目標(biāo)就是使利潤(rùn)達(dá)到最大或成本達(dá)到最小。尤其對(duì)于一些大批生產(chǎn)的企業(yè)，在有限資源的條件下，為滿足市場(chǎng)的需求，如何充分發(fā)揮現(xiàn)有生產(chǎn)能力，以最小的投入取得最大的經(jīng)濟(jì)效益?如何在生產(chǎn)計(jì)劃中確定最佳產(chǎn)品組合？最佳經(jīng)濟(jì)效益目標(biāo)可以是多少？這些都是最優(yōu)化的設(shè)計(jì)問題。對(duì)于這些制定企業(yè)生產(chǎn)計(jì)劃，最有效方法就是線性規(guī)劃。然而，企業(yè)最優(yōu)生產(chǎn)問題不僅僅是將企業(yè)現(xiàn)有資源按照效益最大或成本最低的原則在多項(xiàng)生產(chǎn)任務(wù)中進(jìn)行分配的問題，還應(yīng)該是合理組織資源使企業(yè)的生產(chǎn)任務(wù)最大限度滿足市場(chǎng)需求的問題，而線性規(guī)劃也只能解決將企業(yè)現(xiàn)有資源按照效益最大或成本最低的原則在多項(xiàng)生產(chǎn)任務(wù)中進(jìn)行分配的問題。這其中的原因主要是我們?cè)诶镁€性規(guī)劃制定生產(chǎn)計(jì)劃時(shí)，將資源約束作為剛性約束來(lái)處理，沒有去考慮在市場(chǎng)環(huán)境下部分資源約束是彈性約束。可見，此類問題切不可直接用線性規(guī)劃。對(duì)于這類組織資源使企業(yè)的生產(chǎn)任務(wù)最大限度滿足市場(chǎng)需求的問題，我們現(xiàn)在經(jīng)常采用到線性規(guī)劃的對(duì)偶規(guī)劃。本章將在線性規(guī)劃的理論基礎(chǔ)上，根據(jù)線性規(guī)劃互補(bǔ)最優(yōu)性條件，進(jìn)一步討論最優(yōu)生產(chǎn)問題的對(duì)偶規(guī)劃模型，對(duì)影響企業(yè)資源變化的影子價(jià)格也進(jìn)行了分析和研究，再通過靈敏度分析，對(duì)線性規(guī)劃問題的數(shù)據(jù)集合進(jìn)行進(jìn)一步了解，并用生活中生產(chǎn)計(jì)劃的實(shí)例進(jìn)行了論證。2.1線性規(guī)劃線性規(guī)劃[1,5]就是由目標(biāo)函數(shù)為決策變量的線性函數(shù)和約束條件為線性等式或線性不等式所組成的數(shù)學(xué)規(guī)劃。它是數(shù)學(xué)規(guī)劃中較簡(jiǎn)單的一類，也是最基本的一類數(shù)學(xué)規(guī)劃問題。其實(shí)質(zhì)是在一組線性約束條件下，尋找一組決策變量使得目標(biāo)函數(shù)取得最大或最小的條件極值問題。可見，線性規(guī)劃模型基本上是確定的，它的模型建立過程為確定決策變量、確定目標(biāo)函數(shù)、確定約束條件。該線性規(guī)劃模型常用于有限資源的分配問題。設(shè)為決策變量，為價(jià)值系數(shù)，為消耗系數(shù)，為資源限制系數(shù)，則標(biāo)準(zhǔn)的線性規(guī)劃模型表示如下：（1）其中線性規(guī)劃的基本定理:如果可行域非空有界，那么線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域D上的頂點(diǎn)上達(dá)到最優(yōu)值。根據(jù)線性規(guī)劃基本定理，啟發(fā)了Dantzig的單純形法，即將尋優(yōu)的目標(biāo)集中在D上各個(gè)頂點(diǎn)上。單純形法是求解線性規(guī)劃問題的一種通用的有效算法，它的基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。設(shè)B是由A中m個(gè)線性無(wú)關(guān)的列向量組成的一個(gè)基，，其中為基B對(duì)應(yīng)的基變量和價(jià)值系數(shù)，為N對(duì)應(yīng)的非基變量和價(jià)值系數(shù)。定理1最優(yōu)解判別定理:對(duì)于線性規(guī)劃問題，若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，那這個(gè)基本可行解就是最優(yōu)解。上面討論的是一般的線性規(guī)劃模型以及最優(yōu)解的求法。然而，現(xiàn)實(shí)生活中，常常遇到的不是僅僅靠一般的線性規(guī)劃模型就能解決的生產(chǎn)方面資源配置問題。下面我們?cè)龠M(jìn)一步討論線性規(guī)劃的對(duì)偶規(guī)劃問題。2.2對(duì)偶線性規(guī)劃及其影子價(jià)格對(duì)偶理論[5]是線性規(guī)劃的重要內(nèi)容之一。隨著線性規(guī)劃問題研究的深入，人們發(fā)現(xiàn)對(duì)應(yīng)于每個(gè)線性規(guī)劃問題都伴生著一個(gè)相應(yīng)的線性規(guī)劃問題。前者是由矩陣A、右端向量b和價(jià)值向量C定義的，稱之為原問題；后者也是有相同的數(shù)據(jù)集合A、b和C構(gòu)成，稱之為原問題的對(duì)偶問題。上述的線性規(guī)劃模型（1）的對(duì)偶問題可表示如下：（2）由線性規(guī)劃的對(duì)偶理論可以知道：如果原問題（1）有最優(yōu)解，那么對(duì)偶問題（2）也有最優(yōu)解，并且兩者的目標(biāo)函數(shù)值相等，即有：。為對(duì)偶問題最優(yōu)解，它代表在資源最優(yōu)利用下，對(duì)各種單位資源的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻(xiàn)而作出的估價(jià)，簡(jiǎn)稱影子價(jià)格。影子價(jià)格的大小客觀地反映了各種資源在系統(tǒng)內(nèi)稀缺程度，會(huì)直接關(guān)系到資源的最有效利用。影子價(jià)格是一種編輯價(jià)格，的值相當(dāng)于在資源得到最優(yōu)利用的條件下，每增加1個(gè)單位時(shí)，目標(biāo)函數(shù)Z的增加值。影子價(jià)格的大小客觀地反映了各種不同資源在系統(tǒng)內(nèi)的稀缺程度，同時(shí)也是一種成本機(jī)會(huì)，在市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)這種資源用于擴(kuò)大生產(chǎn)；相反當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格，企業(yè)應(yīng)賣出這種資源。隨著資源的買進(jìn)賣出，企業(yè)資源的影子價(jià)格也隨著發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。由此可見企業(yè)資源的影子價(jià)格直接關(guān)系到資源的最有效利用，根據(jù)影子價(jià)格企業(yè)可以對(duì)有限的資源進(jìn)行合理的配置，自主地節(jié)約使用某種稀缺資源，使有限資源發(fā)揮更大的經(jīng)濟(jì)效益。2.3線性規(guī)劃的靈敏度分析線性規(guī)劃問題所對(duì)應(yīng)的數(shù)據(jù)集合A、b、C常常是通過預(yù)測(cè)或估計(jì)所得到的的統(tǒng)計(jì)數(shù)據(jù)，可能存在一定的誤差。同時(shí)，隨著市場(chǎng)環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)也可能發(fā)生變化。那么，就有必要去分析下這些數(shù)據(jù)波動(dòng)時(shí)，對(duì)當(dāng)前的最優(yōu)解或最優(yōu)基產(chǎn)生什么影響，即是所謂的靈敏度分析。此外，在生產(chǎn)計(jì)劃中，對(duì)于給定的目標(biāo)點(diǎn)，要想使之成為最優(yōu)解，可以通過三條途徑來(lái)實(shí)現(xiàn)[10]，即：1、通過改變模型（1）的目標(biāo)函數(shù)中價(jià)值系數(shù)C，使得給定的目標(biāo)解成為最優(yōu)解。由于不改變可行域D，因此，預(yù)期目標(biāo)解必須是線性規(guī)劃原問題的可行解；2、通過改變模型（1）中資源擁有量b，使得預(yù)期目標(biāo)解成為可行解。由于可行域D的擴(kuò)張或平移，因此，給定的目標(biāo)解可以不是線性規(guī)劃原問題的可行解。3、通過改變模型（1）中資源消耗系數(shù)，即約束函數(shù)的斜率A,使得預(yù)期目標(biāo)解成為可行解。由于可行域D的形狀發(fā)生了變化，因此，給定的目標(biāo)解可以不是線性規(guī)劃原問題的可行解。下面，我們分別討論當(dāng)價(jià)值系數(shù)C、資源擁有量b和資源消耗系數(shù)向量A變化的響應(yīng)情況：1、考慮只有價(jià)值向量C的改變的情形。若是非基變量的價(jià)值系數(shù)，為該價(jià)值系數(shù)的改變量，只要，就可以保持現(xiàn)行最優(yōu)解依舊最優(yōu)，由此可以確定價(jià)值系數(shù)的可變化范圍，其中為的檢驗(yàn)數(shù)。若是某基變量的價(jià)值系數(shù)，為該價(jià)值系數(shù)的改變量，只要非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)，就可以保持現(xiàn)行最優(yōu)解依舊最優(yōu)，由此可以確定價(jià)值系數(shù)的可變化范圍。2、考慮只有資源擁有量b的改變的情形。B的波動(dòng)會(huì)使最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值，但可以不改變?cè)顑?yōu)基B，只要即可，其中為原最優(yōu)解。3、考慮只有資源消耗系數(shù)A的改變的情形。一般而言，約束矩陣A的改變可能導(dǎo)致不同的最優(yōu)解和最優(yōu)基，進(jìn)行靈敏度分析不是一件簡(jiǎn)單的事。下面，只談及兩種較簡(jiǎn)單的情形。增加一個(gè)新變量，假設(shè)在獲得原線性規(guī)劃的最優(yōu)解之后，又發(fā)現(xiàn)了一個(gè)新變量，其對(duì)應(yīng)的價(jià)值系數(shù)為，在新的約束矩陣中對(duì)應(yīng)的系數(shù)列向量為，于是得到如下新的線性規(guī)劃問題：；增加一個(gè)約束，不妨假設(shè)此附加的約束條件為不等式形式，即，其中是n維行向量，為右端項(xiàng)系數(shù)，于是新的線性規(guī)劃模型變?yōu)椤?.4線性規(guī)劃模型在生產(chǎn)中資源配置方面的應(yīng)用舉例一豆制品加工廠[4,9]用黃豆生產(chǎn)A，B，C三種豆制品，1公斤黃豆可以在甲類設(shè)備上用12小時(shí)加工成3公斤A，或者在乙類設(shè)備上用8小時(shí)加工成4公斤B，或者在丙類設(shè)備上用6小時(shí)加工成4公斤C。根據(jù)市場(chǎng)需求，生產(chǎn)的A，B，C全部能售出，且每公斤A獲利24元，每公斤B獲利16元，每公斤C獲利12元?，F(xiàn)在加工廠每天能得到120公斤黃豆的供應(yīng)，每天正式工人總的工作時(shí)間為960小時(shí)，并且甲類設(shè)備每天至多能加工100公斤A，乙類設(shè)備每天至多能加工120公斤B，丙類設(shè)備的加工能力沒有限制。1、為該廠制定一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大。2、若用16元可以買到1公斤黃豆，應(yīng)否作這項(xiàng)投資？若投資，每天最多購(gòu)買多少公斤黃豆？3、若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？4、由于市場(chǎng)需求變化，每公斤C的獲利增加到14元，應(yīng)否改變生產(chǎn)計(jì)劃？2.4.1變量說(shuō)明Z盈利（元）生產(chǎn)A所用的黃豆重量（公斤）生產(chǎn)B所用的黃豆重量（公斤）生產(chǎn)C所用的黃豆重量（公斤）2.4.2問題分析本問題的目標(biāo)是使得該廠每天獲利最大，要做的決策是生產(chǎn)計(jì)劃，即如何合理配置黃豆，分別用多少公斤黃豆生產(chǎn)豆制品A，B，C。決策收到的限制：原料供應(yīng)、勞動(dòng)時(shí)間、設(shè)備的加工能力。按照問題，將決策變量、目標(biāo)函數(shù)和約束條件用數(shù)學(xué)符號(hào)及式子表示出來(lái)，就可得到下面的線性規(guī)劃模型。2.4.3模型假設(shè)假設(shè)1：A，B，C每公斤的獲利與它們各自產(chǎn)量無(wú)關(guān)；假設(shè)2：A，B，C每公斤的獲利與它們相互間產(chǎn)量無(wú)關(guān)；假設(shè)3：加工A，B，C的黃豆的重量可以是任意實(shí)數(shù)。2.4.4模型建立2.4.5模型求解將上述模型輸入LINDO求解，可以得到以下結(jié)果（見圖2.1）：圖2.1求解結(jié)果2.4.6結(jié)果分析1、圖2.1的第2,3,4,5,6行明確地告訴我們，這個(gè)線性規(guī)劃的最優(yōu)解為，最優(yōu)值為Z=6960，即該廠的生產(chǎn)計(jì)劃為：每天用30公斤黃豆生產(chǎn)A，每天用30公斤黃豆生產(chǎn)B，每天用60公斤黃豆生產(chǎn)C，這樣能使每天獲利最大，獲利6960元。2、圖2.1的第8行“DUALPRICES”告訴我們，增加1公斤黃豆時(shí)利潤(rùn)增長(zhǎng)24元，即1公斤黃豆的影子價(jià)格為24元；圖2.1的第23行“CURRENTRHS”的“ALLOWABLEINCREASE”和“ALLOWABLEDECREASE”給出了黃豆的影子價(jià)格有意義條件下約束右端的限制范圍：黃豆最多增加30公斤。綜上，用16元可以買到1公斤黃豆，低于1公斤黃豆的影子價(jià)格，應(yīng)該做這項(xiàng)投資，但每天最多購(gòu)買30公斤黃豆。3、圖2.1的第9行“DUALPRICES”告訴我們，勞動(dòng)時(shí)間增加1小時(shí)時(shí)利潤(rùn)增長(zhǎng)4元，即1小時(shí)勞動(dòng)的影子價(jià)格為4元。綜上，聘用臨時(shí)工人，付給的工資應(yīng)低于勞動(dòng)時(shí)間的影子價(jià)格才可以增加利潤(rùn)，所以工資最多是每小時(shí)4元。4、圖2.1的第19行“CURRENTCOEF”的“ALLOWABLEINCREASE”和“ALLOWABLEDECREASE”給出了最優(yōu)解不變條件下目標(biāo)函數(shù)系數(shù)的允許變化范圍：的系數(shù)為（48-12,48+12），即（36,60）。注意：系數(shù)的允許范圍需要的系數(shù)不變。綜上，若每公斤C的獲利增加到14元，則系數(shù)變?yōu)?4*4=56，在允許范圍內(nèi)，所以不應(yīng)改變生產(chǎn)計(jì)劃。2.5本章小結(jié)本章所探討的線性規(guī)劃模型，常用單純形法求解。線性規(guī)劃模型日益成熟，在生活各方面都會(huì)經(jīng)常用到線性規(guī)劃模型，通過對(duì)線性規(guī)劃模型的數(shù)據(jù)A，b，C進(jìn)行靈敏度分析，可以盡可能控制這些數(shù)據(jù)的變化范圍，使得企業(yè)保持一定的收益。此外，對(duì)于影響決策的資源占有量b的影子價(jià)格，可以對(duì)現(xiàn)有資源實(shí)現(xiàn)最大收益時(shí)估價(jià)，可以使資源合理配置，使資源發(fā)揮最大的經(jīng)濟(jì)效益。3多階段的動(dòng)態(tài)規(guī)劃模型所謂多階段決策問題[1]是指這樣一類活動(dòng)過程：它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段上都需要作出決策，而一個(gè)階段的決策確定以后，將會(huì)影響以后各階段的活動(dòng)及其決策，當(dāng)所有階段的決策確定后，就完全確定了該問題的活動(dòng)過程。各個(gè)階段所確定的決策就構(gòu)成了一個(gè)決策序列，成為一個(gè)策略，一般來(lái)說(shuō)，由于每一階段可供選擇的決策往往不止一個(gè)，因此，對(duì)于整個(gè)過程，就會(huì)有許多可供選擇的策略。若對(duì)應(yīng)于一個(gè)策略，可以由一個(gè)量化的指標(biāo)來(lái)確定這個(gè)策略所對(duì)應(yīng)的活動(dòng)過程的效果，那么，不同的策略就有各自的效果。在所有可供選擇的策略中，對(duì)應(yīng)效果最好的策略稱為最優(yōu)策略。把一個(gè)問題劃分成若干個(gè)相互聯(lián)系的階段，選取其最優(yōu)策略，這類問題就是多階段決策問題。它要求決策者不能用孤立的觀點(diǎn)看待各階段的決策。多階段決策問題，不論其本身是否與時(shí)間有關(guān)，由于分為階段來(lái)依次解決，這便具有了明顯的時(shí)序性，而在各階段中所采取的決策是隨階段而變動(dòng)的，不同階段采取不同決策，這便是“動(dòng)態(tài)”的含義。動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種常見方法。動(dòng)態(tài)規(guī)劃把比較復(fù)雜的問題劃分成若干階段，通過逐段求解，最終得到全局最優(yōu)解。這種“分而治之，逐步改善”的方法已在一些較難解決的問題中顯示出了優(yōu)越性，尤其是離散性問題，用動(dòng)態(tài)規(guī)劃的方法去處理，比用線性規(guī)劃或非線性規(guī)劃方法有時(shí)更為有效。此外，雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。迄今為止，動(dòng)態(tài)規(guī)劃模型已廣泛應(yīng)用于經(jīng)濟(jì)、生物、工程、軍事等許多領(lǐng)域，并取得了很好的效果。本章具體研究多階段的動(dòng)態(tài)規(guī)劃模型及其在資源分配問題上的實(shí)例應(yīng)用。3.1資源分配問題上的動(dòng)態(tài)規(guī)劃模型所謂“資源分配問題”就是把一定數(shù)量的若干資源合理地分配給若干個(gè)使用者，使指標(biāo)函數(shù)達(dá)到最優(yōu)。這里僅討論一種資源的分配問題。其一般提法是，設(shè)某種資源的總量為a，擬用于n項(xiàng)經(jīng)營(yíng)活動(dòng)，若給第j項(xiàng)活動(dòng)分配個(gè)單位，其收益為，問應(yīng)如何分配，才能使這n項(xiàng)經(jīng)營(yíng)活動(dòng)總的收益值最大？對(duì)于該問題，我們可以直接表示為因此，可用非線性規(guī)劃方法求解。但是利用這類問題的特性，也可以把它看做一個(gè)多階段決策問題，建立如下的動(dòng)態(tài)規(guī)劃模型：1、以階段變量k表示資源分配給第k項(xiàng)經(jīng)營(yíng)活動(dòng)的過程；2、以狀態(tài)變量表示在開始給第k項(xiàng)經(jīng)營(yíng)活動(dòng)分配資源時(shí)尚剩余的資源數(shù)量；3、以決策變量表示分配給第k項(xiàng)經(jīng)營(yíng)活動(dòng)的資源數(shù)量，則允許決策集合為；4、狀態(tài)轉(zhuǎn)移方程為；5、以表示從現(xiàn)有個(gè)單位資源中分配給第k項(xiàng)經(jīng)營(yíng)活動(dòng)個(gè)單位資源后的預(yù)計(jì)收益；6、以表示從現(xiàn)有個(gè)單位資源中分配給第k項(xiàng)到第n項(xiàng)經(jīng)營(yíng)活動(dòng)后，所得的最大利益，則函數(shù)基本方程為3.2動(dòng)態(tài)規(guī)劃模型在資源分配問題的應(yīng)用舉例某工廠擬將5臺(tái)先進(jìn)設(shè)備分配給下屬的甲、乙、丙三個(gè)分廠，分廠獲得該設(shè)備后每年為總廠提供的盈利如下表所示(如表3.1)：表3.1各分廠獲得該設(shè)備后每年為總廠提供的盈利分廠分分分廠盈利（萬(wàn)元）元）設(shè)備（臺(tái)）012345甲乙丙000354710691112121112131112試問：該工廠如何分配這些設(shè)備，才能使總廠的盈利最大？3.2.1變量說(shuō)明k表示給甲、乙、丙三個(gè)分廠分配的過程，其中k=1,2,3表示在開始給第k個(gè)分廠分配時(shí)尚未分配的臺(tái)數(shù)表示分配給第k分廠的臺(tái)數(shù)表示從現(xiàn)有臺(tái)中分配給第k分廠臺(tái)后的預(yù)計(jì)盈利表示從現(xiàn)有臺(tái)中分配給第k分廠到第3分廠后，所得的最大盈利3.2.2問題分析本問題可以看做一個(gè)多階段決策問題，采用動(dòng)態(tài)規(guī)劃方法解決之，將問題分為3個(gè)子問題，分別作出決策，最終得到一個(gè)策略，使得工廠獲得最大盈利。3.2.3模型假設(shè)假設(shè)1：設(shè)備不會(huì)出現(xiàn)故障，影響盈利；假設(shè)2：甲乙丙三者的單位利潤(rùn)與它們相互間箱數(shù)無(wú)關(guān)；假設(shè)3：甲乙丙三者的設(shè)備臺(tái)數(shù)可以是任意整數(shù)。3.2.4模型建立3.2.5模型求解1、算法描述根據(jù)以上的模型，可設(shè)計(jì)解資源分配問題的動(dòng)態(tài)規(guī)劃算法[2,6]maxprofit如下：publicstaticvoidmaxprofit(intn,intm,int[][]v,int[][]p){//該maxprofit函數(shù)主要得到問題的最優(yōu)值，即資源分配問題的總盈利//n:設(shè)備數(shù)量;m:分廠數(shù)量//v[i][j]:i臺(tái)設(shè)備提供給第j分廠將得到的盈利//p[i][j]:記錄f[i][j]的值是由哪一個(gè)子問題的解得到.//f[i][j]:用i臺(tái)設(shè)備分配給后j個(gè)分廠將得到的盈利int[][]f=newint[n+1][m+1];for(inti=1;i<=n;i++)f[i][0]=0;for(intj=1;j<=m;j++)f[0][j]=0;for(inti=1;i<=n;i++){f[i][m]=v[i][m];p[i][m]=i;}for(intj=m-1;j>=1;j--)for(inti=1;i<=n;i++)for(intk=0;k<=i;k++){if(f[i][j]<f[i-k][j+1]+v[k][j]){f[i][j]=f[i-k][j+1]+v[k][j];p[i][j]=k;}}System.out.printf("最大獲利是：%2d萬(wàn)元\n",f[n][1]);}publicstaticvoiddistribution(intn,intm,int[][]p){//該distribution得到問題的最優(yōu)解，即資源分配問題的資源分配方案intk=n;System.out.print("資源分配方案：\n");for(intj=1;j<=m;j++){System.out.printf("%1d臺(tái)設(shè)備分配給第%1d分廠使用\n",p[k][j],j);k=k-p[k][j];}}2、運(yùn)行結(jié)果根據(jù)以上的算法設(shè)計(jì)，可以得到該例子的運(yùn)行結(jié)果（見圖3.1）：圖3.1運(yùn)行結(jié)果3.2.6結(jié)果分析根據(jù)以上的運(yùn)行結(jié)果（見圖3.1），可以知道總廠每年最大的盈利為15萬(wàn)元，其中，最優(yōu)分配方案為：分別給甲、乙、丙門市部分配0箱，2箱，3箱。3.3本章小結(jié)我們研究多階段決策問題，常用的有效方法就是動(dòng)態(tài)規(guī)劃模型。1、建立動(dòng)態(tài)規(guī)劃模型的步驟(1)、根據(jù)時(shí)間或空間的自然特征，把實(shí)際問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段，使問題能夠轉(zhuǎn)化成一個(gè)多階段決策問題。(2)、正確地選擇狀態(tài)變量，確定狀態(tài)集合。(3)、確定決策變量及每個(gè)階段的允許決策集合。(4)、寫出狀態(tài)轉(zhuǎn)移方程，即給出從第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律：。(5)、正確的寫出指標(biāo)函數(shù)。(6)、寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程。其中如何選定狀態(tài)是關(guān)鍵的一步，狀態(tài)應(yīng)能描述過程的特征，可以直接或間接觀測(cè)，并且具有無(wú)后效性，即當(dāng)某階段的狀態(tài)給定后，過程以后的演變與該階段以前的狀態(tài)無(wú)關(guān)。2、動(dòng)態(tài)規(guī)劃的適用條件任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無(wú)后效性。3、動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：動(dòng)態(tài)規(guī)劃把較為復(fù)雜的問題劃分為若干個(gè)相互聯(lián)系的階段，每個(gè)階段的求解問題相對(duì)簡(jiǎn)單，而通過逐段求解這一遞推過程便可得到原問題的全局最優(yōu)解。此外，動(dòng)態(tài)規(guī)劃得到的是全過程和所有后部子過程的各個(gè)狀態(tài)的最優(yōu)解，這在討論最優(yōu)決策和最優(yōu)值對(duì)于狀態(tài)的穩(wěn)定性，或者實(shí)際問題要尋找次優(yōu)解時(shí)是很有用的。還有，由于動(dòng)態(tài)規(guī)劃方法反映了動(dòng)態(tài)過程演變的聯(lián)系和特征，在計(jì)算時(shí)可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。缺點(diǎn)：沒有統(tǒng)一標(biāo)準(zhǔn)模型可供采用，也沒有萬(wàn)能的構(gòu)造模型的方法。不同的實(shí)際問題，其動(dòng)態(tài)規(guī)劃模型也隨之不同，因而，實(shí)際問題的動(dòng)態(tài)規(guī)劃模型的建立往往需要豐富的想象力和靈活的技巧性，這就帶來(lái)了應(yīng)用上的局限性，同時(shí)，也就需要我們?cè)谝院蟮难芯恐羞M(jìn)一步尋求更好的算法。結(jié)論本論文主要對(duì)最優(yōu)化方法在生活中資源配置方面的應(yīng)用進(jìn)行了理論知識(shí)的闡述和通過舉例論證來(lái)探討。論文首先介紹了最優(yōu)化方法和資源配置方面的理論知識(shí)，提出了最優(yōu)化方法在資源配置方面的應(yīng)用的重要性。在當(dāng)今各方面競(jìng)爭(zhēng)越來(lái)越激烈的時(shí)代下，資源方面的競(jìng)爭(zhēng)成為成為生活中至關(guān)重要的一方面。如何去真正做到資源的合理配置，僅憑經(jīng)驗(yàn)，直覺等非客觀因素來(lái)做一個(gè)決策已然不可行。而最優(yōu)化方法主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)，必定成為生活中資源配置方面的一個(gè)重要使用工具。論文在第二章具體介紹了最優(yōu)化方法中的線性規(guī)劃模型及其在生活中生產(chǎn)計(jì)劃制定的實(shí)例應(yīng)用。主要探討了資源的影子價(jià)格如何直接關(guān)系到資源的最有效利用，提高經(jīng)濟(jì)效益，以及研究了線性規(guī)劃模型中的數(shù)據(jù)集合的波動(dòng)對(duì)最優(yōu)解或最優(yōu)基的影響。線性規(guī)劃模型在有限資源的配置方面具有十分重要的現(xiàn)實(shí)價(jià)值。論文在第三章具體介紹了最優(yōu)化方法中的多階段的動(dòng)態(tài)規(guī)劃模型及其在生活中資源分配問題中的實(shí)例應(yīng)用。主要探討了動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想在多階段決策問題上的應(yīng)用。動(dòng)態(tài)規(guī)劃模型在多階段的資源分配問題具有重要的現(xiàn)實(shí)應(yīng)用價(jià)值。在整個(gè)論文的研究里面，可以看出最優(yōu)化方法在現(xiàn)實(shí)生活中具有重要的現(xiàn)實(shí)意義，我們應(yīng)該將數(shù)學(xué)最優(yōu)化問題最有效地結(jié)合到生活實(shí)際中。不管是適用于資源有限的線性規(guī)劃模型，還是適用于多階段資源配置的動(dòng)態(tài)規(guī)劃模型，都可以體現(xiàn)出最優(yōu)化方法提供了生活上合理配置資源十分重要的參考，并從數(shù)據(jù)上給予人們做出決策提供關(guān)鍵的支持。當(dāng)然在現(xiàn)實(shí)生活中，我們不能僅靠最優(yōu)化方法的理論知識(shí)直接做出資源配置的決策，還要結(jié)合個(gè)人經(jīng)驗(yàn)、市場(chǎng)變化等各種因素，將最優(yōu)化方法的理論知識(shí)最有效的結(jié)合到生活中資源配置方面的問題上，才能確保真正做到資源合理配置，實(shí)現(xiàn)資源的有效利用，提高經(jīng)濟(jì)效益。另外，以下幾個(gè)問題還需要以后進(jìn)一步研究探討:第一，線性規(guī)劃是指從各種限制條件的組合中，選擇出最為合理的計(jì)算方法，建立線性規(guī)劃模型從而求得最佳結(jié)果。由于個(gè)人的能力問題，所舉得的生活實(shí)例主要談及有限資源的合理配置，沒去涉及到設(shè)備更新等因素?？梢姡绻婕暗竭@些方面的因素，做出的決策將更具有現(xiàn)實(shí)意義，這就需要我們進(jìn)一步研究線性規(guī)劃模型在生活中資源配置方面的應(yīng)用。第二，論文中的多階段的動(dòng)態(tài)規(guī)劃模型主要應(yīng)用于一種資源的分配問題。然而，在現(xiàn)實(shí)生活中，我們往往要做到的是多種資源的組合分配問題。如果進(jìn)一步談及動(dòng)態(tài)規(guī)劃模型在多種資源的組合分配問題的應(yīng)用，將對(duì)論文結(jié)論的說(shuō)服力進(jìn)一步加強(qiáng)，這就需要我們進(jìn)一步研究探討。第三，由于研究經(jīng)驗(yàn)不足以及實(shí)際處理能力還不夠強(qiáng)，論文中所選取的例子在各方面處理上離實(shí)踐仍有偏差，這則表明選取的例子還沒能真正與實(shí)踐結(jié)合，也不夠完善。此外，還可以進(jìn)一步結(jié)合最優(yōu)化方法中的其他優(yōu)化理論，談?wù)勂湓谫Y源配置方面的應(yīng)用。論文只能對(duì)于實(shí)踐有著一定的參考性，但若要成為實(shí)踐中直接引用的方案，還是遠(yuǎn)遠(yuǎn)不夠的。參考文獻(xiàn)[1]唐煥文、秦學(xué)志主編.實(shí)用最優(yōu)化方法[M].大連：大連理工大學(xué)出版社，2010.[2]陳寶林主編.最優(yōu)化理論與算法[M].北京：清華大學(xué)出版社，2005.[3]盧險(xiǎn)峰主編.最優(yōu)化方法基礎(chǔ)[M].上海：同濟(jì)大學(xué)出版社，2003.[4]姜啟源等編.數(shù)學(xué)模型[M].北京：高等教育出版社,2003.[5]黃桐城.運(yùn)籌學(xué)基礎(chǔ)教程[M].上海：上海人民出版社，2010.[6]王曉東.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2008.[7]溫清芳.最優(yōu)化方法在數(shù)學(xué)建模中的應(yīng)用[J].寧德師專學(xué)報(bào)(自然科學(xué)版),2007,(02).[8]韓瑋.現(xiàn)實(shí)生活中最優(yōu)化問題的數(shù)學(xué)模型構(gòu)造[J].數(shù)學(xué)通報(bào),2007,(02).[9]謝高峰.常見的最優(yōu)化問題[J].高中生,2010,(21).[10]楊冬英.最優(yōu)化理論與方法在企業(yè)生產(chǎn)經(jīng)營(yíng)中的應(yīng)用[D].中北大學(xué),2008.[11]侯林潔.探討數(shù)學(xué)最優(yōu)化問題在現(xiàn)實(shí)生活中的應(yīng)用[J].赤峰學(xué)院學(xué)報(bào)(自然科學(xué)版),2012,02:196-197.[12]劉茂松.最優(yōu)化方法在農(nóng)資商品物流管理中的運(yùn)用[J].山西財(cái)經(jīng)學(xué)院學(xué)報(bào),1984,04:27-32.[13]Cevikcan,Emre.Amathematicalprogrammingapproachforwalking-workerassemblysystems[J].ASSEMBLYAUTOMATION,34(1):56-58.[14]Lee,CY.Adynamiclot-sizingmodelwithdemandtimewindows[J].MANAGEMENTSCIENCE,2001,47(10):1384-1395.[15]Fomeni,FD.ADynamicProgrammingHeuristicfortheQuadraticKnapsackProble