线性规划问题的数学模型省名师优质课获奖课件市赛课一等奖课件

数学建模系列讲座

（一）线性规划模型第1页线性规划问题第一节线性规划问题数学模型（一）引言线性规划是运筹学主要分支之一，也是研究较早、发展较快、应用较广而且比较成熟一个分支。自1947年线性规划被成功利用于工业、交通、农业和军事等各个领域后，现在它已成为管理科学主要基础和伎俩之一。伴随计算机普及，它适应领域越来越广泛。线性规划研究问题主要有两类：一是一项任务确定后，怎样统筹安排，尽可能作到用最少人力物力资源去完成这一任务。二是已经有一定数量人力物力资源，怎样安排使用他们，使得完成任务最多。其实这两类问题是一个问题两个方面，就是所谓寻求整个问题某个整体指标最优问题。

1.运输问题2.生产组织与计划问题3.合理下料问题4.配料问题5.布局问题6.分配问题第2页（二）线性规划问题数学模型1.运输问题

设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们生产供给B1、B2、B3三个工地。其需要量分别为17万块、18万块和15万块。自各产地到各工地运价格以下表：问应怎样调运，才使总运费最省。

运价工地砖厂B1B2B3A1506070A260110160第3页解：设xij表示由砖厂Ai运往工地Bj砖数量（i=1,2；j=1,2,3)运量工地砖厂B1B2B3发量A1x11x12x1323A2x21x22x2327收量17181550第4页目标函数约束条件第5页2.生产组织与计划问题

某工厂生产A、B两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润以下表所表示。问怎样制订生产计划使两种产品总利润最大？单位产品

产品耗用资源

资源A（千克）B（千克）现有资源铜（吨）94360电力（千瓦）45200劳动日（个）310300单位利润（万元/千克）712

第6页

解：假设生产A产品x1千克，B产品x2千克，x1，x2称为决

策变量，简称变量。得到利润7x1+12x2万元，这一问

题数学模型为：

约束条件

目标函数第7页

上述例子即使有不一样实际内容，不过都可归结为一类优化问题。从数学上说它们含有以下共同特征：

⑴

每一个问题都是求一组变量（称为决议变量）值。这组变量一组定值就代表一个详细方案。通常要求这组变量取值是非负。

⑵

存在一定限制条件，称为约束条件。这些约束条件都能够用一组线性等式或不等式来表示。⑶

都有一个期望到达目标，而且这个目标能够表示为决议变量线性函数（称为目标函数）。按所研究问题不同，要求目标函数值最大化或最小化。我们将含有上述三个特点最优化问题归结为线性规划问题，其数学模型称为线性规划问题数学模型，简称线性规划数学模型。第8页线性规划问题数学模型普通形式

（1）式称为目标函数（2）式中等式或不等式称为约束条件（3）式是非负约束条件

x1,

x2,…,xn称为决议变量，简称变量。第9页满足约束条件一组变量值称为线性规划问题一个可行解，使目标函数取得最大（或最小）可行解称为最优解。此时，目标函数值称为最优值。

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

首先，确定决议变量。线性规划数学模型建得是否轻易，求解是否方便，取决于决议变量选取是否得当。

其次，确定约束条件，并依据实际问题添加非负条件。明确问题中全部限制条件，并用决议变量线性等式或不等式表示。普通可用表格形式列出全部限制数据，然后依据所列出数据写出对应约束条件，以防止遗漏或重复所要求限制要求。

最终，确定目标函数，并确定是求极大还是求极小。用决议变量线性函数来表示实际问题所要到达目标，得到目标函数。第10页第二节两个变量线性规划问题图解法例1求x1、x2值，使它们满足而且使目标函数f=2x1+5x2值最大。图解法是利用直观几何图形求解线性规划一个几何解法第11页x12x1+5x2=192x1+5x2=152x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80x2最优解为x1=2，x2=3相应目标函数最大值为S=2*2+5*3=19第12页x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0x2=3x1=4x1+2x2=80x2例2

若把例1目标函数改为s=x1+2x2，最优解有

