运筹学基础-线性规划(方法)

第一章线性规划及单纯形法本章主要内容

线性规划概述绪论一般线性规划问题的数学模型线性规划问题的图解法线性规划的基本定理单纯形法用计算机软件求解线性规划问题线性规划的应用举例2【开篇案例】某旅行社为了迎接旅游黄金周的到来，对一日游导游人员的需求经过统计分析如表所示。为了保证导游充分休息，导游每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排导游人员的作息，既满足工作需要，又使配备的导游人数最少？一、人力资源分配的问题线性规划时间所需导游人数星期日40星期一34星期二32星期三35星期四28星期五46星期六423【开篇案例】明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？二、生产计划的问题线性规划4【开篇案例】某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？三、配料问题线性规划5【开篇案例】某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；四、投资问题问：a.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？线性规划6归纳上述研究的主要内容：

（2）计划任务确定的情况旧：如何统筹安排，精心筹划，用最少的资源来实现。这方面的问题涉及到系统的投入和求极小值问题（1）资源确定的情况下：如何合理利用、合理规划，使得完成的任务最大。这方面的问题涉及到系统的产出和求最大值问题研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力和物力消耗，获利更多更好的社会需求产品。此项研究即为规划问题线性规划7

线性规划是运筹学的一个重要分支。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法——单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。线性规划概述

线性规划是一种合理利用资源、合理调配资源的应用数学方法。其中：规划就是利用某种数学方法使得有效资源的运用最优化；线性就是用来描述就是之间关系的函数是线性函数。线性规划8在生产管理和经济活动中经常提出这样一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。

在管理中一些典型的线性规划应用主要包括：

合理利用线材问题：如何下料使用材最少

配料问题：在原料供应量的限制下如何获取最大利润

投资问题：从投资项目中选取方案，使投资回报最大

产品生产计划：合理利用人力、物力、财力等，使获利最大

劳动力安排：用最少的劳动力来满足工作的需要

运输问题：如何制定调运方案，使总运费最小问题：如何建立线性规划模型？线性规划

盈亏平衡问题：掌握企业盈亏界限，合理安排生产能力9【引例】生产计划的问题某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时，生产每件产品Ⅱ需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品Ⅰ获得2元，生产Ⅱ获得3元，问如何安排生产，使总的利润最大。§1.1一般线性规划问题的数学模型

则该问题的数学模型表示为

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0设生产Ⅰ、Ⅱ产品为x1、x2件问题：建立线性规划模型要考虑的关键要素？线性规划10一、线性规划问题的三大要素决策变量

是指实际系统或决策问题中有待确定的因素，是系统中的可控因素。如生产Ⅰ、Ⅱ产品为x1、x2件，

x1、x2

即为决策变量

决策变量的取值范围。如此题的

x1≥0、x2≥

0约束条件

任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。如设备能力、原材料数量等

是决策者对决策问题目标的数学描述。如时间最省、利润最大、成本最低。此题是利润最大

maxZ=

2x1+3x2

约束条件是决策方案可行的保障。

约束条件的基本类型：大于等于“≥”、等于“＝”、小于等于“≤”目标函数

目标函数应该是决策变量的线性函数。

有的目标要实现最大，有的则要求最小。

线性规划11二、线性规划模型的构建线性规划建模步骤：明确问题，确定目标，列出约束条件；

收集资料，确立模型；模型求解与检验

优化后的分析其中：最为困难的是建模线性规划12【例1】生产计划问题线性规划某企业生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品Ⅰ需占用各设备为2、1、4、0小时，生产每件产品Ⅱ需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品Ⅰ获得2元，生产Ⅱ获得3元，问如何安排生产，使总的利润最大。13建立模型：(1)决策变量

要决策的问题是两种产品的产量，因此有两个决策变量：设x1为产品Ⅰ产量，x2为产品Ⅱ产量。

生产单位产品Ⅰ需占用各设备A为2工时，生产单位产品Ⅱ需占用各设备A为2工时，A设备的能力总量限制为12工时，则A设备能力约束条件表述为：

(2)约束条件

生产这两种产品受到现有生产能力的制约，用量不能突破。

2x1+2x2

≤12

同理，B、C、D设备的能力约束条件为

x1+2x2

