搜档网
当前位置:搜档网 › 数学建模(教案)第一章--线性规划

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

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

数学建模

第一章 线性规划

§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 a x 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)达到最小值的可行解叫最优解。

可行域所有可行解构成的集合称为问题的可行域,记为R。

1.4 线性规划的图解法

图解法简单直观,有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示,阴影区域即为LP问题的可行域R。对于每一固定的值z,使目标函数值等于z的点构成的直线称为目标函数等位线,当z变动时,我们得到一族平行直线。让等位线沿目标函数值减小的方向移动,直到等位线与可行域有交点的最后位置,此时的交点(一个或多个)即为LP的最优解。

对于例1,显然等位线越趋于右上方,其上的点具有越大的目标函数值。不难看出,本例的最优解为T

*=,最优目标值

x)6,2(

26

z。

*=

从上面的图解过程可以看出并不难证明以下断言:

(1)可行域R可能会出现多种情况。R可能是空集也可能是非空集合,当R非空时,它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域,也可能是无界区域。

(2)在R非空时,线性规划既可以存在有限最优解,也可以不存在有限最优解(其目标函数值无界)。

(3)R非空且LP有有限最优解时,最优解可以唯一或有无穷多个。

(4)若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域R 的“顶点”。

上述论断可以推广到一般的线性规划问题,区别只在于空间的维数。在一般的n 维空间中,满足一线性等式∑==n

i i i b x a 1的点集

被称为一个超平面,而满足一线性不等式∑=≤n i i i b x a 1

(或∑=≥n

i i i b x a 1

的点集被称为一个半空间(其中),,(1n a a 为一n 维行向量,b 为一实数)。有限个半空间的交集被称为多胞形,有界的多胞形又被称为多面体。易见,线性规划的可行域必为多胞形(为统一起见,空集Φ也被视为多胞形)。

在一般n 维空间中,要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点,但这一几何概念的推广在一般n 维空间中的几何意义并不十分直观。为此,我们将采用另一途径来定义它。

定义1 称n 维空间中的区域R 为一凸集,若R x x ∈?21,及)1,0(∈?λ,有R x x ∈-+21)1(λλ。

定义2 设R 为n 维空间中的一个凸集,R 中的点x 被称为R 的一个极点,若不存在R x x ∈21、及)1,0(∈λ,使得21)1(x x x λλ-+=。

定义1 说明凸集中任意两点的连线必在此凸集中;而定义2 说明,若x 是凸集R 的一个极点,则x 不能位于R 中任意两点的连线上。不难证明,多胞形必为凸集。同样也不难证明,二维空间中可行域R 的顶点均为R 的极点(R 也没有其它的极点)。

1.5 求解线性规划的Matlab 解法

单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由

George Dantzig 于1947年提出的,近60年来,虽有许多变形体已被开发,但却保持着同样的基本观念。由于有如下结论:若线性规划问题有有限最优解,则一定有某个最优解是可行区域的一个

极点。基于此,单纯形法的基本思路是:先找出可行域的一个极点,据一定规则判断其是否最优;若否,则转换到与之相邻的另一极点,并使目标函数值更优;如此下去,直到找到某一最优解为止。这里我们不再详细介绍单纯形法,有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab 解法。

Matlab5.3中线性规划的标准型为

b Ax x

c T x ≤ such that min 基本函数形式为linprog(c,A,b),它的返回值是向量x 的值。还有其它的一些函数调用形式(在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式),如:

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X 0,OPTIONS) 这里fval 返回目标函数的值,Aeq 和beq 对应等式约束beq x Aeq =*,LB 和UB 分别是变量x 的下界和上界,0x 是x 的初始值,OPTIONS 是控制参数。

例2 求解下列线性规划问题 321532m a x x x x z -+=

???

??≥≥+-=++0,,105273

21321321x x x x x x x x x 解 (i )编写M 文件 c=[2;3;-5];

a=[-2,5,-1]; b=-10; aeq=[1,1,1]; beq=7;

x=linprog(-c,a,b,aeq,beq,zeros(3,1)) value=c'*x

(ii )将M 文件存盘,并命名为example1.m 。

(iii )在Matlab 指令窗运行example1即可得所求结果。 例3 求解线性规划问题 32132 min x x x z ++=

???

??≥≥+≥++0,,6238243

2121321x x x x x x x x 解 编写Matlab 程序如下: c=[2;3;1];

a=[1,4,2;3,2,0]; b=[8;6];

[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))

1.6 可以转化为线性规划的问题

很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如: 例4 问题为

b

Ax x x x n ≤+++ t.s.|

|||||min 21

