线性规划1

第四篇 线性规划

线性规划的雏形最早出现在1823年傅里叶的工作中，后来一些著名的学者，如 里昂惕夫(W.Leontief)在1933年，冯诺依曼(von Neumann)在1928、1937年都有过 相关工作。不过完整的模型、理论和算法是丹齐格(G.B.Dantzig)为解决二次大战中的后勤供应问题而产生的，如同1983年美国科学、工程和公共事务政策委员会所写的一段关于线性规划的影响与贡献：线性规划是为解决二次大战中的后勤供应问题而产生的，单纯形方法的提出及其在初期成功的应用，使得能用线性规划解决的问题的类型先是缓慢地，但接着就是急速地增加。线性规划成为几乎所有的商业活动、工业生产和军事行动的一部分。由于在设计和操作过程中应用了线性规划，已经节约了亿万美元。

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分 支,它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料；二是生产组织与计划的改进，即合理安排人力物力资源。线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。《经济大词典》定义线性规划：一种具有确定目标，而实现目标的手段又有一定限制，且目标和手段之间的函数关系是线性的条件下，从所有可供选择的方案中求解出最优方案的数学方法。

第一章 线性规划模型

§1 若干模型

例1某农户有耕地20公顷，可采用甲乙两种种植方式。甲种植方式每公顷需投资2800 元，每公顷投工6个，可获收入10000元，乙方式每公顷需投资1500元，劳动15个工日，可获收入12000元，该户共有可用资金42000元、240个劳动工日。问如何安排甲乙两种方式的生产，可使总收入最大?

解 设甲种植方式1x 公顷，乙种植方式2x 公顷，总收入S 元。按照题意，求

12max 1000012000S x x =+，

使得

121212122800150042000,61524020,,0

x x x x x x x x +≤??+≤??

+≤??≥?， 例2营养学家指出，成人良好的日常饮食应该至少提供0.075kg 的碳水化合物，0.06kg

的蛋白质，0.06kg 的脂肪，1kg 食物A 含有0.105kg 碳水化合物，0.07kg 蛋白质，0.14kg 脂肪，花费28元；而1食物B 含有0.105kg 碳水化合物，0.14kg 蛋白质，0.07kg 脂肪，花费21元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物A 和食物B 多少kg ？

解 设每天食用1x kg 食物A 和2x kg 食物B ，总成本为z 元，那么根据题意，求

12min 2821z x x =+，

使得

1212

12120.1050.100.0750.070.140.06

0.140.070.06,0

x x x x x x x x ≥??≥??

+≥??≥?＋＋ 例3 某班有男同学30人,女同学20人，星期天去植树，根据经验，一天男同学平均每

人挖坑20个，或栽树30棵，或给25棵树浇水；女同学平均每人挖坑10个，或栽树20棵，或给15棵树浇水.问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？

解：设男同学中挖坑、栽树、浇水的人数分别为111213,,x x x ；女同学中挖坑、栽树、浇 水的人数分别为212223,,x x x ，S 为植树棵树.由题意，求ij x , 使得满足约束条件：

112111112132122222132233201030202530,20,,150+=+++≤??=+++≤??

???≥∈ij ij x x x x x x x x x x Z

x x x x ， 并使目标函数11212010S x x =+的值最大，即求1121max 2010S x x =+

例4用工安排问题

某工场从星期一到星期日，每天需要工作人员数如下；

该工厂规定每位工作人员连续工作5天，休息2天，试问应如何雇用工作人员使雇用总数最少？

解 设i x 为从星期i 开始工作的人数，i =1,2,…7由题意，求

1234567min z x x x x x x x =++++++ s.t. 1456712

5671236712347123452345634567171315191416110,,1,2, (7)

i

i 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 Z i +

+++≥??++++≥??++++≥?

++++

≥??++++≥??++++≥?

++++≥?

?≥∈=?

例5 某商店制订某商品7-12月进货售货计划.已知商店仓库客量不得超过500件， 6

月底已存货200件，以后每月初进货一次.假设各月份某商品买进售出单价如下表，问各月

进货售货各多少，使得总收入最多？

解 设7-2月各月初进货数量为i x 件.各月售货数量为i y 件（i =1，2，…6），z 为总收入.由题意，求