无穷多个，它们对应目标函数值都是8。（见下列图）第13页例3求x1、x2值，使它们满足而且使目标函数s=2x1+2x2值最小。第14页x1x20X1-x2=1X1+2x2=02X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16最优解X1=1，x2=0,目标函数最小值s=2解：例4

若把例3改为使目标函数值最大，从图可看出目标函数无上界，所以无最优解第15页例5

求x1、x2值，使它们满足而且使目标函数s=2x1+2x2值最小。第16页x1x2-x1+

x2=1x1+

x2=-2没有可行解，当然没有最优解。解：第17页（一）线性规划问题标准形式

线性规划问题数学模型有各种不一样形式。为了便于讨论，需要将线性规划数学模型写成统一格式。

线性规划问题标准型是：第三节单纯形法约束条件（2）式又称等式约束（3）式称非负约束。标准型特点为（1）目标函数为最大值形式（2）约束条件用等式表示且等式右端常数为非负值（3）决议变量非负。第18页

把普通线性规划问题化成标准型过程称为线性规划问题标准化。线性规划问题标准化方法以下：1.求目标函数最小值

令F=-f，则可将求f最小值问题转化成求F最大值问题，即2.约束条件为不等式

引入一个非负变量xn+i，转化为线性等式，称

xn+i为松弛变量。3.若有bi≤0可在该约束条件两边同乘-1，化为

4.假如有某个变量xj无非负约束

可引进非负变量xj/,xj//，令xj=xj/-

xj//

代入约束条件和目标函数中。第19页例1

将下面线性规划问题化成标准型。解⑴引进松弛变量

x4≥0

,

x5≥0

，将式中不等式约束条件变换成等式约束条件：⑵将3x1-x2-2x3=-5两边同乘-1，变为-3x1+x2+2x3=5⑶变量x3无非负约束，引进非负变量x6,x7，令x3=x7-x6，代入约束条件和目标函数。得最终，令F=-f，则可将求f最小值问题转化成求F最大值问题。标准型为：第20页（二）、基本概念

定义在线性规划标准型中，假如有变量只在某一个约束方程中系数为1，在其余约束方程中系数全为0，则称为该约束一个基变量；假如每个等式约束都有一个基变量，则称等式约束条件是这些基变量经典方程组。假如线性规划约束条件是经典方程组，不失普通性，设n个变量线性规划问题经典方程组为：第21页其中基变量为x1,

x2,

…

,

xm，从而xm+1,

xm+2,

…

,

xn称为非基变量。

令非基变量xm+1=0,

xm+2=0,

…

xn=0，则可求得约束方程一个解：x1=b1,

x2=b2,

…

,

xm=bm,

xm+1=0

,

xm+2=0,

…

,

xn=0称为基本解。假如bi≥0(i=1,2,…,m)则称此基本解为基本可行解。

(三)、单纯形法1．单纯形法基本思想单纯形法基本思绪是：依据标准型，从可行域一个基本可行解开始，转移到另一个基本可行解，而且使目标函数值逐步变优，当目标函数值到达最大值时，就得到问题最优解。第22页下面举例说明单纯形法基本思想

例2

求解线性规划问题

解

先将问题化成标准型第23页显然x4,

x5为基变量，x1,

x2,

x3为非基变量，约束条件是经典方程组。由（1）可得：将（2）代入目标函数可得f=2x1+3

x2+

x3+0,令非基变量x1=

x2=

x3

=0则有f=2x1+3

x2+1x3+0=0

,

同时得到一个基本可行解

x1=

x2=

x3

=0,x4=1,x5=3

由f=2x1+3

x2+

x3+0可知，非基变量系数都是正数，若将其中任意一个非基变量变成基变量（取值从0变成正数）,都能够使目标函数值增加,所以只要在目标函数表示式中还存在有正系数非基变量，就表示目标函数值还有增加可能，从而不是最优解，就需要将非基变量与基变量进行对换。我们把非基变量转换为基变量称为进基。普通选择正系数最大那个非基变量（本例为x2）为进基变量，以求得目标函数值较快增加。将x2换入到基变量中。同时，还要确定基变量中有一个要换出来成为非基变量。变量由基变量转化成非基变量称为出基。第24页怎样确定出基变量，由（2）式，x2

为进基变量，x1,

x3仍为非基变量，故x1,

