第二章线性规划

1第二章线性规划

线性规划内容框架2第二章线性规划的数学模型线性规划LinearProgramming

LP规划论中的静态规划在有限资源的条件下，合理分配和利用资源，以期取得最佳效益的优化方法。求解方法：图解法单纯形解法

3第一部分

线性规划的数学模型第二章线性规划

第一节线性规划一般模型第二节线性规划的图解法第三节线性规划的标准型第四节线性规划解的概念第二部分

线性规划的单纯形法Homework4现有三个仓库（A,B,C）的产品运往四个纺织厂。运费情况如下：

问应当怎样调运使运费最省？5一、线性规划问题的三要素

决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。有的目标要实现极大，有的则要求极小。目标函数是决策变量的线性函数。第一节线性规划一般模型6二、线性规划的定义第一节线性规划一般模型对于求取一组变量xj

(j=1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极值（极大值或极小值）的一类最优化问题称为线性规划问题，简称线性规划。7

某饮料公司在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。

销地产地B1B2B3B4产量A1A2A3632575843297523销量2314第一节线性规划一般模型例1.运输问题二、线性规划模型的构建8(1)决策变量。

决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件。产量之和等于销量之和,故要满足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4供应平衡条件非负性约束xij≥0(i=1,2,3；j=1,2,3,4)

第一节线性规划一般模型9minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

综上所述，该问题的数学模型表示为

x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij≥0(i=1,2,3；j=1,2,3,4)

s.t.第一节线性规划一般模型subjectto10某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120例2.生产计划问题第一节线性规划一般模型11问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg；B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：劳动力约束9X1+4X2≤360

设备约束4X1+5X2

≤200

原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥0第一节线性规划一般模型补例.教材P1712用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式为：四、线性规划的一般模型

max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(≥,＝)b1a21x1+a22x2+…+a2nxn≤(≥,＝)b2……………am1x1+am2x2+…+amnxn≤(≥,＝)bmx1,x2,…,xn≥(≤)0第一节线性规划一般模型13用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，而维数再高以后就不能图示了。一、图解法的基本步骤第二节LP问题的图解法可行域的确定可行解最优解141.可行域的确定例3的数学模型为

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D五边形OABCD内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。第二节LP问题的图解法152.最优解的确定Z=30Z=42Z=15目标函数Z=

3x1+5x2代表以Z为参数的一族平行线。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优(极大或极小)的解第二节LP问题的图解法?16由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。目标函数最优值（如果存在）一定在可行域的边界达到，而不可能在其内部。二、说明第二节LP问题的图解法17例: 求解下列线性规划问题

MaxZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20第二节LP问题的图解法18X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X2

0X1

019第二节LP问题的图解法唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个相邻顶点同时得到最优解，则它们连线上的每一点都是最优解。无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）。无可行解：若约束条件相互矛盾，则可行域为空集。二、解的可能性20X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20唯一的最优解X1

0X2

021X1X1=1X1=6X2=4X2X1+2X2=10ABCDE

MAXZ=2X1+4X2

S.T.X1+2X210X16X24X11X1,X202X1+4X2=Ω存在无穷多解MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X1

0X2

022X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X20X16X24X11X1,X20可行域无界MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X1

0X2

023X1X1=1X2X1+2X2=104X1-3X2=0MAXZ=4X1-3X2

S.T.X1+2X2

10X11X1,X20MAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20可行域无界X1

0X2

024线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；约束条件有“≤”、“≥”和“＝”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0，决策变量非负。一、标准型第三节线性规划的标准型25第三节线性规划的标准型26minZ=X1+3X2S.T.6X1+7X28-X1+3X2-6X1-X2=3X10不符合线性规划的标准形式目标函数“极小值”约束方程右端存在负数约束方程还不是等式约束

存在自由变量X2第三节线性规划的标准型271.代数式二、标准型的表达方式（代数式、矩阵式）maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)简记第三节线性规划的标准型282.矩阵式

第三节线性规划的标准型29目标函数极小化问题

minZ=CX，只需将等式两端乘以-1即变为极大化问题。因为minZ=-max(-Z)=CX，令Z′=-Z，则maxZ′=-CX右端常数项非正两端同乘以-1约束条件为不等式当约束方程为“≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“≥”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。

决策变量xk没有非负性要求令xk=xk′-xk〃，xk′≥0，xk〃≥0，用xk′-xk〃

取代模型中xk三、非标准型向标准型转化

第三节线性规划的标准型30目标函数标准化示意图&目标函数极小化/右端常数项非正

——两边同乘-1&约束条件是≤类型

——左边加非负松弛变量

&约束条件是≥类型

——左边减非负剩余变量

&变量符号不限

——引入新变量

转化规则简要：第三节线性规划的标准型31例3minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2+x3≥-2x1≥0,x3≤0S.t.第三节线性规划的标准型Step-1minZ=

x1+2x2+3x3′x1+2x2+x3′≤52x1+3x2+x3′≥6

-x1-x2-x3′≥-2x1≥0,x3′≥0

S.t.32Step-2minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)

+x3′≥6

-x1-(x2′-x2〃)

-x3′≥-2x1,

x2′,x2〃

,x3′≥0

Step-3minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃

)

+x3

′≤2x1,

x2′,x2〃,x3′≥0第三节线性规划的标准型S.t.S.t.33Step-4minZ=

x1+2(x2′-x2〃)

+3x3′

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4≥0Step-5minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=5

2x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4,x5≥0第三节线性规划的标准型S.t.S.t.34Step-6minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2

x1,

x2′,x2〃,x3′,x4,x5,x6

≥0Step-7maxZ=-x1-2(x2′-x2〃)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

第三节线性规划的标准型S.t.S.t.35例4maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.第三节线性规划的标准型x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+0x4+0x5

S.t.标准型作业：

1、教材后作业9（建立数学模型）2、教材后作业1（化标准型）3、教材后作业2的①（图解法）37第四节LP问题的基本性质一．LP解的基本概念可行解：满足约束条件AX=b,X≥0的解。最优解：使目标函数最优的可行解，称为最优解。基n元线性约束方程组，m个方程线性无关；即矩阵A的秩R(A)=m；根据线性代数定理可知，n＞m，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。?秩的定义n元线性方程组Ax=b解的讨论X1X1=1X1=6X2=4X2X1+2X2=10ABCDEMAXZ=4X1-3X2

S.T.X1+2X210X16X24X11X1,X20X2

0X1

0可行域可行解39线性方程组的增广矩阵例1的标准型

maxZ=

3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5单位矩阵第四节LP问题的基本性质40基（基矩阵）：系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。或称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,…,m)。的基矩阵B最多C53=10，如下：x3x4x5x1x4x5x2x4x5x3x1x5x3x2x5x3x4x1x3x4x2x1x2x5x