其中T n x x x ][1 =,A 和b 为相应维数的矩阵和向量。

要把上面的问题变换成线性规划问题,只要注意到事实:对任意的i x ,存在0,>i i v u 满足

i i i v u x -=,i i i v u x +=|| 事实上,我们只要取2||i i i x x u +=

,2

||i

i i x x v -=就可以满足上面的条件。

这样,记T n u u u ][1 =,T n v v v ][1 =,从而我们可以把上面的问题变成

∑=+n

i i i

v u

1

)(m i n

??

?≥≤-0

,)( t.s.v u b

v u A

§2 运输问题(产销平衡)

例5 某商品有m 个产地、n 个销地,各产地的产量分别为m a a ,,1 ,各销地的需求量分别为n b b ,,1 。若该商品由i 产地运到j

销地的单位运价为ij c ,问应该如何调运才能使总运费最省?

解:引入变量ij x ,其取值为由i 产地运往j 销地的该商品数量,数学模型为

∑∑==m i n

j ij

ij x

c 11

min

s.t. ????

?????≥====∑∑==0,,2,1,,,1,1

1ij m

i j ij n

j i ij x n j b x m i a x

显然是一个线性规划问题,当然可以用单纯形法求解。

对产销平衡的运输问题,由于有以下关系式存在:

∑∑∑∑∑∑=======??? ??=???? ??=m

i i n

j n j m i ij m

i n j ij j a x x b 1

11111 其约束条件的系数矩阵相当特殊,可用比较简单的计算方法,习

惯上称为表上作业法(由康托洛维奇和希奇柯克两人独立地提出,简称康—希表上作业法)。

表上作业法是单纯形法在求解运输问题时的一种简化方法,其求解工作在运输表上进行逐步迭代如下:先按某一规则找出一个初始解(初始调运方案);再对现行解作最优性判断;若这个解不是最优的,就在运输表上对它进行调整改进,得一新解;再判断,再改进,直到得到最优解。

§3 指派问题(又称分配问题Assignment Problem )

3.1 指派问题的数学模型

例6 拟分配n 人去干n 项工作,每人干且仅干一项工作,若分配第i 人去干第j 项工作,需花费ij c 单位时间,问应如何分配工作才能使工人花费的总时间最少?

容易看出,要给出一个指派问题的实例,只需给出矩阵

)(ij c C =,C 被称为指派问题的系数矩阵。

引入变量ij x ,若分配i 干j 工作,则取1=ij x ,否则取0=ij x 。上述指派问题的数学模型为

∑∑==n i n

j ij

ij x

c 11

min

s.t. n ,1,2,j i,, 1 0,,2,1,1,,2,1,11

1?????

??????======∑∑== 或ij n

i ij n

j ij x n j x n i x (5)

(5)的可行解既可以用一个矩阵(称为解矩阵)表示,其每行每

列均有且只有一个元素为1,其余元素均为0,也可以用n ,,1 中的一个置换表示。

(5)的变量只能取0或1,从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解,其约束方程组的系数矩阵十分特殊(被称为全单位模矩阵,其各阶非零子式均为1±),其非负可行解的分量只能取0或1,故约束10或=ij x 可改写为0≥ij x 而不改变其解。此时,指派问题被转化为一个特殊的运输问题,其中n m =,1==j i b a 。

3.2 求解指派问题的匈牙利算法

由于指派问题的特殊性,又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。算法主要依据以下事实:如果系数矩阵)(ij c C =一行(或一列)中每一元素都加上或减去同一个数,得到一个新矩阵)(ij b B = ,则以C 或B 为系数矩阵的指派问题具有相同的最优指派。

利用上述性质,可将原系数阵C 变换为含零元素较多的新系数阵B ,而最优解不变。若能在B 中找出n 个位于不同行不同列的零元素,令解矩阵中相应位置的元素取值为1,其它元素取值为零,则所得该解是以B 为系数阵的指派问题的最优解,从而也

是原问题的最优解。

由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ,D 的每列元素再减去其所在列的最小元素得以实现。

下面通过一例子来说明该算法。 例7 求解指派问题,其系数矩阵为

?????

????

???=1622

19

17

1718222418192117

22191516C 解 将第一行元素减去此行中的最小元素15,同样,第二行元素减去17,第三行元素减去17,最后一行的元素减去16,得

?????

????

???=0631

01571240

74011B 再将第3列元素各减去1,得

?????

???????=**

**20531005711407301B 以2B 为系数矩阵的指派问题有最优指派

???

?

??43124321 由等价性,它也是例7的最优指派。

有时问题会稍复杂一些。

例8 求解系数矩阵C 的指派问题

?????

??

?????????=61071041066141512141217766698979712C

解:先作等价变换如下

∨∨

∨????????

?????

???→????????????????----- 26360

40*089

57

510*00*

0032202

*056107104106614151214121776669897971246767

容易看出,从变换后的矩阵中只能选出四个位于不同行不同

列的零元素,但5=n ,最优指派还无法看出。此时等价变换还可进行下去。步骤如下:

(1) 对未选出0元素的行打∨; (2) 对∨行中0元素所在列打∨;

(3) 对∨列中选中的0元素所在行打∨; 重复(2)、(3)直到无法再打∨为止。 可以证明,若用直线划没有打∨的行与打∨的列,就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合,找出未覆盖的元素中的最小者,令∨行元素减去此数,∨列元素加上此数,则原先选中的0元素不变,而未覆盖元素中至少有一个已转变为0,且新矩阵的指派问题与原问题也等价。上述过程可反复采用,直到能选取出足够的0元素为止。例如,对例5变换后的矩阵再变换,第三行、第五行元素减去2,第一列元素加上2,得

???

??

?

?

?

????????04140

400811353800003420207

现在已可看出,最优指派为???

?

??5314254321。

§4 对偶理论与灵敏度分析

4.1 原始问题和对偶问题

考虑下列一对线性规划模型: x c T m a x s.t. 0,≥≤x b Ax

(P) 和

y

b T min s.t.

0,≥≥y c y A T

(D)

称(P )为原始问题,(D )为它的对偶问题。

不太严谨地说,对偶问题可被看作是原始问题的“行列转置”: (1) 原始问题约束条件中的第j 列系数与其对偶问题约束条

件中的第j 行的系数相同; (2) 原始目标函数的系数行与其对偶问题右侧的常数列相

同; (3) 原始问题右侧的常数列与其对偶目标函数的系数行相

同; (4) 在这一对问题中,除非负约束外的约束不等式方向和优

化方向相反。 考虑线性规划:

0,s.t.min ≥=x b Ax x

c T

把其中的等式约束变成不等式约束,可得 0, s.t. min ≥??

?

???-≥??????-x b b x A A x c T 它的对偶问题是

[

][

]

c y y A A y y b b T

T T

T

≤??

?

???-?

?

?

???-2121 s.t.max

其中1y 和2y 分别表示对应于约束b Ax ≥和b Ax -≥-的对偶变量组。

令21y y y -=,则上式又可写成

c y A y b T T ≤ s.t. max

原问题和对偶的对偶问题约束之间的关系:

min

max

???

??≤≥无限制变量

00 ??

???=≥≤行约束 ???

??=≤≥行约束

??

?

??≤≥无限制变量00 4.2 对偶问题的基本性质

1o 对称性:对偶问题的对偶是原问题。

2o 弱对偶性:若x 是原问题的可行解,y 是对偶问题的可行解。则恒有:y b x c T T ≤。

3o 无界性:若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。

4o 可行解是最优解时的性质:设x ?是原问题的可行解,y ?是对偶问题的可行解,当y b x

c T T ??=时,y x ?,?是最优解。 5o 对偶定理:若原问题有有限最优解,那么对偶问题也有最优解;且目标函数值相同。

6o 互补松弛性:若y x

?,?分别是原问题和对偶问题的最优解,则

0)?(?,0)?(?=-=-c y A x b x A y

T T T 由上述性质可知,对任一LP 问题(P),若它的对偶问题(D)可能的话,我们总可以通过求解(D )来讨论原问题(P ):若(D)无界,则(P)无可行解;若(D)有有限最优解*w ,最优值b w *,则利用互补松弛性可求得(P)的所有最优解,且(P)的最优值为b w *。例如对只有两个行约束的LP ,其对偶问题只有两个变量,总可用图解法来求解。

例9 已知线性规划问题

5432132532min x x x x x ++++=ω 432..54321≥++++x x x x x t s 33254321≥+++-x x x x x 5,,2,1,0 =≥j x j

已知其对偶问题的最优解为5

3,54*

2

*1==y y ,最优值为5*=z 。试用对偶理论找出原问题的最优解。

解 先写出它的对偶问题

2134max y y z += s.t. 2221≤+y y

321≤-y y

53231≤+y y ③

221≤+y y ④ 3321≤+y y

0,21≥y y 将*

2*1,y y 的值代入约束条件,得②,③,④为严格不等式;设原问

题的最优解为),,(*5*1*x x x =,由互补松弛性得0*

4*3*2===x x x 。因 0,*2*1>y y ;原问题的两个约束条件应取等式,故有

43*5*1=+x x 32*5*1=+x x

求解后得到1,1*

5*1==x x ;故原问题的最优解为

]'10001[*=X ;最优值为5*=w 。