x3值为零。代入（2）式可得

伴随x2值增加，x4,

x5值会逐步变小，因为

才能确保x4≥0,

x5≥0

（即解可行性）。当x2=9/4时，x5=0。即用

x2替换x5（x5出基），于是得到新基变量x4,

x2

,非基变量x1,

x3,

x5

。这种确定出基变量方法称为最小比值标准。第25页由（2）式写出用非基变量表示基变量表示式：整理得

代入目标函数得f=27/4+5/4

x1-17/4

x3–9/4x5令非基变量x1=

x3=

x5

=0得一新基本可行解

x1=0,x2=9/4,x3=0,x4=1/4,x5

=0代入代入目标函数

得对应目标函数值

f=27/4非基变量x1系数是正数，说明目标函数值还可能增加，于是再用上述方法，确定进基、出基变量，又得到另一个基本可行解

x1=1,x2=2,x3=x4=x5

=0f=2×1+3×2=8用非基变量表示目标函数f=8-3x3–5x4-1x5第26页式中全部非基变量系数均是负数，意味着目标函数值不可能再增加，故此时基本可行解就是最优解，最优值为8

2．最优性检验由标准形等式约束条件得代入目标函数进行简单运算后，用非基变量表示目标函数为称为非基变量检验数。将用检验数来判定线性规划问题是否有最优解，有最优解定理。第27页定理(1)假如关于非基变量全部检验数

则基本可行解就是最优解(2)假如关于非基变量全部检验数且其中有一个非基变量xm+k检验数为零

则该线性规划问题有无穷多个最优解(3)假如存在非基变量xm+k检验数>0

且xm+k对应系数列均小于等于零

则该线性规划问题无最优解

第28页3.单纯形表

用表格形式来表示上面求解线性规划问题单纯形法计算过程能够使计算和检验愈加简便。详细方法以下：

将目标函数式改写为-f+c1

x1

+c2

x2

+…+cnxn=0且作为等式约束方程组第m+1个方程，得对方程组(3-1)增广矩阵施行初等行变换，化为以下阶梯形矩阵第29页将矩阵表示成单纯形表xBb100010

001-f000-f0x1x2…xmxm+1…xnx1x2…xmb1b2bm……………………a1m+1a2m+1amm+1a1na2namn……下面经过详细例子说明用单纯形法求解线性规划问题。

第30页例1

用单纯形法解线性规划问题解

将该线性规划问题化为标准型第31页显然x3,

x4,

x5为基变量，x1,