≤84x1≤16线性规划4x2≤1214

(3)目标函数

目标是利润最大化，用Z表示利润，则

(4)非负约束:

产品Ⅰ、Ⅱ的产量不应是负数，否则没有实际意义，这个要求表述为

则该问题的数学模型表示为maxZ=2x1+3x2

x1

≥0，x2

≥0

目标函数约束条件线性规划

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥015【例2】运输问题

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

销地产地B1B2B3B4产量A1A2A3632575843297523销量2314线性规划16建立模型：(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)632575843297线性规划17【例3】营养问题

某养鸡场所用的混合饲料是由n种配料组成。要求这种混合饲料必须含有m种不同的营养成份，而且要求每单位混合饲料中第i种营养成份的含量不能低于bi(i=1,2,…,m）。已知第i种营养成份在每单位的第j种配料中的含量为aij,j=1,2,…,n，每单位的第j种配料的价格为cj

。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小.配料营养成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm单价c1c2…

cn线性规划18建立模型：MinZ=c1x1+c2x2+…+cnxn设xj

表示在单位混合饲料中，第j种配料的含量（j=1,2,…,n）则有如下的数学模型：配料营养成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm价格c1c2…

cna11x1+a12x2+…+a1nxn≥

b1a21x1+a22x2+…+a2nxn≥

b2……am1x1+am2x2+…+amnxn≥

bmx1≥0,x2≥0,…,xn≥0线性规划19【例4】污水处理问题

例靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。第一化工厂每天排放污水2万m3，第二化工厂每天排放污水1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/m3和800元/m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？

设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0线性规划20思考：人力资源分配问题的建模问题：如何建立该问题的线性规划模型?线性规划某旅行社为了迎接旅游黄金周的到来，对一日游导游人员的需求经过统计分析如表所示。为了保证导游充分休息，导游每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排导游人员的作息，既满足工作需要，又使配备的导游人数最少？时间所需导游人数星期日40星期一34星期二32星期三35星期四28星期五46星期六4221【答案】线性规划设周日、周一、周二、周三、周四、周五、周六开始工作的导游人员数分别x1、x2、x3、x4、x5、x6、x7，所需的导游人员数为z。则有：时间所需导游人数星期日40星期一34星期二32星期三35星期四28星期五46星期六4222思考：生产计划问题的建模明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？设：自己铸造甲、乙、丙为x1、x2、x3；外购甲、乙为x4、x5问题：如何建立该问题的线性规划模型线性规划23【答案】

解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和

可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下的数学模型。目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0线性规划24思考：配料问题的建模某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？设xij表示第i种（甲、乙、丙）产品中原料j的含量。问题：如何建立该问题的线性规划模型原料1原料2原料3甲x11x12x13乙x21x22x23丙x31x32x33线性规划25【答案】

解：设xij分别表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。线性规划目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）xij≥0,i=1,2,3;j=1,2,326思考：投资问题的建模某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；问：a.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b.应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。问题：如何建立该问题的线性规划模型线性规划27小结：线性规划模型三大要素决策变量

每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值就代表一个具体的方案。

约束条件

存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。

都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。目标函数满足以上三个条件的数学模型称为线性规划数学模型。线性规划28三、线性规划一般模型的代数表达式max(min)Z=c1x1+c2x2+…+cnxn

问题：线性规划如何求解？a11x1+a12x2+…+a1nxn≤(或＝,≥)b1a21x1+a22x2+…+a2nxn≤(或＝,≥)b2……………am1x1+am2x2+…+amnxn≤(或＝,≥)bmx1,x2,…,xn≥(≤)0线性规划线性规划的求解方法图解法单纯形法公式法29§1.2线性规划问题的图解法

对于简单的线性规划问题(只有两个决策变量的线性规划问题)，我们通过图解法可以对它进行求解。

图解法即是用图示的方法来求解线性规划问题。图解法简单直观，有助于了解线性规划问题求解的基本原理。

一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。

线性规划30线性规划图解法基本步骤：1、建立直角坐标系；2、确定可行域；可行域——约束条件所构成的区域3、图示目标函数；4、最优解的确定。最优解——可行域中使目标函数值达到最优的点

31一、图解法的基本步骤

满足所有约束条件的解叫可行解，解的集合称之为可行域。即所有约束条件共同围成的区域。1、可行域的确定例1的数学模型为：x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D

五边形OABCD内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0线性规划322、最优解的确定

确定x1、x2希望目标函数

Z=

3x1+5x2达到最大，图形中Z=

3x1+5x2代表以Z为参数的一族平行线，即等值线。

等值线：位于同一直线上的点的目标函数值相同。

Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)D最优解：可行解中使目标函数最优(极大或极小)的解

