运筹学-1-线性规划1

1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题的求解方法线性规划问题的求解方法图解法图解法单纯形法单纯形法单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用线性规划研究的主要问题线性规划研究的主要问题：线性约束条件下的线性函数极致问题线性约束条件下的线性函数极致问题在一定的人力、财力、资源条件下，如何合理安排使用，使效益最高? 某项任务确定后，如何安排人力、财力、物力，使之花费最省?线性规划介绍线性规划介绍历史悠久，理论成熟，应用广泛历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规

2、划、整运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规数规划、目标规划和多目标规划都是以线性规划为基础的。划为基础的。解决稀缺资源最优分配的有效方法，使付出解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。的费用最小或获得的收益最大。线性规划线性规划问题问题的的发展发展1939年，前苏联数学家康托洛维奇用线性模型研究提年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题高组织和生产效率问题1947年，年，Dantzig提出求解线性规划的提出求解线性规划的单纯形法单纯形法1950-1956年，主要研究线性规划的年，主要研究线性规划的对偶理论

3、对偶理论1958年，发表整数规划的年，发表整数规划的割平面法割平面法1960年，年，Dantzig和和Wolfe研究成功分解算法，奠定了研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。大规模线性规划问题理论和算法的基础。1963年年Dantzing写成写成“Linear Programming and Extension”1979年，苏联的年，苏联的Khachiyan提出提出“椭球法椭球法” ，1984年，年，印度的印度的Karmarkaa提出提出“投影梯度法投影梯度法”研究成功线性研究成功线性规划的多项式算法。规划的多项式算法。 线性规划是研究线性不等式组的理论，或者说是研线性规

4、划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应究（高维空间中）凸多面体的理论，是线性代数的应用和发展。用和发展。一、线性规划问题及其数学模型线性规划问题及其数学模型1、问题的提出、问题的提出 设设 备备产产 品品 A B C D单件利润单件利润（元）（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 台台 数数 12 8 16 12 例例1 某工厂用某工厂用A,B,C,D四种设备生产四种设备生产I,II两种产品，两种产品，已知生产单位产品所需各种设备的数量、在计划期内已知生产单位产品所需各种设备的数量、在计划期内各种设备的拥有量以及每单位产品各种设

5、备的拥有量以及每单位产品I,II的利润见下表的利润见下表所示，问应如何安排生产才能使总利润最大？所示，问应如何安排生产才能使总利润最大？建立该问题的数学模型建立该问题的数学模型解解(1)(1)决策变量决策变量: :设生产产品设生产产品I x1个单位，产品个单位，产品II x2个个单位；单位； (2)(2)目标目标：总利润最大，于是记成：总利润最大，于是记成max z=2x1+3x2, z , z 称为目标函数；称为目标函数； (3)(3)限制条件限制条件 ( (约束条件约束条件) )a:a:各种设备的数量有限，无论如何安排生产，各种设备的数量有限，无论如何安排生产，x1,x2均应满足如下条件：

6、均应满足如下条件：121212221228416412xxxxxx b:产量产量x1,x2不能为负，即不能为负，即1200 x,x数学模型数学模型121212122212284164120 xxxxxs.t.xx ,x 1223maxzxx即线性规划模型。即线性规划模型。目标函数目标函数约束条件约束条件例例2 某昼夜服务的公交线路每天各时间区段内所需司某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：机和乘务人员数如下：班次班次 时间时间 所需人数所需人数 1 6:00-10:00 601 6:00-10:00 60 2 10:00-14:00 70 2 10:00-14:00 7

7、0 3 14:00-18:00 60 3 14:00-18:00 60 4 18:00-22:00 20 4 18:00-22:00 20 5 22:00-2:00 20 5 22:00-2:00 20 6 2:00-6:00 30 6 2:00-6:00 30 设司乘人员在各时间段一开始时上班，并连续设司乘人员在各时间段一开始时上班，并连续工作工作8 8小时，问该公司线路至少应配备多少司乘人小时，问该公司线路至少应配备多少司乘人员。列出该问题的数学模型员。列出该问题的数学模型设设x1,x2,x6为各班新上班人数，考虑到在每个时间为各班新上班人数，考虑到在每个时间段工作的人数既包括该时间段新上

8、班的人又包括上一段工作的人数既包括该时间段新上班的人又包括上一个时间段上班的人员，按所需人员最少的要求可列出个时间段上班的人员，按所需人员最少的要求可列出本例的数学模型：本例的数学模型：目标函数：目标函数：约束条件：约束条件：1612233445561266070602020300 xxxxxxxxxxxxx ,x ,.,x 123456minzxxxxxx上面两优化模型，都具有下述特征：上面两优化模型，都具有下述特征：(1)(1)每个问题都用一组未知量每个问题都用一组未知量x1,x2,.,xn表示所求方案，表示所求方案，通常这些变量都是非负的，称为通常这些变量都是非负的，称为决策变量决策变量