123456123456max 292426282225(282425272323)

z y y y y y y x x x x x x =+++++-+++++ s.t.

11211231122341122334

5

112233445

611223344556200500

200500

200500

200500200500

2005000,0,,,(1,...6).

i i i i y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x y x x y x Z y Z i ≤+≤?≤+-+≤≤+-+-+≤≤+-+-+-+≤≤+-+-+-+-+≤≤+-+-+-+-+-+≤≥≥∈∈=?

????????

?

例6 运输问题 设某产品有m 个产地12,,...,m A A A ，n 个销地12,,...,n B B B .每单位产品从产地i A 运往销地j B 的运费为ij C .已知产地i A 的产量为(1,...,)i a i m =，销地j B 的需求量为(1,...,)j b j n =，满足

j

i

a b

≥∑∑试问应如何安排运输.使保证供给，且使运费最省.

解：设由i A 运往j B 的产品为ij x 单位.由题意求 11

min m n

ij ij

i j z c x

===

∑∑

s.t. 11

,1,2,...,,1,...,0,1,...,,1,...,m

ij j i n

ij i j ij x b j n x a i m x i m j n ==?≥=???≤=???≥==??

∑∑

§2 线性规划模型的基本结构

由第一节的线性规划数学模型，我们看到它的基本结构由以下三个部分构成： 1.决策变量 ——未知数。它是通过模型计算来确定的决策因素。又分为实际变量和计算变量，计算变量又分松弛变量和人工变量等。

2.目标函数——经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。

3.约束条件——实现目标的制约因素，由线性表达式给出，包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。

决策变量、约束条件、目标函数是线性规划的三要素。 两则典型形式 线性规划问题基本上可以归结为两种形式： （A ） 1

max ==

∑n

j j

j z c x

s.t. 1,1,2,...,0,1,2,...,n

ij j i j j

a x

b i m x j n =?≤=???≥=?∑ ；

（B ） 1

min n

j j

j z c x

==

∑

s.t. 1,1,2,...,0.1,2,...,n

i j j i j j

a x b

i m x j n =?≥=???≥=?∑

矩阵表示

令()()1212=,...,,,,...,T n n C c c c x x x x =,，()12...T

m b b b b =，()12()...ij m n n A a ααα?==，

则（A ）问题可表示为：

max z Cx =

s.t. 0

Ax b

x ≤??

≥?

也可表示为

max =z Cx

s.t. 10,1,2,...α=?≤???≥=?∑n

i i i i

x b

x i n

同样可以用矩阵表示(B)问题。如同上面的例子所显示，线性规划的模型形式不完全一样,其中(A)与(B)是典型的两类。

§3 线性规划标准形式及化标准型的方法 线性规划问题的标准形式应具备如下几点： （1）目标函数是求最大值（也可定为求最小值）；

（2）在约束条件中，除了变量的非负约束外，其它所有约束条件均用等式表示；

（3）每个约束条件的常数项均是非负的（0i b ≥）；

（4）所有未知量受非负限制。

实际上，任一线性规划问题可以等价地转化为标准型，方法如下：

1. 目标函数的转换.如原问题求min z ，则等价于求max()z -.

2. 约束条件的转换

在约束条件中，如果有“≤”的非严格不等式限制，则可以通过引入松弛变量，化为等

式限制，如第i 个约束条件为

1

n

ij j

i j a x

b =≤∑，

引进0n i x +≥使得

1

n

i j j n i i

j a x x b +=+

=∑ 成立，此时称n i x +为松弛变量。

如果在约束条件中有“≥”的非严格不等式限制，则可以通过引入剩余变量，化为等式

限制，如

1

n

ij j

i j a x

b =≥∑，

引进0n i x +≥，使得

1

n

ij j n i i j a x x b +=-=∑

其中引进的新变号n i x +称为剩余变量.

3.若常数i b 为负数时可将该约束条件的两边同乘以1-，则右边常数i b 变为正数i b -。

4.变量的非负约束.若某个变量()

j j j x l l ≥≤.则可令()

.j j j j j j y x l l x y =--就是一个非负变量.如果j x 没有非负限制，称为自由变量. 自由变量可用

,0j j j

j j

x u v u v =-??

≥? 来代替.