本题中：满足目标函数最大的极点是离原点距离最远的点(4,6)Z=3x1+5x2＝24Z=3x1+5x2＝30Z=39Z=42线性规划最优解（4，6）maxZ=4233二、解的几种可能性唯一最优解：只有一个最优点。如上题的最优解（4,6）

多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D如例1的数学模型变为

maxZ=

3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12线性规划线段BC上所有的点都是最优解34

例如

maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1Z=6Z=12S.t.无界解：线性规划线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）可行域无边界35

无解：线性规划若约束条件相互矛盾，则可行域为空集。例如

maxZ=

3x1+2x2x1+x2

≤1x1+2x2≥3x1≥0,x2≥0x1+x2=1x1+2x2=3x212-1x1123-1S.t.可行域为空集36【例】求最大值问题数学模型为：

四边形OBQC内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。maxZ=

8x1+6x24x1+2x2≤602x1+4x2≤482x1+3x2≤36x1≥0,x2≥02x1+3x2

=36x1x2510510150C(0,12)4x1+2x2

=602x1+4x2

=48B(15,0)Z=126Q(13.5,3)结论：在Q(13.5,3)处利润最大为126，Q(13.5,3)为最优解线性规划最优解为（13.5,3）maxZ=12637【例】求最小值问题设有某林场需配制某种灭虫药水500公斤，该药水系由甲与乙两种药水混合而成。甲种药水每公斤5元，乙种药水每公斤8元。按照两种药水的化学性质，在混合时，500公斤混合药水中含甲种药水最多不能超过400公斤，含乙种药水最少不能少于200公斤。问如何配制可使该药水配制成本最低？.

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0则数学模型为：设：500公斤混合药水中，甲种药水x1公斤，乙种药水x2公斤线性规划38求解：线性规划数学模型为：

线段BC上的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0结论：等成本线往右下移，成本越来越小，A(300,200)成本为最小Z=5x1+8x2

=4000Z=3100x2

=200x1+x2

=500x1x2102004000B(0,500)100300500x1

=400100200300400CA最优解为（300,200）minZ=310039练习题：用图解法求解下列问题－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥01.约束条件为：（1）maxZ=

4x+y画出可行域图形，求下面几种情况下的最优解（2）minZ=

2x-3y（3）maxZ=2x-3y（4）maxZ=x+2y线性规划40练习题：求解－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥0（1）maxZ=

4x+y求下面几种情况下的最优解（2）minZ=

2x-3y（4）maxZ=

x+2y（3）maxZ=

2x-3yx+3y=3－x+2y=2x－y

=3x1x2161234523x+2y=6(2,2)(4,1)(3,0)(0,1)Z=4x+y=1Z=10Z=12Z=17Z=-3Z=-2Z=5Z=6最优解x=4,y=1maxZ=

17最优解x=0,y=1minZ=

-3Z=2x+y=1Z=3Z=6有无穷多最优解maxZ=

6最优解x=3,y=0maxZ=

6线性规划41§1.3线性规划解的基本定理线性规划

多于两个决策变量的线性规划问题已经不能用图解法求解，因此需要寻求新的求解方法。由于线性规划问题的数学模型有各种不同的形式，比如

目标函数有极大化和极小化；

约束条件有“≤”、“≥”和“＝”三种情况；

决策变量一般有非负性要求，有的则没有。

为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算。42一、线性规划的标准形式的转换方法线性规划（一）线性规划问题的标准形式线性规划的标准形式为：

目标函数最大化

约束条件为等式，

右端常数项

bi≥0

决策变量非负

maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥043线性规划标准型的表达方式有代数式、矩阵式两种：（二）标准型的表达方式

1、代数式maxZ=c1x1+c2x2+…+cnxn

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

(i=1,2,…,m)xj≥0(j=1,2,…,n)线性规划44