4.3 灵敏度分析

灵敏度分析是指对系统或周围事物因周围条件变化显示出来的敏感程度的分析。

在以前讨论线性规划问题时,假定j i ij c b a ,,都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变,j c 值就会变化;ij a 往往是因工艺条件的改变而改变;i b 是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题:当这

些参数有一个或几个发生变化时,已求得的线性规划问题的最优解会有什么变化;或者这些参数在什么范围内变化时,线性规划问题的最优解不变。这里我们就不讨论了。

4.4 参数线性规划

参数线性规划是研究j i ij c b a ,,这些参数中某一参数连续变化时,使最优解发生变化的各临界点的值。即把某一参数作为参变量,而目标函数在某区间内是这参变量的线性函数,含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。

习 题 一

1. 某厂生产三种产品I ,II ,III 。每种产品要经过B A ,两道工序加工。设该厂有两种规格的设备能完成A 工序,它们以21,A A 表示;有三种规格的设备能完成B 工序,它们以321,,B B B 表示。产品I 可在B A ,任何一种规格设备上加工。产品II 可在任何规格的A 设备上加工,但完成B 工序时,只能在1B 设备上加工;产品III 只能在2A 与2B 设备上加工。已知在各种机床设备的单件工时,原材料费,产品销售价格,各种设备有效台时以及满负荷操作时机床设备的费用如下表,要求安排最优的生产计划,使该厂利润最大。

2. 有四个工人,要指派他们分别完成4项工作,每人做各项工作所消耗的时间如下表:

问指派哪个人去完成哪项工作,可使总的消耗时间为最小?

3. 某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位,只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米,带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹,每出发轰炸一次除来回路程汽油消耗(空载时每升汽油可飞行4千米)外,起飞和降落每次各消耗100升。有关数据如表所示。

方案,要求建立这个问题的线性规划模型。

线性规划经典例题及详细解析

一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值就是 。 3. 已知变量x,y 满足约束条件+201-70x y x x y -≤??≥??+≤? ,则 y x 的取值范围就是( )、 A 、 [95,6] B 、(-∞,95 ]∪[6,+∞) C 、(-∞,3]∪[6,+∞) D 、 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 与y 须满足约束条件?? ???≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大值 就是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥??-+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的值为( ) A. -3 B 、 3 C 、 -1 D 、 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥??+-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B 、 1 C 、 5 D 、 无穷大

高中数学简单的线性规划教案教学设计

课题:简单的线性规划 一、教材分析: 1、教材的地位与作用: 线性规划是运筹学的一个重要分支,在实际生活中有着广泛的应用。本节 内容是在学习了不等式、直线方程的基础上,利用不等式和直线方程的有关知识 展开的,它是对二元一次不等式的深化和再认识、再理解。通过这一部分的学习, 使学生进一步了解数学在解决实际问题中的应用,体验数形结合和转化的思想方 法,培养学生学习数学的兴趣、应用数学的意识和解决实际问题的能力。 2、教学重点与难点: 重点:画可行域;在可行域内,用图解法准确求得线性规划问题的最优解。 难点:在可行域内,用图解法准确求得线性规划问题的最优解。 二、目标分析: 在新课标让学生经历“学数学、做数学、用数学”的理念指导下,本节课 的教学目标分设为知识目标、能力目标和情感目标。 知识目标: 1、了解线性规划的意义,了解线性约束条件、线性目标函数、可行解、可行 域和最优解等概念; 2、理解线性规划问题的图解法; 3、会利用图解法求线性目标函数的最优解. 能力目标: 1、在应用图解法解题的过程中培养学生的观察能力、理解能力。 2、在变式训练的过程中,培养学生的分析能力、探索能力。 3、在对具体事例的感性认识上升到对线性规划的理性认识过程中,培养学生运用数形结合思想解题的能力和化归能力。 情感目标: 1、让学生体验数学来源于生活,服务于生活,体验数学在建设节约型社会中的作用,品尝学习数学的乐趣。