9、。(2)(2)都存在一组都存在一组约束条件约束条件，这些约束条件都可以用一，这些约束条件都可以用一组组线性线性等式或不等式表示。等式或不等式表示。(3)(3)都有一个要实现的目标，并且这个目标可表示为都有一个要实现的目标，并且这个目标可表示为一组决策变量的一组决策变量的线性线性函数称为函数称为目标函数目标函数。目标函数。目标函数可以是求最大也可以是求最小。可以是求最大也可以是求最小。具有上述特征的数学模型就称为具有上述特征的数学模型就称为线性规划模型线性规划模型。比例性：决策变量变化引起目标的改变量与决比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；策变量改变量成正比；可加性：每个

10、决策变量对目标和约束的影响独可加性：每个决策变量对目标和约束的影响独立于其它变量；立于其它变量；连续性：每个决策变量取连续值；连续性：每个决策变量取连续值；确定性：线性规划中的参数确定性：线性规划中的参数ai , bi , ci为确定值。为确定值。线性规划数学模型中隐含的假设线性规划数学模型中隐含的假设线性规划问题应用线性规划问题应用 市场营销市场营销(广告预算和媒介选择，竞争性定价，新产品广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划开发，制定销售计划) 生产计划制定生产计划制定(合理下料，配料，合理下料，配料，“生产计划、库存、生产计划、库存、劳力综合劳力综合”) 库存管理库存管

11、理(合理物资库存量，停车场大小，设备容量合理物资库存量，停车场大小，设备容量) 运输问题运输问题 财政、会计财政、会计(预算，贷款，成本分析，投资，证券管理预算，贷款，成本分析，投资，证券管理) 人事人事(人员分配，人才评价，工资和奖金的确定人员分配，人才评价，工资和奖金的确定) 设备管理设备管理(维修计划，设备更新维修计划，设备更新) 城市管理城市管理(供水，污水管理，服务系统设计、运用供水，污水管理，服务系统设计、运用)线性规划数学模型线性规划数学模型线性规划的适用情况线性规划的适用情况要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择

