当前位置:文档之家› 线性规划模型的应用与灵敏度分析正文

线性规划模型的应用与灵敏度分析正文

线性规划模型的应用与灵敏度分析正文
线性规划模型的应用与灵敏度分析正文

线性规划模型的应用与灵敏度分析

第一章线性规划问题

1.线性规划简介及发展

线性规划(Linear Programming)是运筹学中研究最早、发展最快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法,研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写为LP。它是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面,为合理利用有限的人力、物力、财力等资源做出的最优决策,提供科学的依据。

线性规划及其通用解法——单纯形法是由美国G.B.Dantzig在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视[1]。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法,为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力[2]。1951年美国经济学家库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年莱姆基提出对偶单纯形法,1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年塔克提出互补松弛定理,1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究[3]。由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。建立线性规

划模型线性规划研究的问题主要有两类:一类是当一项任务确定后,如何统筹安排,尽量做到以最少的人力、物力等资源去完成;另一类是在人力、物力等资源确定的情况下,如何安排使用这些资源,使创造的价值最多,其实质是解决稀缺资源在有竞争环境中如何进行最优分配的问题,即寻求整个问题的某个整体指标最优的问题[4]。

2. 线性规划的数学模型

2.1 线性规划问题

例1-1某工厂在计划期内要安排生产两种产品Ⅰ,Ⅱ,已知生产单位产品所需的设备台数及A,B 两种原材料的消耗量,见表1-1。该工厂每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排生产计划使该工厂获得的利润最大?有关资料如下

表1-1产品、资源信息

产品 Ⅰ Ⅱ 资源限量

设备/台 1 2 8 原材料A/kg 4 0 16 原材料B/kg

4

12

用数学语言来描述生产计划的安排,建立数学模型。

解:设x 1,x 2分别表示在计划期内产品Ⅰ,Ⅱ的生产量,在满足资源限量的条件下,它们必须同时满足下列条件。

对设备有效台数: 8221≤+x x 对原材料A : 1641≤x 对原材料B : 1242≤x

该工厂的生产目标是在不超过所有资源限量的条件下,确定生产量x 1,x 2,使该 得到的利润最大。若用Z 表示总利润,则有

2132max x x Z +=

综合上述,该生产计划问题可用数学模型表示为

2132max x x Z +=

?????

??≥≤≤≤+0,12416

4822

12

121x x x x x x (1-1)

这就是一个线性规划模型[5]。 2.2 线性规划问题的数学模型

线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成的符合抽象数学模型。下面介绍建立实际问题线性规划模型的基本步骤。

(1) 确定决策变量。这是很关键的一步,决策变量选取得当,不仅会使线性规划的数学模型建得容易,而且求解比较方便。

(2) 找出所有限制条件,并用决策变量的线性等式或不等式来表示,从而得到约束条件。一般可用表格形式列出所有的限制数据,然后根据所列出的数据写出相应的约束条件,以避免遗漏或重复所规定的限制要求。

(3) 把实际问题所要达到的目的用决策变量的线性函数来表示,得到目标函数,并确定是求最大值还是最小值。 (4) 根据实际问题添加非负约束。

线性规划的数学表达式成为线性规划的数学模型,一般形式为

n n x c x c x c Z +++= 2211max(min)

(1-2)

s.t.?????

??

??≥≥≥≥=≤+++≥=≤+++≥=≤+++0

,,0,0),(),(),(2122112222212111212111n m

n mn m m n n n n x x x b

x a x a x a b x a x a x a b x a x a x a (1-3)

其中,式(1-2)称为目标函数,(1-3)式称为约束条件。

2.3 线性规划的性质

定理1 线性规划问题的可行解X 是基可行解的充要条件是X 的非零分量对应的系 数矩阵A 的列向量线性无关[6]。

定理2 若一个线性规划问题有可行解,则它必有基本可行解[7]。

定理3 若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。

证明:设)

2()

1(,X

X 是可行域的顶点,若)

0(X

不是顶点,且目标函数在)

0(X

处达到

最优)

0(*CX

Z =(标准型是Z Z max *=)。

因为)0(X

不是顶点,所以D 的顶点线性表示为

)

(1

)

0(i k

i i

X

a

X

∑==

(1-4)

在所有顶点中必然能找到某个顶点)

(m X

,使)

(m CX

是所有)

(i CX

中最大者,并且将

)

(m X

代替式(1-5)中所有的)(i X ,这就得到)

()

(1)

(1

m m k

i i i k

i i CX

X

C X

C =≤∑∑==αα,由此得

到)

()

0(m CX

CX

≤,根据假设)

(O CX

最大值,所以只能有)

()

0(m CX

CX

=,即目标函数在

顶点)

(m X

处也达到最大值。

有时目标函数可能在多个顶点处达到最大值,这时在这些顶点的凸集合上也达到最大值,称这种线性规划问题有无穷多最优解。

由以上的讨论可知,为了寻求线性规划问题的最优解,只从其有限数目的基本可行解中去寻找基础最优解就可以了。尽管如此,当数m,n 较大时,用此种方法求其最优解也是不可行的[8]。

第二章求解线性规划的方法

1. 图解法

图解法是求解线性规划模型的一种重要方法,线性规划中一些重要的性质、概念和求解思想都来源于此。当只有两个决策变量时,可以用图解法求解。它具有简单直观的特点。

为了给后面的线性问题的基本理论提供较直观的几何说明,先介绍线性规划问题的图解法[8]。

我们把满足约束条件和非负约束条件的一组解叫做可行解,所有可行解组成的集合称为可行域。

图解法的求解步骤如下:

第一步,根据约束画出可行域,先以决策变量为坐标,建立直角坐标系,再根据各约束条件,作出可行域。

第二步,作出一条目标函数等值线,并确定增值方法。

第三步,沿等值线的法线方向值增大方向移动,从而找到最大值。

图解法得出线性规划的几种情况:

表2-1 解的几种情况

解的几种情况约束条件图形特点方程特点

惟一解一般围成有限区域,最

优值只在一个顶点达到

--

无穷多解在围成的区域边界上,至少

有两个顶点处达到最优目标和某一约束方程成比例

无可行解(无解)围不成区域有矛盾方程

无界解(无解)围成无界区域,

且无有限最优值

缺少一必要条件的方程

2. 单纯形法

2.1 单纯形法的发展

单纯形法(simplex methods ),求解线性规划的通用方法。单纯形法是美国数学家G .B.Dantzig 于1947年首先提出的。简单的说就是一种数学迭代方法,求解基本过程是从一个基本可行解跳到另一个基本可行解的逐步替代,从而使目标函数不断得到改善。它的理论根据是:线性规划问题的可行域是n 维向量空间n R 中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到[9]。

2.1.1 单纯形法的基本思路

单纯形法的基本思路是:根据线性规划问题的标准型,从可行域中某个基本可行解(一个顶点)开始,转换到另一个基本可行解(顶点),并且当目标函数达到最大值时,问题就得到了解决,其基本思路的框架图如下图2-1。

否 是

图2-1 单纯形法的基本思路

例2-1 用单纯形法讨论例1-1的求解。 解:已知例1.1的标准型为:

5

432100032max x x x x x Z ++++= (2-1)

???

??

?

?=≥=+=+=+5

,,2,1,01241648252

412

1 j x x x x x x x j (2-2)

约束条件(2-2)的系数矩阵

????

?

?

?==10

4

001004

00121),,,,(54321P P P P P A 给出一个初始基本可行解

是否最优

从当前基可行解出发,寻求一个能使目标函数值活的改善的新的基本可行解

写出最优解

显然,3x ,4x ,5x 的系数列向量

????? ??=0013P ,????? ??=0104P ,???

?

? ??=1005P (2-3) 是线性独立的,因而这些向量构成一个基

()???

?

?

?

?==10

0010

001

,,543P P P B (2-4) 对应于B 的基变量为3x ,4x ,5x ,从约束条件(2-2)中可以看到

2

51

42

1341241628x x x x x x x -=-=--= (2-5)

当令非基变量021==x x ,这时得到一个基本可行解)