2、让学生体验数学活动充满着探索与创造,培养学生勤于思考、勇于探索的精神; 3、让学生学会用运动观点观察事物,了解事物之间从一般到特殊、从特殊到一般的辨证关系,渗透辩证唯物主义认识论的思想。 三、过程分析: 数学教学是数学活动的教学。因此,我将整个教学过程分为以下六个教学环节:1、创设情境,提出问题;2、分析问题,形成概念;3、反思过程,提炼方法;4、变式演练,深入探究;5、运用新知,解决问题;6、归纳总结,巩固提高。 1、创设情境,提出问题: 在课堂教学的开始,我以一组生动的动画(配图片)描述出在神奇的数学王 国里,有一种算法广泛应用于工农业、军事、交通运输、决策管理与规划等领域, 应用它已节约了亿万财富,还被列为20世纪对科学发展和工程实践影响最大的十 大算法之一。它为何有如此大的魅力?它又是怎样的一种神奇算法呢?我以景激 情,以情激思,点燃学生的求知欲,引领学生进入学习情境。 接着我设置了一个具体的“问题”情境,即2006世界杯冠军意大利足球队(插 图片)营养师布拉加经常遇到的这样一类营养调配问题: 甲、乙、丙三种食物的维生素A、B的含量及成本如下表: 布拉加想购这三种食物共10千克,使之所含维生素A不少于4400单位,维生 素B不少于4800单位,问三种食物各购多少时成本最低,最低成本是多少? 同学们,你能为布拉加解决这个棘手的问题吗? 首先将此实际问题转化为数学问题。我请学生完成这一过程如下: 解:设所购甲、乙两种食物分别为x、y千克,则丙食物为10-x-y千克. 由题意可知x、y应满足条件:

六种经典线性规划例题

线性规划常见题型及解法 求线性目标函数的取值范围 2 2 2 x y A D y 2 O x x=2 求可行域的面积 y y M 5 2 x y 2 y x y 2 x y 2 x y x (3,5] y =2 ( 13 例1 x+2y 时 6 的点 C 、 x , 个 y 6 y 3 2 x + y —3 = 0 C 、 5 A 、 4 B 、 1 D 、无穷大 () 0,将 有 最小值 故选A .B A --- 作出可行域如右图 点个数为13个,选D x + y =2 则z=x+2y 的取值范围是 () 旦y =2 0 0表示的平面区域的面积为 三、求可行域中整点个数 解:|x| + |y| <2等价于 解:如图,作出可行域,作直线I : I 向右上方平移,过点A ( 2,0 ) 2,过点B ( 2,2 )时,有最大值 [2,6] B 、[2 ,5] C 、[3,6] 解:如图,作出可行域,△ ABC 的面积即为所求,由梯形OMBC 的面积减去梯形OMAC 的 面积即可,选B 例 3、满足 |x| + |y| <2 A 、9 个 B 、10 个 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性 目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 (x 0,y 0) (x 0,y p 0) (xp 0,y 0) (xp 0,y p 0) 是正方形内部(包括边界),容易得到整 y)中整点(横纵坐标都是整数)有() D 、 14 个 2x 例2、不等式组x x 若x 、y 满足约束条件 y O C V —? x 2x + y —6= 0

八种 经典线性规划例题(超实用)

线性规划常见题型及解法 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 2 2 2 x y x y ≤ ? ? ≤ ? ?+≥ ? ,则z=x+2y的取值范围是() A、[2,6] B、[2,5] C、[3,6] D、(3,5] 解:如图,作出可行域,作直线l:x+2y=0,将l向右上方平移,过点A(2,0)时,有最小值2,过点B(2,2)时,有最大值6,故选 A 二、求可行域的面积 例2、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为() A、4 B、1 C、5 D、无穷大 解:如图,作出可行域,△ABC的面积即为所求,由梯形OMBC 的面积减去梯形OMAC的面积即可,选 B 三、求可行域中整点个数 例3、满足|x|+|y|≤2的点(x,y)中整点(横纵坐标都是整数)有() A、9个 B、10个 C、13个 D、14个 解:|x|+|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图,是正方形内部(包括边界),容易得到整点个数为13个,选 D

四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ,使z=x+ay(a>0) 取得最小值的最优解有无数个,则a的值为() A、-3 B、3 C、-1 D、1 解:如图,作出可行域,作直线l:x+ay=0,要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个,则将l向右上方平移后与直线x+y=5重合,故a=1,选 D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 220 240 330 x y x y x y +-≥ ? ? -+≥ ? ?--≤ ? ,则z=x2+y2的最大值和最小值分别是() A、13,1 B、13,2 C、13,4 5 D 、 解:如图,作出可行域,x2+y2是点(x,y)到原点的距离的平方,故最大值为点A(2,3)到原点的距离的平方,即|AO|2=13,最小值为原点到直线2x+y-2=0的距离的平方, 即为4 5 ,选 C 六、求约束条件中参数的取值范围 例6、已知|2x-y+m|<3表示的平面区域包含点(0,0)和(-1,1),则m的取值范围是() A、(-3,6) B、(0,6) C、(0,3) D、(-3,3) 解:|2x-y+m|<3等价于 230 230 x y m x y m -++>? ? -+- ? ? -< ? ,故0<m<3,选 C

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

数学建模 第一章 线性规划 §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)达到最小值的可行解叫最优解。

数学建模 线性规划模型

数学建模线性规划模型 数学建模教案,线性规划模型 一、问题的提出 在生产管理和经营活动中经常提出一类问题,即如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果。 例1 若需在长为4000mm的圆钢上,截出长为698mm和518mm两种毛坯,问怎样截取才能使残料最少, 初步分析可以先考虑两种“极端”的情况: (1)全部截出长为698mm的甲件,一共可截出 EQ F(4000,698) ?5件,残料长为510mm。 (2)全部截出长为518mm的乙件,一共可截出 EQ F(4000,518) ?7件,残料长为374mm。由此可以想到,若将 x个甲件和y 个乙件搭配起来下料,是否可能使残料减少,把截取条件数学化地表示出来就是: 698 x + 518y ? 4000 x ,y都是非负整数 目标是使:z = EQ F(698x + 518y,4000) (材料利用率)尽可能地接近或等于1。(尽可能地大) 该问题可用数学模型表示为: 目标函数 : max z = EQ F(698x + 518y,4000) 满足约束条件: 698 x + 518y ? 4000 , (1) x ,y都是非负整数 . (2) 例2 某工厂在计划期内要安排生产I 、II两种产品,已知生产单位产品所需的设备台数及A、B两种原料的消耗,如下表所示。

