最优装载问题及最优化方法在资源配置方面的应用

问题描述

有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。

容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

(1)首先将第一艘轮船尽可能装满；

(2)将剩余的集装箱装上第二艘轮船。

1、队列式分支限界法求解

在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。

活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。

节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r<bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。

为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。

找到最优值后，可以根据parent回溯到根节点，找到最优解。

算法具体代码实现如下：

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//装载问题

队列式分支限界法求解

#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;

//指向父节点的指针

bool

LChild;

//左儿子标识

Type

weight;

//节点所相应的载重量

};

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};//下标从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<<"分支限界选择结果为:"<<endl;

for(int

i=1;

i<=4;

i++)

{

cout<<x[i]<<"

";

}

cout<<endl;

cout<<"最优装载重量为："<<bestw<<endl;

return

0;

}

//将活节点加入到活节点队列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)//可行叶节点

{

if(wt

==

bestw)

{

//当前最优装载重量

bestE

=

E;

bestx[n]

=

ch;

}

return;

}

//非叶节点

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[])

{//队列式分支限界法，返回最优装载重量，bestx返回最优解

//初始化

Queue<QNode<Type>*>

Q;

//活节点队列

Q.Add(0);

//同层节点尾部标识

int

i

=

1;

//当前扩展节点所处的层

Type

Ew

=

0,

//扩展节点所相应的载重量

bestw

=

0,

//当前最优装载重量

r

=

0;

//剩余集装箱重量

for(int

j=2;

j<=n;

j++)

{

r

+=

w[j];

}

QNode<Type>

*E

=

0,

//当前扩展节点

*bestE;

//当前最优扩展节点

//搜索子集空间树

while(true)

{

//检查左儿子节点

Type

wt

=

Ew

+

w[i];

if(wt

<=

c)//可行节点

{

if(wt>bestw)

{

bestw

=

wt;

}

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

}

//检查右儿子节点

if(Ew+r>bestw)

{

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

}

Q.Delete(E);//取下一扩展节点

if(!E)//同层节点尾部

{

if(Q.IsEmpty())

{

break;

}

Q.Add(0);

//同层节点尾部标识

Q.Delete(E);

//取下一扩展节点

i++;

//进入下一层

r-=w[i];

//剩余集装箱重量

}

Ew

=E->weight;

//新扩展节点所对应的载重量

}

//构造当前最优解

for(int

j=n-1;

j>0;

j--)

{

bestx[j]

=

bestE->LChild;

bestE

=

bestE->parent;

}

return

bestw;

}

程序运行结果如图：

2、优先队列式分支限界法求解

解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。

优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。

在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

算法具体代码实现如下：

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——初始为新叶节点的位置，逐层向上，寻找最终位置

int

i

=

++CurrentSize;

while

(i

!=

1

&&

x

>

heap[i/2])

{

//

i不是根节点，且其值大于父节点的值，需要继续调整

heap[i]

=

heap[i/2];

//

父节点下降

i

/=

2;

//

继续向上，搜寻正确位置

}

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--];

//

取最后一个节点，从根开始重整

//

find

place

for

y

starting

at

root

int

i

=

1,

//

current

node

of

heap

ci

=

2;

//

child

of

i

while

(ci

<=

CurrentSize)

{

//

使ci指向i的两个孩子中较大者

if

(ci

<

CurrentSize

&&

heap[ci]

<

heap[ci+1])

{

ci++;

}

//

y的值大于等于孩子节点吗？

if

(y

>=

heap[ci])

{

break;

//

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

}

//

否，需要继续向下，重整堆

heap[i]

=

heap[ci];

//

大于父节点的孩子节点上升

i

=

ci;

//

向下一层，继续搜索正确位置

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;

//

从最后一个内部节点开始，一直到根，对每个子树进行堆重整

for

(int

i

=

CurrentSize/2;

i

>=

1;

i--)

{

T

y

=

heap[i];

//

子树根节点元素

//

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//装载问题

优先队列式分支限界法求解

#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;

//指向活节点在子集树中相应节点的指针

Type

uweight;

//活节点优先级(上界)

int

level;

//活节点在子集树中所处的层序号

};

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;

//指向父节点的指针

bool

LChild;

//左儿子节点标识

};

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};//下标从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<<"分支限界选择结果为:"<<endl;

for(int

i=1;

i<=4;

i++)