x2为非基变量。可得单纯形表(下表所表示）。这种直接从线性规划问题得到单纯形表称为初始单纯形表xBb22100

121

[2]0108400016-f

2

3

00001x3x4x5x1x2x3x4x5初始基本可行解为x1=

x2=0,x3=12,x4=8,x5=16。因为检验系数有正数，所以这个基本可行解不是最优解。从x1，

x2中选一个检验数最大变量x2进基。依据最小比值标准(mim{12/2,8/2}=4)确定,x4出基。进基变量x2所在列与出基变量x4所在行交叉处元素称为主元，加上方括号，再施行行初等变换，将主元所在列主元化为1，其余元素化为0，得下表注

用最小比值标准确定出基变量普通方法是：在单纯形表中，b列元素与进基变量列对应正元素之比，取其比值最小所对应基变量出基。第32页xBb

1

01-104

1/2101/20

4[4]000

16-f1/200

-3/20-12x3x2x5x2x3x5x4x11xBb001-1-1/400101/2-1/8210004-f000

-3/2

-1/8-14x1x2x3x4x5x3注：比值相等时可任选其一

x2x11/4最优解为x1=4x2=2x3=x4=x5=0目标函数值为f=14

非基变量检验数小于0第33页例2

用单纯形法求解线性规划问题解

x3,

x4为基变量，x1,

x2为非基变量。可得初始单纯形表

XBb[1]-1102-31014-f32000X1X3X4X2X3X4第34页XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有检验数>0系数列均≤0

无最优解例3用单纯形法求解线性规划问题第35页解

将该线性规划问题化为标准型：F=-f进行换基迭代，计算过程如表第36页XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18XBb[1]11006120108010013-F33000011100601-1102010013-F00-300-18xBb

[1]

1100

6

12010

801003-F

33

0000

11100601-110

201003-F0

0

-300-18

x1x4

x3x5

x2

x3x4x5x1x4x511非基变量有检验数<0，有检验数=0无穷多个最优解其中一个最优解是x1=6,

x2=0最优值为f=-F=-18第37页第四节两阶段法

求解线性规划问题单纯形法必须满足每个等式约束都有一个基变量即线性规划约束条件是经典方程组，但经常出现情况是线性规划标准型约束条件不是经典方程组，从而不含有初始单纯形表，这时，需要在线性规划问题中加入人工变量，把问题变为约束条件是经典方程组情形，再按上述方法换基迭代求出最优解。

人工变量是后加入原约束方程组中虚拟变量，我们必须把它们从基变量中逐步替换掉。若经过基变换，基变量中不再含有些人工变量，这表示原问题有解；若经过基变换，最终在基中还有一个或几个人工变量，这意味着原问题无可行解。两阶段法是处理人工变量方法之一，它是将加入人工变量后线性规划问题分成两阶段求解。第38页第一阶段：判断原线性规划问题是否有基本可行解。其方法是：对于线性规划问题标准型目标函数、等式约束、非负约束引入人工变量y1,

y2,…,ym，结构一个辅助线性规划问题。

对辅助线性规划问题应用单纯形法，求出辅助问题最优解。若最优值Z=0，说明全部些人工变量都变换为非基变量，表明原问题已得到一个基本可行解，则进入第二阶段；不然原问题无可行解，计算结束。第39页第二阶段：在第一阶段所得初始单纯形表基础上，进行换基迭代。将第一阶段最终计算表中目标函数系数换成原问题目标函数系数，划去人工变量所在列，完成单纯形表，就得到求解原问题初始单纯形表。然后用单纯形法进行计算求出最优解。例1

用两阶段法求解下面线性规划问题解第一阶段

：第一、第二约束中暂缺基变量，分别引入人工变量y1、

y2,引入辅助线性规划问题第40页Z用非基变量表示：

用单纯形表进行换基迭代以下XBb511[8]101024320110-Z7541000201001-Z00011102-Z0000-1-10XB

x1

x2x3

x4y1y2by1511[8]1010y224320110-Z754100020第41页XBx1x2x3x4

y1y2b

x45/81/81/811/805/4y23/4[15/4]11/40-1/4115/2-Z3/415/411/40-5/4015/2

x4

3/501/3012/15-1/301x21/5111/150-1/154/152-Z0000-1-10因为得到辅助问题最优值Z=0，且人工变量均已出基，于是进入第二阶段。第42页第二阶段

在第一阶段最终表中划去人工变量所在列，并将-Z行换成

-f行即得原问题初始单纯形表。这里需注意是，填–f行前，需将f

用非基变量表示，由上表最终一次换基迭代知：用单纯形法进行计算，以下表所表示第43页XBx1x2x3x4bx4[3/5]01/3011x21/5111/1502-f20-1/30-10x1101/185/35/3x20113/18-1/35/3-f00-4/9-10/3-40/3原线性规划问题最优解为

x1=5/3,x2=5/3,x3=x4=0最优值为

f=40/3

第44页例2

用两阶段法求解下面线性规划问题解化成标准型第45页解第一阶段

：引入人工变量y1、y2、y3,引入辅助线性规划问题Z用非基变量表示：

用单纯形表进行换基迭代以下：

第46页xBx1x2x3y1y2y3by195010014y213-20102y3[3]-230014-Z136100020y10[11]-910-32y2011/3-301-1/32/3x11-2/31001/34/3-Z044/3-1200-13/38/3x201-9/111/110-3/112/11y2000-1/312/30x1105/112/3305/3316/11-Z000-4/30-1/30第47页于是得辅助问题最优值Z=0。人工变量y2还未出基，且y2所在行非人工人工变量列元素均为零，无法让y2出基。不过由最终一个单纯形表中y2所在行，得这表明原问题约束方程组中第二个方程可由第一个方程减去二倍第三个方程得出。所以，第二个方程是多出，故最终一个迭代基变量y2所