线性规划的数学模型与基本性质

线性规划及单纯形法

1．线性规划介绍

2．线性规划数学模型

3．线性规划标准形式

4．线性规划的图解法

5．线性规划基本概念

6．单纯形法

7．应用举例1．线性规划介绍历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划理论的发展：1939年前苏联康托洛维奇（KOHTOPOBUZ）《生产组织与计划中的数学方法》提出“解乘数法”。1．线性规划介绍列奥尼德·康托罗维奇，前苏联人，由于在1939年创立了享誉全球的线形规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖。美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法“单纯形法”。被称为线性规划之父。1．线性规划介绍

线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。1．线性规划介绍1960年，“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖

佳林·库普曼斯，美国人，他将数理统计学成功运用于经济计量学，对资源最优分配理论做出了贡献。1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯．姆．李与杰斯开莱尼应用计算机处理目标规划问题。计算机50约束100变量

30000约束3000000变量1．线性规划介绍从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。1．线性规划介绍保罗-萨缪尔逊（PAULASAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里·列昂惕夫（WASSILYLEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETHJ.ARROW）,美国人，因与约翰-希克斯（JOHNR.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTONM.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。1．线性规划介绍线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高?某项任务确定后，如何安排人、财、物，使之最省?

例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大？项目III每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）212．线性规划数学模型例2捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费28004500600073002．线性规划数学模型目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。项目III每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）21例1用数学语言描述2．线性规划数学模型解：设变量xij表示捷运公司在第i(i＝1．…，4)个月初签订的租借期为j〔j＝1，…，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例2月份1234所需仓库面积15102012合同租借期限1个月2个月3个月4个月合同期内的租费28004500600073002．线性规划数学模型AB备用资源煤1230

劳动日3260

仓库0224

利润4050求：最大利润的生产计划。练习1生产计划问题2．线性规划数学模型maxZ=40x1+50x2解:设产品A,B产量分别为变量x1

，x2x1

+2x2

303x1+2x2

602x2

24x1，x2

0s.t.2．线性规划数学模型求：最低成本的原料混合方案？

原料ABＣ每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量练习2混合配料问题2．线性规划数学模型解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x4

4x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)s.t.2．线性规划数学模型决策变量：向量(x1…xn)T

决策人要考虑和控制的因素。非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…xn)线性式，求Z极大或极小线性规划模型特点2．线性规划数学模型如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定2．线性规划数学模型19max(min)Z=c1x1+c2x2+…+cnxnn个变量价值系数第i种资源的拥有量技术系数或工艺系数a11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2………am1x1+am2x2+…+amnxn(=,)bmxj0(j=1,…,n)s.t.线性规划的一般式2．线性规划数学模型线性规划的简写式2．线性规划数学模型线性规划的向量表示式2．线性规划数学模型线性规划的矩阵表示式2．线性规划数学模型比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。隐含的假设2．线性规划数学模型仓库\工厂123库存

121350222430334210

需求401535练习3运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？2．线性规划数学模型解：设xij为i

仓库运到j工厂的原棉数量(i

=1,2,3j=1,2,3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0st.2．线性规划数学模型练习4连续投资10万元A：从第1年到第4年每年初投资，次年末回收本利1.15；B：第3年初投资，到第5年末回收本利1.25，最大投资4万元；C：第2年初投资，到第5年末回收本利1.40，最大投资3万元；D：每年初投资，每年末回收本利1.11。求：使5年末总资本最大的投资方案。分析：

12345Ax1A

x2A

x3A

x4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D2．线性规划数学模型解：xik(i=1,2,…,5;k=A,B,C,D)为第i年初投资到第k个项目的资金数。MaxZ=1.15x4A+1.40x2C+1.25x3B+1.11x5Dx1A+x1D=10x2A+x2C+x2D=1.11x1Dx2C

3x3A+x3B+x3D=1.15x1A+

1.11x2Dx3B

4x4A+x4D=1.15x2A+

1.11x3Dx5D=1.15x3A+

1.11x4Dxik0s.t.2．线性规划数学模型线性规划问题应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)2．线性规划数学模型线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2．线性规划数学模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,≤0线性规划的标准形式目标函数：max约束条件 ：=变量符号 ：≥03．线性规划标准形式标准型的一般型minz=c1x1+c2x2+…+cnxn其中

bi

0(i=1,2,…,m)a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmxj0(j=1,2,…,n)s.t.3．线性规划标准形式P1P2………Pna11a12………a1n其中A=a21a22………

a2n

…am1am2………amnx1x=x2

xn…

b1b=b2

bm…C=(C1C2…Cn)标准型的矩阵型minZ=Ax=bx0b0

3．线性规划标准形式x1Ax=(P1P2…Pn)x2=b

