文档库 最新最全的文档下载
当前位置:文档库 › 线性规划1

线性规划1

线性规划1
线性规划1

习题一

1.1 用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

(1) min z =6x1+4x2(2) max z =4x1+8x2

st. 2x1+x2≥1 st. 2x1+2x2≤10

3x1+4x2≥1.5 -x1+x2≥8

x1, x2≥0 x1, x2≥0

(3) max z =x1+x2(4) max z =3x1-2x2

st. 8x1+6x2≥24 st. x1+x2≤1

4x1+6x2≥-12 2x1+2x2≥4

2x2≥4 x1, x2≥0

x1, x2≥0

(5) max z =3x1+9x2(6) max z =3x1+4x2

st. x1+3x2≤22 st. -x1+2x2≤8

-x1+x2≤4 x1+2x2≤12

x2≤6 2x1+x2≤16

2x1-5x2≤0 x1, x2≥0

x1, x2≥0

1.2. 在下列线性规划问题中,找出所有基本解,指出哪些是基本可行解并分别代入目标函数,比较找出最优解。

(1) max z =3x1+5x2(2) min z =4x1+12x2+18x3

st. x1+x3=4 st. x1+3x3-x4=3

2x2+x4=12 2x2+2x3-x5=5 3x1+2x2+x5=18 x j≥0 (j=1, (5)

x j≥0 (j=1, (5)

1.3. 分别用图解法和单纯形法求解下列线性规划问题,并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。

(1) max z =10x1+5x2

st. 3x1+4x2≤9

5x1+2x2≤8

x1, x2≥0

(2) max z =100x1+200x2

st. x1+x2≤500

x1≤200

2x1+6x2≤1200

x1, x2≥0

10

1.4. 分别用大M 法和两阶段法求解下列线性规划问题,并指出问题的解属于哪一类:

(1) max z =4x 1+5x 2+ x 3 (2) max z =2x 1+ x 2+ x 3

st. 3x 1+2x 2+ x 3≥18 st. 4x 1+2x 2+2x 3≥4

2x 1+ x 2 ≤4 2x 1+4x 2 ≤20

x 1+ x 2- x 3=5 4x 1+8x 2+2x 3≤16

x j ≥0 (j =1,2,3) x j ≥0 (j =1,2,3)

(3) max z = x 1+ x 2 (4) max z =x 1+2x 2+3x 3-x 4

st. 8x 1+6x 2≥24 st. x 1+2x 2+3x 3=15

4x 1+6x 2≥-12 2x 1+ x 2+5x 3=20

2x 2≥4 x 1+2x 2+ x 3+ x 4=10

x 1, x 2≥0 x j ≥0 (j =1, (4)

(5) max z =4x 1+6x 2 (6) max z =5x 1+3x 2+6x 3

st. 2x 1+4x 2 ≤180 st. x 1+2x 2+ x 3≤18

3x 1+2x 2 ≤150 2x 1+ x 2+3x 3≤16

x 1+ x 2=57 x 1+ x 2+ x 3=10

x 2≥22 x 1, x 2≥0,x 3无约束

x 1, x 2≥0

1.5 线性规划问题max z =CX ,AX =b ,X ≥0,如X*是该问题的最优解,又λ>0为某一常数,分别讨论下列情况时最优解的变化:

(1) 目标函数变为max z =λCX ;

(2) 目标函数变为max z =(C +λ)X ;

(3) 目标函数变为max z = C

X ,约束条件变为AX =λb 。

1.6 下表中给出某求极大化问题的单纯形表,问表中a 1, a 2, c 1, c 2, d 为何值时以及表中变量属于哪一种类型时有:

(1) 表中解为唯一最优解;

(2) 表中解为无穷多最优解之一;

(3) 表中解为退化的可行解;

(4) 下一步迭代将以x 1替换基变量x 5 ;

(5) 该线性规划问题具有无界解;

(6) 该线性规划问题无可行解。

x 1 x 2 x 3 x 4 x 5

x 3 d 4 a 1 1 0 0

x 4 2 -1 -5 0 1 0

x 5 3 a 2 -3 0 0 1

c j -z j c 1 c 2 0 0 0

1.7 战斗机是一种重要的作战工具,但要使战斗机发挥作用必须有足够的驾驶

员。因此生产出来的战斗机除一部分直接用于战斗外,需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为a j(j=1,…,n),又每架战斗机每年能培训出k名驾驶员,问应如何分配每年生产出来的战斗机,使在n年内生产出来的战斗机为空防作出最大贡献?

1.8.某石油管道公司希望知道,在下图所示的管道网络中可以流过的最大流量是多少及怎样输送,弧上数字是容量限制。请建立此问题的线性规划模型,不必求解。

1.9. 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下:

班次时间所需人数

1 6:00-10:00 60

2 10:00-14:00 70

3 14:00-18:00 60

4 18:00-22:00 50

5 22:00-2:00 20

6 2:00-6:00 30

设司机和乘务人员分别在各时间区段一开始时上班,并连续工作八小时,问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。

1.10 某班有男生30人,女生20人,周日去植树。根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多?请建立此问题的线性规划模型,不必求解。

1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。

问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立此问题的线性规划的数学模型。

甲乙丙原料成本(元/千克) 每月限量(千克)A≥60%≥15% 2.00 2000

B 1.50 2500

C ≤20%≤60%≤50% 1.00 1200

加工费(元/千克)0.50 0.40 0.30

售价 3.40 2.85 2.25

1.1

2. 某商店制定7-12月进货售货计划,已知商店仓库容量不得超过500件,

11

6月底已存货200件,以后每月初进货一次,假设各月份此商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收入最多?请建立此问题的线性规划模型,不必求解。

月份7 8 9 10 11 12

买进单价28 24 25 27 23 23

售出单价29 24 26 28 22 25

1.13 .某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日,春夏季4000人日,如劳动力本身用不了时可外出干活,春夏季收入为

2.1元/人日,秋冬季收入为1.8元/人日。该农场种植三种作物:大豆、玉米、小麦,并饲养奶牛和鸡。种作物时不需要专门投资,而饲养动物时每头奶牛投资400元,每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草,并占用人工秋冬季为100人日,春夏季为50人日,年净收入400元/每头奶牛。养鸡时不占土地,需人工为每只鸡秋冬季需0.6人日,春夏季为0.3人日,年净收人为2元/每只鸡。农场现有鸡舍允许最多养3000只鸡,牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。

1.14 某厂接到生产A、B两种产品的合同,产品A需200件,产品B需300件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段,产品A每件需要2小时,产品B每件需要4小时。机械加工阶段又分粗加工和精加工两道工序,每件产品A需粗加工4小时,精加工10小时;每件产品B需粗加工7小时,精加工12小时。若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时,精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。此外在粗加工阶段允许设备可进行500小时的加班生产,但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料,为该厂制订一个成本最低的生产计划。

该三种产品l季度初无库存,要求在4季度末各库存150件。已知该厂每季度生产工时为15000小时,生产I、Ⅱ、Ⅲ产品每件分别需时2、4、3小时。因更换工艺装备,产品I在2季度无法生产。规定当产品不能按期交货时,产品I,Ⅱ每

12

件每迟交一个季度赔偿20元,产品Ⅲ赔偿10元;又生产出来产品不在本季度交货的,每件每季度的库存费用为5元。问:该厂应如何安排生产,使总的赔偿加库存的费用为最小(要求建立数学模型,不需求解)。

1.16 某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成,或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成,或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元,他们每周都工作48小时,但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务,该公司需要每周总有效工作小时数为:第一项工作10000小时。第二项工作20000小时,第三项工作30000小时。又能招收到的工人数为技工不超过400人,力工不超过800人。试建立数学模型,确定招收技工和力工各多少人。使总的工资支出为最少(建立数学模型,不需求解)。

复习思考题

1.17 试述线性规划数学模型的结构及各要素的特征。

1.18 求解线性规划问题时可能出现哪几种结果,哪些结果反映建模时有错误。

1.19 什么是线性规划问题的标准型式,如何将一个非标准型的线性规划问题转化为标准型式。

1.20 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。

1.21 试述单纯形法的计算步骤,如何在单纯形表上去判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

1.22 如果线性规划的标准型式变换为求目标函数的极小化min Z,则用单纯形法计算时如何判别问题已得到最优解。

1.23 在确定初始可行基时,什么情况下要在约束条件中增添人工变量,在目标函数中人工变量前的系数为(一M)的经济意义是什么。

1.24 什么是单纯形法计算的两阶段法,为什么要将计算分两个阶段进行,以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。

1.25 简述退化的含义及处理退化的勃兰特规则。

1.26 举例说明生产和生活中应用线性规划方面,并对如何应用进行必要描述。

1.27 判断下列说法是否正确:

(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的;

(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大;

(c)线性规划问题的每一个基解对应可行域的一个顶点;

(d)如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点;

13

(e)对取值无约束的变量x j,通常令x j=x jˊ-x j",其中x jˊ≥0,x j"≥0,在用单纯形法求得的最优解中有可能同时出现x jˊ>0,x j">0。

(f)用单纯形法求解标准型式的线性规划问题时,与大于0对应的变量都可以被选作换人变量;

(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负;

(h) 单纯形法计算中,选取最大正检验数对应的变量为换入变量,将使目标函数值得到最快的增长;

(i)一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果;

(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示;

(k)若Xˊ、X"分别是某一线性规划问题的最优解,则它们的线性组合也是该线性规划问题的最优解。

14

简单的线性规划教案[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 变化时,可以得到一族互相平行的直线,如图,由于这些直线的斜率是确定的,

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

数学建模 第一章 线性规划 §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 线性规划 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(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 标准型为

简单的线性规划教案一

简单的线性规划教案一 【教学目标】 1.知识与技能:使学生了解二元一次不等式表示平面区域;了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念;了解线性规划问题的图解法,并能应用它解决一些简单的实际问题; 2.过程与方法:经历从实际情境中抽象出简单的线性规划问题的过程,提高数学建模能力; 3.情态与价值:培养学生观察、联想以及作图的能力,渗透集合、化归、数形结合的数学思想,提高学生“建模”和解决实际问题的能力。 【教学重点】 用图解法解决简单的线性规划问题 【教学难点】 准确求得线性规划问题的最优解 【教学过程】 1.课题导入 [复习提问] 1、二元一次不等式0>++C By Ax 在平面直角坐标系中表示什么图形? 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 的最大值是多少?

第一章线性规划

-1- 第一章 线性规划 §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 乙机床时总利润最大,则2 1,x x 应满足 (目标函数)2134max 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 中规定线性规划的标准形式为 x c x T min s.t. ?? ? ??≤≤=?≤ub x lb beq x Aeq b Ax 其中c 和x 为n 维列向量,A 、Aeq 为适当维数的矩阵,b 、beq 为适当维数的列向量。

高中数学优秀教案 简单的线形规划简单的线性规划(一)

课题:7.4 简单的线性规划(一) 授课人:石家庄市第一中学孟庆善 教材分析: 本节课是在学生学习了直线与直线方程的关系,初步了解了二元一次方程的几何意义的基础上,引领学生进一步研究二元一次不等式的几何意义,为后面学习用图解法求二元函数最值问题创造条件.使学生体会数与形的转化过程,逐步加强学生应用几何图形解决代数问题的意识. 基于以上分析,在教学中应充分利用多媒体课件向学生展示代数条件与几何图形的对应关系,加强学生对问题的了解,培养学生学习数学的兴趣. 教学目标: 1.使学生了解二元一次不等式表示平面区域; 2. 掌握根据二元一次不等式(组)正确做出平面区域的方法,培养学生作图的能力. 3.让学生通过观察、联想,体验数学的作用,培养学生学习数学的兴趣,培养学生勤于思考、勇于探索和团结协作的精神。 教学重点: 二元一次不等式表示平面区域. 教学难点: 1.二元一次不等式表示平面区域; 2.根据二元一次不等式(组)正确做出平面区域. 教法分析:师生互动,探究、研讨、辨析、总结 鉴于高二学生已具有较好的数学基础知识和较强的分析问题、解决问题的能力,本节课以学生为中心,以问题为载体,采用启发、引导、探索相结合的教学方法.首先设置“问题”情境,激发学生解决问题的欲望;其次提供观察、探索、交流的机会,引导学生独立思考,有效地调动学生思维,使学生在开放的活动中获取知识.恰当的利用多媒体课件辅助教学,直观生动地呈现学生思维的形成过程,从而提高教学效率.在教学过程中,注重学生的探索经历和发现新知的体验,使其形成自己对数学知识的理解和有效的学习策略.

教学过程:

二元一次不等式表示平面区域的作图步骤:⑴作出直线;⑵取特殊点;⑶代入 表示的平面区域.

第一章线性规划及单纯形法习题

第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 (1)??? ??≥≥+≥++=0,42266432min 2 121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ??? ??≤≤≤≤≤++=83105120106max 21212 1x x x x x x z (4) ?????≥≤+-≥-+=0 ,2322 265max 1 221212 1x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,0232624 322min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解,指出哪些是基可行解,并确定最优 解。 (1) ??? ??? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2)

??? ??=≥=+++=+++++-=)4,,1(01022274322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题,并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 (1) ??? ??≥≤+≤++=0,825943510max 1 221212 1x x x x x x x x z (2) ?????≥≤+≤++=0,242615 532max 1 221212 1x x x x x x x x z 5.上题(1)中,若目标函数变为21m ax dx cx z +=,讨论c,d 的值如何变化,使该问题可行域的每一顶点依次使目标函数达到最优。 6.考虑下述线性规划问题: ? ????≥≤+≤++=0 ,max 122221212121112 1x x b x a x a b x a x a dx cx z 式中311≤≤c ,642≤≤c , 3111≤≤-a ,5212≤≤a ,1281≤≤b , 5221≤≤a ,6422≤≤a ,14102≤≤b ,试确定目标函数最优值的下界和上 界。 7.分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题,并指出属哪一类解。 (1) ??? ?? ? ?=≥≥-≥+-≥+++-=)3,2,1(0022 2622max 32313213 21j x x x x x x x x x x x z j (2) ??? ??≥≥+≥++++=0,,62382432min 3 21213213 21x x x x x x x x x x x z

线性规划1

习题一 1.1 用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 (1) min z =6x1+4x2(2) max z =4x1+8x2 st. 2x1+x2≥1 st. 2x1+2x2≤10 3x1+4x2≥1.5 -x1+x2≥8 x1, x2≥0 x1, x2≥0 (3) max z =x1+x2(4) max z =3x1-2x2 st. 8x1+6x2≥24 st. x1+x2≤1 4x1+6x2≥-12 2x1+2x2≥4 2x2≥4 x1, x2≥0 x1, x2≥0 (5) max z =3x1+9x2(6) max z =3x1+4x2 st. x1+3x2≤22 st. -x1+2x2≤8 -x1+x2≤4 x1+2x2≤12 x2≤6 2x1+x2≤16 2x1-5x2≤0 x1, x2≥0 x1, x2≥0 1.2. 在下列线性规划问题中,找出所有基本解,指出哪些是基本可行解并分别代入目标函数,比较找出最优解。 (1) max z =3x1+5x2(2) min z =4x1+12x2+18x3 st. x1+x3=4 st. x1+3x3-x4=3 2x2+x4=12 2x2+2x3-x5=5 3x1+2x2+x5=18 x j≥0 (j=1, (5) x j≥0 (j=1, (5) 1.3. 分别用图解法和单纯形法求解下列线性规划问题,并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 (1) max z =10x1+5x2 st. 3x1+4x2≤9 5x1+2x2≤8 x1, x2≥0 (2) max z =100x1+200x2 st. x1+x2≤500 x1≤200 2x1+6x2≤1200 x1, x2≥0 9

1第一章线性规划讲解

目录 未找到目录项。 第一章 线性规划 §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 应满足 (目标函数)2134max 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 beq x Aeq =?

简单的线性规划问题(附答案)

简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法,并能应用它解决一些简单的实际问题. 知识点一 线性规划中的基本概念 知识点二 线性规划问题 1.目标函数的最值 线性目标函数z =ax +by (b ≠0)对应的斜截式直线方程是y =-a b x +z b ,在y 轴上的截距是z b , 当z 变化时,方程表示一组互相平行的直线. 当b >0,截距最大时,z 取得最大值,截距最小时,z 取得最小值; 当b <0,截距最大时,z 取得最小值,截距最小时,z 取得最大值. 2.解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下,解决简单线性规划问题的步骤可以概括为:“画、移、求、答”四步,即, (1)画:根据线性约束条件,在平面直角坐标系中,把可行域表示的平面图形准确地画出来,可行域可以是封闭的多边形,也可以是一侧开放的无限大的平面区域. (2)移:运用数形结合的思想,把目标函数表示的直线平行移动,最先通过或最后通过的顶点(或边界)便是最优解. (3)求:解方程组求最优解,进而求出目标函数的最大值或最小值. (4)答:写出答案.

知识点三 简单线性规划问题的实际应用 1.线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源,问怎样运用这些资源,使完成的任务量最大,收到的效益最大; (2)给定一项任务,问怎样统筹安排,使完成这项任务耗费的人力、物力资源量最小. 常见问题有: ①物资调动问题 例如,已知两煤矿每年的产量,煤需经两个车站运往外地,两个车站的运输能力是有限的,且已知两煤矿运往两个车站的运输价格,煤矿应怎样编制调动方案,才能使总运费最小? ②产品安排问题 例如,某工厂生产甲、乙两种产品,每生产一个单位的甲种或乙种产品需要的A 、B 、C 三种材料的数量,此厂每月所能提供的三种材料的限额都是已知的,这个工厂在每个月中应如何安排这两种产品的生产,才能使每月获得的总利润最大? ③下料问题 例如,要把一批长钢管截成两种规格的钢管,应怎样下料能使损耗最小? 2.解答线性规划实际应用题的步骤 (1)模型建立:正确理解题意,将一般文字语言转化为数学语言,进而建立数学模型,这需要在学习有关例题解答时,仔细体会例给出的模型建立方法. (2)模型求解:画出可行域,并结合所建立的目标函数的特点,选定可行域中的特殊点作为最优解. (3)模型应用:将求解出来的结论反馈到具体的实例中,设计出最佳的方案. 题型一 求线性目标函数的最值 例1 已知变量x ,y 满足约束条件???? ? y ≤2,x +y ≥1,x -y ≤1,则z =3x +y 的最大值为( ) A .12 B .11 C .3 D .-1 答案 B 解析 首先画出可行域,建立在可行域的基础上,分析最值点,然后通过解方程组得最值点的坐标,代入即可.如图中的阴影部分,即为约束条件对应的可行域,当直线y =-3x +z 经 过点A 时,z 取得最大值.由????? y =2,x -y =1????? ? x =3,y =2,此时z =3x +y =11.

第一章线性规划及单纯形法习题

第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 (1)??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解,指出哪些是基可行解,并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题,并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。

《简单线性规划(1)》教学设计

课题:简单线性规划(一) 北京师范大学第二附属中学王张平 教材:人教版(B版)普通高中课程标准实验教科书(必修5)第三章§3.5.2 教学目标: 1.知识目标:理解线性规划有关概念,初步学会解决简单的线性规划问题. 2.能力目标:渗透数形结合的数学思想;加强学生自主探究、合作交流的意识;进一步培养学生在研究问题中主动借助现代信息技术手段辅助思维的习惯. 3.情感目标:让学生感受探究问题的乐趣和解决问题的成就感,通过带领学生解决实际问题及对线性规划有关历史的简单回顾,感受数学的文化价值. 教学重点、难点: 探究解决简单线性规划问题的方法. 教学方式: 学生自主探究和教师引导相结合. 教学手段: CASIO图形计算器、多媒体、几何画板. 教学过程: 一. 设置情境,问题引入 通过实际问题,创设问题情境. 问题一:资金分配 前不久的四川大地震,牵动了全国人民的心,灾后重 建是当务之急.北京某企业积极响应北京市对口支援什邡 市重建的号召,打算对中小学教学楼的重建(包括各项附 属设施)提供支援,预算投入资金不超过1000万元.根 据当前实际情况,要求投入中学建设的资金不少于投入小 学建设资金的1.8倍,初步估算中学教学楼的平均造价为 每百平方米14万元,小学教学楼的平均造价为每百平方 米8万元.并且对两者的建设面积都不低于1000平方 米.请你帮该企业计算一下,如何分配这笔资金能使得 教学楼重建后的面积最大?最大面积为多少?

学生活动: (1) 独立将实际问题转化为数学问题; (2) 针对得到的“约束条件”(不等式组),做出相应的平面区域. 预案:学生会比较顺利的列出不等式组,不容易想到列出“目标函数”,教师作适当引导, 让学生列出二元函数表达式. 说明: (1) 学生已经学习了“二元一次不等式组表示平面区域”的问题,作为上述知识的应 用,这里设计了从实际问题出发,创设问题情境,从而引起学生的探究兴趣; (2) 放手让学生独立解决.碰到问题(如何处理一个“二元函数”的最值问题),引起 认知冲突,激发求知的欲望. 二. 深入研究, 探求解法 针对“问题一”中提出的数学问题,让学生自己探究解决的方法,教师巡视观察. 设建设中学教学楼面积为x 百平方米, 建设小学教学楼面积y 百平方米, 建筑总面积为z 百平方米. z = x +y . 满足: 学生活动:学生合作交流,进行自主探究. 预案一:学生利用图形计算器的取点功能作出自由点,并度量其坐标,然后在所绘区域 内移动该点,并直接计算x +y 的值进行比较,容易猜想出使z 取得最大值的点的位置. 预案二:让学生思考使z 取某个特殊值(如60)时点的位置.部分学生容易想到:满足 条件的点的集合为直线x +y =60与所画区域的交集.可再取两个特殊值让学生思考,引导他们发现直线之间的平行关系,并思考z 的几何意义:把目标函数化成y x z =-+1481000 141.881010x y x y x y +≤??≥?? ? ≥? ?≥ ?

简单的线性规划(一)

课题:7.4简单的线性规划(一) 教学目的: 1.使学生了解二元一次不等式表示平面区域; 2.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念; 3.了解线性规划问题的图解法,并能应用它解决一些简单的实际问题王新敞 4.培养学生观察、联想以及作图的能力,渗透集合、化归、数形结合的数学思想,提高学生“建模”和解决实际问题的能力王新敞 5.结合教学内容,培养学生学习数学的兴趣和“用数学”的意识,激励学生创新王新敞 教学重点:二元一次不等式表示平面区域. 教学难点:把实际问题转化为线性规划问题,并给出解答. 授课类型:新授课王新敞 课时安排:1课时王新敞 教具:多媒体、实物投影仪王新敞 内容分析: “简单的线性规划”是在学生学习了直线方程的基础上,介绍直线方程的一个简单应用,这是《新大纲》对数学知识应用的重视.线性规划是利用数学为工具,来研究一定的人、财、物、时、空等资源在一定条件下,如何精打细算巧安排,用最少的资源,取得最大的经济效益.它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支,并能解决科学研究、工程设计、经常管理等许多方面的实际问题.中学所学的线性规划只是规划论中的极小一部分,但这部分内容体现了数学的工具性、应用性,同时也渗透了化归、数形结合的数学思想,为学生今后解决实际问题提供了一种重要的解题方法―数学建模法.通过这部分内容的学习,可使学生进一步了解数学在解决实际问题中的应用,培养学生学习数学的兴趣、应用数学的意识和解决实际问题的能力王新敞 依据新大纲及教材分析,二元一次不等式表示平面区域以及线性规划的有关概念比较抽象,按高二学生现有的知识和认知水平难以透彻理解,再加上学生对代数问题等价转化为几何问题以及数学建模方法解决实际问题有一个学习消化的过程,故本节知识内容定为了解层次王新敞 本大节内容渗透了多种数学思想,是向学生进行数学思想方法的教学的好教材,也是培养学生观察、作图等能力的好教材王新敞 本节内容与实际问题联系紧密,有利于培养学生学习数学的兴趣和“用数学”的意识以及解决实际问题的能力王新敞 本小节的重点是二元一次不等式表示平面区域,难点是把实际问题转化为线性规划问题,并给出解答.解决难点的关键是根据实际问题中的已知条件,找出约束条件和目标函数,利用图解法求得最优解.为突出重点,本节教学应指导

1--线性规划1--入门

第一章线性规划 1 线性规划 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分-------数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。 自从1947年美国学者丹西格提出求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000元与3000元。生产甲机床需用B A、机器加工,加工时间分别为每台2小时和1小时;生产乙机床需用C 、三种机器加工,加工 B A、 时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时,问该厂应生产甲、乙机床各几台,才能使总利润最大?

上述问题的数学模型:设该厂生产1x 台甲机床和2x 乙机床时总利 润最大,则21,x x 应满足 (目标函数)2134max x x z += (1) s.t.(约束条件)???????≥≤≤+≤+0 ,7 81022122121x x x x x x x (2) 这里变量21,x x 称之为决策变量,(1)式被称为问题的目标函数, (2)中的几个不等式是问题的约束条件,记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素(决策变量/ 目标函数/约束条件)。由于上面的目标函数及约束条件均为线性函数,故被称为线性规划问题。 总之,线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题。 1 线性规划的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 标准型为

简单的线性规划--含答案

- 课时作业20 简单线性规划 时间:45分钟 满分:100分 课堂训练 1.若变量x 、y 满足约束条件???? ? x +y ≤2,x ≥1, y ≥0, 则z =2x +y 的最 大值和最小值分别为( ) A .4和3 B .4和2 C .3和2 D .2和0 【答案】 B 【解析】 画出可行域如图: 《 作l 0:2x +y =0.平移l 0到经过点A (或B ), 即当直线z =2x +y 过A (2,0)时z 最大,过B (1,0)时z 最小,z max =4,z min =2.

2.若实数x ,y 满足不等式组???? ? x +3y -3≥0,2x -y -3≤0, x -my +1≥0, 且x +y 的最 大值为9,则实数m =( ) A .-2 B .-1 C .1 D .2 【答案】 C 【解析】 画出??? ?? x +3y -3≥0, 2x -y -3≤0, 表示的平面区域如图,又x - my +1=0, 》 恒过(-1,0)点,当m <0时,x +y 无最大值,故选项A 、B 错误,因此m >0,又满足条件的可行域必须是一个三角形,联立 ????? 2x -y -3=0, x -my +1=0, 解得A (3m +12m -1,52m -1),∴3m +12m -1+5 2m -1 =9,解 得m =1.

3.(2013·北京文)设D 为不等式组???? ? x ≥0,2x -y ≤0, x +y -3≤0 表示的平面 区域,区域D 上的点与点(1,0)之间的距离的最小值为________. 【答案】 25 5 【解析】 区域D 如图所示: 则(1,0)到区域D 的最小值即为(1,0)到直线y =2x 的距离:|2×1-0|5 =25 5. 4.设z =2x +3y -6,式中x ,y 满足条件????? 2x +y ≥6, x +2y ≥6, x ≥0, y ≥0. 求 z 的最小值. ) 【分析】 在平行直线系中先作过原点的直线,再将直线平移到 可行域中.

相关文档