0(X

T

X

)

12,16,8,0,0()

0(= (2-6)

将式(2-3)代入目标函数(2-1)得到

032021=++=x x Z (2-7) 这个基本可行解表示:工厂没有安排生产Ⅰ,Ⅱ产品;资源都没有被利用,所以工厂的利润0=Z 。

分析目标函数的表达式(2-7)可以看到:非基变量1x ,2x 的系数都是正数,因此将非基变量变为基变量,目标函数的值就可能增大,从经济意义上讲,安排生产产品Ⅰ或Ⅱ,就可以使工厂的利润指标增加,所以只要在目标函数(2-7)的表达式中还存在有正系数的非基变量,这表示目标函数值还有增加的可能,就需要将非基变量与某个基变量进行对换,一般选择正系数最大的那个非基变量2x 为换入变量,将它换入到基变量中区,同时还有确定基变量中有一个要换出来成为非基变量,可按以下方法来确定换出变量。

现分析式(2-5),当将2x 定为换入变量后,必须从3x ,4x ,5x 中换出一个,并保证其余的都是非负,即3x ,4x ,5x ≥0。

当01=x ,由式(2-5)得到

4120

160

2825423≥-=≥=≥-=x x x x x (2-8)

从式(2-8)中可以看出,只有选择

3)4/12,2/8min(2=-=x (2-9)

时,才能使式(2-8)成立。因为当32=x 时,基变量05=x ,所以可用2x 去替代5x 。

以上数学模型说明了每生产一件产品Ⅱ,需要用掉的各种资源数为(2,0,4)。这些资源中的薄弱环节确定了产品Ⅱ的产量。原材料B 的数量决定产品Ⅱ的产量只能是

34/122==x 件。

为了求得以243,,x x x 为基变量的一个基本可行解和进一步分析问题,需将方程(2-5)中2x 的位置对换。得到

5

21

41

2312441682x x x x x x x -=-=-=+ (2-10)

用高斯消去法求解,得到以非基变量表示的基变量

5

21

45

1325.034165.02x x x x x x x -=-=+-= (2-11)

再将式(1-12)代入目标函数(1-6)得到

5175.029x x Z -+=

(2-12)

令非基变量051==x x ,得到9=Z ,并得另一个基本可行解T

X

)

0,16,2,3,0()

0(=。

从目标函数的表达式(2-12)中可以看到,非基变量1x 的系数是正的,说明目标函数的值还可以增大,还不是最优解。于是用上述方法,确定换入、换出变量,继续迭代,再得到另外一个基本可行解T

X

)

0,8,0,3,2()

2(=。

再经过一次迭代,得到一个基本可行解T

X )

4,0,0,2,4()

3(=。

而这时得到的目标函数的表达式是

43125.05.114x x Z --= (2-13) 再分析目标函数(2-13),可知所有非基变量3x ,4x 的系数都是负数,这说明若要用剩余资源3x ,4x ,就必须支付附加费用。所以当043==x x 时,即不再利用这些资源时,目标函数达到最大值,那么)

3(X

是最优解。这说明当产品Ⅰ生产4件,产品Ⅱ生产2

件,工厂才能得到最大利润。

通过上例,可以了解利用单纯形法求解线性规划问题的思路。 2.1.2 单纯形法的一般描述和求解步骤 一般的线性规划问题的求解有以下几个步骤。

(1) 确定初始基本可行解。为了确定初始基本可行解,首先要找出初始可行解。 设一线性规划问题为

∑==

n

j j j

x c

Z 1

max

??

???

=≥=∑=n j x b x P j n

j j j ,,2,1,01

(2-14) 可分为两种情况讨论。

① 若),,2,1(n j P j =中存在一个单位基,则将其作为初始可行基

?????

???????==10

10001),,,(21

m

P P P B (2-15) ② 若),,2,1(n j P j =中不存在一个单位基,则人为地构造一个单位初始基。 (2) 检验最优解。得到初始基本可行解后,要检验该解是否为最优解。如果是最优解,则停止运算;否则转入(3)基变换。下面给出最优性判别定理。

一般情况下,经过迭代后可以得到以非基变量表示基变量的表达式

j n

m j ij

i

j x a

b x ∑+=-

=1

'' ),,2,1(m i = (2-16)

将式(2-11) 代入式(2-10)的目标函数,整理后得

j n

i n

i ij

i

j

m

i i

i x a

c c

b

c Z )(max 1

1

'1

'∑∑∑===-

+

=

(2-17)

∑==

n i i

i b c Z 1

'0,∑==

m

i ji

i

j

a c Z

1

' ),,1(n m j += (2-18)

于是

∑+=-+

=n

m j j j j

x Z c

Z Z 1

0)(max (2-19)

再令 j j j Z c -=σ ),,1(n m j += (2-20) 则得到以非基变量表示目标函数的表达式

∑+=+

=n

m j j j

x Z Z 1

0max σ

(2-21)

(3) 基变换。若初始基本可行解)

