大学教案-线性规划

渭南师范学院

数学系讲稿

2012〜2013学年第二学期

教研室__________计算数学_________

课程名称__________线性规划_________

授课对象数专升本12级

授课教师____________路玉麟_________

职称____________讲师_________

教材名称《线性规划》•武汉大学出版社•张干宗

2013年3月10日

渭南师范学院数学系教师教案纸

《线性规划》课程教案讲稿

授课题目（教学章节或主题）：

授课类型课堂讲授

刖百线性规划概述

授课时间第1周第1节

教材分析：

本章主要介绍了线性规划的基本概念。

教学目的与要求：

要求学生掌握线性规划的作用和意义。

重点与难点：

重点：线性规划的基本概念

难点：常见线性规划问题

教学内容与过程（设想、方法、手段）

启发式教学、课堂精讲、讲练结合

思考题、讨论题、作业：

参考资料（含参考书、文献等）：

第页

渭南师范学院数学系教师教案纸

教学内容与过程课后分析

刖B

线性规划的英文全称为：LinearProgramming,可简称为LP.

一、线性规划所属学科

线性规划是“运筹学”中应用最广泛、理论最成熟的一个分支.

'线性规划

非线性规划

,,.静态规划整数规划

规n1P划A牝07规划

多目标规划

动态规划

运筹学对策论

决策论

排队论

图论

存储论

模型论

二、线性规划发展简史

三十年代末，苏联数学家康托洛维奇开始研究生产组织中的线性规划问

题.1947年美国数学家丹捷格提出了单纯形(Simplex)方法及有关理论，为

线性规划奠定了理论基础.五十年代，线性规划成为经济学家分析经济问题

的重要工具.随着计算机的迅猛发展，线性规划现被广泛应用于工业、农业、

商业等各个领域.

三、用线性规划方法解决实际问题的两大特点

1、全局性——从全局出发，将全局目标作为追求目标；

2、定量性——通过建立数学模型，对实际问题进行定量分析，而不是

只做定性分析.

数学模型指：将实际问题用一系列数学表达式(函数、方程、不等式等)

表示出来，称这系列数学表达式为该实际问题的数学模型.

同时应注意全局的相对性，即对于车间，企业是全局；但对于集团公司，

企业是局部，集团公司才是全局.

第页

渭南师范学院数学系教师教案纸

教学内容与过程课后分析

四、线性规划方法解决的两类问题

1、任务一定，如何安排，可使人、财、物最省；

2、人、财、物一定，如何安排，可使任务完成量最多.

五、线性规划可解决以下几方面的问题

1、运输问题：某产品有若干个产地、若干个销地，如何运输，使总运

费最省；

c“土㈤如］时/资源一定，如何安排生产，使产值（或利润）最高

2、生产组织问题：士，，，一卬“-4」二行

［产值一定，如何安排生产，使成本最低

3、配料问题：如何搭配各种原料，既符合质量（营养）要求，又使成本

最低；

4、投资问题：资金一定，投向谁、投多少、期限多长，使若干年后本

利和最高；

5、库存问题：在仓库容量有限情况下，如何确定库存物资的品种、数

量、期限，使库存效益最佳；

6、合理播种问题：在土地资源有限的情况下，种什么、种多少，使效

益最高；

六、用线性规划方法解决实际问题的步骤

1、提出问题，收集资料；

2、建立线性规划数学模型；

3、用线性规划方法解模型；

4、给出最优决策方案.

七、讲授内容

1、建模；

2、用图解法解线性规划问题；

3、用计算机软件解线性规划模型；

4、写最优决策方案.

八、考试方式：

第页

渭南师范学院数学系教师教案纸

教学内容与过程课后分析

第页

渭南师范学院数学系教师教案纸

《线性规划》课程教案讲稿

授课题目（教学章节或主题）：

授课类型课堂讲授

第一章线性规划数学模型的建立

授课时间第周第节

教材分析：

本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型的方法.

教学目的与要求：

通过本章学习，使学生理解线性规划数学模型的概念及一般表示形式；掌握线性规划数学模