12、对于要实现的目标有多种方案可选择有影响决策的若干约束条件有影响决策的若干约束条件目标函数：目标函数：约束条件：约束条件：2 2、线性规划数学模型的形式、线性规划数学模型的形式c1,c2,cn称为称为价值系数价值系数，b1,b2,bm称为称为资源系数或右端资源系数或右端项常数项常数, ,aij称为称为技术系数或约束系数技术系数或约束系数一般形式一般形式nnxcxcxcZ .max(min)2211 021221111212111nmnmnmmnnxxxbxaxaxabxaxaxats,.,),(.),(.紧缩形式紧缩形式目标函数：目标函数：约束条件：约束条件：向向 量量 形形 式：式： njjj

13、xcZ1max(min) ),.,(),.,(),(njxmibxajinjjij210211CXZ max(min) 01Xbxptsnjjj),(.),.,(ncccC21 nxxX1 mjjjaap1 mbbb1矩阵形式：矩阵形式：CXZ max(min) 0XbAXts),(. mnmnaaaaA1111),.,(ncccC21 nxxX1 mbbb1一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、空间直角坐标三个变量、空间直角坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式二、线性规

14、划问题的求解方法二、线性规划问题的求解方法例例1、 0,0124 16 482122232max2121212121xxxxxxxxxxZ(一一)图图 解解 法法步骤：步骤：(1)建立平面直角坐标系；建立平面直角坐标系； (2)画出可行域画出可行域; (3)作目标函数等值线；作目标函数等值线； (4)寻找最优解寻找最优解.01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解：解：x1 = 4 x2 = 2有唯一最优解，有唯一最优解，Z = 14Z = 14x2 x1(4 2) 00124 16 4821222322121212121xxxxxxxxxxZ,max

15、可行域可行域最优解最优解目标函数等值线目标函数等值线x2=-2/3x1+z/3 例例2、 例例3、 0,02 1223622max212212121xxxxxxxxxZ无穷多最优解无穷多最优解121212122210 m ax Zxxxxxxx , x 无有限最无有限最优解优解x1x1x2 x2 12121212min321236,0 Zxxxxxxxx x1x2 无可行解无可行解例例5、 例例4、121212122210 m in Zxxxxxxx , x 唯一解唯一解x1x2 线性规划问题的解的情况：线性规划问题的解的情况：n有可行解有可行解 有唯一最优解有唯一最优解 有无穷多个最优解有无

16、穷多个最优解 无有限最优解无有限最优解n无可行解无可行解图解法的启示图解法的启示(1)(1)具有两个变量的线性规划问题的可行域是凸多边具有两个变量的线性规划问题的可行域是凸多边形。形。(2)(2)若线性规划存在最优解，它一定在可行域的某个若线性规划存在最优解，它一定在可行域的某个顶点顶点得到。得到。 虽然图解法只能求解包含虽然图解法只能求解包含2 2个或个或3 3个变量的问题，个变量的问题，作为算法，没有太大价值，但是上述结论却非常有意作为算法，没有太大价值，但是上述结论却非常有意义。它将搜索最优解的范围从可行域的无穷多个点缩义。它将搜索最优解的范围从可行域的无穷多个点缩小到有限几个顶点。从而

17、开启了人们的思路。而后面小到有限几个顶点。从而开启了人们的思路。而后面我们要介绍的求解多维线性规划的单纯形法就是在此我们要介绍的求解多维线性规划的单纯形法就是在此结论的基础上推广得到的。结论的基础上推广得到的。( (二二) )线性规划模型的标准形式线性规划模型的标准形式1 1、标准形式、标准形式1maxnjjjZc x 1(1,2,.,)0(1,2,., )nijjijja xb imxjn 2 2、特征：、特征： (1)(1)目标函数为求极大值；目标函数为求极大值； (2)(2)所有约束条件（非负条件除外）都是等式所有约束条件（非负条件除外）都是等式; ; (3) (3)右端常数项均为非负右

18、端常数项均为非负; ; (4) (4)所有决策变量均为非负。所有决策变量均为非负。1maxnjjjZc x 1(1,2,.,)0(1,2,., )nijjijja xb imxjn 1maxnjjjZc x 1(1,2,.,)0(1,2,., )nijjijja xb imxjn 矩阵形式：矩阵形式：maxZCX . .0AXbs tX mnmnaaaaA1111),.,(ncccC21 nxxX1 mbbb1向向 量量 形形 式：式：maxZCX 1. .0njjjp xbs tX ),.,(ncccC21 nxxX1 mjjjaap1 mbbb13、转换方式：、转换方式： (1) (1)

19、目标函数的转换目标函数的转换min,jjZc x 若若求求极极小小值值即即则则可可将将目目标标函函数数乘乘以以(-1)(-1).转转化化为为求求极极大大值值问问题题 jjxcZZmax即即,.ZZ 也也就就是是令令可可得得到到上上式式(2)0,ib 若若约约束束条条件件右右边边的的某某一一常常数数项项. 1 乘上乘上相对应的约束方程两边相对应的约束方程两边这时只要在这时只要在ib(3)(3)约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为称为松弛变量松弛变量称为称为剩余变量剩余变量 ijijbxa,ijjn iia xxb 0n ix ijjia xb ,ijjn

20、iia xxb 0n ix (4)(4)变量的变换变量的变换0 jjjjjjxxxxxx,其中其中可令可令量量若存在取值无约束的变若存在取值无约束的变若存在取非正值的变量若存在取非正值的变量xj,可令可令xj=-xj,其中其中xj 0.例例 1、将下列线性规划问题化为标准形式、将下列线性规划问题化为标准形式32132xxxZ min )(,.无非负限制无非负限制为无约束为无约束32132132132105232475xxxxxxxxxxxxts,:054354 xxxxx且且替换替换用用解解),( 13 个个约约束束方方程程两两边边乘乘以以将将第第变变为为求求极极大大值值将将极极小小值值问问题

21、题反反号号 ,67,xx引引入入变变量量:标准形式如下标准形式如下1245max23()Zxxxx 1245612457124512456757442. .3225,0 xxxxxxxxxxs txxxxx xxxxx 32132xxxZ min )(,.无非负限制无非负限制为无约束为无约束32132132132105232475xxxxxxxxxxxxts例例2、将线性规划问题化为标准型、将线性规划问题化为标准型解：解：212xxZ max 无约束无约束212121043583xxxxxxts,.134max2()Zxxx 13451346134563885. .334,0,xxxxs tx

22、xxxx xxxx 212xxZ max 无约束无约束212121043583xxxxxxts,.134max2()Zxxx 13451346134563885. .334,0,xxxxs txxxxx xxxx 1 1、解的概念、解的概念 可行解可行解：满足约束条件：满足约束条件(2)(2)、(3)(3)的解为可行解。的解为可行解。所有可行解的集合称为所有可行解的集合称为可行域可行域。 最优解最优解：使目标函数：使目标函数(1)(1)达到最大值的可行解。达到最大值的可行解。(三三)线性规划问题的解线性规划问题的解 1101nijjijja xb i,.,ms.t.xj,.,n (1)(2)(

23、3) mmnmmpppaaaaB,.,211111 1njjjmaxzc x (1,2,.,).jpjm则为基向量称.jjpx与基向量对应的变为基变量量非非基基变变量量除除基基变变量量以以外外的的变变量量为为(3):(2),()Am nn m B设 为约束方程组 的阶系数矩设基阵是(0),AmmBB 矩矩阵阵 中中的的阶阶非非奇奇异异子子矩矩阵阵则则 是是线线性性规规划划问问题题.的一个基的一个基 不妨设不妨设121212122212284164120 xxxxxs.t.xx ,x 1223maxzxx 123456221000120100,400010040001Ap ppppp 12312

24、4152622122841641201 26jxxxxxxs.t.xxxxxj, ,., 1223maxzxx 345610000100,00100001Bpppp基基基向量，基向量，均为均为6543pppp,3456,xxxx 为为基基变变量量 基可行解：满足变量非负约束条件基可行解：满足变量非负约束条件(3)(3)的基解。的基解。 可行基：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。(4):(2),(2)基基解解 在在约约束束方方程程组组中中 令令所所有有非非基基变变量量为为零零 由由解解出出称为称为的值的值取取将这个解加上非基变量将这个解加上非基变量个基变量的唯一

25、解个基变量的唯一解,0m.个个基基解解的的个个数数不不超超过过线线性性规规划划问问题题的的基基解解mnC 123124152622122841641201 26jxxxxxxs.t.xxxxxj, ,., 解方程组得解方程组得令令,0021 xx12168126543 xxxx,.),()(为基解为基解则则1216812001 X(1)(0,0,12,8,16,12)0.X由由于于故故为为基基可可行行解解.),(为可行基为可行基则则6543ppppB 基与解的对应关系：基与解的对应关系： 非可行解非可行解可可行行 基基解解 可行解可行解 基解基解解与解之间解与解之间的关系为：的关系为：基解基解

26、基基可行基可行基基可行解基可行解最优基最优基基最优解基最优解例例1 求出下面线性规划的所有基解，并指出哪些是基可行解。求出下面线性规划的所有基解，并指出哪些是基可行解。121212122351562240maxzxxxxxxx ,x 1212312412342351562240maxzxxxxxxxxx ,x ,x ,x 35106201A 化为标准型：化为标准型：1524b 秩秩A=2, 1123562BP ,P取取得基可行解得基可行解15 30 044X, , 213BP ,P 取取得基可行解得基可行解 4 0 3 0X, , , 314BP ,P 取取得基解得基解 5 0 06X, ,

27、, 423BP ,P 取取得基解得基解 0 1245 0X, 524BP ,P 取取得基可行解得基可行解 0 3 0 18X, , , 634BP ,P 取取得基可行解得基可行解 0 0 15 24X, , 需待解决的理论问题需待解决的理论问题 什么条件下什么条件下LP的可行域非空？可行域的可行域非空？可行域D有何特性？有何特性？ 可行域可行域D是否有顶点？顶点有多少个？顶点的数学是否有顶点？顶点有多少个？顶点的数学含义？含义？ 是否一定能保证最优解在顶点（是否一定能保证最优解在顶点（D内）上达到？内）上达到？ 顶点是什么概念？顶点是什么概念？ 基本可行解是否存在？如何判断？基本可行解是否存在

28、？如何判断？ 基本可行解是否唯一对应基本可行解是否唯一对应D的一个顶点？的一个顶点？ 如何求基本可行解？如何求基本可行解？ 凸集凸集：设：设K K是是n n维欧氏空间的一个点集，若任意两点维欧氏空间的一个点集，若任意两点 12XK,XK 12101XXxK 1011 21kiii,i, ,.,k, 的连线上的一切点的连线上的一切点则称则称K K为凸集。为凸集。 凸集的特征是：连接集合中任意两点的线段也在集凸集的特征是：连接集合中任意两点的线段也在集合之中。合之中。 凸组合凸组合：设：设X(1),X(2),X(k)是是n n维欧氏空间的维欧氏空间的K K个点，个点，若存在满足若存在满足则称则称

29、1212kkxXX.X 为为X(1),X(2),X(k)的凸组合。的凸组合。2.线性规划问题解的几何意义线性规划问题解的几何意义顶点顶点：设：设K K是凸集是凸集, ,定理定理3.13.1线性规划问题的可行域线性规划问题的可行域D=x|Ax=b,x0是一是一个凸集。个凸集。XK 12XK,XK 1212XD,XD,XX且且, ,若若X不能表示成任何不能表示成任何两点连线的内点两点连线的内点，则称，则称X为为K的一个顶点的一个顶点( (或极点或极点) )关于线性规划问题解的性质，介绍以下几个定理：关于线性规划问题解的性质，介绍以下几个定理：证明：设证明：设 112200AXb,X;AXb,X,

30、则则 121xXX 令令 1210AxAXAXb,x 则则且且xD因此，根据凸集的定义，因此，根据凸集的定义，D D为凸集。为凸集。定理定理3.2 X3.2 X是可行域是可行域D=x|Ax=b,x0D=x|Ax=b,x0的顶点的充的顶点的充要条件是：要条件是：X X是该线性规划问题的基可行解。是该线性规划问题的基可行解。证明：必要性证明：必要性 设设X X是是D D的顶点。若的顶点。若X X不是基可行解，不是基可行解，不妨设不妨设1210000kknx,x,.,x,x.x 12k,., 10kjjjP 由引理由引理1 1知知P1,P2,Pk必线性相关，于是存在不全为必线性相关，于是存在不全为0

31、 0的一组数的一组数满足满足 01 2jjjxmin, j, ,.,k 令令0 显显然然 1112200TkkXx,x,.,x, ,., 取取 2112200TkkXx,x,.,x, ,.,易于验证易于验证 1212121122XD,XD,XXXXX且且且且 1210000kknx,x,.,x,x.xkm 12120 1XD,XD,XX,且且及及，有有此与此与X X是是D D的顶点矛盾，因而的顶点矛盾，因而X X是基可行解。是基可行解。充分性：设充分性：设X X是问题的基可行解，不妨设是问题的基可行解，不妨设于是于是P1,P2,Pk必线性无关。若必线性无关。若X X不是不是D D的顶点，则存在

32、的顶点，则存在 121XXX 于是，对于是，对j=k+1,k+2,n,有有 1201jjjxxx 因此，对于因此，对于j=k+1,k+2,n,应有应有 120jjxx 1210kjjjjPxx 并并有有故故P1,P2,Pk必线性相关，这与已知矛盾必线性相关，这与已知矛盾.因此，因此，X必为顶点必为顶点.(1)(2)XX 由由于于 12kx,x,.,x 0 x再再设设是是可可行行定理定理3.33.3若可行域非空有界，则线性规划问题一定可以若可行域非空有界，则线性规划问题一定可以在可行域的某个顶点上找到最优解。在可行域的某个顶点上找到最优解。证明：不妨设可行域的顶点为证明：不妨设可行域的顶点为域域

33、D D的任意一点。由引理的任意一点。由引理2,2,有有 011011kkiiiiiixx, 0111kkiiimiii,.,kiicxcxcxmax cxcx 因因此此，设设 011kkimmiiiicxcxcxcx则则有有，由由x(0)的任意性，知线性规划在顶点的任意性，知线性规划在顶点x(m）处达到最优。处达到最优。说明说明1 1：说明说明2 2：重要结论重要结论线性规划问题的可行域是凸集；凸集的每个顶点对应线性规划问题的可行域是凸集；凸集的每个顶点对应一个基可行解，基可行解个数是有限的，当然凸集的一个基可行解，基可行解个数是有限的，当然凸集的顶点也是有限的；若线性规划有最优解，必在可行域

34、顶点也是有限的；若线性规划有最优解，必在可行域某顶点上达到，亦即在有限个基可行解中存在最优解。某顶点上达到，亦即在有限个基可行解中存在最优解。因此，可以在有限个基可行解中去找最优解。这就是因此，可以在有限个基可行解中去找最优解。这就是下节将介绍的单纯形法的理论依据，该方法是一种在下节将介绍的单纯形法的理论依据，该方法是一种在基可行解中搜索最优解的算法。基可行解中搜索最优解的算法。单纯形法的单纯形法的基本思想基本思想是：首先从可行域的一个基可行解是：首先从可行域的一个基可行解( (一个顶点一个顶点) )出发，然后判断它是否为最优解，若是则停出发，然后判断它是否为最优解，若是则停止计算止计算; ;

35、否则就找一个更好的基可行解，再进行检验否则就找一个更好的基可行解，再进行检验, ,如如此反复经过有限次迭代此反复经过有限次迭代, ,直至找到最优解直至找到最优解, ,或者判定它无或者判定它无界界( (即无有限最优解即无有限最优解) )为止。为止。(四四)单纯形法单纯形法找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个使目标函数转移到另一个使目标函数更优的基可行解更优的基可行解最优解最优解是是否否循循环环结束结束例例1求解下列线性规划问题求解下列线性规划问题 0,124 16 482122232max2121212121xxxxxxxxxxZ变成标准型变成标准型 0, 12 4

36、16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ约束方程组的系数矩阵约束方程组的系数矩阵6543 xxxx,21xx ,为基变量为基变量为非基变量为非基变量 345610000100,00100001BP P P P 123456221000120100,400010040001AP P P P P P将基变量用非基变量表示将基变量用非基变量表示3124125162122282164124- -xxxxxxxxxx 目标函数变为：目标函数变为：1223zxx令：令：120 xx则：则： 基本可行解为基本可行

37、解为X(0)=（0, 0, 12, 8, 16, 12）此时，此时，Z = 0，它表明该厂未安排产品，它表明该厂未安排产品I,II的生产，资源未被利用，的生产，资源未被利用，故利润为故利润为0.0.（2）（1）3456x12 x8 x16 x12120 xx3456x12 x8 x16 x12从目标函数从目标函数(2)可见，可见，x1,x2的系数均为正，故若使这两个非基变量的系数均为正，故若使这两个非基变量中的一个变成基变量，均可能使目标函数值增加，为使变换后目中的一个变成基变量，均可能使目标函数值增加，为使变换后目标函数值增加的幅度最大，标函数值增加的幅度最大，选正系数最大的那个非基变量选正

38、系数最大的那个非基变量x2进基。进基。(进基原则进基原则)确定出基变量的确定出基变量的原则原则是是使得到的基解满足非负约束条件使得到的基解满足非负约束条件。于是有。于是有324256212208 201601240- -xxxxxxx :(),经经济济意意义义 安安排排生生产产产产品品I I 或或IIII 都都可可以以使使工工厂厂的的利利润润指指标标.增增加加为为使使上上不不等等式式成成立立, ,只只有有选选择择212 812min, ,3224x266263,0,xxxxx当当时时即即 由由基基变变量量变变成成了了非非基基变变量量. .即即用用替替换换.换换基基ABCDII经经济济意意义义:

39、 :若若将将四四种种设设备备全全部部用用于于生生产产产产品品, ,于于是是可可得得22212812,224xxx6,4,3.II即即生生产产产产品品分分别别为为 件件件件 无无穷穷多多件件件件现现在在考考虑虑必必须须同同时时兼兼顾顾四四种种设设备备一一起起用用于于生生产产产产品品II,II,因因此此最最多多只只能能生生产产产产品品II3II3件件. .否否则则设设备备D D就就不不够够用用了了. .,因因此此出出基基变变量量的的选选择择式式体体现现了了兼兼顾顾各各种种限限制制条条件件的的思思想想又又称称为为最最小小比比值值法法则则. .26xx将将方方程程组组中中和和 的的位位置置对对换换.

40、.为为此此, ,只只要要将将原原约约束束方方程程组组2x的的增增广广矩矩阵阵进进行行初初等等行行变变换换, ,使使新新的的基基变变量量 的的系系数数列列向向量量6,x变变为为原原基基变变量量所所对对应应的的系系数数列列向向量量 即即将将220200041P 初初等等行行变变换换221000121201008400010160400011212010062110010224000101610100034 变变换换后后的的增增广广矩矩阵阵所所表表示示的的方方程程组组是是13614615261262122416134xxxxxxxxxx162345,x xxxxx用用非非基基变变量量表表示示基基变变

41、量量得得31641651261622122164134xxxxxxxxxx163924Zxx目目标标函函数数变变为为当当x1=x6=0时，时，z=9,X(1)=(0,3,6,2,16,0)146263465461221341222842xxxxxxxxxxx 由于由于(4)中中x1的系数为正，可选的系数为正，可选x1为进基变量，则为进基变量，则x4为出基变量，为出基变量，于是新的基变量为于是新的基变量为x1,x2,x3,x5,非基变量为非基变量为x4,x64611324zxx最优解为最优解为:X=(4，2，0，0，0，4）Z=14继继续续迭迭代代一一次次，即即可可得得341142zxx6341

42、34534234424444122xxxxxxxxxxxx 1.确定初始基可行解确定初始基可行解对标准型的线性规划问题对标准型的线性规划问题1maxnjjjZc x 1(1). .(2)0(1,2,., )njjjjP xbs txjn 若在约束条件若在约束条件(1)的系数矩阵中存在一个单位矩阵的系数矩阵中存在一个单位矩阵.,.,.mP PP12100010001作为初始基，则可以求出基解，若基解非负作为初始基，则可以求出基解，若基解非负,则为基可行解则为基可行解.2.从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解( )(,., ,., )TmXxxx00001200设初

43、始基可行解中的前设初始基可行解中的前m个为基变量，即个为基变量，即代入约束条件代入约束条件(1)有有( )mi iiPxb013写出写出(3)系数矩阵的增广矩阵系数矩阵的增广矩阵.mmjnPPPPPPb121,.mjnmjnm mmjmnmaaabaaabaaab11111212221100010001因因,.,mPP1是一个基，其他向量是一个基，其他向量jP可用这个基的线性可用这个基的线性组合来表示，有组合来表示，有或或mjij iiPa P1( )mjij iiPa P104将将(4)式乘上一个正的数式乘上一个正的数 0得得( )mjij iiPa P105(3)式式+(5)式并经过整理后

44、有式并经过整理后有( )miijijixaPPb016由由(6)式找到满足约束方程组式找到满足约束方程组njjjP xb1的另一个点的另一个点( )X1，有，有( )(,., ,., ,., )TjmmjXxaxa1001100其中其中( )X1是是的第的第j个坐标的值，要使个坐标的值，要使( )X1是一个基是一个基可行解，可行解，因规定因规定 0故应对所有故应对所有i=1,m,存在存在( )iijxa007令这令这m个不等式中至少有一个等号成立。因为当个不等式中至少有一个等号成立。因为当ija 0时时(7)式显然成立，故可令式显然成立，故可令min( )ilijiijljxxaaa 0008

45、由式由式(8),(),()iijilxail000( )X1故故是一个可行解。又因与变量是一个可行解。又因与变量,.,.,llmjxxxxx111111对应的向量，经重新排列后加上对应的向量，经重新排列后加上b列有如下形式矩阵和增广矩阵列有如下形式矩阵和增广矩阵.ljlmPPPPPPb1211,.jjljllljlljmmjabababbababa11221111100000100000100000000001000001,.,.,ljlmP PPP PP1211因因,lja 0故由上述矩阵元素组成的行列式不为零，故由上述矩阵元素组成的行列式不为零，是一个基。是一个基。 在上述增广矩阵中进行行

46、的初等变换，将第在上述增广矩阵中进行行的初等变换，将第l行乘上行乘上1/alj,再再分别乘以分别乘以(-aij)(i=1,l-1,l+1,m)加到各行上去，则增广矩阵加到各行上去，则增广矩阵左半部变成为单位矩阵，又因左半部变成为单位矩阵，又因/lljba ,., ,.,Tjlljlljmm jbbabababa111111 由此由此X(1)是同是同X(0)相邻的基可行解，且由基向量组成的矩相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。阵仍为单位矩阵。(3)最优性检验和解的判别最优性检验和解的判别将基可行解将基可行解X(0)和和X(1)分别代入目标函数得分别代入目标函数得( )( )mi i

47、izc x001( )( )miiijjizcxac101( )mmi iji ijiic xcc a011( )( )mji ijizcc a019mjji ijicc a 1令令(1)当所有的当所有的j 0时，可以判定现有顶点对应的基可行解时，可以判定现有顶点对应的基可行解即为最优解。即为最优解。(2)当所有的当所有的j 0又对某个非基变量又对某个非基变量xj有有j 0这表明可以找到另一个顶点的目标函数值也达到最大。这表明可以找到另一个顶点的目标函数值也达到最大。此时线性规划问题有无穷多个最优解。此时线性规划问题有无穷多个最优解。反之，当所有非基变量的反之，当所有非基变量的j 0时，线性规

48、划问题具有时，线性规划问题具有唯一解。唯一解。 (3)如果存在某个如果存在某个j 0,又又jP 0由式由式(7)知对任意知对任意 0iijxa00均有均有因而因而的取值可以无限增大不受限制。的取值可以无限增大不受限制。由式由式(9)可见可见( )z1可无限增大，表明线性规划有无界解可无限增大，表明线性规划有无界解1,(1,., )jjBjjBjcC B PcC Pjmn 其中112(,.,) (1,., )TjjjjmjPB Paaajmn CBCBXb1212mmmncccccc1212mmmnxxxxxx12mccc12mxxx12mbbb Z (0)Z 1000100011,12,1,1

49、mmm maaa 1,22,2,2mmm maaa 12nnmnaaa 12000mmni12mjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc 0 0 ijijjacc )min(0kjkjiaab （三）、单纯形表（三）、单纯形表若给定问题若给定问题标准化标准化后后 0b 且且线性无关的线性无关的单位列向量单位列向量，则以这，则以这m个单位列向量构个单位列向量构求解约束方程组即可得基可行解。求解约束方程组即可得基可行解。系数矩阵系数矩阵A中存在中存在m个个1.1.确定初始基可行解确定初始基可行解对

50、于线性规划问题对于线性规划问题 0maxzCXAXbLX 我们首先介绍求初始基可行解的方法我们首先介绍求初始基可行解的方法（一）单纯形法的一般描述（一）单纯形法的一般描述成的单位子矩阵作为初始基成的单位子矩阵作为初始基B, ,则令非基变量取零值则令非基变量取零值求下列问题的初始基可行解求下列问题的初始基可行解121212126423100421200maxzxxxxs.t.xxx ,x 1212312412346423100421200maxzxxxxxs.t.xxxx ,x ,x ,x 23104201A 标准化后标准化后 341001P ,P 取取为初始基为初始基B B1234010012

51、0 xx,x,x令令可可求求得得即初始基可行解为即初始基可行解为X=(0,0,100,120)T2.最优性检验最优性检验最优性判别准则最优性判别准则：设：设X(0)=(0,0,b1,bm)T为对应于为对应于基基B的基可行解，则：的基可行解，则：无最优解判别准则无最优解判别准则若若有有某某个个零零且且检检验验数数不不全全小小于于等等于于为为基基可可行行解解设设,)3()0(X0,0sssisxa 检检验验数数且且所所对对应应的的非非基基变变量量的的所所有有系系数数.),.,2 , 1(限限最最优优解解则则该该线线性性规规划划问问题题无无有有mi ., 0)1()0(为最优解为最优解则则数数若所有

52、非基变量的检验若所有非基变量的检验Xj , 0.变变量量的的检检验验数数为为若若其其中中至至少少有有一一个个非非基基为为最最优优基基B.优解优解则其一般有无穷多个最则其一般有无穷多个最(0)(2)0,.jX 若若所所有有非非基基变变量量的的检检验验数数则则为为唯唯一一最最优优解解最小比值原则最小比值原则0illikiiklkbbmin|aaa (0)0,kX ( (4 4) )若若存存在在检检验验数数则则不不为为最最优优解解 若若此此时时对对于于所所有有0kkikxa 正正的的检检验验数数单单纯纯形形表表对对应应的的非非基基变变量量的的系系数数对对应应则则可可选选取取最最大大检检验验数数中中至

53、至少少有有一一个个为为正正kmi ,),.,1( .作作为为换换入入变变量量的的非非基基变变量量kx)(,列列数数字字计计算算现现行行基基变变量量的的值值设设已已确确定定换换入入变变量量为为bxk从从中中系系数数的的比比值值的的系系数数列列向向量量中中对对应应正正和和换换入入变变量量,kx即即取最小者取最小者,l .作作为为换换出出变变量量对对应应的的基基变变量量将将llx 3.基变换基变换主元列与主元行交叉处的元素称为主元列与主元行交叉处的元素称为主元素主元素。按主元素进行迭代运算按主元素进行迭代运算,kx换换入入变变量量所所在在的的列列称称为为主主元元列列,lx换换出出变变量量所所在在的的

54、行行称称为为主主元元行行,数数列列中中相相应应的的目目标标函函数数系系改改变变取取代代列列中中用用在在BlkBCxxX，将将主主元元素素变变为为以以主主元元素素为为基基准准利利用用矩矩阵阵的的初初等等行行变变换换1,.主元列变为单位列向量主元列变为单位列向量（二）单纯形算法步骤：（二）单纯形算法步骤：步骤步骤1 1 将线性规划问题标准化，确定初始可行基和初将线性规划问题标准化，确定初始可行基和初始基可行解始基可行解，建立初始单纯形表建立初始单纯形表; ;步骤步骤2 2 检查非基变量的检验数，若所有检查非基变量的检验数，若所有0j 0jkjmax 0s, 有有则已得最优解，计算结束；否则转下一步

55、则已得最优解，计算结束；否则转下一步;确定确定xk为换入变量。为换入变量。步骤步骤3 3 若对于若对于单纯形表中单纯形表中x xs s 对应的列向量非正对应的列向量非正，则该问题无有限最优解，计算结束；否则转下一步，则该问题无有限最优解，计算结束；否则转下一步;步骤步骤4 4 据据 110ikiklkiliminB b/ a |aB b/ a确定确定xl 为换出变量。称为换出变量。称alk 为主元素，同时转入下一步为主元素，同时转入下一步;步骤步骤5 5以以alk为主元进行迭代运算，得新的单纯形表，重为主元进行迭代运算，得新的单纯形表，重复以上步骤，直到得到最优解。复以上步骤，直到得到最优解。

56、 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ1. 唯一最优解唯一最优解121212122212284164120 xxxxxs.t.xx ,x 1223maxzxxcj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1-Z0 i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4

57、 x5 x6000 x3x4x516 4 0 0 0 1 0 -Zi3x23010001/42620100-1/210010 0-1/2cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4-Z-9 i2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4

58、1 2 0 1 0 0 0 1/44412-Z-13 0 0 0 -2 0 1/4icj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0-Z-14 0 0 -1/2 -1 0 0i 0 0 0 -2 0 1/4-13-Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0

59、 0 0 0cjicj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0-Z-14 0 0 0 -3/2 -1/8 0i 0 0 0 -2 0 1/4-13-Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cji2. 无穷多个最优解无穷多

60、个最优解12121212123224321430maxzxxxx;xx;s.t.xx;x ,x 12123124125123453224321430maxzxxxxx;xxx;s.t.xxx;x ,x ,x ,x ,x 引入松弛变量引入松弛变量x3,x4,x5化化为标准形为标准形CBXBbx1 x2 x3 x4 x5 3 2 0 0 0ix3x4x50004143-13122-1100010001-z03 2 0 0 014/33/1x3x4x100331 -1 0 0 150 5 0 1 -370 1 1 0 1-z-90 5 0 0 -371x3x2x102310 1 0 1/5 -3/5