0(X

不是最优解,又不能判别无界时,由目标

函数(2-10)的约束条件可看到,当某些0>j σ,j x 增加则目标函数值还可能增加,这时就要将其中某个非基变量换到基变量中去(称为换入变量),同时,某个基变量要换成非基变量(称为换出变量),随之会得到一个新的基本可行解。从一个基本可行解到另一个基本可行解的变换,就是进行一次基变换。从几何意义上就是从可行域的一个顶点转向另一个顶点。

(4) 迭代。在确定了换入变量k x 和换出变量l x 后,要把k x 和l x 的位置进行对换,就是说要把k x 对应的系数列向量k P 变成单位列向量。这可以通过对约束方程组的增广矩阵进行初等行变换来实现,变换结果得一新的基本可行解。然后转入(2)。

2.2 单纯形法的进一步讨论

对于一般的线性规划问题,在用单纯形法求解之前,总是先化为标准型。如果在系数矩阵中有一个单位阵,则可以作为初始可行基。如果约束条件的系数矩阵中不存在单位矩阵,则可以通过添加人工变量的方法,在标准型的约束方程的系数矩阵中人为地构造一个单位阵,从而获得初始可行基,再作进一步迭代。

在单纯形迭代过程中,要求人工变量逐步从基变量被替换出,变为非基变量,这有两种方法:大M 法和两阶段法[10]。

人工变量法的基本思想:对于线性规划问题,有时候很难找出初始基本可行解,

这时可以考虑加入人工变量的方法来解决问题。

基本原理对于标准型的线性规划问题:

?????

??

??≥≥≥=+++=+++=++++++=0

,,0,0max 21221122222121112121112211n m

n mn m m n n n n n n x x x b

x a x a x a b x a x a x a b x a x a x a x c x c x c z

(2-22)

给每个约束方程硬性加入一个人工变量之后得到:

?????

??

??≥≥=+++=+++=++++++=+++++0

,,,0,,.........m a x 11112

221211*********m n n n m

m n n mn m n n n n n n n n x x x x b x x a x a b x x a x a b x x a x a x c x c x c z

(2-23)

这样,就可以以m n n n x x x +++,...,,21为基变量,得到问题的初始基本可行解。在求解的过程中,通过迭代不断地将这些人工变量从基变量中迭代出去,使人工变量均等于0,从而求得原始问题的最优解。若不能把人工变量完全迭代出去,则表明原始问题无可行解。

下面介绍人工变量的两种方法。 (1) 大M 法

在目标函数求最大值的线性规划问题中,设人工变量在目标函数中的系数为-M ,M 为任意大的正数。只要人工变量不为零,目标函数最大值就是一个任意小的数。

(2) 两阶段法

第一阶段:建立一个辅助线性规划,并求解,以判断原线性规划是否存在可行解。 所有人工变量都变成非基变量,目标函数最小值为0,原问题存在基可行解。转到第二阶段。

若目标函数大于0,至少有一个人工变量不能从基变量中转出,由于它取正值,原

问题没有可行解。停止。

第二阶段:在第一阶段最优表格中去掉人工变量,将目标函数系数换成原问题的目标函数系数,接下去用单纯形法计算,直到得到最优解为止。

3.单纯形法

对偶规划是线性规划问题从另一个角度进行研究,是线性规划理论的进一步深化,也是线性规划理论的进一步深化,也是线性规划理论整体的一个不可分割的组成部分。

3.1 对偶问题的提出

每个线性规划都有另一个线性规划(对偶问题)与它密切相关,对偶理论揭示了原问题与对偶问题的内在联系[11]。

3.2 对偶问题的数学模型及对偶关系 原问题P 的标准形式:

??

?≥≤=0

..max X b AX t s CX

Z (2-24)

n m ij T

n a A x x x X ?==)(,),,,(21

对偶问题D 的标准形式:

??

?≥≥=0

..min Y C YA t s Yb

ω (2-25) ),,,(21n y y y Y =

当我们讨论对偶问题时,它必定是与原问题成对出现的;同时,原问题与对偶问题之间没有严格的界限,它们互为对偶:一个是原问题,则另一个就为对偶问题。表2-1给出了线性规划原问题与对偶问题的对应关系,该表也可以看做是一个线性规划原问题转化为对偶问题的一般规律。其中,对于变量与约束间关系的理解,必须考虑到对偶模型的约束与原问题模型的变量相对应,变量则是与原问题模型的约束相对应。如原问题是最小化,则可将对偶问题看做原问题[12]。

表2-1 原问题模型与对偶问题模型的对应关系

原问题(或对偶问题) 对偶问题(或原问题) 目标函数最大化(Z max )

目标函数最小化(ωmin )

n 个变量 m 个约束

约束条件的资源向量(右端项) 目标函数的价格向量(系数)

n 个约束 m 个变量

目标函数的价格向量 约束条件的资源向量

变量???

??≤≥无约束00

约束??

?

??

=≤≥”形式“”形式“”形式“ 约束??

?

??=≤≥”形式“”形式“”形式“ 变量??

?

??≥≤无约束00

例2-2 试求下列线性规划问题的对偶问题。

321422min x x x Z ++=

???

??

??≥≥++≥++≥++0,,5643

732532321321321321x x x x x x x x x x x x (2-26)

解:设对应于约束条件(2-14)的对偶变量分别为,,,321y y y 则由表2-1中原问题与对偶问题的对应关系,可以直接写出上述线性规划问题的对偶问题,有

321532max y y y ++=ω

???

??

?

?≥≤++≤++≤++0,,46752

43232321321321321y y y y y y y y y y y y (2-27) 3.3 线性规划的对偶理论

线性规划的对偶理论包括以下几个主要的基本定理: 定理2-1(对称性定理) 对偶问题的对偶是原问题。 这一定理的内涵显而易见,证明从略。

定理2-2(弱对偶定理) 设X和Y分别是原问题P和对偶问题D的可行解,则必有Yb

CX≤[13]。

定理2-3(对偶原理) 原问题P与对偶问题D存在如下对应关系:

(1) P有最优解的充要条件是D有最优解。

(2) 若P无界则D不可行,若D无界则P不可行。

(3) 若*

X和*Y分别是P和D的可行解,则它们分别为P和D的最优解的充要条件是b

Y

CX*

*=。

原问题与对偶问题的对应关系见表2-2。

表2-2 原问题与对偶问题解的对应关系

对应关系

对偶问题

有最优解无界无可行解

原问题有最优解一定不可能不可能无界不可能不可能一定无可行解不可能一定可能

定理2-4(互补松弛定理) 如果X和Y分别为P和D的可行解,它们分别为P和D 的最优解的充要条件是0

)

(=

-X

YA

C和0

)