型的三要素；掌握建立线性规划数学模型的步骤和方法；能熟练的建立一些问题的线性规划数学

模型；理解线性规划数学模型解的含义.

重点与难点：

重点：线性规划数学模型的建立

难点：建立线性规划数学模型

教学内容与过程（设想、方法、手段）启发式教学、课堂精讲、讲练结合

1、供求平衡条件下的运输问题模型的建立；

2、线性规划数学模型的三要素；

3、建立线性规划数学模型的步骤；

4、线性规划问题解的概念（可行解、可行解集、最优解、最优值）；

5、线性规划的概念；

6、线性规划数学模型的一般形式.

思考题、讨论题、作业：

参考资料（含参考书、文献等）：

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型

的方法.

一、建立线性规划数学模型的例

例1供求平衡状态下的运输问题

有两个农场A和42,产粮量分别为23万吨和27万吨，要将粮食运往耳，B2,

吗三个城市，三个城市的粮食需求量分别为17、18和15万吨.农场到各城市的运

价如下表

运价表单位：元/万吨

、运价

城市\

与B2B3

农场

Ai506070

A260110160

问：应如何调运，可使总运费最省？试建立该问题的数学模型.

分析此问题有两个供应方4和A2，三个需求方用，斗,吗，假设这五者

组成一个封闭系统，两个供应者的粮食只能提供给这三个需求方，同时三个需求方

的粮食也只能从这两个供应者处获得.

要建立该问题数学模型，必须首先从问题出发.

该题问“应如何调运，使总运费最省”.

“应如何调运”指从农场4分别向三个城市运多少万吨粮食(三个量)，从农场

A2分别向三个城市运多少万吨粮食(三个量)，共计6个量.

上述6个量是可以变化的，在计算前是未知的，是有待决策的，称其为决策变

量.在建立数学模型时应首先将其设出.为便于区分供应方和需求方，将其设为双

下标变量.

设：从农场A(i=1,2)运往城市Bj(J=1,2,3)的调运量为%.j(i=1,2"=1,2,3)万

吨.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

注意，此时的Xf既表示从农场A发往城市鸟的发出量，同时也表示城市吗从

农场Ai处的接收量.

如占3表示从农场A,运往城市B3的粮食量，同时表示城市鸟从农场A,处的接

收量.

为方便讨论问题，运输问题通常先列出如下调运表.

调运表

调运量y市

产粮量

用当当

(可供应量)

A占1占2龙1323

4堂工21X22X2327

需求量171815供求平衡

在这五个部门组成的封闭系统中,所有供应方的可供应量之和(23+27=50)为整个

系统的可供应量，整个系统中所有城市粮食需求量之和(17+18+15=50)构成系统的总

需求量.由于该系统的总供应量和总需求量都是50,相等，故在调运表最后一个单

元格中填写“供求平衡”.此问题即为供求平衡状态下的运输问题.

上述所设的6个决策变量(调运量)应满足一定要求，这些要求就应从供求平

衡开始.

由于供求平衡，供应方和需求方均恰好得到满足，即：两个供应方的粮食恰好

全部运出，三个需求方所需要的粮食也恰好全部得到满足，下面通过列表将文字语

言转化为数学表达式.

供应方：调出量恰好等于产粮量

供应方调出量恰好等于产粮量

Ai匹1+X\1+匹3=23

/2]+工22+工23=27

需求方：调入量恰好等于需求量

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

需求方调入量恰好等于需求量

用孙+孙=17

%再2+x22=18

辱国3+X23二15

于是，所设决策变量同时满足以上五个方程，且由于尤叮为调运量，必须非负.

x\\+x\2+和=23

X-y।+工22+工23=27

1+x-y।=17

所以=1,2;j=1,2,3)应满足:

西2+工22=18

