运筹学课件邮电经济管理学院

线性规划与单纯形邮电大学经济管理学： Copyright©2013 Chapter1线性规(Linear本章主要内容本章主要内容单纯形单纯形法的进一步讨论－人工变量LP模型的应 Copyright©2013 线性规划问题的数学模规划问线性规划通常解决下列两类问题用最少的资源（如 线性规划通常解决下列两类问题最好的经济效益（如产品量最多、利润最大.） Copyright©2013 线性规划问题的数学模x例1.1如图所示，如何截取x使铁皮所围成的容积最xv

2x2adv

2x)

x(2)

2x)2x6 Copyright©2013 线性规划问题的数学模例1.2生产计划问 Copyright©2013 线性规划问题的数学模生产方案2生产20个桌子，10个椅子，木工仍剩余10小 Copyright©2013 线性规划问题的数学模资源使用利用产品数使用资剩余资收桌椅木油木油100203 Copyright©2013 线性规划问题的数学模目标函 Maxz约束条 4x1+3x2≤2x1+x2≤x1,x2 Copyright©2013 例1.3:某工厂拥有A、B、C三种类型的设备，生产甲、乙设备32设备21设备03利润（元/件问题：工厂应如何安排生产可获得最大的总利润 Copyright©2013 线性规划问题的数学模解：设变量为第种（甲、乙）产品的生产件数＝，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。 是我们可以得到不等式：3x1+2x2≤65； 是我们可以得到不等式：2x1+x2≤40； Copyright©2013 线性规划问题的数学模 是我们可以得到不等式：3x2≤75；另外，产品数不可能为负，即x1,x2≥0。 x2。综合上述讨论，在加工时间以及利润与 Copyright©2013 线性规划问题的数学模目标函 Maxz 约束条 3x1+2x2≤2x1+x2≤3x2≤75x1,x2 Copyright©2013 线性规划问题的数学模练习某企业计划生产甲、乙两种产品。这些产品分设产ABCD利润（元甲2乙8 Copyright©2013 线性规划问题的数学模解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为 Z=2x1+2x1+2x2≤x1+ ≤ ≤ ≤x1≥0,x2≥ Copyright©2013 线性规划问题的数学模 Decisionvariables目标函 Objective约束条 问题都用一组决策变量表示某个方 Copyright©2013 在管理中一些典型的线性规划合理利用线材问题：如何在保证生产的条件下，下料最配料问题：在原料供应量的限制下如何获取最大利投资问题：从投资项目中选取方案，使投资回报最劳动力安排：用最少的劳动力来满足工作的需问题：如何制定调运方案，使总运费最 Copyright©2013 练 班时所需人16：00——210：00——314：00——418：00——522：00——62：00—— Copyright©2013 解：设xi表示第i班次时开始上班的 目标函数 x1+x2+x3+x4+x5+约束条件+≥+≥+≥+≥+≥+≥x1,x2,x3,x4,x5,x6≥ Copyright©2013 线性规划问题的数学模cn线性规划数学模型cn目标函数：max(min)

c2x2约束条件

()

()

m2

,xnn

Zcjxj简写为

nn

aijx

()

(i12m)xj

(j12n) Copyright©2013 线性规划问题的数学模向量形式

pjx ()其中

X XC c1x

a

b1bxXx

Pj

1j

Bn

m Copyright©2013 线性规划问题的数学模矩阵形式：

(min)

AX

)X0X0其中

C

c2

cn

a1n

x1

b1bAb

B

amn

n

mxx Copyright©2013 图解线性规划问题的求解方坐两个变量、直角坐坐—般有

图解法单纯形

三个变量下面我们分析一下简单的情况——只有两个决策 Copyright©2013 图解图解法的步骤1、在平面上建立直角坐标2、图示约束条件，找出可3、图示目标函数和寻找最 Copyright©2013 图解例1.6用图解法求解线性规划问maxZ=2X1+X1+1.9X2≥3.8X1-1.9X2≤s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0 Copyright©2013 图解 Z=2X1+ X1+1.9X2=11=

X1-1.9X2=-3.817.2=2X1++4=2X1+ 20=2X1+可行可行此点是唯一最优解且最优目标函数maxmaxZminZoLo：0=2X1+