(=

-AX

b

Y。

互补松弛定理也称松紧定理,它描述了线性规划问题达到最优时,原问题(或对偶问题)的变量取值和对偶问题(或原问题)约束的松紧性之间的对应关系。我们知道,在一对互为对偶的线性规划问题中,原问题的变量和对偶问题的约束是一一对应的,原问题的约束和对偶问题的变量也是一一对应的。当线性规划问题达到最优时,我们不仅可以同时得到原问题与对偶问题的最优解,而且还可以得到变量与约束之间的一种对应关系。互补松弛定理即揭示了这一点。

3.4 对偶单纯形法的思路

对偶单纯形法是用对偶理论求解原问题的一种方法,而不是求解对偶问题解的单纯形法。与对偶单纯形法相对应,已有的单纯形法称原始单纯形法[14]。

对偶单纯形法适应求解:

(1)使用条件:①检验数全部≤0;

②解答列至少一个元素小于零。

(2)实施对偶单纯形法的基本原则

在保持对偶可行的前提下进行基变换—每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。

(3) 计算步骤

① 建立初始单纯形表,计算检验数行。

???

???

?

??

?<≥>??

?<≥≤,另行处理;至少一个元素

原始单纯形法;—解答列至少一个检验数,转下步;至少一个元素

已得最优解;—解答列检验数全部000000

② 基变换。

先确定换出变量——解答列中的负元素(一般选最小的负元素)对应的基变量出基;即

{}l i i i

b B b B b B )(0)()(m i n 111---=< (2-28)

相应的行为主元行。

然后确定换入变量—原则是:在保持对偶可行的前提下,减少原始问题的不可行性。如果

'''0m i n lk k

k lj lj j j j a z c a a z c -=??

????????<- (2-29)

(最小比值原则),则选k x 为换入变量,相应的列为主元列,主元行和主元列交叉处的元素lk a '为主元素。

③ 将主元素进行换基迭代(旋转运算、枢运算),将主元素变成1,主元列变成单位向量,得到新的单纯形表。

继续以上步骤,直至求出最优解[15]。 例2-3 用对偶单纯形法解下列线性规划问题

2193min x x +=ω

?????

??≥≥+≥+≥+0,373

42..2

121

2121x x x x x x x x t s (2-30)

解:先将这个问题化成标准型

2193max x x Z --=

???

??

??≥=-+=-+=-+0,,373

42..51521

421321x x x x x x x x x x x t s (2-31)

再建立这个问题的初始单纯形表,并进行迭代计算,见下表。

表2-3 初始单纯形表

j c

-3

-9

B C B X

b

1x

2x

3x

4x

5x

0 3x

-2 -1 -1 1 0 0 0 4x

-3 -1 -4 0 1 0 0

5x

-3 -1 -7 0 0 1 j

j Z

c -

-3 -9 0 0 0 j θ

-3/-1

-9/-1

--

--

--

表2-4 单纯形表(第一步迭代)

j c

-3

-9

B C B X b

1x

2x

3x

4x

5x

-3 1x 2 1 1 -1 0 0 0 4x

-3 0 -3 -1 1 0 0

5x

-3 0 -6 -1 0 1 j

j Z

c -

6

0 -6 -3 0 0 j θ

--

-6/-3

-3/-1

--

--

表2-5 单纯形表(第二次迭代)

j c

-3

-9

B C B X b

1x

2x

3x

4x

5x

-3 1x 5/3 1 0 -4/3 1/3 0 -9 2x

1/3 0 1 1/3 -1/3 0 0

5x

1 0 0 1 -

2 1 j

j Z

c -

8

0 0 -1 -2 0 j θ

--

-1

-2

--

最优解是T Y )1,0,0,3/1,3/5(*= 目标函数最优值为8max min =-=Z S 。

第三章 灵敏度分析

灵敏度分析是研究与分析一个系统(或模型)的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此,灵敏度分析几乎在所有的运筹学方法中以及在各种方案进行评价时都是很重要的[16]。

1.边际值(影子价)i q

首先以(≤max,)为例。

边际值(影子价)i q 是指在最优解的基础上,当第i 个约束行的右端项i b 减少一个单位时,目标函数的变化量

∑=--=

=m

k k

k B

B b B

C

b B C x f 1

1

1

)()( (3-1)

i B i i B

C b x f q )(/)(1

--

=??= (3-2)

机会成本

i B l n B n B

C P B

C z )(1

1

1-+-+== (3-3)

因此

?

?

?=++剩余变量松弛变量,人工变量

l n z -l n i z q (3-4)

机会成本的另外表达形式

∑∑==--=

=

=m

i m

i ij

i

ij i B

j B j a q a B

C

P B C z 1

1

1

1

)( (3-5)

关于影子价的一些说明

①影子价是资源最优配置下资源的理想价格,资源的影子价与资源的紧缺度有关; ②松弛变量增加一个单位等于资源减少一个单位; ③剩余变量增加一个单位等于资源增加一个单位;

④资源有剩余,在最优解中就有对应松弛变量存在,且其影子价为0;

⑤影子价为0,资源并不一定有剩余。

2.价值向量的灵敏度分析

价值向量(即目标函数系数)的灵敏度分析分为原最终单纯形表中j c 与非基变量和基变量对应两种情况来讨论[17]。

(1) 若j c 是非基变量j x 的系数,则其对应的最终单纯形表中的检验数为

j B j j

P B C c 1

--=σ

(3-6)

∑=-

=m

i i

ij

j j

y a

c 1

σ

(3-7)

当j c 变化j c ?,要保证最终单纯形表的最优解不变,必有

01

'≤-?+=-j B j j j

P B C c c σ

(3-8)

保证最终单纯形表最优解不变,可得j c 的允许变化值j c ?

j j B j c P B C c -≤?-1

(3-9)

(2) 若r c 是基变量r x 的系数,应有B r C c ∈,当r c 变化r c ?时,就引起B C 的变化,这时

A B

c A B

C A B

C C r B B B 1

1

1

)0,,0,,0,,0()(---?+=?+

),,,(211rn r r r B a a a c A B C ?+=- (3-10) 若要求原最优解不变,必须满足0'≤j σ。于是得到

当 rj j r rj a c a /,0σ≤?< (3-11)

rj

j

r rj a c a /,0σ

≥?> (3-12)

所以,r c ?可变化的范围是

{}}{j

rj rj j r rj j

rj j a a c a a 0|/min 0|/max <≤?≤>σσ (3-13)

3.灵敏度的应用

(1)投入产出法中灵敏度分析

可以用来研究采取某一项重大经济政策后将会对国民经济的各个部门产生怎样的影响。

(2)方案评价中灵敏度分析

可以用来确定评价条件发生变化时备选方案的价值是否会发生变化或变化多少。

线性规划模型及其举例

线性规划模型及其举例 摘要:在日常生活中,我们常常对一个问题有诸多解决办法,如何寻找最优方案,成为关键,本文提出了线性规划数学模型及其举例,在一定约束条件下寻求最优解的过程,目的是想说明线性规划模型在生产中的巨大应用。 关键词:资源规划;约束条件;优化模型;最优解 在工农业生产与经营过程中,人们总想用有限的资源投入,获得尽可能多的使用价值或经济利益。如:当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多,利润最大)。 一.背景介绍 如果产出量与投入量存在(或近似存在)比例关系,则可以写出投入产品的线性函数式: 1()n i ij j j f x a x ==∑,1,2,,,1i m m =+ (1) 若将(1)式中第(1m +)个线性方程作为待求的目标函数,其余m 个线性方程作为资源投入的限制条件(或约束条件),则(1)式变为: OPT. 1()n j j j f x c x ==∑ ST. 1 n ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2) 0,j x ≥ 1,2,,j n =… (2)式特点是有n 个待求的变量j x (1,2,,j n =…);有1个待求的线性目标函数()f x ,有m 个线性约束等式或不等式,其中i b (1,2,,i m =…)为有限的资源投入常量。将客观实际问题经过系统分析后,构建线性规划模型,有决策变量,目标函数和约束条件等构成。 1.决策变量(Decision Variable,DV )在约束条件范围内变化且能影响(或限定)目标函数大小的变量。决策变量表示一种活动,变量的一组数据代表一个解决方案,通常这些变量取非负值。 2.约束条件(Subject To,ST )在资源有限与竞争激烈的环境中进行有目的性的一切活动,都

用excel规划求解并作灵敏度分析

题目 如何利用EXC E L求解线性规划 问题及其灵敏度分析 第 8 组 姓名学号 乐俊松 090960125 孙然 090960122 徐正超 090960121 崔凯 090960120王炜垚 090960118 蔡淼 090960117南京航空航天大学(贸易经济)系 2011年(5)月(3)日

摘要 线性规划是运筹学的重要组成部分,在工业、军事、经济计划等领域有着广泛的应用,但其手工求解方法的计算步骤繁琐复杂。本文以实际生产计划投资组合最优化问题为例详细介绍了Excel软件的”规划求解”和“solvertable”功能辅助求解线性规划模型的具体步骤,并对其进行了灵敏度分析。

目录 引言 (4) 软件的使用步骤 (4) 结果分析 (9) 结论与展望 (10) 参考文献 (11)

1. 引言 对于整个运筹学来说,线性规划(Linear Programming)是形成最早、最成熟的一个分支,是优化理论最基础的部分,也是运筹学最核心的内容之一。它是应用分析、量化的方法,在一定的约束条件下,对管理系统中的有限资源进行统筹规划,为决策者提供最优方案,以便产生最大的经济和社会效益。因此,将线性规划方法用于企业的产、销、研等过程成为了现代科学管理的重要手段之一。[1] Excel中的线性规划求解和solvertable功能并不作为命令直接显示在菜单中,因此,使用前需首先加载该模块。具体操作过程为:在Excel的菜单栏中选择“工具/加载宏”,然后在弹出的对话框中选择“规划求解”和“solvertable”,并用鼠标左键单击“确定”。加载成功后,在菜单栏中选择“工具/规划求解”,便会弹出“规划求解参数”对话框。在开始求解之前,需先在对话框中设置好各种参数,包括目标单元格、问题类型(求最大值还是最小值)、可变单元格以及约束条件等。 2 软件的使用步骤 “规划求解”可以解决数学、财务、金融、经济、统计等诸多实 际问题,在此我们只举一个简单的应用实例,说明其具体的操作 方法。 某人有一笔资金可用于长期投资,可供选择的投资机会包括购买国库券、公司债券、投资房地产、购买股票或银行保值储蓄等。投资者希望投资组合的平均年限不超过5年,平均的期望收益率不低于13%,风险系数不超过4,收益的增长潜力不低于10%。问在满足上述要求的前提下投资者该如何选择投资组合使平均年收益率最高?(不同的投资方式的具体参数如下表。)

线性规划模型的应用分析

第3章线性规划模型的应用 1.某企业制造三种仪器,甲种仪器需要17小时加工装配,8小时检测,售价300元。乙种仪器需要10小时加工装配,4小时检测,售价200元。丙种仪器需要2小时加工装配,2小时检测,售价100元。三种仪器所用的元件和材料基本一样,可供利用的加工装配时间为1000小时,检测时间为500小时。又根据市场预测表明,对上述三种仪器的要求不超过50台、80台、150台。试求企业的最优生产计划。 解:首先将问题中的数据表示到如下表格: i maxZ=300x1+200x2+100x3 17x1+10x2+2x3≤1000 8x1+4x2+2x3≤500 x1≤50 x2≤80 x3≤150 x1,x2,x3≥0 2. 某铸造厂要生产某种铸件共10吨,其成分要求:锰的含量至少达到0.45%,硅的允许范围是 3.25%~5.5%。目前工厂有数量充足的锰和三种生铁可作为炉料使用。这些炉料的价格是:锰为15元/公斤,生铁A为340元/吨,生铁B为380元/吨,生铁C为280元/吨。这三种生铁含锰和含硅量(%)如表3.22所示,问工厂怎样选择炉料使成本最低。 表3.22 成分锰有部分是纯锰,部分是从生铁中提炼出来的,所以改进表格如下:

设铸件中含有三种生铁和锰的量分别为xi(i=1,2,3,4)吨,则数学模型如下: maxZ=340x1+380x2+280x3+15000x4 x1+x2+x3+x4=10 0.45%x1+0.5%x2+0.35%x3+x4≥0.45%*10 4%x1+1%x2+0. 5%x3≥3.25%*10 4%x1+1%x2+0. 5%x3≤5.5%*10 xi≥0(i=1,2,3,4) 3. 某工厂要做100套钢架,每套用长为2.9m,2.1m和1.5m的圆钢各一根。已知原料每根长7.4m,问应如何下料,可使所用原料最省。 解: 4. 绿色饲料公司生产雏鸡、蛋鸡、肉鸡三种饲料。这三种饲料是由A、B、C三种原料混合而成。产品的规格要求、产品单价、日销售量、原料单价见表3.23、表3.24。受资金和生产能力的限制,每天只能生产30吨,问如何安排生产计划才能获利最大? 表3.23 产品名称规格要求销售量(吨)售价(百元) 雏鸡饲料原料A不少于50% 5 9 原料B不超过20% 蛋鸡饲料原料A不少于30% 18 7 原料C不超过30% 肉鸡饲料原料C不少于50% 10 8 表3.24

数学建模(教案)第一章--线性规划

数学建模 第一章 线性规划 §1 线性规划 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工,加工时间分别为每台2小时和1小时;生产乙机床需用C B A 、、三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时,问该厂应生产甲、乙机床各几台,才能使总利润最大? 上述问题的数学模型:设该厂生产1x 台甲机床和2x 乙机床时总利润最大,则21,x x 应满足 (目标函数) 2134m ax x x z += (1) s.t. ( 约 束 条 件 ) ?????? ?≥≤≤+≤+0 ,781022122 121x x x x x x x (2) 这里变量21,x x 称之为决策变量,(1)式被称为问题的目标函数,(2)中的几个不等式是问题的约束条件,记为s.t.(即subject to)。

上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数,故被称为线性规划问题。 总之,线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题。 在解决实际问题时,把问题归结成一个线性规划数学模型是很重要的一步,但往往也是困难的一步,模型建立得是否恰当,直接影响到求解。而选取适当的决策变量,是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量,b 为m 维列向量,A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为 b Ax x c x T -≤-- that such min 1.3 线性规划问题的解的概念 一般线性规划问题的标准型为 ∑==n j j j x c z 1min (3) ∑==≤n j i j ij m i b x a 1,,2,1 s.t.Λ (4) 可行解 满足约束条件(4)的解),,,(21n x x x x Λ=,称为线性规划问题的可行解,而使目标函数(3)达到最小值的可行解叫最优解。

线性规划灵敏度分析

淮北师范大学 2011届学士学位论文 线性规划灵敏度分析 学院、专业数学科学学院数学与应用数学 研究方向运筹学 学生姓名陈红 学号20071101008 指导教师姓名张发明 指导教师职称副教授 2011年4月10日

线性规划的灵敏度分析 陈 红 (淮北师范大学数学科学学院,淮北,235000) 摘 要 本文主要从价值系数j c 的变化,技术系数ij a 的变化,右端常数i b 的变化以及增加新的约束条件和增加一个新变量的灵敏度这几个方面来进行研究;资源条件是线性规划灵敏度分析中的主要应用内容,而对于资源条件b 的一个重要应用是:“影子价格问题”的实际应用,最后简述了线性规划在经济及管理问题上的典型应用和从求解例题的图解法揭示了最优解的一些重要特征。 关键词 单纯形法,灵敏度分析,最优解,资源条件,价值系数

Sensitivity Analysis of Linear Programming Chen Hong (School of Mathematical Science,Huaibei Normal University ,Huaibei,235000) Abstract This thesis is mainly from the variety of the cost coefficient …j c ?, the variety of technology coefficient …ij a ?, the variety of the resources condition…i b ?and increase the new restraint and new variable to analytical linear programming of sensitivity analysis.This thesis is mainly based on the simplex method and dual simplex method of linear programming to system analytical the influence of the variety upon the optical solution of the coefficient of the simplex table.Linear programming of sensitivity analysis in physically of application is mainly about application of the variety of resources c ondition…i b ?in the economic management …shadow price problem?. Keywords simplex method, sensitivity analysis, optimum solution , resources condition ,cost coefficient

matlab、lingo程序代码23-线性规划问题及灵敏度分析

线性规划问题及灵敏度分析在LINGO软件中的实现 (龙少波李东阳罗添元) 一、问题的提出: 某公司饲养实验用的动物以出售给动物研究所,已知这些动物的生长对饲 料中3种营养成分(蛋白质、矿物质和维生素)特别敏感,每个动物每周至少需 要蛋白质60g,矿物质3g,维生素8mg,该公司能买到5种不同的饲料,每种饲 料1kg所含各种营养成分和成本如下表所示,如果每个小动物每周食用饲料不超 过52kg,才能满足动物生长需要。 A1 A2 A3 A4 A5 营养最 低 要求蛋白质(g) 0.3 2 1 0.6 1.8 60 矿物质(g) 0.1 0.05 0.02 0.2 0.05 3 维生素(mg) 0.05 0.1 0.02 0.2 0.08 8 成本(元/ kg)0.2 0.7 0.4 0.3 0.5 问题: 1.求使得总成本最低的饲料配方? 2.如果另一个动物研究对蛋白质的营养要求变为59单位, 但是要求动物的价格比现在的价格便宜0.3元,问该养殖所 值不值得接受? 3.由于市场因素的影响,X2的价格降为0.6元每千克, 问是否要改变饲料配方? 二、建立线性规划数学模型 解答: (1)设需要饲料A1, A2, A3, A4分别为X1, X2, X3, X4kg,则建立线 性规划数学模型如下: 目标函数:MinS=0.2X1+0.7X2+0.4X3+0.3X4+0.5X5 约束条件:0.3X1+2X2+X3+0.6X4+1.8X5>=60 0.1X1+0.05X2+0.02X3+0.2X4+0.05X5>=3 005X1+0.1X2+0.02X3+0.2X4+0.08X5>=8

线性规划模型在生活中的实际应用

线性规划模型在生活中的实际应用 一、线性规划的基本概念 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素. 二、线性规划模型在实际问题中的应用 (1)线性规划在企业管理中的应用范围 线性规划在企业管理中的应用广泛,主要有以下八种形式: 1.产品生产计划:合理利用人力、物力、财力等,是获利最大. 2.劳动力安排:用最少的劳动力来满足工作的需要. 3.运输问题:如何制定运输方案,使总运费最少. 4.合理利用线材问题:如何下料,使用料最少. 5.配料问题:在原料供应的限制下如何获得最大利润. 6.投资问题:从投资项目中选取方案,是投资回报最大. 7.库存问题:在市场需求和生产实际之间,如何控制库存量从而获得更高利益. 8.最有经济计划问题:在投资和生产计划中如何是风险最小 . (2)如何实现线性规划在企业管理中的应用 在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系,摸清企业的资

源.首先通过建网、建库、查询、数据采集、文件转换等,把整个系统的各有关部分的特征进行量化,建立数学模型,即把组成系统的有关因素与系统目标的关系,用数学关系和逻辑关系描述出来,然后白较好的数学模型编制成计算机语言,输入数据,进行计算,不同参数获取的不同结果与实际进行分析对比,进行定量,定性分析,最终作出决策.

一般线性规划数学模型

一般线性规划问题 1. 线性规划的条件: ① 决策变量有没有---------------------必须有 ② 目标函数和约束条件是不是决策变量的线性表达式------------------必须是 ③ 决策变量非负条件是否满足-------------必须满足 ④ 目标函数是否表现出极大化或极小化------必须表现 2. 线性规划的表达式 目标函数: x c x c x c n n z Max Min +???++=2211)( 约束条件: b x a x a x a n n 112 12 1 11 )(≤≥+???++ b x a x a x a n n 222 2 21 21 )(≤≥+???++ b x a x a x a n n 332 2 31 31 )(≤≥+???++ ..............

b x a x a x a n n nn n )(2 2 1 n1 ≤≥+???++ 非负性约束: 0,,0,02 1 ≥???≥≥x x x n 问题重述 某储蓄所每天的营业时间是上午9时到下午5时。根据经验,每天不同时间段所需要的服务员数量如表17所示。储蓄所可以雇用全时和半时两类服务员。全时服务员每天报酬100元,从上午9时到下午5时工作,但中午12时到下午2时之间必须安排1h 的午餐时间。储蓄所每天可以雇用不超过3名的半时服务员,每个半小时服务员必须连续工作4h ,报酬40元。(1)问该储蓄所应如何雇用全时和半时两类服务员。(2)如果不能雇用半时服务员,每天至少增加多少费用。(3)如果雇用半时服务员的数量没有限制,每天可以减少多少费用? 表16 每天不同时间段所需要的服务员数量

线性规划模型的应用与灵敏度分析正文

线性规划模型的应用与灵敏度分析 第一章线性规划问题 1.线性规划简介及发展 线性规划(Linear Programming)是运筹学中研究最早、发展最快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法,研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写为LP。它是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面,为合理利用有限的人力、物力、财力等资源做出的最优决策,提供科学的依据。 线性规划及其通用解法——单纯形法是由美国G.B.Dantzig在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视[1]。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法,为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力[2]。1951年美国经济学家库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年莱姆基提出对偶单纯形法,1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年塔克提出互补松弛定理,1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究[3]。由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。建立线性规

数学建模习题——线性规划

某银行经理计划用一笔资金进行有价证券的投资,可供购进的证券以及其信用等级、到期年限、收益如下表所示.按照规定,市政证券的收益可以免税,其他证券的收益需按50%的税率纳税.此 表四 问:(1)若该经理有1000万元资金,应如何投资? (2)如果能够以2.75%的利率借到不超过100万元资金,该经理应如何操作? (3)在1000万元资金情况下,若证券A的税前收益增加为4.5%,投资应否改变?若证券C的税前收益减少为4.8%,投资应否改变? 解:设利润函数为M(x),投资A、B、C、D、E五种类型的证券资金分别为

12345,,,,x x x x x 万元,则由题设条件可知 12345123452341234512345123451234512345()0.0430.0270.0250.0220.0451000400 225 1.4()9154325(),,,,0 M x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++≤++≥++++≤++++++++≤++++≥ 利用MATLAB 求解最优解,代码如下: c=[-0.043 -0.027 -0.025 -0.022 -0.045]; A=[1 1 1 1 1;0 -1 -1 -1 0;0.6 0.6 -0.4 -0.4 3.6;4 10 -1 -2 -3]; b=[1000;-400;0;0]; Aeq=[]; beq=[]; vlb=[0;0;0;0;0]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) 运行结果如下:

线性规划与灵敏度分析练习题

线性规划练习题 1、用单纯形表求解以下线性规划问题 (1) max z= x1-2x2+x3 s.t. x1+x2+x3≤12 2x1+x2-x3≤ 6 -x1+3x2≤9 x1, x2, x3≥0 (2) min z= -2x1-x2+3x3-5x4 s.t x1+2x2+4x3-x4≤ 6 2x1+3x2-x3+x4≤12 x1+x3+x4≤ 4 x1, x2, x3, x4≥0 (3) min z= 3x1-x2 s.t. -x1-3x2≥-3 -2x1+3x2≥-6 2x1+x2≤8 4x1-x2≤16 x1, x2≥0 二、配料问题 某工厂要用四种合金T1,T2,T3和T4为原料,经熔炼成为一种新的不锈钢G。这四种原料含元素铬(Cr),锰(Mn)和镍(Ni)的含量(%),这四种原料的单价以及新的不锈钢材料G所要求的Cr,Mn和Ni的最低含量(%)如下表所示: 表错误!文档中没有指定样式的文字。-1 设熔炼时重量没有损耗,要熔炼成100公斤不锈钢G,应选用原料T1,T2,T3和T4各多少公斤,使成本最小。 灵敏度分析练习题 一、已知以下线性规划问题

max z= 2x1+x2-x3 s.t. x1+2x2+x3≤8 -x1+x2-2x3≤4 x1, x2, x3≥0 及其最优单纯形表如下: z x1 x6 (1)求使最优基保持不变的c2=1的变化范围。如果c2从1变成5,最优基是否变化,如果变化,求出新的最优基和最优解。 (2)对c1=2进行灵敏度分析,求出c1由2变为4时的最优基和最优解。 (3)对变量x3在第二个约束中的系数a23=-2进行灵敏度分析,求出a23从-2变为1时新的最优基和最优解。 (4)增加一个新的变量x6,它在目标函数中的系数c6=4,在约束条件中的系数向量为a6 1 2 = ? ? ? ? ? ?, 求新的最优基和最优解。 (5)增加一个新的约束x2+x3≥2,求新的最优基和最优解。 (6)设变量x1在约束条件中的系数向量由 1 1 - ? ? ? ? ? ?变为 -? ? ? ? ? ? 1 2 ,求出新的最优基和最优解。 二、某工厂用甲、乙、丙三种原料生产A、B、C、D四种产品,每种产品消耗原料定额以及三种原料 的数量如下表所示: (1)求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量。 (2)求四种产品的利润在什么范围内变化,最优生产计划不会变化。 (3)求三种原料的影子价格和四种产品的机会成本,并解释最优生产计划中有的产品不安排生产的原因。 (4)在最优生产计划下,哪一种原料更为紧缺?如果甲原料增加120吨,这时紧缺程度是否有变化?

运筹学-线性规划模型在实际生活中的应用

线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色,研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域,是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析,如何合理的分配利用,最终找到最优解使企业利润最大,说明了线性规划在实际生活中的应用,而且对线性规划问题模型的建立,模型的解进行了分析,运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言:线性规划(Linear programming,简称LP)是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。 在实际生活中,经常会遇到一定的人力、物力、财力等资源条件下,如何精打细算巧安排,用最少的资源取得最大的效益的问题,而这正是线性规划研究的基本容,它在实际生活中有着非常广泛的应用.任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策,即如何有效地利用人力、物力完成更多的任务,或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下,大量不同的资源必须同时进行分配,需要这些资源的活动可以是不同的生产活动,营销活动,金融活动或者其他一些活动。随着计算技术的不断发展,使成千上万个约束条件和决策变量的线性规划问题能迅速地求解,更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题,贴近生活,很好的吧线性规划应用到生活实践中。 1、简单线性问题步骤简单介绍 建模是解决线性规划问题极为重要的环节,一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际容,要明确目标函数和约束条件,通过表格的形式把问题中的已知

线性规划模型的应用与灵敏度分析

摘要 线性规划是解决稀缺资源最优分配的有效方法,使付出的费用最少或获得的利益最大。它的研究对象是有一定的人力、财力、资源条件下,如何合理安排使用,效益最高;某项任务确定后,如何安排人、财、物,使之最省。它要解决的问题的目标可以用数值指标反映,对于要实现的目标有多种方案可以选择,有影响决策的若干约束条件。本文主要介绍了线性规划模型在实际生活中的应用,其中包括解线性方程组的各种方法,如图解法、单纯形法、以及对偶单纯形法等等,以及简单介绍了有关灵敏度分析的方法。由于许多问题仅仅利用线性规划的方法还不足以解决,因此用到了对偶理论,也因此引出了对偶单纯形法。对偶规划是线性规划问题从另一个角度进行研究,是线性规划理论的进一步深化,也是线性规划理论整体的一个不可分割的组成部分。灵敏度分析是对线性规划结果的再发掘,是对线性规划理论的充要应用,本文以实例验证灵敏度分析的实际应用。 关键词:线性规划;单纯形法;对偶单纯形法

ABSTRCT Linear programming is an effective method to solve the optimal allocation of scarce resources, make the cost of pay or receive at least the interests of the largest. Its object of study is the human and financial resources, resource conditions, how to reasonably arrange to use, benefit is supreme; A task is determined, how to arrange people, goods, and make it the most provinces. It to the target can be used to solve the problem of the numerical indicators, to achieve a variety of solutions to choose from, have an impact on the decision of some constraint conditions. Through the subject design, can deepen the operations research, optimization method, linear programming, nonlinear programming, to improve the integrated use of knowledge, improve the ability of using the sensitivity analysis to solve various practical problems. This article mainly introduces the application of linear programming model in real life, including the various methods of solving linear equations, as shown in figure method, simplex method and dual simplex method, etc., and simply introduces the method of sensitivity analysis. Due to many problems just by using the method of linear programming is not enough to solve, so use the duality theory, thus raises the dual simplex method. The dual programming is linear programming problem from another Angle, is the further deepening of linear programming theory, linear planning theory as a whole is also an integral part of. Sensitivity analysis is to discover, the result of the linear programming is the charge to application of linear programming theory. Keywords: linear programming;Simplex method;The dual simplex method

灵敏度分析实验例子

实验报告 课程名称:运筹学 实验项目名称:应用Excel对线性规划进行灵敏度分析班级与班级代码: 实验室名称(或课室): 专业: 任课教师: 学号: 姓名: 实验日期:2010 年10 月18 日 广东商学院教务处制

姓名实验报告成绩 评语: 指导教师(签名) 年月日说明:指导教师评分后,实验报告交院(系)办公室保存。

实验二应用Excel对线性规划的灵敏度分析 一、实验目的与要求 1.了解线性规划模型中各参数的变化对最优解的影响。 2.会用Excel中提供的敏感性报告对目标函数系数进行灵敏度分析。 3.会用Excel中提供的敏感性报告对约束条件右端值的灵敏度分析。 二、实验步骤与方法 1.可以在电子表格中采取试验的方法,不断增加或减少的 c值,直到最优 j 解发生改变,以找到最优解发生变化时对应的 c值.但是,这样计算太 j 麻烦了。 2.在Excel求得最优解之后,在其右边列出了它可以提供的三个报告。 选择第二项敏感性报告的选项,就可以得到灵敏度的分析报告,它显示在模型的工作表之前。 3.当几个价值系数同时变动时,注意使用百分之百法则。 4.对约束条件限定数的灵敏度分析同上:选择第二项“敏感性报告”的 选项,就可以得到灵敏度的分析报告,其中“约束”表即是。 5.若几个约束限定数同时变动,也要注意使用百分之百法则。 三、实验内容 第1题. 医院放射科目前可以开展X线平片检查和CT检查业务,现拟购买磁共振仪,以增A 设磁共振检查业务。为此A医院收集了有关信息,从医院获取最大利润角度出发,问是否应购买磁共振仪?经过资料收集,A医院估计今后放射科如果开展此3项业务,在现有放射科医务人员力量和病人需求的情况下,每月此3项业务的最多提供量为1800人次。平均每人次检查时间、每月机器实际可使用时间、平均每人次检查利润如下表 放射科业务 项目X线平片检查CT检查磁共振检查平均每人次检查时间(小时/次)0.1 0.25 0.5 每月机器实际可使用时间(小时)300 120 120 平均每人次检查利润(元/次)20 60 10

线性规划的实际应用模型

目录 摘要 ---------------------------------------------------1 引言 ---------------------------------------------------2 一线性规划的概念 -------------------------------------3 二线性规划的实际应用 ----------------------------------4 ( (四)体育上的应用 1.合理安排比赛问题 -------------13 2.选拔选手问题 -----------------14 (五)旅行上的问题:旅行背包问题 ------------------------15 (六)航空上的问题:航空时间安排问题 --------------------16 (七)城市规划的应用:设施布点问题 ----------------------18 (八)日常生活上的应用 1.食用油的结构优化问题 ---------19 2.饮食问题 ---------------------21 (九)农业上的应用:农业种植问题 ------------------------23 三总结及参考文献 --------------------------------------25 线性规划的实际应用模型 王丽娜 (渤海大学数学系辽宁锦州 121000 中国)

摘要:本文从运筹学的角度分析线性规划的实际应用模型,随着人类社会的进步,科学 技术的发展,经济全球化进程的日益加快,线性规划在实际中的应用越来越广泛,主要应用 于经济与管理,军事,金融,体育,旅行,航空,城市规划,日常生活,农业九大方面,因此,线性 规划作为一门科学已被人们广泛接受,并已日益成为人类社会和经济生活中一种不可或缺的 工具。 关键词:运筹学线性规划分析模型 Zhe model in practical application of linear programming Wang lina (Department of Mathematics Bohai University Liaoning Jinzhou 121000 China) Abstract:This article analyse the practical application of linear programming from the sight of operational research,with the advancement of human society,the development of science and technology and the faster grogramming has wider application in the practical,has been applied to nine aspects,in econemy,management,military,finance,physical education,travelling,airline,city planning,daily life, agriculture.The examples will be given to show the application in the nine aspects given abo。 Key word:operational research ,linaear programming, analy ,model 引言 线性规划是运筹学的一个重要分支。也是研究较早的,发展较快 的,应用较广而比较成熟的一个分支。

线性规划问题及其数学模型

第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)????? ? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ????? ? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)?? ??? ??? ???==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij (4)???????????=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确,为什么? (1)如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解; (2)如果线性规划的对偶问题无可行解,则原问题也一定无可行解; ( 3)在互为对偶的一对原问题与对偶问题中,不管原问题是求极大或极小,原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值; (4)任何线性规划问题具有唯一的对偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示,求表中各括弧内未知数的值。

线性规划问题及灵敏度分析

实验一 线性规划问题及灵敏度分析 实验目的:了解WinQSB 软件在Windows 环境下的文件管理操作,熟悉软件界面内容, 掌握操作命令。用WinQSB 软件求解线性规划,掌握winQSB 软件写对偶规划,灵敏度分析和 参数分析的操作方法。 实验每组人数及学时:组人数1人,学时数:4学时 实验环境:装有WinQSB 软件的个人电脑 实验类型:验证性 实验内容: 一、 用WinQSB 软件求解线性规划的方法: 操作步骤: 1.将WinQSB 文件复制到本地硬盘;在WinQSB 文件夹中双击setup.exe 。 2.指定安装WinQSB 软件的目标目录(默认为C:\ WinQSB )。 3. 安装过程需输入用户名和单位名称(任意输入),安装完毕之后,WinQSB 菜单自动 生成在系统程序中。 4.熟悉WinQSB 软件子菜单内容及其功能,掌握操作命令。 5.求解线性规划。启动程序 开始→程序→WinQSB→Linear and Integer Programming 。 6.学习例题 点击 Problem→lp.lpp, 点击菜单栏Solve and Analyze 或点击工具栏中 的图标用单纯形法求解,观赏一下软件用单纯形法迭代步骤。用图解法求解,显示可行域, 点击菜单栏Option →Change XY Ranges and Colors,改变X1、X2的取值区域(坐标轴的 比例),单击颜色区域改变背景、可行域等8种颜色,满足你的个性选择。 下面结合例题介绍WinQSB 软件求解线性规划的操作步骤及应用。 用WinQSB 软件求解下列线性规划问题: 1234 max 657Z x x x x =+++ s.t. 12341 2341231234 312342692608521507300 01020,,0,x x x x x x x x x x x x x x x x x x x x +++≤??-+-≥??++=?-≥??-≥?≤≤??≥?无约束 解:应用WinQSB 软件求解线性规划问题不必化为标准型,如果是可以线性化的模型则先 线性化,对于有界变量及无约束变量可以不用转化,只需要修改系统的变量类型即可,对于 不等式约束可以在输入数据时直接输入不等式符号。 (1)启动线性规划(LP )和整数规划(ILP )程序 点击开始→程序→WinQSB →Linear and Integer Programming ,显示线性规划和整数规 划工作界面(注意菜单栏、工具栏和格式栏随主窗口内容变化而变化)。这一程序解决线性 规划(LP )以及整数线性规划(ILP )问题。

线性规划模型在企业生产计划中的应用

诚信声明 我声明,所呈交的毕业论文是本人在老师指导下进行的研究工作及取得的研究成果。据我查证,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,我承诺,论文中的所有内容均真实、可信。 毕业论文作者签名:签名日期:年月日

摘要:在企业生产过程中,生产资源的分配直接影响到企业的经济效益。因此,企业在制定生产计划时,人力物力和时间等资源的优化配制是首要面对的关键问题,而建立线性规划模型则是目前解决该问题的有效方法之一。本文旨在针对上述有限资源条件的约束下,通过建立相应的线性规划模型来制定生产计划以实现企业资源最优化、利益最大化,同时利用LINGO 11.0软件求解线性规划模型并分析在某些资源变动时对该模型所产生的影响并寻求最优生产方案。 关键词:企业生产计划;线性规划;数学模型;LINGO 11.0

Abstract:In the enterprise production process, the allocation of production resources directly affects the economic efficiency of enterprises. Therefore, enterprises in the development of production plan, formulated to optimize the resources of manpower and time is the key problem of face. And to establish the linear programming model is one of the effective ways to solve the problem. This paper aimed at the limited resource constraints, by establishing linear programming model corresponding to make production plan in order to realize the maximization of enterprise resource optimization, interest, and using LINGO11.0 software to solve the linear programming model and analysis the influence on the model in some resource changes and seek the optimal production plan. Key words:Production plan;Linear programming;Mathematical model; LINGO 11.0 目录

相关主题
相关文档 最新文档