x[3+x23=15

>0(/=1,2;J=1,2,3)

称上述条件为约束条件，满足约束条件的解称为可行解.

分析可行解的情况.

山于方程组中无矛盾方程，且有效方程的个数（4个）少于未知量的个数（6个），方

程组有无穷多个解，进一步满足非负条件的解也有无穷多个，即可行解有无穷多个,

每个可行解对应着一个调运方案（可执行方案）.如：

方案1BiB?星

113923

165627

171815

方案2B\B?自

A」1121023

A2166527

171815

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

显然，应有无穷多种调运方案.每个调运方案都对应着一个总运费.

方案1对应的总运费为：

1x50+13x60+9x70+16x60+5x110+6x160=3930(TE)；

方案2对应的总运费为：

1x50+12x60+10x70+16x60+6x110+5x160=3890(%).

即该题有无穷多个调运方案，不同调运方案对应不同运费，该问题要从无穷多

个调运方案中找出一个使总运费最省的方案，即使总运费函数

S=SOX”+60玉2+70占3+6O.r21+110x22+160x23

取得最小值的一组变量=12)=1,2,3)的取值.

综上，该问题数学模型列写如下：

解设：山农场A,(1=1,2)运往城市吗(1=1,2,3)的调运量为

xij(i=1,2;j=1,2,3)万吨.则该问题的数学模型为：

求一组变量(i=1,2；j=1,2,3)的值，使其满足：

X\\+再2+%13=23

工21+工2)+工23=27

X]।+欠21=17

<

匹2+x22=18

x13+x23=15

>0(i=l,2;；=l,2,3)

并使最小.

5=50XH+60X12+70X13+60AT21+110x22+160x23

此问题充分体现了全局观念.需求方不能仅考虑自己运费是否最低，而必须从

整个封闭系统总运费最低的角度出发，做到局部利益服从整体利益.

该题属第一类问题，即任务一定，如何安排，使人、财、物最省.

通过例1对线性规划数学模型有关问题作如下归纳.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

二、线性规划数学模型的三要素

所有线性规划数学模型都要求一组变量的值，称该组变量为决策变量；该组决

策变量都要满足一组条件，称该组条件为约束条件.一般，约束条件由两部分组成:

一部分为非负约束，剩下部分为数量约束；通常，满足约束条件的解若存在有无穷

多个，我们最终不是求这无穷多个解分别是什么，而要寻求一个目标.这个目标由

函数表示，称为目标函数，线性规划问题最终要使目标函数取得最大值或最小值.

决策变量、约束条件、目标函数分别构成了线性规划数学模型的三大要素.即

决策变量

数量约束

线性规划数学模型三要素约束条件

非负约束

目标函数

三、建立线性规划数学模型的步骤

建立实际问题线性规划数学模型的过程，实际是“翻译”的过程，即将实际问

题翻译成数学表达式的过程.通常先用文字将实际问题表示出来，再将文字转化为

数学表达式.具体步骤如下：

1、设决策变量——根据题目的“问题”，设决策变量；

2、列写约束条件——根据题目要求（字面或隐含）列出约束条件，约束条件中通

常包含非负限制.

3、写目标函数，并注明求最大或最小.通常目标函数要求在题目的问中提出.

四、线性规划问题解的概念

1、可行解：满足约束条件的解称为线性规划问题的可行解.

2、可行解集：全体可行解组成的集合.

3、最优解：使目标函数实现最优的可行解.

4、最优值：最优解对应的目标函数值.

由上述分析知，线性规划问题最终就是要求最优解和最优值，该过程称作解线

性规划问题的过程，或求线性规划问题的解的过程.

通常人们靠经验、靠想象求最优解，如上述例1,人们通常从当今的最低运费开

始设计•，直至满足所有需求方的需求，具体操作如下：

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

山于冬到生的运费最低，因而用的需求17万吨全部从4处获得，4得到满

足；在余下的运费中，A1到岛的运费最低，将A1剩余的6万吨给斗，斗所需的

另12吨只能从运费相对较低的A2处获得；由于此时4的粮食已全部运出，尽管运

解线性规划问题的方法有图解法、单纯形方法、对偶单纯形方法、两阶段法、

大M法等，我们在第五章中主要学习使用计算机软件求解.

通过计算机软件求解，可得例1的最优调运方案为：

最优方案B,层当

A081523

1710027

171815

