作文,,,,线性规划在,生活优化问题中的应用

【www.zhuodaoren.com--作文】

作文,,,,线性规划在,生活优化问题中的应用(一)
浅谈线性规划在生活中的应用2

浅谈线性规划在生活中的应用

摘 要 线性规划的研究对象是计划管理工作中有关安排和估值的问题,解决的主要问题是在给定条

件下,按某一衡量指标来寻找安排的最优方案.文章涉及的是在两个限定条件下的最大利润问题，它是一种最简单的线性规划，解决的方法就是用图象法和消去法.

关键词 线性规划;松弛变量;最优解;目标函数 中图分类号 0122.1

线性规划作为数学规划中最简单的一种问题.它的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大或极小值问题.如果约束条件和目标函数都是呈线性关系的就叫线性规划.要解决线性规划问题，从理论上讲都要解线性方程组，而解线性方程组的常见方法是图象法和消去法.

1 预备知识

线性规划是数学规划中理论成熟,方法有效,应用最广泛的一个分支.它研究满足一组线性的等式或不等式约束条件,对一定的线性目标函数进行最优化处理的问题.它是由丹捷格(G.B.Dantzig)在1947年发表的成果.所解决的问题是美国制定空军军事规划时提出的,并提出了求解线性规划问题的方法.

2 线性规划问题解的基本概念

2.1 线性规划

线性规划是在线性约束的有限集合上使一个仿射函数(仿射函数亦即线性函数)达到最大(或最小)的优化问题.

2.2 松弛变量

松弛变量表示一个决策过程中原料消耗的剩余量.

2.3 可行解,可行域

满足若干个约束条件的解称为线性规划问题的可行解,所有的可行解构成的集合叫它的可行域.

2.4 最优解

满足若干个约束条件和某个目标函数式的可性解称为线性规划问题的最优解.

2.5 基本可行解

满足若干个非负条件的基本解称为基本可行解.

3 简单线性规划问题的解法

将实际生活中的线性规划问题,抽象为数学形式,目的在于找到解决问题的方法.为此,我们作以下一些讨论.

3.1 最大利润问题

例1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗.如表1所示:

表1

,使该工厂在限定条件下获利最多?

显见,这个问题可以用以下的数学模型来描述:

设x1,x2分别表示在计划期内产品Ⅰ、Ⅱ的产量.因为设备的有效台时是8,这是一个限制产量的条件,所以确定产品Ⅰ、Ⅱ的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为:x12x28.同理,因原材料的限量,可以得到两个不等式:4x116,4x212.

该厂的目标是在不超过所有资源限量的条件下,如何确定产量x1,x2以得到最大的利润.用z表示利润,这时z2x13x2.综合上述,此计划问题可用数学模型表示为:

目标函数: z2x13x2

x12x28

4x161

约束条件: 

124x2

x1,x20

3.2 两个变量的线性规划问题的图解法

现在我们用图解法来解上述的例1:

在以x1,x2为坐标轴的直角坐标系中,非负条件x10,x20是指第一象限.每一个约束条件都代表一个半平面,如约束条件

x12x28是代表以直线x12x28为边界

的左下方的半平面.若同时满足:

x10,x20,x12x28,4x116和4x212的约束条件的点,必然落在x1,x2坐标

轴和由这三个半平面交成的区域内(如右图).

阴影区域中的每一个点(包括边界)都是这个线性规划问题的解,因而此区域是此线性规划问题的解集合,称它为可行域.

再来分析目标函数z2x13x2.在这个坐标平面上,它可表示以z为参数,以一族平行线:x2()x1

2

为斜率的3

z

.位于同一直线上的点,具有相同的目标函数值,因而称它为“等值3

2z

线”.当z值由小变大时,直线x2()x1沿其法线方向向右上方移动．当移动到Q2点时，

33

使z值在可行域边界上实现最大化（如下图）:

这就得到了例

１的最优解对应的点

23

Q2,Q2点的坐标为(4,2).于是可计算出满足

所有约束条件的最大值z14．

这说明该厂的最优生产计划方案是：生产４件产品Ⅰ，生产２件产品Ⅱ，可得最大利润为14元．

3.3 用消去法解两个变量的线性规划问题

例２ 某车间生产甲、乙两种产品，已知制造一件甲产品需要Ａ种元件５个,Ｂ种元件３个；制造一件乙产品需要Ａ种元件２个，Ｂ种元件３个.现因某种条件限制,只有A种元件180,B种元件135个；每件甲种产品可获利20元, 每件乙种产品可获利15元.试问在这种条件下,应该生产甲、乙两种产品各多少件才能得到最大利润?