I II 设备 1 2 8台数 原材料A 4 0 16kg 原材料B 0 4 12kg 该工厂每生产一件产品I可获利 2 元,每生产一件产品II可获利 3 元,问应如何安排生产计划使工厂获利最多, 这问题可以用以下的数学模型来描述:设 x, x分别表示在计划期内产品I、II 的产量。 1 2 因为设备的有效台数为8 ,这是一个限制产量的条件,所以在确定I 、II的产量时,要考虑不超过设备的有效台数,即可用不等式表示为: x + 2x ? 8 . 1 2同理,因原材料A 、B的限量,可以得到以下不等式: 4 x ? 16 1 4 x ? 12. 2 该工厂的目标是在不超过所有资源限量的条件下,如何确定产量x、x以得到最大 1 2的利润。若用 z 表示利润,这时z = 2x + 3 x。综上所述,该计划问题可用数学模型表 1 2 示为: 目标函数 : max z = 2x + 3 x 1 2 满足约束条件: x + 2x ? 8 1 2 4 x ? 16 1 4 x ? 12. 2

《简单的线性规划问题》教案

《简单的线性规划问题》教学设计 (人教A版高中课标教材数学必修5第三章第3.3.2节) 祁东二中谭雪峰 一、内容与内容解析 本节课是《普通高中课程标准实验教科书数学》人教A版必修5第三章《不等式》中第3.3.2《简单的线性规划问题》的第一课时. 本课内容是线性规划的相关概念和简单的线性规划问题的解法. 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.本节内容是在学习了不等式和直线方程的基础上,利用不等式和直线方程的有关知识展开的.简单的线性规划指的是目标函数含两个自变量的线性规划,其最优解可以用数形结合方法求出.简单的线性规划关心的是两类问题:一是在人力、物力、资金等资源一定的条件下,如何使用它们来完成最多的任务;二是给定一项任务,如何合理规划,能以最少的人力、物力、资金等资源来完成. 本节内容蕴含了丰富的数学思想方法,突出体现了优化思想、数形结合思想和化归思想. 通过这一部分的学习,使学生进一步了解数学在解决实际问题中的应用,体验数形结合和转化的思想方法,培养学生学习数学的兴趣、应用数学的意识和解决实际问题的能力. 二、教学目标 一)、知识目标 1.了解线性规划的意义、了解线性约束条件、线性目标函数、可行解、可行域、最优解等基本概念. 2.理解线性规划问题的图解法 3. 会用图解法求线性目标函数的最优解. 二)、能力目标 1.在应用图解法解题的过程中培养学生的观察能力、理解能力. 2.在变式训练的过程中,培养学生的分析能力、探索能力.

3.培养学生观察、联想、作图和理解实际问题的能力,渗透化归、数形结合的数学思想. 三)、情感目标 1.让学生体验数学来源于生活,服务于生活,品尝学习数学的乐趣. 2.让学生体验数学活动充满着探索与创造,培养学生勤于思考、勇于探索的精神. 三、教学重点、难点 重点:线性规划问题的图解法;寻求有实际背景的线性规划问题的最优解. 难点:借助线性目标函数的几何含义准确理解线性目标函数在y 轴上的截距与z最值之间的关系. 四、学习者特征分析 1. 已经掌握用平面区域表示二元一次不等式(组) 2. 初步学会分析简单的实际应用问题 3. 能根据实际数据假设变量,并从中抽象出不等的线性约束条件并用相应的平面区域进行表示 本节课学生在学习过程中可能遇到以下疑虑和困难: 1.将实际问题抽象成线性规划问题; 2.用图解法解线性规划问题中,为什么要将求目标函数最值问题转化为经过可行域的直线在y轴上的截距的最值问题?如何想到要这样转化? 3.数形结合思想的深入理解. 五、教学与学法分析 本节课以学生为中心,以问题为载体,采用启发、引导、探索相结合的教学方法.课堂中应注重创设师生互动、生生互动的和谐氛围,通过学生动手实践、动脑思考等方法探究数学知识获取直接经验,进而培养学生的思维能力和应用意识等. 1.设置“问题”情境,激发学生解决问题的欲望; 2.提供“观察、探索、交流”的机会,引导学生独立思考,有效地调动学生思维,使学生在开放的活动中获取直接经验.

高中数学线性规划经典题型