该调运方案对应的运费为3650元，是所有可执行方案中运费最省的方案.

至于如何用程序解模型我们将在以后学习.下面我们仍然介绍建立数学问题的

数学模型的方法.

例2资源利用问题

某企业生产A,B两种产品，已知生产单位产品A和B分别需要消耗

钢材8吨和9吨，煤5吨和8吨，电力6度和4度，劳动力4人日和12人

EI.现该企业有钢材400吨，煤320吨，电力280度，劳动力350人II.又

知生产单位产品A和B各能获利8千元和1万元.问应如何安排生产，可

使企业利润最大？试建立该问题的数学模型.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

分析可将已知条件列表如下：

单耗产品

AB现有量

资

钢材（吨）89400

煤（吨）58320

电力（度）64280

人力（人日）412350

单位利润（千元）810

显然，B的单位利润高于A的单位利润，应多生产，但B对资源的消耗大，在

资源有限的情况下，生产数量必然少于同样资源条件下A产品的生产数量.另外，

现有资源数量与B的单耗间也不成比例，因此应对两种产品产量进行合理搭配，才

能在现有资源条件下创造出最高利润.此处的“如何安排生产”指在现有资源条件

下，A、B两种产品产量分别为多少.

决策变量：A、B两种产品产量，分别为内和£

约束条件：生产过程中对各种资源的消耗量不超过现有量

资源消耗量不超过现有量

<

钢材8匹+9X2400

<

煤5^1+8X2320

电力+4工2<280

<

劳动力4.+12X2350

显然，满足上述条件的解有无穷多个，每个解对应一个生产方案，不同生产方

案对应不同的企业利润.

目标函数：企业利润最大，即5=跖+10%2最大.

该问题数学模型列写如下.

解设：A、B两种产品产量分别为玉和乙.

则该问题的数学模型为：

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

求一组变量网和£的值，使其满足：

8Xj+9々4400

5x,+8X2<320

-6.+4盯4280

4X1+12X2<350

xt,x2>0

并使S=8X]+10x2最大.

此问题属第二类问题，即人、财、物一定，如何安排，使任务完成量最多.

此题需要说明的几个问题：

(1)关于决策变量：资源利用问题中的决策变量只能设各种产品的产量，而不能

设资源消耗量.因为产量作为决策变量，约束条件中的资源消耗量及目标函数中的

企业利润都可以通过决策变量(产量)表示，也便于利用计算出的结果安排生产.但若

设资源消耗量为决策变量，则很难分辨这些资源是由哪些产品消耗的，因而企业利

润无法表示，也就无法写出目标函数.

(2)关于约束条件：约束条件中的数量约束不能写成等式约束

+9巧=400

5匹+8巧=320

6X]+4X2=280

4占+12X2=350

这是由于：

①等式约束表示各种资源恰好全部用完，与实际问题不符，此时的利润未必

最大.因为利润最大时，某些资源可能恰好用完，但某些资源可能有剩余；

②上述方程组可能无解；

③即使方程组有解，即使此时利润最大，在列约束条件时，也不必写成“=”，

因为没有普遍性.而“W”中包含“="，应靠解规划问题解出结果可能均

为=,但不能事先写成=.

(3)此题通过计算机程序解得最优解和最优值为：

maxS=420

占=27.5

x2—20

即：产品A生产27.5个单位，产品B生产20个单位时，企业利润最大，最

大利润为420千元.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

（4）资源利用问题分析：将最优解代入约束条件的左端，即可得到最优生产方案

条件下各种资源的实际消耗量（如下表），将实际消耗量与资源现有量作比较，可分析

出各种资源的属性.

资源消耗量现有量余量

钢材8x27.5+9x20=4004000

煤5x27.5+8x20=297.532022.5

电力6x27.5+4x20=24528035

劳动力4x27.5+12x20=3503500

由于钢材和劳动力恰好用完，称其为稀缺资源，而煤和电力有剩余，称其为剩

余资源，同时可计算出剩余资源的剩余量.

（5）假设采用预先买电的方式，该企业应买245度电.

（6）假设要求劳动力全部上岗，则约束条件变为