解: 设应该生产甲产品x1件,乙产品x2件,才能得到最大利润S元.根据题意,此问题可用数学模型表示为:

目标函数 S20x115x2

5x12x2180

满足约束条件 3x13x2135

x,x0

21【作文,,,,线性规划在,生活优化问题中的应用】

即求解满足约束条件的x1,x2,使目标函数S20x115x2的值最大.为此,引进松弛变量

x3,x4,把线性规划问题化为标准形式:

求SS20x115x2的最小值,并且满足：

'

5x12x2x3180



3x13x2x4135

x,x,x,x012345x12x2180

也就是求方程组 

3x13x2135

的非负解,并且使目标函数SS20x115x2的值最小．

显然,有一个可行解是: x10,x20,x3180,x4135. 相应的目标函数值为: S200150

'

'

(1)(2)

'

0

再从目标函数SS20x115x2看出.如果x1不取0,而增大x1的值,目标函数的值可以减少.为此,把x1换成x3.

由(1)得

x136

21x2x3 55

21

x36xx32155

这样,原方程组可改写成 

x1353(362x1x)3x423255

相应的目标函数可改为: SS20(36

'

(3)

(4)

21

x2x3)15x2 55

7207x24x3

显然,又可得另一个可行解是: x136,x20,x30,x427 相应的目标函数值为: S7207040 720

再从目标函数S1'S7207x24x3看出．如果x2不取0,而增大x2的值,目标函数的值还可以减少.为此,把x2换成x4,并且化简(4)得

x215将(5)式代入(3)式得

'

15

x3x439

(5)

2151

(15x3x4)x3 539512

30x3x4

39

x136

12

x30xx43139

因而方程组可改写成 

x151x5x23439

15

x3x4)4x3 39535

x4 825x3

39