2、矩阵式简化为maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0线性规划45（三）非标准型向标准型转化如目标函数极小化问题：通过变量代换划为标准型只需将等式两端乘以-1即变为极大化问题。因为minZ=–max(–Z)=CTX，令Z′=-Z，则maxZ′=–CTXminZ=CTX如约束条件中右端常数项非正：通过方程两端同乘“－1”如约束条件为不等式：通过增加变量来划为标准型

当约束方程为“≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；如4X1＋2X2

≤60→4X1＋2X2

＋X3

=60

当约束条件为“≥”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)。如X1＋X2

≥20→X1＋X2

－X3

=20

如决策变量xk没有非负性要求：通过变量代换实现

令xk=xk‘－xk〃，其中令xk′，xk〃≥0，用xk′、xk〃取代模型中xk线性规划46【例1】试将如下线性规划问题化成标准型例1的标准型

maxZ=

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

3x1+5x2+0x3

x1+x3=82x2≤123x1+4x2≤36x1,x2,x3

≥0maxZ=

3x1+5x2+0x3+

0x4

x1+x3=8

2x2+x4=12

3x1+4x2≤36x1,x2,x3,x4≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=8

2x2+x4=12

3x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0需要化为标准型引进一松驰变量x3线性规划引进一松驰变量x4引进一松驰变量x547【例2】试将如下线性规划问题化成标准型minZ=

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

-x1-x2-x3≥-2x1≥0,x3≤0S.t.例2的标准化minZ=

x1+2x2+3x3′x1+2x2+x3

′≤52x1+3x2+x3

′≥6

-x1-x2+x3

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

minZ=

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

minZ=

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

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4

x1+2(x2′-x2〃

)

+x3

′+x4=52x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

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

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′

+0x4+0x5

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

maxZ′=-x1-2(x2′-x2〃

)

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

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

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

maxZ′=-

x1-2(x2′-x2〃

)

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

)

+x3

′≤5

2x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-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

需要化为标准型令－x3＝x3’令-Z＝Z’线性规划无约束，令引进变量x4x5x6两端同时乘以-148【例3】试将如下线性规划问题化成标准型例3的标准型为：

需要化为标准型线性规划49练习：试将如下线性规划问题化成标准型（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15x1≥3x2≥2x1,

x2≥0，x3无限制S.t.线性规划50【答案】（1）maxZ=-x1+3

x3+4

x4+0

x5+0

x62x1+4

x2+x3-2

x4+

x5

=13

6x1+x3+8

x4-x6

=50

x1-4

x2+5

x3+3

x4=10xi≥0,i=1,2,3,4,5,6S.t.（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.线性规划51【答案】（2）maxZ’=

-6

x1-7

x2+

x’3－x’’3

+0x4+0x5+0x6+0x73x1+2

x2-x’3+x’’3

+x4

=10

x2+x’3－x’’3+x5

=15x1-x6

=3x2-

x7=2x1,

x2,

x’3,x’’3,

x4,

x5,

x6,

x7≥0S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15x1≥3x2≥2x1,

x2≥0，x3无限制S.t.线性规划52二、线性规划解的概念

在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为：

求解线性规划问题就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数（1）达到最大值。

若设矩阵A的秩R(A)=m；根据线性代数定理可知，当R(A)=m＜n，则方程组有无穷多个解，这也正是线性规划寻求最优解的余地所在。线性规划53关于标准型解的若干基本概念可行解与非可行解满足约束条件（2）和非负条件（3）的解

X

称为可行解，约束方程的解空间可行解非可行解最优解：使目标函数(1)达到最大的可行解称为最优解可行解组成的集合叫做可行域问题是可行解有无穷多个满足约束条件（2）但不满足非负条件（3）的解X称为非可行解线性规划54

线性规划对于标准型设约束方程组的系数矩阵为A=(P1,P2,…,Pn)，A的秩为m，则约束方程有无穷解时，R(A)=m＜n基：A中任意m个线性无关的列所构成的矩阵称为该标准型的一个基。基向量：B=（P1,P2,…,Pm），|B|0为该标准型的一个基，则称P1,P2,…,Pm为基向量。基变量与非基变量

基变量：与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm

)T;

非基变量：其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xn

)T