8X1+9它4400

5再+8X2<320

<6x（+4巧<280.

+12X2=350

x],x2>0

（7）假设劳动力市场有充足的劳动者供应，则约束条件中应将劳动力约束删去，

变为：

8犬]+9X2<400

5x}+8X2<320

6^+4%2<280'

x[yx2>0

例3营养问题

有一位消费者欲购买营养物，根据医生要求，他所购买的营养物中，维生素A

的含量不低于9克，维生素C的含量不低于19克.现有六种营养物可供选择，单位

该营养物所含维A和维C的数量，及六种营养物的购买价格如下表：

单位含量7养物

与当为B&为练

维A（克）102212

维C（克）013132

购买价格（元）202560353739

问：他应如何购买，既符合医生要求，又花钱最省？试建立该问题的

数学模型.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

分析显然，满足医生要求的购买方案有很多，但不同购买方案所花的钱数不

同，该题要求找出花钱最少的方案.

决策变量：此处的“应如何购买”指六种营养物应分别购买多少.设六种营养

物的购买量分别为玉，x2,,xb.

约束条件：购买营养物的实际含量不低于医生要求

不低医生要

维生素实际含量

于求

维>

A+2X3+2X4+/+2%69

维>

Cx2+3X3+匕+3X5+2X619

显然，满足上述数量约束条件和非负限制的解有无穷多个，每个解对应•个购

买方案，花的钱数各不相同.

目标函数：花钱最少，即S=20XI+25%+60七+35》4+37》5+394最小.

该问题数学模型列写如下.

解设：营养物吗的购买量为吃(/=1,2,…,6)

则该问题的数学模型为：

求一组变量与(/=1,2,…,6)值，使其满足：

X]+2.+2X4+%+2%-9

-x2+3X3+乙+3X5+2X6>19

>0(y=1,2,-,6)

并使S=20%]+25X2+6OX3+35》4+37*5+394最小.

思考一下，该题属于第几类问题.

以上三个问题虽属于三个不同领域，但都是优化问题，都是要求满足一定约束

条件的最值问题，因而都属于规划问题，它们具有以下共同特点：

1、都要求一组决策变量的值.决策变量的每一组取值对应着一个可执行方案.通

常一个规划问题有无穷多个可执行方案.

2、都要满足一组约束条件，约束条件由数量约束和非负限制组成，其中数量约

束可能是等式约束、可能是不等式约束，在不等式约束中，可能是约束，也

可能是“2”约束.

3、都有一个目标函数，根据题目不同，有的目标函数求最大，有的求最小.

若约束条件为“W”约束，目标函数一般求最大，对应着人、财、物一定，如

何安排，使任务完成量最多问题；若约束条件为“2”约束，目标函数通常求最小，

对应着任务一定，如何安排，使成本最低问题.

4、约束条件和目标函数都是决策变量的线性表达式.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

五、线性规划数学模型的一般形式

当规划问题中的约束条件和目标函数都是决策变量的线性表达式时，称规划问

题为线性规划问题.

线性规划数学模型的一般形式为：

求一组变量七,％2,£的值，使其满足：

生内+aX2x2+---+a[nxn<(=,>)/?,

a2ix]+a22x2+---+alnxn<(=,>)b2

4”内+为"2*2+…+<(=,»,“

Xj>0(j=1,2,•••,»)

并使S=C]X]+c2x2+…+c”x”最大(或最小).

或写成

max(min)S=c}x}+c2x2+…+cnxn

%内+%2々+…<(=,2)4

在内+a22x2+---+a2nxn<(=,>)b2

amixt+a„l2x2+•-■+amnxn<(=,>)b,„

Xj>0(j=1,2,•••,«)

例4供求不平衡时的运输问题

例1中若农场为的粮食产量提高到了25万吨，其他条件不变，问如何调运,

使总运费最省？试建立该问题的数学模型.

解由农场=1,2)运往城市Bj(j=1,2,3)的调运量为xij(i=1,2;j=1,2,3)

万吨.

调运表

调运量城

产粮量

一B为

2(可供应量)

孙X\2的325