高考线性规划归类解析 一、平面区域和约束条件对应关系。 例1、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是() (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥?? +≤??≤≤? (C) 003x y x y x -≤?? +≤??≤≤? (D) 0003x y x y x -≤?? +≥??≤≤? 解析:双曲线224x y -=的两条渐近线方程为y x =±,与直线3x =围 成一个三角形区域(如图4所示)时有0 003x y x y x -≥?? +≥??≤≤? 。 点评:本题考查双曲线的渐近线方程以及线性规划问题。验证法或排除法是最效的方法。 例2:在平面直角坐标系中,不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是() (A)42 (B)4 (C) 22 (D)2 解析:如图6,作出可行域,易知不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域是一个三角形。容 易求三角形的三个顶点坐标为A(0,2),B(2,0),C(-2,0).于是三角形的面积为: 11 ||||42 4.22 S BC AO =?=??=从而选B。 点评:有关平面区域的面积问题,首先作出可行域,探求平面区域图形的性质;其次利用面积公式整体或部分求解是关键。 二、已知线性约束条件,探求线性截距——加减的形式(非线性距离——平方的形式,斜率——商的形式)目标关系最值问题(重点) 例3、设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则 ①y x 32+的最大值为 。(截距) 解析:如图1,画出可行域,得在直线 2x-y=2与直线x-y=-1 的交点A(3,4)处,目标函数z 最大值为18 点评:本题主要考查线性规划问题,由线性约束条件画出可行域,然后求出目标函数的最大值.,是一道较为简单的送分题。数形结合是数学思想的重要手段之一。 ②则2 2 x y +的最小值是 . ③1y x =+的取值范围是 . 图1

数学建模线性规划

线性规划 1.简介: 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源. 线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.规划问题。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。 (x)都是线性函数,则该模型称为在优化模型中,如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 (1)决策变量 (2)目标函数f(x) (x)≤0称为约束条件) (3)约束条件(g i 3.建立线性规划的模型 (1)找出待定的未知变量(决策变量),并用袋鼠符号表示他们。 (2)找出问题中所有的限制或者约束,写出未知变量的线性方程或线性不等式。

(3)找到模型的目标或判据,写成决策变量的线性函数,以便求出其最大值或最小值。以下题为例,来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品,每单位产品消耗和获得的利润如表 试拟订生产计划,使该厂获得利润最大 解答:根据解题的三个基本步骤 (1)找出未知变量,用符号表示: 设甲乙两种产品的生产量分别为x 1与x 2 吨,利润为z万元。 (2)确定约束条件: 在这道题目当中约束条件都分别为:钢材,电力,工作日以及生产量不能为负的限制 钢材:9x 1+5 x 2 ≤360, 电力:4x 1+5 x 2 ≤200, 工作日:3x 1+10 x 2 ≤300, x 1≥0 ,x 2 ≥0, (3)确定目标函数: Z=7x 1+12 x 2

高二数学教案:简单的线性规划(Word版)

高二数学教案:简单的线性规划 (2021最新版) 作者:______ 编写日期:2021年__月__日 【一】 教学目标 (1)使学生了解并会用二元一次不等式表示平面区域以及用二元一次不等式组表示平面区域; (2)了解线性规化的意义以及线性约束条件、线性目标函数、

线性规化问题、可行解、可行域以及解等基本概念; (3)了解线性规化问题的图解法,并能应用它解决一些简单的实际问题; (4)培养学生观察、联想以及作图的能力,渗透集合、化归、数形结合的数学思想,提高学生“建模”和解决实际问题的能力; (5)结合教学内容,培养学生学习数学的兴趣和“用数学”的意识,激励学生勇于创新. 教学建议 一、知识结构 教科书首先通过一个具体问题,介绍了二元一次不等式表示平面区域.再通过一个具体实例,介绍了线性规化问题及有关的几个基本概念及一种基本解法-图解法,并利用几道例题说明线性规化在实际中的应用. 二、重点、难点分析

本小节的重点是二元一次不等式(组)表示平面的区域. 对学生来说,二元一次不等式(组)表示平面的区域是一个比较陌生、抽象的概念,按高二学生现有的知识和认知水平难以透彻理解,因此学习二元一次不等式(组)表示平面的区域分为两个大的层次: (1)二元一次不等式表示平面区域.首先通过建立新旧知识的联系,自然地给出概念.明确二元一次不等式在平面直角坐标系中表示直线某一侧所有点组成的平面区域不包含边界直线(画成虚线).其次再扩大到所表示的平面区域是包含边界直线且要把边界直线画成实线. (2)二元一次不等式组表示平面区域.在理解二元一次不等式表示平面区域含义的基础上,画不等式组所表示的平面区域,找出各个不等式所表示的平面区域的公共部分.这是学生对代数问题等价转化为几何问题以及数学建模方法解决实际问题的基础. 难点是把实际问题转化为线性规划问题,并给出解答. 对许多学生来说,从抽象到的化归并不比从具体到抽象遇到的问题少,学生解数学应用题的最常见困难是不会将实际问题提炼成数学问题,即不会建模.所以把实际问题转化为线性规划问题作为本节的

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1. 什么是线性规划模型,在模型中各系数的经济意义是什么? 2. 线性规划问题的一般形式有何特征? 3. 建立一个实际问题的数学模型一般要几步? 4. 两个变量的线性规划问题的图解法的一般步骤是什么? 5. 求解线性规划问题时可能出现几种结果,那种结果反映建模时有错误? 6. 什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 7. 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8. 试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 10.大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什么?最大化问题呢? 11.什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情况下,继续第二阶段? 二、判断下列说法是否正确。 1. 线性规划问题的最优解一定在可行域的顶点达到。 2. 线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。 5. 线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解,那么它必有最优解。 7. 用单纯形法求解标准形式(求最小值)的线性规划问题时,与0 >j σ对应的变量都可以被选作换入变量。 8. 单纯形法计算中,如不按最小非负比值原则选出换出变量,则在下一个解中至少有一个基变量的值是负的。 9. 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量,可使目 标函数值得到最快的减少。 10. 一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。 三、建立下面问题的数学模型 1. 某公司计划在三年的计划期内,有四个建设项目可以投资:项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资,年末可收回本利120% ,每年又可以重新将所获本利纳入投资计划;项目Ⅱ需要在第一年初投资,经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资额不得超过20万元;项目Ⅲ需要在第二年年初投资,经过两年可收回本利160% ,但用于该项目的最大投资额不得超过15万元;项目Ⅳ需要在第三年年初投资,年末可收回本利140% ,但用于该项目的最大投资额不得超过10万元。在这个计划期内,该公司第一年可供投资的资金有30万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润? 2.某饲养场饲养动物,设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单 价如下表2—1所示:

线性规划经典例题及详细解析

1 / 6 一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22 x y +的最小值是 。 3. 已知变量x ,y 满足约束条件+201-70x y x x y -≤?? ≥??+≤? ,则 错误! 的取值范围是( )。 A 。 [错误!,6] B.(-∞,错误!]∪[6,+∞) C.(-∞,3]∪[6,+∞) D 。 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大 值是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处 取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的 值为( ) A. -3 B. 3 C 。 -1 D. 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B. 1 C. 5 D 。 无穷大

人教版 高中数学 简单的线性规划问题教案

简单的线性规划问题 一、教学内容分析 普通高中课程标准教科书数学5(必修)第三章第3课时 这是一堂关于简单的线性规划的“问题教学”. 线性规划是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支,它能解决科 学研究、工程设计、经济管理等许多方面的实际问题. 简单的线性规划(涉及两个变量)关心的是两类问题:一是在人力、物力、资金等资源 一定的条件下,如何使用它们来完成最多的任务;二是给定一项任务,如何合理规划,能以 最少的人力、物力、资金等资源来完成.突出体现了优化的思想. 教科书利用生产安排的具体实例,介绍了线性规划问题的图解法,引出线性规划等的概 念,最后举例说明了简单的二元线性规划在饮食营养搭配中的应用. 二、学生学习情况分析 本节课学生在学习了不等式、直线方程的基础上,又通过实例,理解了平面区域的意义, 并会画出平面区域,还能初步用数学关系式表示简单的二元线性规划的限制条件,将实际问 题转化为数学问题. 从数学知识上看,问题涉及多个已知数据、多个字母变量,多个不等关 系,从数学方法上看,学生对图解法的认识还很少,数形结合的思想方法的掌握还需时日, 这都成了学生学习的困难. 三、设计思想 本课以问题为载体,以学生为主体,以数学实验为手段,以问题解决为目的,以几何画 板作为平台,激发他们动手操作、观察思考、猜想探究的兴趣。注重引导帮助学生充分体验 “从实际问题到数学问题”的建构过程,“从具体到一般”的抽象思维过程,应用“数形结 合”的思想方法,培养学生的学会分析问题、解决问题的能力。 四、教学目标 1.了解线性规划的意义,了解线性约束条件、线性目标函数、可行解、可行域和最优解等概念;理解线性规划问题的图解法;会利用图解法求线性目标函数的最优解. 2.在实验探究的过程中,让学生体验数学活动充满着探索与创造,培养学生的数据分析能力、探索能力、合情推理能力及动手操作、勇于探索的精神; 3、在应用图解法解题的过程中,培养学生运用数形结合思想解题的能力和化归能力,体验数学来源于生活,服务于生活,体验数学在建设节约型社会中的作用. 五、教学重点和难点 求线性目标函数的最值问题是重点;从数学思想上看,学生对为什么要将求目标函数最值问题转化为经过可行域的直线在y轴上的截距的最值问题?以及如何想到要这样转化?存在一定疑虑及困难;教学应紧扣问题实际,通过突出知识的形成发展过程,引入数学实验来突破这一难点.

数学建模-线性规划

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

简单的线性规划教案

简单的线性规划教案文档编制序号:[KKIDT-LLE0828-LLETD298-POI08]

简单的线性规划 【教学目标】 1.知识与技能:使学生了解二元一次不等式表示平面区域;了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念;了解线性规划问题的图解法,并能应用它解决一些简单的实际问题; 2.过程与方法:经历从实际情境中抽象出简单的线性规划问题的过程,提高数学建模能力; 3.情态与价值:培养学生观察、联想以及作图的能力,渗透集合、化归、数形结合的数学思想,提高学生“建模”和解决实际问题的能力。 【教学重点】用图解法解决简单的线性规划问题 【教学难点】准确求得线性规划问题的最优解 【教学过程】 1.课题导入 [复习提问] 1、二元一次不等式0 Ax在平面直角坐标系中表示什么图形 By + > +C 2、怎样画二元一次不等式(组)所表示的平面区域应注意哪些事项 3、熟记“直线定界、特殊点定域”方法的内涵。 2.讲授新课 在现实生产、生活中,经常会遇到资源利用、人力调配、生产安排等问题。 1、下面我们就来看有关与生产安排的一个问题: 引例:某工厂有A、B两种配件生产甲、乙两种产品,每生产一件甲产品使用4个A配件耗时1h,每生产一件乙产品使用4个B配件耗时2h,该厂每天最多可从

配件厂获得16个A 配件和12个B 配件,按每天8h 计算,该厂所有可能的日生产安排是什么 (1)用不等式组表示问题中的限制条件: 设甲、乙两种产品分别生产x 、y 件,又已知条件可得二元一次不等式组: 2841641200 x y x y x y +≤??≤?? ≤??≥?≥?? (1) (2)画出不等式组所表示的平面区域: 如图,图中的阴影部分的整点(坐标为整数的点)就代表所有可能的日生产安排。 (3)提出新问题: 进一步,若生产一件甲产品获利2万元,生产一件乙产品获利3万元,采用哪种生产安排利润最大 (4)尝试解答: 设生产甲产品x 件,乙产品y 件时,工厂获得的利润为z ,则z=2x+3y .这样,上述问题就转化为: 当x,y 满足不等式(1)并且为非负整数时,z 的最大值是多少 把z=2x+3y 变形为23 3 z y x =-+,这是斜率为23 -,在y 轴上的截距为3 z 的直线。当z 变化时,可以得到一族互相平行的直线,如图,由于这些直线的斜率是确定的,因此只要给定一个点,(例如(1,2)),就能确定一条直线(2 83 3 y x =-+),这说明,截距3z 可以由平面内的一个点的坐标唯一确

简单的线性规划教案[1]

简单的线性规划教案 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】

简单的线性规划【教学目标】 1.知识与技能:使学生了解二元一次不等式表示平面区域;了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念;了解线性规划问题的图解法,并能应用它解决一些简单的实际问题; 2.过程与方法:经历从实际情境中抽象出简单的线性规划问题的过程,提高数学建模能力; 3.情态与价值:培养学生观察、联想以及作图的能力,渗透集合、化归、数形结合的数学思想,提高学生“建模”和解决实际问题的能力。 【教学重点】用图解法解决简单的线性规划问题 【教学难点】准确求得线性规划问题的最优解 【教学过程】 1.课题导入 [复习提问] 1、二元一次不等式0 +C Ax在平面直角坐标系中表示什么图形? By + > 2、怎样画二元一次不等式(组)所表示的平面区域应注意哪些事项 3、熟记“直线定界、特殊点定域”方法的内涵。 2.讲授新课 在现实生产、生活中,经常会遇到资源利用、人力调配、生产安排等问题。 1、下面我们就来看有关与生产安排的一个问题:

引例:某工厂有A 、B 两种配件生产甲、乙两种产品,每生产一件甲产品使用4个A 配件耗时1h,每生产一件乙产品使用4个B 配件耗时2h ,该厂每天最多可从配件厂获得16个A 配件和12个B 配件,按每天8h 计算,该厂所有可能的日生产安排是什么? (1)用不等式组表示问题中的限制条件: 设甲、乙两种产品分别生产x 、y 件,又已知条件可得二元一次不等式组: 2841641200 x y x y x y +≤??≤?? ≤??≥?≥?? (1) (2)画出不等式组所表示的平面区域: 如图,图中的阴影部分的整点(坐标为整数的点)就代表所有可能的日生产安排。 (3)提出新问题: 进一步,若生产一件甲产品获利2万元,生产一件乙产品获利3万元,采用哪种生产安排利润最大? (4)尝试解答: 设生产甲产品x 件,乙产品y 件时,工厂获得的利润为z ,则z=2x+3y .这样,上述问题就转化为: 当x,y 满足不等式(1)并且为非负整数时,z 的最大值是多少? 把z=2x+3y 变形为233z y x =-+,这是斜率为23-,在y 轴上的截距为3z 的直线。 当z 变化时,可以得到一族互相平行的直线,如图,由于这些直线的斜率是确定的,

线性规划与数学建模简介

第十三章线性规划与数学建模简介 【授课对象】理工类专业学生 【授课时数】6学时 【授课方法】课堂讲授与提问相结合 【基本要求】1、了解数学模型的基本概念、方法、步骤; 2、了解线性规划问题及其数学模型; 3、了解线性规划问题解的性质及图解法. 【本章重点】线性规划问题. 【本章难点】线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤,并以几个典型线性规划问题为例,介绍构建数学模型的方法及其解的性质。 §1 数学建模概述 一、数学建模 数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法,必须从实际问题出发,遵循从实践到认识再实践的认识规律,围绕建模的目的,运用观察力、想象力的抽象概括能力,对实际问题进行抽象、简化,反复探索,逐步完善,直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此,数学建模是一种定量解决实际问题的创新过程。 二、数学模型的概念 模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律F=ma就是一个典型的(数学)模型。一般地,可以给数学模型下这样的定义:数学模型是磁于以部分现实世界为一定目的而做的抽象、简化的数学结构。 通俗而言,数学模型是为了一定目的对原型所作的一种抽象模拟,它用数学 式子,数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程: 1.建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此,我们首先要发现这类需要解决的实际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划,组织必要的人力、物力等,确立建模课题。 2.模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进行抽象简化,人们就无法准确把握它的本质属性,而模型假设就是根据建模的目的对原型进行抽象、简化,抓住反映问题本质属性的主要因素,简化掉那些非本质的

3.3.2简单的线性规划(2)教案

3.3.2简单的线性规划问题(第四课时) 一、设计问题,创设情境 练习1:(1)作出不等式组表示的平面区域(如图阴影部分),即可行域. 将z1=x+y变形为y=-x+z1,这是斜率为-1、随z1变化的一簇平行直线. z1是直线在y轴上的截距.当然直线要与可行域相交,即在满足约束条件时目标函数z1=x+y取得最值. 由图可见,当直线z1=x+y经过可行域上的点B时,截距z1最小. 得B点的坐标为x=,y=. 所以z1的最小值为. 同理,当直线z1=x+y与可行域的边界x+y=6重合时,z1最大为6. (2)同理将z2=3x+y化为y=-3x+z2,这是斜率为-3的一簇平行直线.如图所示,当它过可行域上的点A(0,6)时,z2最小为6. (3)同理将z3=x+4y化为y=-x+,它是斜率为-的一簇直线.如图所示,当直线经过可行域上的点C时,最大,即z3最大. 解方程组 得点C的坐标为x=,y=. 所以z3的最小值为. 问题1:是目标函数对应的直线的斜率与可行域中边界对应的直线的斜率的大小关系不同导致的. 练习2:解:z=ax+y可化为y=-ax+z, 因为z=ax+y在可行域中的点B处取得最小值,

所以,直线z=ax+y与可行域只有一个公共点B或与边界AB重合,或与边界BC重合. 所以-2≤-a≤-. 所以实数a的取值范围是. 练习3:学生探究一:能够把可行域中的所有“整点”都求出来.求这些最优解时,可根据可行域对x的限制条件,先令x去整数,然后代入到可行域,求出y的范围,并进一步求出y的整数值. 学生探究二:因为x,y∈N,则必有x+y∈N.又因为当x=,y=时,z1的最小值为,且直线z1=x+y应该向上方(或右方,或右上方)移动,所以相对应的z1的值大于. 所以令z1=x+y=5,即y=-x+5,代入得 即1≤x≤3,所以当或时,z1取得最小值5. 问题2:结合等量关系,将“二元”问题转化为“一元”问题求解.当可行域范围较小,包含的整点个数很少时,方法一比较简洁;反之,方法二较为简洁. 二、使用规律,解决问题 【例题】解:设需截第一种钢板x张,第二种钢板y张,则 用图形表示以上限制条件,得到如图所示的平面区域(阴影部分). 由题意,得目标函数为z=x+y. 可行域如图所示. 把z=x+y变形为y=-x+z,得到斜率为-1、在y轴上截距为z的一族平行直线. 由图能够看出,当直线z=x+y经过可行域上的点M时,截距z最小. 解方程组 得点M.而此问题中的x,y必须是整数,所以M不是最优解.经过可行域内整点且使截距z最小的直线是

相关主题