{

cout<<x[i]<<"

";

}

cout<<endl;

cout<<"最优装载重量为："<<bestw<<endl;

return

0;

}

//将活节点加入到表示活节点优先队列的最大堆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);

}

//优先队列式分支限界法，返回最优载重量，bestx返回最优解

template<class

Type>

Type

MaxLoading(Type

w[],Type

c,int

n,int

bestx[])

{

//定义最大的容量为1000

MaxHeap<HeapNode<Type>>

H(1000);

//定义剩余容量数组

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;//当前扩展节点所处的层

bbnode

*E

=

0;//当前扩展节点

Type

Ew

=

0;

//扩展节点所相应的载重量

//搜索子集空间树

while(i!=n+1)//非叶子节点

{

//检查当前扩展节点的儿子节点

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

{

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

}

//右儿子节点

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

//取下一扩展节点

HeapNode<Type>

N;

H.DeleteMax(N);//非空

i

=

N.level;

E

=

N.ptr;

Ew

=

N.uweight

-

r[i-1];

}

//构造当前最优解

for(int

j=n;

j>0;

j--)

{

bestx[j]

=

E->LChild;

E

=

E->parent;

}

return

Ew;

}

程序运行结果如图：本科毕业设计（论文）最优化方法在资源配置方面的应用学院应用数学学院专业信息与计算科学（信息计算方向）年级班别学号学生姓名指导教师摘要数学与我们日常生活息息相关，如何将数学最优化问题有效的结合到生活实际中，是当今面临的最热门话题。最优化方法是一门应用相当广泛的学科，它主要研究在众多方案中选择最佳方案，因而被广泛而深入的应用于生活中生产、管理等领域，例如，资源配置、生产计划等。因此，对最优化方法在生活中的应用研究具有重要的意义。本论文主要研究最优化方法在生活中生产、管理资源配置方面问题中的应用，具体介绍了最优化方法中的线性规划模型和动态规划模型及其它们在资源配置方面的应用。本文的主要内容和成果就是介绍了线性规划模型在生活中生产计划制定的应用以及多阶段的动态规划模型在生活中资源分配问题上的应用，并用相应的数学软件Lindo及算法解决对应的实例。本文所建立的数学模型有成熟的理论基础，又有相应的生活实例的支持，可信度高，对最优化方法在资源配置方面的应用研究具有重要参考意义。关键字：最优化方法，线性规划，动态规划，资源配置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线性规划模型及其应用32.1线性规划32.2对偶线性规划及其影子价格42.3线性规划的灵敏度分析52.4线性规划模型在生产中资源配置方面的应用举例72.5本章小结93多阶段的动态规划模型103.1资源分配问题上的动态规划模型103.2动态规划模型在资源分配问题的应用举例113.3本章小结15结论16参考文献18致谢191绪论最优化方法[1,3,5]（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的最优化问题，是系统工程的基础理论之一，最优化方法强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。最优化方法在工业、农业、物流、经济计划、人力资源、军事等行业都有着非常广泛的应用。有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中95%曾使用过线性规划，75%使用过运输模型，90%使用过网络计划技术，43%使用过动态规划。由此可见最优化方法是一门应用性很强的学科。特别是随着计算机技术的不断发展，最优化方法各种优化模型的求解过程都可以通过专门的应用软件来完成，因此，最优化方法越来越显示出其广泛的使用价值。资源配置(resourceallocation)是指对相对稀缺的资源在各种不同用途上加以比较作出的选择。资源是指社会经济活动中人力、物力和财力的总和，是社会经济发展的基本物质条件。在社会经济发展的一定阶段上，相对于人们的需求而言，资源总是表现出相对的稀缺性，从而要求人们对有限的、相对稀缺的资源进行合理配置，以便用最少的资源耗费，生产出最适用的商品和劳务，获取最佳的效益。资源配置合理与否，对一个国家经济发展的成败有着极其重要的影响。对于如今竞争非常激烈的现实生活中，如何最合理地配置生活中生产、管理中的有限资源，取得最好的经济效益，当今面临的最热门话题。这也是生活中各类决策者所要考虑到的，首先，要先制定一个最优化的模型，然而，这些模型不是一成不变的，由于市场需求的不确定因素，针对不同的最优化问题，我们要具体问题具体分析，根据具体情况，制定一个最适合的最优化模型。因此，自最优化方法提出后，国内外对资源配置方面进行了大量的研究，并提出了一系列算法解决此问题。当然，我们的研究受到各种因素的影响，存在着非结构性的复杂问题，仅用数学模型是很难加以描述和解决的。总之，随着社会的不断发展和进步，实践将对最优化方法提出更新更多的研究课题，最优化方法正处于不断发展、不断进步的时期。本文将介绍最优化方法模型的建立和模型的分析、求解，探讨其在生活中生产、管理资源配置方面问题中的应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用——生产计划；以及动态规划的模型、求解、应用――资源分配问题。2线性规划模型及其应用随着国际经济贸易的发展，国际社会的竞争越来越剧烈，如何最合理地配置企业有限资源，取得最佳经济效益，已经成为我们目前急需解决的一大问题。在现实生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。任何资源，如劳动力、原材料、设备或资金等都是有限的。因此，必须进行合理的配置，寻求最佳的利用方式。所谓的最佳的方式，必须有一个标准或目标，这个标准或目标就是使利润达到最大或成本达到最小。尤其对于一些大批生产的企业，在有限资源的条件下，为满足市场的需求，如何充分发挥现有生产能力，以最小的投入取得最大的经济效益?如何在生产计划中确定最佳产品组合？最佳经济效益目标可以是多少？这些都是最优化的设计问题。对于这些制定企业生产计划，最有效方法就是线性规划。然而，企业最优生产问题不仅仅是将企业现有资源按照效益最大或成本最低的原则在多项生产任务中进行分配的问题，还应该是合理组织资源使企业的生产任务最大限度满足市场需求的问题，而线性规划也只能解决将企业现有资源按照效益最大或成本最低的原则在多项生产任务中进行分配的问题。这其中的原因主要是我们在利用线性规划制定生产计划时，将资源约束作为刚性约束来处理，没有去考虑在市场环境下部分资源约束是弹性约束。可见，此类问题切不可直接用线性规划。对于这类组织资源使企业的生产任务最大限度满足市场需求的问题，我们现在经常采用到线性规划的对偶规划。本章将在线性规划的理论基础上，根据线性规划互补最优性条件，进一步讨论最优生产问题的对偶规划模型，对影响企业资源变化的影子价格也进行了分析和研究，再通过灵敏度分析，对线性规划问题的数据集合进行进一步了解，并用生活中生产计划的实例进行了论证。2.1线性规划线性规划[1,5]就是由目标函数为决策变量的线性函数和约束条件为线性等式或线性不等式所组成的数学规划。它是数学规划中较简单的一类，也是最基本的一类数学规划问题。其实质是在一组线性约束条件下，寻找一组决策变量使得目标函数取得最大或最小的条件极值问题。可见，线性规划模型基本上是确定的，它的模型建立过程为确定决策变量、确定目标函数、确定约束条件。该线性规划模型常用于有限资源的分配问题。设为决策变量，为价值系数，为消耗系数，为资源限制系数，则标准的线性规划模型表示如下：（1）其中线性规划的基本定理:如果可行域非空有界，那么线性规划问题的目标函数一定可以在可行域D上的顶点上达到最优值。根据线性规划基本定理，启发了Dantzig的单纯形法，即将寻优的目标集中在D上各个顶点上。单纯形法是求解线性规划问题的一种通用的有效算法，它的基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。设B是由A中m个线性无关的列向量组成的一个基，，其中为基B对应的基变量和价值系数，为N对应的非基变量和价值系数。定理1最优解判别定理:对于线性规划问题，若某个基本可行解所对应的检验向量，那这个基本可行解就是最优解。上面讨论的是一般的线性规划模型以及最优解的求法。然而，现实生活中，常常遇到的不是仅仅靠一般的线性规划模型就能解决的生产方面资源配置问题。下面我们再进一步讨论线性规划的对偶规划问题。2.2对偶线性规划及其影子价格对偶理论[5]是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生着一个相应的线性规划问题。前者是由矩阵A、右端向量b和价值向量C定义的，称之为原问题；后者也是有相同的数据集合A、b和C构成，称之为原问题的对偶问题。上述的线性规划模型（1）的对偶问题可表示如下：（2）由线性规划的对偶理论可以知道：如果原问题（1）有最优解，那么对偶问题（2）也有最优解，并且两者的目标函数值相等，即有：。为对偶问题最优解，它代表在资源最优利用下，对各种单位资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中所作出的贡献而作出的估价，简称影子价格。影子价格的大小客观地反映了各种资源在系统内稀缺程度，会直接关系到资源的最有效利用。影子价格是一种编辑价格，的值相当于在资源得到最优利用的条件下，每增加1个单位时，目标函数Z的增加值。影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度，同时也是一种成本机会，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也随着发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。由此可见企业资源的影子价格直接关系到资源的最有效利用，根据影子价格企业可以对有限的资源进行合理的配置，自主地节约使用某种稀缺资源，使有限资源发挥更大的经济效益。2.3线性规划的灵敏度分析线性规划问题所对应的数据集合A、b、C常常是通过预测或估计所得到的的统计数据，可能存在一定的误差。同时，随着市场环境，工艺条件和资源数量的改变，这些数据也可能发生变化。那么，就有必要去分析下这些数据波动时，对当前的最优解或最优基产生什么影响，即是所谓的灵敏度分析。此外，在生产计划中，对于给定的目标点，要想使之成为最优解，可以通过三条途径来实现[10]，即：1、通过改变模型（1）的目标函数中价值系数C，使得给定的目标解成为最优解。由于不改变可行域D，因此，预期目标解必须是线性规划原问题的可行解；2、通过改变模型（1）中资源拥有量b，使得预期目标解成为可行解。由于可行域D的扩张或平移，因此，给定的目标解可以不是线性规划原问题的可行解。3、通过改变模型（1）中资源消耗系数，即约束函数的斜率A,使得预期目标解成为可行解。由于可行域D的形状发生了变化，因此，给定的目标解可以不是线性规划原问题的可行解。下面，我们分别讨论当价值系数C、资源拥有量b和资源消耗系数向量A变化的响应情况：1、考虑只有价值向量C的改变的情形。若是非基变量的价值系数，为该价值系数的改变量，只要，就可以保持现行最优解依旧最优，由此可以确定价值系数的可变化范围，其中为的检验数。若是某基变量的价值系数，为该价值系数的改变量，只要非基变量对应的检验数，就可以保持现行最优解依旧最优，由此可以确定价值系数的可变化范围。2、考虑只有资源拥有量b的改变的情形。B的波动会使最优解和最优目标函数值，但可以不改变原最优基B，只要即可，其中为原最优解。3、考虑只有资源消耗系数A的改变的情形。一般而言，约束矩阵A的改变可能导致不同的最优解和最优基，进行灵敏度分析不是一件简单的事。下面，只谈及两种较简单的情形。增加一个新变量，假设在获得原线性规划的最优解之后，又发现了一个新变量，其对应的价值系数为，在新的约束矩阵中对应的系数列向量为，于是得到如下新的线性规划问题：；增加一个约束，不妨假设此附加的约束条件为不等式形式，即，其中是n维行向量，为右端项系数，于是新的线性规划模型变为。2.4线性规划模型在生产中资源配置方面的应用举例一豆制品加工厂[4,9]用黄豆生产A，B，C三种豆制品，1公斤黄豆可以在甲类设备上用12小时加工成3公斤A，或者在乙类设备上用8小时加工成4公斤B，或者在丙类设备上用6小时加工成4公斤C。根据市场需求，生产的A，B，C全部能售出，且每公斤A获利24元，每公斤B获利16元，每公斤C获利12元。现在加工厂每天能得到120公斤黄豆的供应，每天正式工人总的工作时间为960小时，并且甲类设备每天至多能加工100公斤A，乙类设备每天至多能加工120公斤B，丙类设备的加工能力没有限制。1、为该厂制定一个生产计划，使每天获利最大。2、若用16元可以买到1公斤黄豆，应否作这项投资？若投资，每天最多购买多少公斤黄豆？3、若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？4、由于市场需求变化，每公斤C的获利增加到14元，应否改变生产计划？2.4.1变量说明Z盈利（元）生产A所用的黄豆重量（公斤）生产B所用的黄豆重量（公斤）生产C所用的黄豆重量（公斤）2.4.2问题分析本问题的目标是使得该厂每天获利最大，要做的决策是生产计划，即如何合理配置黄豆，分别用多少公斤黄豆生产豆制品A，B，C。决策收到的限制：原料供应、劳动时间、设备的加工能力。按照问题，将决策变量、目标函数和约束条件用数学符号及式子表示出来，就可得到下面的线性规划模型。2.4.3模型假设假设1：A，B，C每公斤的获利与它们各自产量无关；假设2：A，B，C每公斤的获利与它们相互间产量无关；假设3：加工A，B，C的黄豆的重量可以是任意实数。2.4.4模型建立2.4.5模型求解将上述模型输入LINDO求解，可以得到以下结果（见图2.1）：图2.1求解结果2.4.6结果分析1、图2.1的第2,3,4,5,6行明确地告诉我们，这个线性规划的最优解为，最优值为Z=6960，即该厂的生产计划为：每天用30公斤黄豆生产A，每天用30公斤黄豆生产B，每天用60公斤黄豆生产C，这样能使每天获利最大，获利6960元。2、图2.1的第8行“DUALPRICES”告诉我们，增加1公斤黄豆时利润增长24元，即1公斤黄豆的影子价格为24元；图2.1的第23行“CURRENTRHS”的“ALLOWABLEINCREASE”和“ALLOWABLEDECREASE”给出了黄豆的影子价格有意义条件下约束右端的限制范围：黄豆最多增加30公斤。综上，用16元可以买到1公斤黄豆，低于1公斤黄豆的影子价格，应该做这项投资，但每天最多购买30公斤黄豆。3、图2.1的第9行“DUALPRICES”告诉我们，劳动时间增加1小时时利润增长4元，即1小时劳动的影子价格为4元。综上，聘用临时工人，付给的工资应低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时4元。4、图2.1的第19行“CURRENTCOEF”的“ALLOWABLEINCREASE”和“ALLOWABLEDECREASE”给出了最优解不变条件下目标函数系数的允许变化范围：的系数为（48-12,48+12），即（36,60）。注意：系数的允许范围需要的系数不变。综上，若每公斤C的获利增加到14元，则系数变为14*4=56，在允许范围内，所以不应改变生产计划。2.5本章小结本章所探讨的线性规划模型，常用单纯形法求解。线性规划模型日益成熟，在生活各方面都会经常用到线性规划模型，通过对线性规划模型的数据A，b，C进行灵敏度分析，可以尽可能控制这些数据的变化范围，使得企业保持一定的收益。此外，对于影响决策的资源占有量b的影子价格，可以对现有资源实现最大收益时估价，可以使资源合理配置，使资源发挥最大的经济效益。3多阶段的动态规划模型所谓多阶段决策问题[1]是指这样一类活动过程：它可以分为若干个相互联系的阶段，在每个阶段上都需要作出决策，而一个阶段的决策确定以后，将会影响以后各阶段的活动及其决策，当所有阶段的决策确定后，就完全确定了该问题的活动过程。各个阶段所确定的决策就构成了一个决策序列，成为一个策略，一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么，不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段，选取其最优策略，这类问题就是多阶段决策问题。它要求决策者不能用孤立的观点看待各阶段的决策。多阶段决策问题，不论其本身是否与时间有关，由于分为阶段来依次解决，这便具有了明显的时序性，而在各阶段中所采取的决策是随阶段而变动的，不同阶段采取不同决策，这便是“动态”的含义。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划是解决多阶段决策过程最优化问题的一种常见方法。动态规划把比较复杂的问题划分成若干阶段，通过逐段求解，最终得到全局最优解。这种“分而治之，逐步改善”的方法已在一些较难解决的问题中显示出了优越性，尤其是离散性问题，用动态规划的方法去处理，比用线性规划或非线性规划方法有时更为有效。此外，虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。迄今为止，动态规划模型已广泛应用于经济、生物、工程、军事等许多领域，并取得了很好的效果。本章具体研究多阶段的动态规划模型及其在资源分配问题上的实例应用。3.1资源分配问题上的动态规划模型所谓“资源分配问题”就是把一定数量的若干资源合理地分配给若干个使用者，使指标函数达到最优。这里仅讨论一种资源的分配问题。其一般提法是，设某种资源的总量为a，拟用于n项经营活动，若给第j项活动分配个单位，其收益为，问应如何分配，才能使这n项经营活动总的收益值最大？对于该问题，我们可以直接表示为因此，可用非线性规划方法求解。但是利用这类问题的特性，也可以把它看做一个多阶段决策问题，建立如下的动态规划模型：1、以阶段变量k表示资源分配给第k项经营活动的过程；2、以状态变量表示在开始给第k项经营活动分配资源时尚剩余的资源数量；3、以决策变量表示分配给第k项经营活动的资源数量，则允许决策集合为；4、状态转移方程为；5、以表示从现有个单位资源中分配给第k项经营活动个单位资源后的预计收益；6、以表示从现有个单位资源中分配给第k项到第n项经营活动后，所得的最大利益，则函数基本方程为3.2动态规划模型在资源分配问题的应用举例某工厂拟将5台先进设备分配给下属的甲、乙、丙三个分厂，分厂获得该设备后每年为总厂提供的盈利如下表所示(如表3.1)：表3.1各分厂获得该设备后每年为总厂提供的盈利分厂分分分厂盈利（万元）元）设备（台）012345甲乙丙000354710691112121112131112试问：该工厂如何分配这些设备，才能使总厂的盈利最大？3.2.1变量说明k表示给甲、乙、丙三个分厂分配的过程，其中k=1,2,3表示在开始给第k个分厂分配时尚未分配的台数表示分配给第k分厂的台数表示从现有台中分配给第k分厂台后的预计盈利表示从现有台中分配给第k分厂到第3分厂后，所得的最大盈利3.2.2问题分析本问题可以看做一个多阶段决策问题，采用动态规划方法解决之，将问题分为3个子问题，分别作出决策，最终得到一个策略，使得工厂获得最大盈利。3.2.3模型假设假设1：设备不会出现故障，影响盈利；假设2：甲乙丙三者的单位利润与它们相互间箱数无关；假设3：甲乙丙三者的设备台数可以是任意整数。3.2.4模型建立3.2.5模型求解1、算法描述根据以上的模型，可设计解资源分配问题的动态规划算法[2,6]maxprofit如下：publicstaticvoidmaxprofit(intn,intm,int[][]v,int[][]p){//该maxprofit函数主要得到问题的最优值，即资源分配问题的总盈利//n:设备数量;m:分厂数量//v[i][j]:i台设备提供给第j分厂将得到的盈利//p[i][j]:记录f[i][j]的值是由哪一个子问题的解得到.//f[i][j]:用i台设备分配给后j个分厂将得到的盈利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万元\n",f[n][1]);}publicstaticvoiddistribution(intn,intm,int[][]p){//该distribution得到问题的最优解，即资源分配问题的资源分配方案intk=n;System.out.print("资源分配方案：\n");for(intj=1;j<=m;j++){System.out.printf("%1d台设备分配给第%1d分厂使用\n",p[k][j],j);k=k-p[k][j];}}2、运行结果根据以上的算法设计，可以得到该例子的运行结果（见图3.1）：图3.1运行结果3.2.6结果分析根据以上的运行结果（见图3.1），可以知道总厂每年最大的盈利为15万元，其中，最优分配方案为：分别给甲、乙、丙门市部分配0箱，2箱，3箱。3.3本章小结我们研究多阶段决策问题，常用的有效方法就是动态规划模型。1、建立动态规划模型的步骤(1)、根据时间或空间的自然特征，把实际问题恰当地划分为若干个阶段，使问题能够转化成一个多阶段决策问题。(2)、正确地选择状态变量，确定状态集合。(3)、确定决策变量及每个阶段的允许决策集合。(4)、写出状态转移方程，即给出从第k阶段到第k+1阶段的状态转移规律：。(5)、正确的写出指标函数。(6)、写出动态规划函数基本方程。其中如何选定状态是关键的一步，状态应能描述过程的特征，可以直接或间接观测，并且具有无后效性，即当某阶段的状态给定后，过程以后的演变与该阶段以前的状态无关。2、动态规划的适用条件任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。3、动态规划的优缺点优点：动态规划把较为复杂的问题划分为若干个相互联系的阶段，每个阶段的求解问题相对简单，而通过逐段求解这一递推过程便可得到原问题的全局最优解。此外，动态规划得到的是全过程和所有后部子过程的各个状态的最优解，这在讨论最优决策和最优值对于状态的稳定性，或者实际问题要寻找次优解时是很有用的。还有，由于动态规划方法反映了动态过程演变的联系和特征，在计算时可以利用实际知识和经验提高求解效率。缺点：没有统一标准模型可供采用，也没有万能的构造模型的方法。不同的实际问题，其动态规划模型也随之不同，因而，实际问题的动态规划模型的建立往往需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性，同时，也就需要我们在以后的研究中进一步寻求更好的算法。结论本论文主要对最优化方法在生活中资源配置方面的应用进行了理论知识的阐述和通过举例论证来探讨。论文首先介绍了最优化方法和资源配置方面的理论知识，提出了最优化方法在资源配置方面的应用的重要性。在当今各方面竞争越来越激烈的时代下，资源方面的竞争成为成为生活中至关重要的一方面。如何去真正做到资源的合理配置，仅凭经验，直觉等非客观因素来做一个决策已然不可行。而最优化方法主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据，必定成为生活中资源配置方面的一个重要使用工具。论文在第二章具体介绍了最优化方法中的线性规划模型及其在生活中生产计划制定的实例应用。主要探讨了资源的影子价格如何直接关系到资源的最有效利用，提高经济效益，以及研究了线性规划模型中的数据集合的波动对最优解或最优基的影响。线性规划模型在有限资源的配置方面具有十分重要的现实价值。论文在第三章具体介绍了最优化方法中的多阶段的动态规划模型及其在生活中资源分配问题中的实例应用。主要探讨了动态规划算法的设计思想在多阶段决策问题上的应用。动态规划模型在多阶段的资源分配问题具有重要的现实应用价值。在整个论文的研究里面，可以看出最优化方法在现实生活中具有重要的现实意义，我们应该将数学最优化问题最有效地结合到生活实际中。不管是适用于资源有限的线性规划模型，还是适用于多阶段资源配置的动态规划模型，都可以体现出最优化方法提供了生活上合理配置资源十分重要的参考，并从数据上给予人们做出决策提供关键的支持。当然在现实生活中，我们不能仅靠最优化方法的理论知识直接做出资源配置的决策，还要结合个人经验、市场变化等各种因素，将最优化方法的理论知识最有效的结合到生活中资源配置方面的问题上，才能确保真正做到资源合理配置，实现资源的有效利用，提高经济效益。另外，以下几个问题还需要以后进一步研究探讨:第一，线性规划是指从各种限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果。由于个人的能力问题，所举得的生活实例主要谈及有限资源的合理配置，没去涉及到设备更新等因素。可见，如果涉及到这些方面的因素，做出的决策将更具有现实意义，这就需要我们进一步研究线性规划模型在生活中资源配置方面的应用。第二，论文中的多阶段的动态规划模型主要应用于一种资源的分配问题。然而，在现实生活中，我们往往要做到的是多种资源的组合分配问题。如果进一步谈及动态规划模型在多种资源的组合分配问题的应用，将对论文结论的说服力进一步加强，这就需要我们进一步研究探讨。第三，由于研究经验不足以及实际处理能力还不够强，论文中所选取的例子在各方面处理上离实践仍有偏差，这则表明选取的例子还没能真正与实践结合，也不够完善。此外，还可以进一步结合最优化方法中的其他优化理论，谈谈其在资源配置方面的应用。论文只能对于实践有着一定的参考性，但若要成为实践中直接引用的方案，还是远远不够的。参考文献[1]唐焕文、秦学志主编.实用最优化方法[M].大连：大连理工大学出版社，2010.[2]陈宝林主编.最优化理论与算法[M].北京：清华大学出版社，2005.[3]卢险峰主编.最优化方法基础[M].上海：同济大学出版社，2003.[4]姜启源等编.数学模型[M].北京：高等教育出版社,2003.[5]黄桐城.运筹学基础教程[M].上海：上海人民出版社，2010.[6]王晓东.算法设计与分析[M].北京：清华大学出版社，2008.[7]温清芳.最优化方法在数学建模中的应用[J].宁德师专学报(自然科学版),2007,(02).[8]韩玮.现实生活中最优化问题的数学模型构造[J].数学通报,2007,(02).[9]谢高峰.常见的最优化问题[J].高中生,2010,(21).[10]杨冬英.最优化理论与方法在企业生产经营中的应用[D].中北大学,2008.[11]侯林洁.探讨数学最优化问题在现实生活中的应用[J].赤峰学院学报(自然科学版),2012,02:196-197.[12]刘茂松.最优化方法在农资商品物流管理中的运用[J].山西财经学院学报,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