X1+1.9X2=

X1-1.9X2= Copyright©2013 图解max

X1+1.9X2=10.2可行

X1-1.9X2=-maxZ=34.2是唯一的。maxo

X1+1.9X2=X1-1.9X2=3.8L0：

34.2= Copyright©2013 图解min X1+1.9X2=10.2DD此点是唯一最 可行maxminoL0：

X1+1.9X2=X1-1.9X2=3.8 Copyright©2013 8例1.7maxZ=2x14x22x1+x28-2x1+x2 x1,x2 解2无有限最优0

-2x1+ 2x1+ Copyright©2013 -0--0-max-x1-x2x1,x2无无可行 Copyright©2013 习题1：maxZ=40x1x1+2x23x1+2x22x224x1,x20 Copyright©2013 解：(1)、建立坐标、确定可行

X1+2X2maxZ=40x1+3X1+2X2x1+2x2x1+2x2x1+2x2x1+2x2(0,15)2

+2x2

2X2 2x,22x1,x23x13x1+2x2(0,30) 2x22x2x1x1 x1=0(纵x2 x2=0(横

Copyright©2013 、求最优

maxZ=40x1+x1+2x2x2=-

+2x22x2C

x1,x23x1+2x2

解：x1解：x1x2=maxZ

Copyright©2013 习题2：maxZ=40x1+ ABC0DX1+ABC0DX1+2x2Z=40x1+80x23x1+2x22x224x1,x20求最优解：BC线 Copyright©2013 图解

习题

maxx13x2xx12 2xx12 3x

3

0、x24

解(无最优解maxZminZ

Copyright©2013 习题

max 2x1x240x11.5x2

30x1x250 x10,x2 无可行解(即无最优解 Copyright©2013 习题习题 z=2x1+3x2x1+2x284x14x212 Copyright©2013 1o.建立平面直角坐标系；3o.画出目标函数的等值线；4o.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。 z=2x1 z=2x1+3x2x1+2x284x14x212 3

Copyright©2013 练习题

最优+最优- 可行x1≥0,可行4- 目标目标函数 Copyright©2013 解解无无可行 Copyright©2013 解解无无可行 Copyright©2013 解 解无无可行

Copyright©2013 无 无可行

Copyright©2013 学习要点通过图解法了解线性规划有几种解的形（唯一最优解；无穷多最优解 解；无可行解作图的关键有三点可行解区域要画正目标函数增加的方向不能画目标函数的直线怎样平行移 Copyright©2013 线性规划问题的数学模线性规划问题的标准形max

c2

...

cna11

...

a1n

x x... 2n x x... m2

,x2,..., Copyright©2013 对max(min)

cxc

c

max(min)Zcjxax x

()

j

nnj

aijx

()

(i12m)am1

am2

amn

()

xj

(j12n)

xnmax

c2

...

cn

...

a21

a22

...

a2n

am2

...

amn

maxZcjxjnsmaxZcjxjns.tja ixi1,,j0,j1,,

C C线性规划问题的数学模maxZmaxZcjxjns.tja ixi1,,j0,j1,,特特点目标函数求最大值（有时求最小值约束条件都为等式方程，且右端常数项bi都大于或等于决策变量xj为非负 Copyright©2013 线性规划问题的数学模5如何化标准形 5如何化标准形

cj

则可将目标函数乘以(-可化为求极大值问题 maxzzcjx也就是：令z

z，可得到上式 Copyright©2013 minZ=2x1+5x2+6x3maxZ’=-Z=-2x1–5x2-6x3-返返 Copyright©2013 线性规划问题的数学模jj 变量x 的变 jjjxj

x

x 变量的变若存在取值无约束的变量

j，可j

xj

Copyright©2013 线性规划问题的数学模3x1+2x2例令x1x1x1x1"0

x1–4x2令x2x2'3x1'-3x1"-2x2'8x1' x1"+4x2'x1',x1",x2' Copyright©2013 线性规划问题的数学模 约束方程的转换：由不等式转换为等式aijxj

aijx

xni

称为松弛变aijx

aijx

xni

称为剩余变 Copyright©2013 线性规划问题的数学模约束条当约束条件为“≤”时

x3为松弛变当约束条件为“≥”时

12x2

x4为剩余变未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。 Copyright©2013 线性规划问题的数学模例maxZ=2x1+ +0·x3例6x1+2x2x1+

+x5=xi0(i

松弛变 Copyright©2013 线性规划问题的数学模例minZ=2x15x2+6x3-4x1+6x2+-x1+ x2+7x3+5x42x2+xi0(i

+0x5+0x6- -x7剩余变 Copyright©2013 线性规划问题的数学模可在等式两端乘可在等式两端乘以“-1”。当出现一，这点将在以后讨论bi=0时，表示出

0的变 Copyright©2013 线性规划问题的数学模 x1+x2+x3--x1-x2-x3 Copyright©2013 线性规划问题的数学模min52x2x2min52x2x2x3 x1xx24 331223x2 0,,x3无约束解:（１）因为x3无符号要求，即x3取正值也可取负值，标准

x3，且

Copyright©2013 minZ2minZ2x1x23x35x1x2x3x 41233x 2123x1x20x3无约束””第一个约束条件是“≤”号，在””左端加入松驰变量x，x≥0,化为 式第二个约束条件是“≥”号，在左端减去剩余变量x，x Copyright©2013 线性规划问题的数学模标准形式如下maxZ'2x 3(xx)0x 0x

3x 2(xx

min

2x1

3x3 5x1x2 x1x2x 3x1x

x34x32x3 Copyright©2013Czh

x2

0x3无约束线性规划问题的数学模例1.minZ=-x1+2x2x1+x2+x3x1-x2+x3化 Copyright©2013 线性规划问题的数学模解x3=x4松弛变量

minZ=-x1+2x2xx1+x2+x37x1-x2+x3Z'=maxZ'=x1–2x2-3x4+3x5+0x6x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,…,x70 Copyright©2013 习题习题解练 Copyright©2013 练 练解解 Copyright©2013 练练习题3：将以下线性规划问题转化为标准minZ=-3x1+5x2+8 -7 2x1-3x2+5x3+6x4≤4x1+2x2+3x3-9x4≥6x2+2x3+3x4≤-x1,x3,x4≥ Copyright©2013 线性规划问题的数学模k阶子式--在m×n矩阵A中，任取k行与k列（k≤m,k≤n），位得的k阶行列式，成为矩阵A的k阶子式。 Copyright©2013 线性规划问题的数学模矩阵的初等变换对调矩阵的两行或两列以非零数k乘矩阵的某一行（列）的所有元素 Copyright©2013 线性规划问题的数学模6规划问题的解ns.tnj Copyright©2013 线性规划问题的数学模最优解：使目标函数达到最大值的可行解 Copyright©2013 线性规划问题的数学模

a1mB

(

pm mmB中每个列向量Pjj12m为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。 Copyright©2013 2x1+3x2-x3≤18x1-x2+x3≤3 Copyright©2013 线性规划问题的数学模maxZ= x1,x2,x3,x4,x5,x6,≥0100 100 10.非11331100010 23 123 1 基

Copyright©2013 线性规划问题的数学模maxZ= x1,x2,x3,x4,x5,x6,≥0121 12133 1

11110

22

非0101001

ht©2013 线性规划问题的数学模…A= … …Pn …基向 非基向 基阵非基矩…X= … …xn)T=(XB…基变 非基变 Copyright©2013 线性规划问题的数学模设XB是对应于基的基变XB=（x1,x2,现若令上式的非基变量xm+1=xm+2=…=xn=0,这时变量的 XB=（x1,x2,…,xm,0,…,0）T Cn值的个数不大于方程数m，基解的总数不超 Cn Copyright©2013 线性规划问题的数学模 Copyright©2013 例 2x1+3x2-x3≤18x1-x2+x3 化为标准

x1,x2,x3,x4,x5,x6,≥0 Copyright©2013 基变量x1、x2、x3，非基变量x4、x5、基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为 Copyright©2013 基变量x1、x2、x4，非基变量x3、x5、基础解（x1，x2，x3，x4，x5，x6）=（27/5，12/，0，2/，0，0）是基础可行解，表示可行域的一个极点。目标函数值为 Copyright©2013 基变量x1、x2、x5，非基变量x3、x4、基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，3，0）是基础解，但不是可行解，不是一个极点。 Copyright©2013 基变量x1、x2、x6，非基变量x3、x4、基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为 Copyright©2013 基变量x2、x3、x4，非基变量x1、x5、基础解（x1，x2，x3，x4，x5，x6）=（0，21/，27/2，30，0，0）是基础解，但不是可行解。 Copyright©2013 基变量x2、x3、x5，非基变量x1、x4、基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为 Copyright©2013 基变量x2、x3、x6，非基变量x1、x4、基础解（x1，x2，x3，x4，x5，x6）=（0，1/，3/，0，0，10）是基础解但不是可行解。 Copyright©2013 凸凸不凸凸不是凸 Copyright©2013 Copyright©2013 单纯形单纯形法的思找出找出一个初始基可行最优是否最最优否循否转移到另一个转移到另一个基本可行（找出更大的目标函数值是：变量迭 Copyright©2013 用表格法求解LP问题，规范的表 单纯形表如下所……b……10……00………………0…1…0…0…cj行——价值系数，b列——列——下面一行——检验数，中间主要部分—— Copyright©2013 单纯形法的计算步例1.12用单纯形法求下列线性规划的最优maxZ3x14x22x1

x

x,x，加入松驰变，加入松驰变量x3、x4为解：1）将问题化

4x22x1

x

x,x,x, Copyright©2013 maxZ3maxZ3x14x22x1x2x13x2x,x,x,x4 00b3213400b3213434000010检验1c1(c3a11c4a21)3(0 0jci Copyright©2013 maxmaxZ3x1 x,x,x,xxx2x1x242将3将3化为换入 换换行 基变

0

1 1

biLa Copyright©2013

3x14x2单纯形法的计算步

2x1x2 x

x,x,x,

b0211001301j3400 400b0404010100maxZmaxZ3x14x22x1x2xx,x,x,124 001044013b0043 Copyright©2013 单纯形法的计算步将问题化 求出线性规划的初始基可行解，列出初始单纯形表 Copyright©2013 单纯形法的计算步进行最优性检①如果表中所有检验

0，则表中的基可行解就是题的最优解，计算停止。否则继续下一步②如果表中所有检验

0，且某非基变量检验数为零则此问题含有无穷多最优解，计算停止。否则继续下一步③如果表中某非基变量的检验 ，且对于系数矩中换入列中的所有系数都小于等于0无法 ），则问题无可行解。计算停止。否则继续下一步 Copyright©2013 单纯形法的计算步 确定换入基的变量。选择j0，对应的变量xj作为换入kk

max{

|

，其对应的xk作为换入 确定换出变量。根据下式计算并选择θ，选最小的θ对应变量作为换出变

L

aik

③用换入变量x替换基变量中的换出变量，得到一个新的基。对00/1/10复3）、4）opyright©2013Czhang. .用单纯形法求下列线性规划的最优maxz=2x1+3x2x1+2x284 4x212x1,x20解：化为标准maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3 =8 4 x1,…x5 Copyright©2013 2300023000 b000814020(4)100010001423000X(0)=(0，0，8，16，12)T，z023000 b0032314000110001024-20002300023000 b00323(14000110001024-200023000 b20328310000110010-4000 Copyright©2013 2300023000 b20328310000110010(200023000 b2034421000010010000X(3)=(4，2，0，04)Tz3=14（最优解 Copyright©2013 练练习2.用单纯形法求解线性规划问

x4x1x2

5x

xx 4xx,x2,x3,x4解：原问题化

z

x1x2

5x

x

x Copyright©2013 练z3xz3x15x2x1x25x1246x347,x2,x73501000θb011101000510-0100500-1001σj=cj- Copyright©2013 θ–θ–σj=cj-X2入基3501000X6出3501000b011101000510-0100500-1001 Copyright©2013 3501000θb0-0111-05510-010–05001-0015σj=cj--0060-00-0201--9551-0011–1500-1001–σj=cj--0600-09-00--1531001-001-σj=cj--000---练3501000θb09-010--531001-001-σj=cj--000---最优解作业

最优值

Copyright©2013 练练习题 用单纯形法求 Copyright©2013 练最优解

最优值

Copyright©2013 练练习4.用单纯形法求解线性规划问max

2x1 5x26x2x x1

x2 x1,x2 Copyright©2013 练解 maxz=2x解 x1+x2 Copyright©2013 maxmax x1+x2 2、列初始单纯形表θbσj=cj- Copyright©2013 maxmax x1+ 21000bθ00510 06201 05110015σj=cj-21000X1σj=cj-21000 Copyright©2013 练2121000b020100511001σj=cj-005100

σj=cj-

Copyright©2013 练3、列新单纯形表 θ σj=cj- σj=cj-

- - -

3X2进基 X5出基 Copyright©2013 练2121000b00510024100 σj=cj-

- 005100241001010-σj=cj- Copyright©2013 21000θb005100241001010-σj=cj-0051002100-1010-σj=cj-0001-2100-1010-σj=cj- Copyright©2013 练4、列新单纯形表21000θb0001-2100-1010-σj=cj-000--解为：X=(7/2,3/2,15/2,0,0)T Copyright©2013 学习学习要点线性规划解的概念以及3个基本定熟练掌握单纯形法的解题思路及求解步 Copyright©2013 单纯形法的进一步讨论－人工人工变量法 Copyright©2013 单纯形法的进一步讨论－人工例1.10用大M法解下列线性规

3

2

x34x13x2x3xxxx

2

12x2x1

x1、x2、x3解：首先将数学模型化为标准形

系数矩阵中不存xx22x

j

立初始单纯形表 Copyright©2013 单纯形法的进一步讨论－人工故人为添加两个单位向量，得

人工变量单纯形法数学模型

2 xj j 其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 Copyright©2013 pygg单纯形法的进一步讨论－人工pygg332-00--b-4-31-010401-201005-12-1000113----3-50-0108-30010-12-1000—5-0-002100—0001-010—j5000020101231001-0010000--→→练最优解

,9,

最优值

Copyright©2013 单纯形法的进一步讨论－人工解的判别唯一最优解判别：最优表中所有非基变量的检验数非零则线性规划具有唯一最优解多重最优解判别：最优表中存在非基变量的检验数为零则线则性规划具有多重最优解（或无穷多最优解） 解的判别：存在某个基变量为零的基本可行解。（略 Copyright©2013 两阶段s. Copyright©2013s.两阶段 Copyright©2013 两阶段在第一阶段中，当人工变量取值为0时，目标函数 Copyright©2013 解题过程第1阶段：解辅助问题当进行到最优表时①若W=0,则得到原问题的一个基本可行解，转②若W>0,则判定原问题无可行解 Copyright©2013 例 maxZ=-x1x1+x2-x1+x2x2x1x2 maxZ=-x1x1+x2--x1

+x7 x1…x50,x6,x7增加人工变 Copyright©2013 minW=x6x1+x2- -x1+x2 +x7=1 x1…x70000011θb1211-0010211-10-001103010010030211000 Copyright©2013 0000011b1211-0010111-0-00030100100110-01-1100010-01-10-00102100110--01-002010-0-001--0000-1--0000011解为：X=(1/2,3/2,0,0,3/2,0,0)目标函数值为Wx可转入第二阶段。去除人工变量，以第一阶段最优解为基可行解 Copyright©2013 去除人工变量，以第一阶段的最优解为基可行解,求解原问题2000b20100010001000020121210101100001020002023110010001100111000解为：X=(0,3,1,2,0)T目标函数值为:maxZ=-x1+2x2单纯形法小单纯性法小结个数 右端项不等极大或极两个以约xj≤bibi<≤=≥求解形令xjx′jxj′≥0xj″令x=-同乘-z′Zmaxz′0- Copyright©2013 单纯形法计算步骤框单纯形法计算步骤框计算检验数是所有σi

最优对某一 有Pi否

无可行 无穷最优

0)

迭代运xk进

用xk替换min( iai,k0)

列出新的alx离l1

al1

1）对主元素行（第l行2)其他行bi＝bi－aibaia Copyright©2013 一般而言，一个经济、管理问题凡是满足以下条存在着多种方 Copyright©2013 线性规划在管理人力资源分配问例 某昼