xn

…P1x1+

P2x2+…+Pnxn=b标准型的向量型3．线性规划标准形式线性规划问题化标准型：(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3．线性规划标准形式(1)、约束条件x3为松弛变量x4为剩余变量

松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“”时：当约束条件为“”时：3．线性规划标准形式3．线性规划标准形式

x1+2x2+x3=30s.t.3x1+2x2+x4=60

2x2

+x5=24x1,

…,x50转化为：minZ=40x1+50x2+0-x3

+0·x4+0·x5

x1

+2x2

303x1+2x2

60s.t.2x2

24

x1，x2

0

例：minZ=40x1+50x2松弛变量3．线性规划标准形式例：

4x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)4x1+6x2+x3+2x4-x5

=12

x1+x2+7x3+5x4-x6=14

2x2+x3+3x4-x7=8

x1,

…,x70剩余变量(2)、变量3x1'-3x1"+2x28x1'

-x1"-4x2

14x1',x1",x201、x

0的情况，3x1+2x28x1-4x214x20令x1=x1'-x1"2、x取值无约束的情况。令x’＝-x。令x=x'-x"3x1'-3x1"+2x2+x3=8x1'

-x1"-4x2+x4=14x1',x1",x2,x3,x403．线性规划标准形式x1'

+x211x1'16x1',x20（3）、x两边有约束的情况。x1+x25-6x110x20-6+6x1+6

10+6

令x1'

=x1+6

0x1'

163．线性规划标准形式(3)、目标函数xo-ZZ令Z'

=-Z

3．线性规划标准形式(4)、右端常数右端项b＜0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。3．线性规划标准形式例3：将maxZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3无限制化为标准型3．线性规划标准形式解：①令x3=x4-

x5②加松弛变量x6③加剩余变量x7

④令Z'=-ZminZ'=x1-2x2+3x4-3x5x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,

x2,

x4,…,x70maxZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3无限制3．线性规划标准形式(1)minZ=2x1-x2+2x3练习5将下列线性规划问题化成标准型：-x1

+x2+x3

=

4-x1

+x2-x3

6x1

0

，x2

0,x3

无约束

s.t.(2)maxZ=2x1+x2+3x3+x4x1

+x2+x3+x3

72x1

-3x2+x3

=-8x1

-2x3+2x4

1x1,

x3

0,x2

0

，x4

无约束

s.t.3．线性规划标准形式(3)minZ=2x1+3x2+5x3x1

+x2-x3

-5

-6x1

+7x2-9x3

=15|19x1

-7x2+5x3|13x1,

x2

0,x3

无约束

s.t.(4)maxZ=x1-3x2-x1

+2x2-5

x1

+3x2=10x1,

x2

无约束

s.t.3．线性规划标准形式Ax=b(1)x