综上所述，线性规划的标准形式为：max Cx

s.t. 0

Ax b

x =??

≥?

其中约束条件决定了可行解域D 。

所谓线性规划问题的可行解是指，满足规划中所有约束条件及非负约束的决策变量的一组取值，其仅与约束条件有关而与目标函数值的大小无关。可行(解)域是由所有可行解构成的集合。根据线性规划的基本理论，任一个线性规划问题的可行域，都是一个有限或无限的凸多边形。线性规划的最优解是指，使目标函数值达到最优(最大或最小)的可行解。一个线性规划问题可以是有解的，也可能是无解的，最优解的个数可能是惟一的，也可能是有无穷多个，即决策变量有许多组不同的取值，都使目标函数达到同一个最优值。

§4 线性规划图解法

例1 求z =3x +5y 的最大值和最小值，使x 、y 满足 约束条件

5315,1,

5 3.x y y x x y +≤??

≤+??-≤?

解 满足约束条件的区域为如右图所示 的三角形区域，视z 为参数，则方程z =3x +5y 表示平面上的平行线族。当直线经过点 A (1.5, 2.5)时，z 达最大值，

z m ax =3×1.5+5×2.5=17。 当直线经过点(2,1)B --时，z 达最小值， z m in =3(2)5(1)11?-+?-=-。

例2 某工厂用两种不同原料生产同一产品，若采用甲种原料，每吨成本1000元，运费500元，可得产品90千克；若采用乙种原料，每吨成本1500元，运费400元，可得产品100千克。今预算每日原料总成本不得超过6000元，运费不得超过2000元，问此工厂每日采用甲、乙两种原料各多少千克，才能使产品的日产量最大？

解 设此工厂每日需甲种原料x 吨，乙种原料y 吨，则可得产品z ＝90x ＋100y (千克)． 由题意，求max 90100z x y =+，

s.t. 100015006000,5004002000,0,0.+≤??

+≤??≥≥?

x y x y x y

即

2312,5420,0,0.+≤??

+≤??≥≥?

x y x y x y 上述不等式组表示的平面区域如图所示，阴影部分(含边界)即为可行域．

作直线l ：90x ＋100y ＝0，并作平行于直线l 的一组直线与可行域相交，其中有一条直线经过可行域上的M 点，且与直线l 的距离最大，此时目标函数达到最大值．这里M

点是

直线2x ＋3y ＝12和5x ＋4y ＝20的交点，容易解得)7

20