Az》21X22X2327

需求量171815供>求

由于供〉求，供应方不能得到满足，而需求方则恰好得到满足，即:

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

供应方：调出量不超过产粮量

供应方调出量不超过产粮量

%占1+为2+±3<25

AaX2]+X22+X23<27

需求方：调入量恰好等于需求量

需求方调入量恰好等于需求量

八+x

%2l=17

当项2+x22=18

鸟“13+123=15

该问题的数学模型为：

求一组变量=1,2;j=1,2,3)的值，使其满足：

+X12+X|3425

X

x2|+工22+23-27

x+x=17

<H2I

Xj2+=18

为3+X23=15

Xij>0(z=1,2;；=1,2,3)

并使S=50再1+60X12+70再3+60々1+IIOX22+160/23最d、.

例5供求不平衡时的运输问题

例4在即将执行最优运输方案时，接到城后之的信息，当的粮食需求量增至

20万吨.问如何调运，使总运费最省？试建立该问题的数学模型.

解设：由农场A,(i=l⑵运往城市鸟(/=1,2,3)的调运量为

(z=1,2;J=1,2：3)万吨.调运表

调运量7市

产粮量

当殳

(可供应量)

4为2工1325

XXX27

A2212223

需求量171820供〈求

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

由于供〈求，供应方能得到满足，而需求方则不能得到满足，即：

供应方：调出量恰好等于产粮量

供应方调出量恰好等于产粮量

AiX|1+占2+X”=25

X2\+X22+X23-27

需求方：调入量不超过需求量

需求方调入量不超过需求量

BiX\\+%21<17

Bi*12+X22<18

坛X13+123<20

该问题的数学模型为：

求一组变量X"(/=1,2;j=1,2,3)的值，使其满足：

X\\+X\2+X\3=25

%21+X22+X23=27

Xjj+x21<17

xi2+x22<18

当3+x23420

x(7>0(/=1,2;j=1,2,3)

并使S=50XH+60XI2+70X[3+60X21+110x22+160x23最小.

例6生产计划问题(工时利用问题)

某精密仪器厂生产甲、乙、丙三种仪器，平均每生产一台甲需7小时加工、6

小时装配、售价为3000元；每生产•台乙需8小时加工、4小时装配、售价为2500

元；每生产一台丙需5小时加工、3小时装配、售价为1800元.每季度可供利用的

加工工时为2000小时，装配工时为1000小时，三种仪器所需元器件基本相同.又

据市场预测知：后场对甲的需求量每季度不超过200台，乙不低于180台，丙无要

求.问应如何安排生产，可使企业产值最高？试建立该问题的数学模型.

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

将已知条件列表如卜.:

单位工时X品

每季度

甲乙丙

可用工时

加工7852000

装配6431000

售价300025001800

市场需求<200>180

分析决策变量：三种仪器每季度产量，分别为不，9和与台；

约束条件：两方面

(1)加工时对设备的消耗工时数不超过每季度可利用工时数：

(2)甲、乙两种仪器每季度实际产量应满足市场对该仪器的需求量.

(1)加工时对设备的消耗工时数不超过每季度可利用工时数：

工序实际消耗量不超过可用量

加工7$+8X2+5均<2000

装配<

6为+4x2+3内1800

(2)甲、乙两种仪器每季度实际产量应满足市场对该仪器的需求量:

甲不超过200台

仪器季度产量不超过需求量

甲<200

乙不低于180台

仪器季度产量不低于需求量

乙X2>180

可行解也有无穷多个.

目标函数：企业产值最高，产值=产量X销售价格.

解设：甲、乙、丙三种仪器每季度产量分别为王，马和£台，

则该问题的数学模型为：

第页

渭南师范学院数学系教师教案纸

教学内容与步骤备注

求一组

变量X],x2,X3的值，使其满足：

7X1+8々+5X3<2000

6X]+4X2+3X3<1000

/<200

x2>180

xl,x2,x320且为整数

并使S=3000%,+2500X2+I8OOX3最大.

例7进售或Ht划问题

某专卖店要制定明年一季度商品