。则有X=XB+XN

最多有个基55

基解令非基变量

XN=0，求得基变量XB的值而得到的解称为基本解(基解)基可行解基解X

的非零分量都0

时，称为基可行解，否则为基非可行解基解基可行解（最多有）最多有种基解基解个数：线性规划基解是有限的基可行解是有限的56【例】线性规划模型的基解演示求解x3=-2x1-x2+10x4=-x1-x2+8x5=-x2+7如果选择基变量x3,x4,x5，则非基变量是x1,x2令非基变量x1=x2=0，得到x3=10，x4=8，x5=7。则此解为基可行解：X0=(0,0,10,8,7)TR(A)=3例1的标准型为得基解X=(0,0,10,8,7)T

因分量均大于0maxZ=

6x1+4x2+0x3+0x4+0x52x1+x2

+x3=10

x1+x2+x4=8x2+x5=7x1,x2,x3,x4,x5≥0线性规划这只为其中一个基可行解57

全部基解求解举例maxZ=

6x1+4x2+0x3+0x4+0x52x1+x2

+x3=10

x1+x2+x4=8x2+x5=7x1,x2,x3,x4,x5≥0线性规划58

线性规划三、线性规划解的基本定理1、预备知识：凸集和顶点凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。顶点：假设K是凸集，XK，若X不能用不同的两个点X1、X2的线性组合表示为X3=X1+(1-)X2(0<<1)，则称K为凸集K的一个顶点（或极点）。都是顶点59

线性规划若线性规划问题存在可行域，则其可行域一定是凸集。

定理2：

线性规划问题的基可行解对应可行域的顶点。

定理3：若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。x1x248123690ABC(4,6)D定理1：2、线性规划解的基本定理60四、线性规划的解题思路线性规划

线性规划问题可以有无数个可行解，而有限个顶点对应的解都是基可行解，最优解只可能在顶点(基可行解)上达到，故只要在有限个基可行解中寻求最优解即可。方法是：从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。61五、线性规划单纯形法的解题流程线性规划确定初试基础可行解求最优解的目标函数值确定改善方向求新的基础可行解检查是否为最优解？是否62六、线性规划解题工具—单纯形表格及其格式线性规划CjC1…Cn-mCjn-m+1…Cn比值CBXBbx1…Xn-mXn-m+1…xnCn-m+1Xn-m+1b1a11…A1n-m1…01Cn-m+2Xn-m+2b2a21…A2n-m0…02………………………Cnxnbmam1…Amn-m0…1m检验数j-Z1…n-mn-m+1…nmaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bm63§1.4线性规划的求解方法——单纯形法

单纯形法(SimplexMethod)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：表格法矩阵法－改良的单纯形法单纯形法的矩阵计算线性规划64初始单纯形表的构建方法Cj比值CBXBb检验数j检验数s：初始时是目标函数的系数（随基的调整变化）变量符号基变量符号（随基的调整变化）基变量在目标函数中的系数（变化）约束方程的常数项约束方程的变量系数检验方法：有一个检验数sj>=0，此时基解不是最优；所有检验数sj<0，此时基解为最优目标函数的系数初始值为0线性规划65一、表格单纯形法的计算步骤maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4+0x5

x1+x3

=82x2+x4

=123x1+4x2+x5=36

标准型取基变量为x3,x4,x5，1、建立初始单纯形表——确定初始基变量则非基变量为x1,x2线性规划662、求初始基可行解并进行最优性检验Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000

令非基变量x1=0，x2=0，找到一个初始基可行解：

x1=0，x2=0，x3=8，x4=12，x5=36，

σj＞0，（因为z=3x1+5x2+0x3+0x4+0x5)可求基可行解的状态即X0=(0,0,8,12,36)T此时利润Z=0此解不是最优线性规划67初始基可行解图示Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX0=(0,0,8,12,36)T说明：一个可行解就是一个生产方案，上述方案表明两种产品都不生产x1=0，x2=0，利润Z=0。线性规划683、寻找另一基可行解Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9交叉元素称为主元首先确定进基变量再确定出基变量线性规划69检验数j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，σ1=3＞0，此解不是最优迭代可求基可行解的状态即得基可行解X1=(0,6,8,0,12)T此时-Z＝-30，