,712(M ，此时z 取到最大值：

.4407

2010071290=?+?

习题1

1. 某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1 小时、在车间3加工3 小时；每生产一扇窗需要在车间2 和车间3加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12 小时、车间3为18小时。又知每生产一扇门需要钢材5公斤，每生产一扇窗需要钢材3公斤，该厂现可为这批新产品提供钢材45公斤。每扇门的利润为300元，每扇窗的利润为500元。而且根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品都能销售出去。问该工厂如何安排这两种新产品的生产计划，能使总利润为最大？试建立线性规划数学模型。

2. 某工厂生产甲、乙两种产品，分别经过A 、B 、C 三种设备加工。已知生产单位产品所需要的台时数、设备的现有加工能力及每件产品的利润情况如下表：

请建立线性规划数学模型，用以制定该厂获得利润最大的生产计划；用图解法求解该数学模型。

3. 要将两种大小不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格的小钢

板的块数如下表所示：

今需要、、三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？ 4. 某农户计划用12公顷耕地生产玉米，大豆和地瓜，可投入48个劳动日，资金36000元。

生产玉米1公顷，需6个劳动日，资金3600元，可获净收入20000元；生产1公顷大豆，需6个劳动日，资金2400元，可获净收入15000元；生产1公顷地瓜需2个劳动日，资金1800元，可获净收入10000元，问怎样安排才能使总的净收入最高。请建立数学模型并用图解法解之。

5. 某工厂生产甲乙丙三种铝合金产品，生产每单位产品甲需用铝和铁分别是3公斤和2公

斤；生产单位产品乙需用铝和铁分别是1公斤和3公斤；生产单位产品丙需用铝和铁分别是1公斤和2公斤。已知生产每单位产品甲乙丙分别能获利5元、4元、3元，而工厂能提供的原材料铝840公斤，铁700公斤，试问如何安排生产才能获得最大利润？ 6. 某工厂生产甲、乙两种产品，已知生产甲产品1吨，需要煤9吨，需电4度，工作日3个（一个工人劳动一天等于一个工作日），生产乙种产品1吨，需要用煤4吨，需电5度，工作日12个，又知甲产品每吨售价7万元，乙产品每吨售价12万元，且每天供煤

最多360吨，供电最多200度，全员劳动人数最多300人，问每天安排生产两种产品各多少吨，才能使日产值最大，最大产值是多少？

7. 某养鸡场有一万只鸡，用动物饲料和谷类饲料混合喂养。每天每只鸡吃混合饲料0.5公

斤，其中动物饲料所占的比例不得多于2/5，动物饲料每公斤2元，谷类饲料每公斤1.6元。饲料公司每周只保证供应谷类饲料25000公斤，问饲料怎样混合才能使成本最低。 8. 某工厂生产n 种产品1,...,n A A ，其中单件产品的利润分别为1,...,n c c .每种产品都需要

经过1,...,m B B 的加工（无次序）限制.其中单件产品j A 在i B 上的所需加工的时间为ij a .在计划期内.设备i B 有效工作时间为i b .问如何安排生产.使所得利润最大？ 9. 将下列线性规划问题转化为标准形式： （1）12max 3=+z x x

s.t. 121212238

14100,1,2

+≤??-+≤??+≤??≥=?i x x x x x x x i

（2）12min 53=+z x x

s.t. 1212

12123343623,0

+≥+≥+≤≥???????x x x x x x x x

(3) 123min 5204=-++z x x x

s.t. 12312312312342100543506300,,0

--≤+-≥-???????++≤≥x x x x x x x x x x x x

(4) 123min 34=++z x x x

s.t. 123123123123754314|62|30,,0

--≥--+-=-??????≤≥?-x x x x x x x x x x x x

第二章 单纯形

§1 凸集

在线性规划的几何理论中，重要的概念有凸集、多面凸集、方向与极方向等，下面将逐一地给出定义。

定义1 设X 是n

R 的点集. 1x 和2x 是X 上任意两点，如对[]0,1λ?∈，都有

()121λλ+-∈x x X ，

则称X 为凸集.这里()121λλ+-x x 称为1x 和2x 的凸组合。

定义2 x 是X 的顶点或极点，当且仅当不存在12,∈x x X 及(0,1)λ∈，使得

12(1)x x x λλ=+-

成立.

定义3 集合{}

x x b α=称为n

R 的超平面.

定义4 集合{}

00x d λλ+≥称为以0x 为顶点，以d 为方向的射线.

定义5已知一个凸集，0x 是其上任一点，若存在非零向量d ，使得{}

00x d λλ+≥也属于该凸集，则称d 是凸集的一个方向.

定义6 设d 是凸集的一个方向，若不存在两个方向1d 和2d ，使得1122d d d λλ=+,其中12,0λλ>，则称d 为极方向.

如右图，1d 和2d 是极方向。

定义7 设12,,...,k ααα是一组向量，集合

10,1,2,...,k i i i

i C i k λαλ=??=≥=????

∑ 称为由12,,...,k ααα组合成的凸锥.

定义8有限个半空间的交集{

},≤∈n

x Ax b x R

称为多面体，其中()

?=ij m n

A a

，

d

2

x 1

12(,,...,)=T m b b b b ；若b =0，则{}

0,≤∈n x Ax x R 称为多面椎体.

定理1 多面体,{}=≤∈n

x Ax b x R X 是凸集。

证明 设1x 和2x 是X 上任意两点，则1≤Ax b ，2≤Ax b ，因此对[]0,1λ?∈，都有

1212((1))(1)λλλλ+-=+-≤A x x Ax Ax b ，

所以12(1)λλ+-∈x x X ，X 是凸集。 因此，多面体也称为多面凸集。

定理2设{}

,0X x Ax b x ==≥有界，则存在有限个顶点12,,...,k x x x ，∈x X 的充分必要条件是，存在1,...,0λλ≥k ，

1

1λ

==∑k

i

i ，使得1

k

i i i x x λ==∑。

定理3 设{}

,0X x Ax b x ==≥无界，则存在有限个顶点12,,...,k x x x 及有有限个极方向12,,...,h d d d ，∈x X 的充分必要条件是存在1,...0λλ≥k ，

1

1λ

==∑k

i

i ，以及1...,0μμ≥h .

使得1

1

λμ===

+∑∑k

h

i i

j

j

i j x x d

。

定理4（最优极方向定理）线性规划问题

max =z Cx

s.t. 0=??≥?

Ax b x

有有限最优值的充要条件是：对可行域D 的所有极方向d ，都有0Cd ≤.

证 必要性. 用反证法，假设存在某个极方向k d ，有0>k Cd 。由定理3，存在有限个顶点12,,...,k x x x 及有有限个极方向12,,...,h d d d ，对于可行域D 内的点x ，

1

1

λμ===+∑∑k h

i i j j i j x x d

当≠j k 时，令0j μ=，而让μ→+∞k ，则→+∞Cx .矛盾

充分性. 由充分性条件，对可行域D 的所有极方向d ，都有0Cd ≤。同样，由定理3有

1

1

λμ===+∑∑k

h

i i j j i j Cx Cx Cd ，

由于()01,...,≤=j Cd j h ，故令0j μ=，1,...,j h =。此时，只须找顶点s x ，使

max s j j

Cx Cx M ==.

那么当s x x =，即()0i i s λ=≠，1s λ=时，s Cx 取到有限的最优值。

§2 最值求解讨论

考虑线性规划的标准型问题： max =z Cx

s.t.0

=≥??

?Ax b

x ，

利用定理2和定理3，我们针对可行域{}

=,0D x Ax b x =≥有界或无界两种情形进行讨论.

（1） 有界情形

设可行域D 有界，则由定理2，对于任意x D ∈，必存在顶点12,,...,,k x x x 以及0λ≥i （

1

1λ

==∑k

i

i ）使得1122...k k x x x x λλλ=+++，其中

12,??

?

?= ?

? ???n x x

x x 12?? ? ?= ? ? ?

??

i i i n i x x x x 。

由于Cx 是线性函数，故

11

λλ==??== ???∑∑k k

i i i i i i Cx C x Cx ，

要求=z Cx 达到最大，问题导致求顶点n x ，使

{}12max ,,...==k h Cx Cx Cx M Cx ，

取=h x x ,即1λ=h ，其余()0i i h λ=≠时，则Cx 达到最大。

于是找使Cx 取最大的问题变成求凸多面体{}

,0x Ax b x =≥的顶点中使Cx 达到最大的点h x .

（2）无界情形

对于x D ∈，由定理3，存在有限个顶点12,,...k x x x ,及有限个极方向12,,...,h d d d , 使

1

1

λμ===+∑∑k h

i i j j i j x x d 。

因此，

1

1

λμ===+∑∑k h

i i j j i j Cx Cx Cd 。

（i ） 若存在0>j Cd ，则问题无解或有无穷大解.

（ii ） 若对?j ，0≤j Cd , 则可选取0μ=j ，依题意, 只须求{}max i i

Cx .若记

{}max ==i h i

Cx M Cx ，

则=h x x 使得线性规划问题取得最大值。

以上的总结是：通过求顶点值,求得最优解。但这个方法的缺点是繁琐. §3 单纯形法基础

现在我们来讨论线性规划问题：

max z Cx =

s.t.0

Ax b

x ≤??

≥?

其中=()?ij m n A a .

通过引进松弛变量12,,...,n n n m x x x +++后，一般说来，此时可行解域的顶点共有n+m 个坐标，其中n 个为零，m 个非零。非零坐标的变量称为基变量，坐标为零对应的变量称为非基变量。此时，约束条件等价地变化为

=Ax b ，()()?+=ij m m n A a 。

注意，这里的系数矩阵A 已经不同于原有的系数矩阵，只是为了方便，仍记为A 。设x 分为基变量部分和非基变量部分，即

B N x x x ??= ???

。

相应地，目标函数系数向量C 也分为基变量对应的系数B C 和非基变量的系数N C ，系数矩阵A 也分为两部分，即=(,)B N C C C ，(,)A B N =。这样，约束条件Ax b =可写为

(,)??

= ???

B N x B N b x ，

即B N Bx Nx b +=，或

1111B N j j j N

x B b B Nx B b B x α----∈=-=-∑ (1)

将（1）代入目标函数

()11B B N N B N N N z C x C x C B b B Nx C x --=+=-+

()11--=+-B N B N C B b C C B N x

()11α--∈=+-∑B j B j j j N

C B b c C B x （2）

若令0N x =，则目标函数值为

1B z C B b -=. （3）

因此，对于max 型问题，在（2）中若某个非基变量j x 前的系数有10α-->j B j c C B ，则当非基变量j x 从零增加时，直观上目标函数z 应有所增加，可见此时1B C B b -并非最大值（严格证明见后面的定理2）。

如果对j N ?∈，1

0α--=-≤j B j j j c C B c z ，则1-B C B b 就是最大值，或说已达最优

状态。所以在1

0α-->j B j c C B

的情形下，j x 不应作为非基变量，而因作为基变量，才能

使目标函数值增加。那么当j x 进入基变量的时候，原先作为基变量的其中一个必须退出。针对1

0α-->j B j c C B

的情形，我们有以下两个定理，是构成寻找退出基的基础.

定理1：若存在j ，使得1

0α-->j B j c C B

，而向量10α-≤j B ，则原问题无界.

证 令10α-??

-=+ ???

j j B d e ，首先可证d 是可行域上的一个方向。因为，若0x 是可行域

上任一点，即0=Ax b ，对于任意0λ≥，0()λλ+=+A x d b Ad 。而

1(,)00α-??

-=+= ???

j j B Ad B N Ae ，

所以，0()λ+=A x d b ，即d 是可行域上的一个方向。

其次，00()λλ+=+C x d Cx Cd ，而

11

(,)00αα--??-=+=-> ???

j B N j j B j B Cd C C c c C B ，

所以，当λ→+∞时，00()λλ+=+→+∞C x d Cx Cd 。故此，原问题无界。

定理2 若1

0α-->j B j c C B

，而1α-j B 中至少有一个正分量，则能找到基本可行解x ，

使1->B Cx C B b ，从而使优化过程得以继续.

证 只须具体找出x ，本定理的证明是构造性的。为简便计，记1

B b b -=以及

121αα-?? ? ?==

? ? ???

j j

mj

j j a a B a 。 设

=min 01,...0β??>==>????i r

ij

ij rj

b b a i m a a ， （4）

这是因为1

b B b -=是可行解。又令

0j j b x e βαβ??

-=+ ???

()

0,0≥≠x x （5）

可证x 即为所求。

注 在约束方程B N Bx Nx b +=中，若令0N x =，则1B x B b -=，称1

0()T

x B b -=是约束方程的一个基本解。或若ξ是Ax b =的解，且ξ的非零分量所对应的系数列向量线性无关时，称ξ为基本解。既是基本解又是可行解的称为基本可行解.

定理2续证 上述所给出的x 是可行解，这是因为

()110βαβ--??

-=+ ???

j j B b B Ax B N A e j j b b βαβα=-+=，

又根据β的构造，易见

120βαβαβαβα??

- ?- ?

-=≥ ? ? ?-??

j j j mj b b b b ，

所以，x 是可行解.

其次，可证x 是基本可行解。

记()12,m B ααα=，则x 所对应的列向量为1211,,...,,,,...,r j r m αααααα-+。用反证法

可证明上述m 个线性无关。否则，j α可由其余m-1个线性表出，即

j i i i j

y αα≠=∑ （6）

又因为1αα-=j j B ，故

()112

j j j m mj a B a ααααα?? ?== ? ???

1α==∑ij m

i i a （7）

（7）减去（6）得 ()

0αα≠+

-=∑rj ij

r i i i r

a a

y （8）

由于0>rj a （根据β的构造），上式说明12,,...,m ααα线性相关，矛盾。这样证明了x 是基本可行解。

最后，计算目标函数值

()0βαβ??-=+ ???

j B

N j b C x C C Ce βαβ=-+j B B j C b C c

()111βα---=+->B j B j B C B b c C B C B b ，

说明了解x 优化了原有的解，过程得以继续。证毕。

关于,x β选取的补充说明 因为

B N Bx Nx b += （9）

当0N x =时，10B x B b b -==≥为可行解，故选取初始基变量要留意。但由于N x 中的j x 要进入，即j x 取值要从零升为0β>。如何选取β，须受（9）节制，此时B x 中某个变量要退出，若记此退出的变量为r x , 则r x 要由原先取值为正变为取值零。这样（9）转变为

B j Bx b βα+= （10）

即

112211j j B j j m mj b a b a x B b B b b a βββαβαβ--??- ?- ?

=-=-= ? ? ?-??

我们的目标要使β尽可能大，但须保证0B x ≥. 因此，可选

min 0,1,...,i

ij ij b a i m a β??==?

???＞0=>r

rj

b a 所以，此时选取00βαββ????

-=+=+ ? ?????

B j j j x b x e e 。

§4 单纯形表及其求解优化方法

根据以上理论推导，给出下面可程序操作的单纯形表格。 单纯形表格1.

计算过程：(1)计算0z 以及-j j c z ，

12012...=+++m B B B m z c b c b c b ，

1212...=+++m j B j B j B mj z c a c a c a ，

1,2,...,=+j n m

(2) 如果所有0j j c z -≤.则达最大值.否则，存在j .使0->j j c z ，则j x 作为进入基. (3) 若{}

=min /0=/β>i ij ij k kj i

b a a b a ，则k x 是退出基。

（4）利用kj a 作为主元素进行消元

(1)(1)

(1)(1)/,/,1,2,...,,1,...,1,1,...,,1,...,1,1,...,k k kj ki ki kj k

i i ij kj

kl

il il ij kj

b b a a a a i n m

b b b a i k k m a a a a a i k k m n a ===+=-

=-+=-

=-++

1,2,...,1,1,...,l j j m n =-++

表中最后一行数据(1)c z -当然可以按照定义一一算出，但是可以证明：

(1)()k

j j kj

a c z c z c z a -=--

- 因为按上述运算规则，

12(1)1122...m k k k k B j B j j B m mj kj kj kj kj a a a a

z c a a c a a c c a a a a a a ??????=-+-+++- ? ? ? ? ? ???????

()k

j j kj

a z c z a =+- 所以

()(1)k

j j kj

a c z c z c z a -=--

- 上式表示最后一行也只需要用第k 行kj a 作为主元素消元而得，这样运算起来非常方便。

例1 求解线性规划问题

12max 3=+z x x

s.t. 1212

23810,1,2+≤??-+≤??≥=?i

x x x x x i .

解 这个问题是二维情形的线性规划问题，因此也可由图解法解出。可行域是由四条直线构成的四边形区域，不难知道在顶点(1,2)处，达到最优值7.

现在我们利用单纯形表来求解，用来熟悉这一有用工具。通过引进松弛变量，将约束条件等价地变为：

12312423810,1,2,3,4++=??

-++

=??≥=?i

x x x x x x x i 。 列单纯表如下：

第一轮

第二轮

第三轮

上表运算结果表明，

1212????== ? ???

??B x x x

是最优解，最优值为7.

例2 求解线性规划问题

123max 362z x x x =++

s.t. 1231233423210,1,2,3++≤??

++≤??≥=?i

x x x x x x x i

解：引进松弛变量45,x x ，原问题等价于求：123max 362z x x x =++

s.t. 12341235342

3210,1,2,3,4,5i

x x x x x x x x x i +++=??+++=??≥=?

列单纯形表如下：

第三轮

第一轮

第二轮

因此，1234521,,0,55x x x x x =

====原问题当12321

,,055===x x x 时达到最优解，最优值12

max 5

z =。

例3 求123max 2z x x x =+-

s.t. 123123123

2644,,0x x x x x x x x x ++≤??

+-≤??≥?

解：引进松弛变量，问题等价于

123max 2z x x x =+-

s.t.123412352+6440,1,2,3,4,5i

x x x x x x x x x i ++=??

+-+=??≥=?

表格运算表明：当12314/3,0,2/3===x x x 时， 有最优值26/3.

简单的线性规划教案[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 ９

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 的最小值． ） 【分析】 在平行直线系中先作过原点的直线，再将直线平移到 可行域中．