0(2)maxZ=(3)定义1：满足约束(1)、(2)的x=(x1…xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解线性规划的标准型4．线性规划的图解法图解法求解的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。

4．线性规划的图解法图解法的步骤：1、在平面上建立直角坐标系；2、图示约束条件，找出可行域；3、图示目标函数和寻找最优解。4．线性规划的图解法例4maxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x204．线性规划的图解法解：(1)、确定可行域

x10x1=0(纵)x20x2=0(横)

x1+2x230x1+2x2=30(0,15)(30,0)x20102030DABC3x1+2x2=60(0,30)(20,0)

2x2=24203010x14．线性规划的图解法(2)、求最优解最优解：x*=(15,7.5)Zmax=975Z=40x1+50x20=40x1+50x2(0,0)，(10,-8)x20102030203010x1DABCC点：x1+2x2=30

3x1+2x2=604．线性规划的图解法Z=40x1+80x2=0

x1+2x2=30DABCx20x1解:最优解：BC线段B点C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(01)例5、maxZ=40x1+80x2x1+2x2303x1+2x2602x224

x1,x204．线性规划的图解法4．线性规划的图解法X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5无界解无有限最优解例6、maxZ=2x1+4x2

2x1+x28-2x1+x22x1,x20Z=02x1+x2=8-2x1+x2=28246x240x14．线性规划的图解法例7、maxZ=3x1+2x2-x1-x21x1,x20无解无可行解-1x1-1x204．线性规划的图解法唯一解无穷多解无有限最优解无可行解有解无解当目标函数的直线族与某约束条件平行，且该问题有解时。约束条件无公共区域。有解但可行域可伸展到无穷时总结4．线性规划的图解法由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(2)、若线性规划可行域存在，则可行域是一个凸集。(3)、若有最优解，定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。4．线性规划的图解法minZ=Ax

=bx0Am×n满秩x

=(x1…xn)T

一、线性规划问题的解的概念5．线性规划基本概念定义1：基(基阵)——设A为约束方程组的m×n阶系数矩阵设(n>m)，其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。P1P2…Pm……Pna11a12…

a1m……a1nA=a21a22…

a2m……

a2n

……am1am2…

amm……amnB5．线性规划基本概念A=(P1…

PmPm+1…

Pn)=(BN)

基向量非基向量…x=(x1…

xmxm+1…

xn)T=(xBxN)T

基变量非基变量

xB

xN…B中的每一个列向量Pj称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。5．线性规划基本概念Ax=b的求解xBxN(BN)=bBxB+NxN=bBxB=b-NxNxB=B-1b-B-1NxNA=(BN)x=(xBxN)T若B为单位矩阵xB=b-NxN若xN＝0xB=B-1b5．线性规划基本概念定义2：可行解——满足方程约束条件的解x＝（x1，x2，…xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。定义3：最优解——使目标函数达到最大值的可行解，称为最优解。5．线性规划基本概念定义4：基本解——对应于基B，x=为Ax=b的一个解，则x为线性规划问题的基本解，也称基解。B-1b0定义5：基本可行解——基B，基本解x=若B-1b0，称基解为基本可行解，也称基可行解。B-1b0※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!定义6：可行基——对应于基可行解的基称为可行基。5．线性规划基本概念例8x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50121003201002001P1P2P3P4P5A=5．线性规划基本概念x1x2x3x4x5x=b=306024B=(P3P4P5)=I

是满秩子矩阵

非基N=(P1P2)x3=30-(x1+2x2)x4=60-(3x1+2x2)x5=24-2x25．线性规划基本概念令x1=

x2=0,x3=30,x4=60,x5=24x===xN0xBB-1b003060245．线性规划基本概念例9：给定约束条件

-x3+x4=0x2+x3+x4=3-x1+x2+x3+x4=2xj0(j=1,2,3,4)求出基变量是x1,x3,x4的基本解，是不是可行解？5．线性规划基本概念

0-11解：B=(P1P3P4)=011-111

01-10B-1=-1/21/2031/21/202b=5．线性规划基本概念x1

x3=B-1b

x4

xB=

01-101

=-1/21/203=3/2

1/21/2023/2∴x=(1,0,3/2,3/2)T是5．线性规划基本概念凸集——D是n维空间的一个集合，x(1),

x(2)∈D,若对任何x(1),

x(2)，有x=x(1)+(1-)x(2)∈D(01)，则D为凸集。定义1：凸集——如果集合D中任意两个点，其连线上的所有点也都是集合D中的点，则称D为凸集。二、凸集及其顶点5．线性规划基本概念x(1)x(2)凸多边形凹多边形x(1)x(2)5．线性规划基本概念第一章

x(1),x(2),…,x(k)

是n维欧氏空间中的k个点，若有一组数

µ1,µ2,…,µk

满足

0µi1(i=1,…,k)定义2µ

i=1ki=1有点x=µ1x(1)

+…+µkx(k)则称点x为x(1),x(2),…,x(k)

的凸组合。凸组合5．线性规划基本概念

凸集D,点xD，若找不到两个不同的点x(1),x(2)D使得

x=x(1)

+(1-)x(2)

(0<<1)

则称x为D的顶点。定义3顶点5．线性规划基本概念证明：设LP问题的可行解域为集合CC={x|Ax=bx0}任取x(1),x(2)C,则

x=x(1)

+(1-)x(2)

0

(0

1)又因为Ax(1)

=b，Ax(2)

=b所以Ax=A[x(1)

+(1-)x(2)

]=b

+(1-)b=b

则

xC，C为凸集定理1：LP问题的可行解域一定是凸集。三、几个基本定理的证明5．线性规划基本概念只须证明：

D的k个顶点x(1),…,x(k)

，有

预理1D为有界凸多面集，xD，x必可表为D的顶点的凸组合。0µi1，使x=µ1x(1)

+…+µkx(k)µ

i=1ki=15．线性规划基本概念证明可用归纳法（略）x(1)x(2)x(3)x’xx’在边界上x在内部x(1)(1-)x(2)(1-)x(3)x=++x＝x’

+(1-)x(2)

(0

1)x’＝x(1)

+(1-)x(3)

(0

1)5．线性规划基本概念证明：设x(1),…,x(k)

为可行域顶点，若x*不是顶点，但

maxZ=Cx*

定理2：可行域有界，最优值必可在顶点得到Cx*=µ

iC

x(i)ki=1µ

iCx(m)ki=1=Cx(m)[设Cx(m)＝Max(C

x(i))]1ikµ

ix(i)ki=1µ

i=1ki=10µi1x*=5．线性规划基本概念引理2：LP问