相应的目标函数改为 S27207(15

'

(6)

(7)

显然,又可得另一个可行解是: x130,x215,x30,x40

535'

S282500

39

825

相应的目标函数值为

从目标函数S2825以这一可行解是最优解.

'

535'x1x4可以看出,目标函数S2825已经是最小值,所39

即原问题的最优解为 x130,x215 相应的目标函数值 SS

'

825

所以在这种条件下,生产甲、乙产品各30件、15件,使得最大利润为825元.

以上是用两种不同的方法解决了我们生产生活中常遇到的最大利润问题.消去法作为数学中常见的一个解方程组的方法,在解线性规划的问题中起到了很重要的作用.下面,我们再看一例,如何用消去法解线性规划中的问题.

例3 求x1,x2的值,使它们满足约束条件

x1x2



x12x2x1,x2

并使目标函数 S2x15x2的最大值.

4380

解: 引进松弛变量x3,x4,x5,把题目对应的线性规划问题化为标准形式:

求S'S2x15x2的最小值,并且满足：

4x1x3

xx432



x2xx8251x1,x2,x3,x4,x50x34x1

也就是求方程组 x43x2

x8x2x

125

的非负解,并且使目标函数SS2x15x2的值最小． 显然,有一个可行解是: x10,x20,x34,x43,x58. 相应的目标函数值为: S12050

再从目标函数S12x15x2看出．如果x1不取0,而增大x1的值,目标函数的值可以减少.为此,把x1换成x3. 由(3)(1)得

'

''

(1)(2) (3)

作文,,,,线性规划在,生活优化问题中的应用(二)
线性规划在现实生活中的应用

线性规划在现实生活中的应用

03742011127崔钊 03742011121王源 03742011151万成 （电子信息工程四区队）

【摘要】：线性规划是运筹学中一种最常用的方法。线性规划在科学决策与经营管理中实效

明显,但是对于规模较大的线性规划模型,其求解过程非常烦琐,不易得出结果。本文简要介绍了线性规划的发展历程以及用ＭＡＴＬＡＢ程序实现了线性规划问题数学模型的求解方法,并进一步通过对实例模型求解方法的分析比较,证明所采用的程序方法有效快捷，为我们解决复杂的线性规划问题提供了方便。

【关键词】：线性规划；建模；方案；ＭＡＴＬＡＢ；约束条件;最优解；

线性规划是运筹学中一种最常用的方法。线性规划是合理利用、调配资源的一种应用数学的方法。它的基本思路就是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,用最少的资源去实现这个任务;二是资源的数量已定,如何利用、分配,使任务完成得最多.前者是求极小,后者是求极大.线性规划是在满足企业内、外部的条件下,实现管理目标和极值问题,就是要以尽少的资源输入来实现更多的社会需要的产品的产出。

一、线性规划及其求解概述

自从1938年由年仅26岁的苏联列宁格勒大学数学教授康托洛维奇提出线性规划后,40年代又由丹捷格(G.B.Dantzig)教授独立地在美国发现,并找到了一种计算线性规划模型的有效方法,也就是我们今天所说的“单纯形法”(Simpexmethod)。之后,在经济学家库普曼斯(T.C.Koopmans)的呼吁下,许多年轻一代的经济学家,比如其中的阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都对线性规划表现出了极大的兴趣,并在运筹学的某些领域中发挥过重要作用,他们都因此而获得了诺贝尔奖金。1975年,康托洛维奇和库普曼斯也因“最优质资源配置理论的贡献”而获诺贝尔经济学奖,遗憾的是丹捷格却榜上无名。现在,在运筹学的众多分支学科中,线性规划已成为研究最为深入,实用效果也最为明显的一个分支。

有了单纯形法以后,对于简单的线性规划模型来说,用相应的方法凭着一支笔和一张纸就能 进行求解,但是对于规模较大的模型来说,这种办法就行不通了,虽然手工列表进行计算从原理上讲并不困难,但是却非常烦琐,单调而且容易出错。从生产和管理以及科学研究中提出来的大量实际问题,其决策变量和约束条件多到十几个、几十个、几百个,甚至成千上万个,这些问题就不是人力所能及的了。由于电子计算机的普及,求解线性规划以及许许多多运筹学问题的软件包也应运而生,并走向市场,成为大型科研机构、厂矿企业、学校和普通用户都不可

缺少的一种工具,Matlab就是其中一个比较常用的软件。

二、线性规划的定义、数学模型

1.线性规划的定义:根据线性规划模型的基本结构,在满足一组约束条件下,求一组变量的值,使得其成为目标函数的最优解。 (1)变量

变量又叫未知数,它是实际系统的未知因素,也是决策系统中的可控因素,一般称为决策变量,常引用英文字母加下标来表示,如X1,X2,X3,„ ,Xn等。 (2)目标函数

将实际系统的目标,用数学形式表现出来,就称为目标函数,线性规划的目标函数是求系统目标的数值,即极大值,如产值极大值、利润极大值或者极小值,如成本极小值、费用极小值、损耗极小值等等。 (3)约束条件

约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面,如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等,这些因素都对模型的变量起约束作用,故称其为约束条件。约束条件的数学表示形式为三种,即≥、=、≤。线性 规划的变量应为正值。

2.线性规划研究的是线性目标函数在线性约束条件下取得最大值或最小值的问题。一般地,线性规划问题的数学模型是: a11x1+a12x2+ „ +a1mxm≤b1 a21x1+a22x2+ „ +a2mxm≤b2 amx1+an2x2+ „ +anmxm≤bm

其中aij(i=1,2,„ ,n;j=1,2,„ ,m),bi(i=1,2,„ ,n)都是常量,xj(j=1,2,„ ,m)是非负变量,求目标函数Z=C1X1+C2X2+ „ +CmXm,的Zmax或Zmin。

三、线性规划模型的建立

（一）线性规划问题的提出

公路工程混合料配合比设计是一门新的工程实用技术，它是在满足一定技术指标的前提下，以取得最大经济效益为目标来确定各种材料的最佳配方比例，从而提高工程质量并降低生产成本。它是工程建设中的一个重要环节，同时也是工程技术管理的重要内容。混合料配合比计算，常规方法有式计算和图解法。这两种方法主要通过手工完成，计算工作量大、出错率高、精度低，且都没有考虑生产成本问题，其计算及结果虽然满足规范要求，但混合料总体成本却很少能达到最低。

例:某混凝土厂出售商品混凝土,原料供应情况如下表(表1):

表1 原料供应情况及成本表

编号 名称 月供应量(方) 单价(元/方) A 碎石 6000 30 B 卵石 4000 25 C 矿渣 13000 35

按工程需要配制混凝土。设各种混凝土骨料的级配限度,水泥、砂等掺和料及生产费用如表2。

表2 混凝土骨料级配限度及辅料、加工费用表

混凝土种类 骨料级配限度 水泥、砂、掺和料及加工费(元/方)

1 A≥60% 45【作文,,,,线性规划在,生活优化问题中的应用】

C≤20%

2 C≥60% 50

3 A≤15% 60

C≤50%

假设三种混凝土的售价均为每方120元;为简化计算,设每方骨料生产1方混凝土,生产的混凝

本文来源：http://www.zhuodaoren.com/yuwen352443/

推荐访问:运筹学中线性规划问题 线性代数在生活中应用