建模培训之线性规划

线性规划(LinearProgramming)线性规划问题及其数学模型线性规划问题的求解方法线性规划的图解法线性规划的单纯形法单纯形法的进一步讨论线性规划模型的应用当前1页，总共103页。

为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例一、有一正方形铁皮，如何截取x使容积为最大？xa此为无约束极值问题一、线性规划问题及其数学模型（一）、问题的提出当前2页，总共103页。

设备产品ABCD利润（元）

Ⅰ21402

Ⅱ22043有效台时1281612

例二、已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题当前3页，总共103页。问题中总有未知的变量，需要我们去解决。

要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。

如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。（二）、数学模型

1、当前4页，总共103页。目标函数：约束条件：①②③2、线性规划数学模型的一般形式当前5页，总共103页。也可以记为如下形式：目标函数：约束条件：当前6页，总共103页。如将上例用表格表示如下：设变量

产品j

设备i

有效台时

利润

当前7页，总共103页。向量形式：当前8页，总共103页。矩阵形式：当前9页，总共103页。规划确定型随机型静态规划动态规划线性规划非线性规划整数规划非整数规划整数规划非整数规划3、规划类型当前10页，总共103页。一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式二、线性规划问题的求解方法

（一）、求解方法当前11页，总共103页。1、解的概念⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解：使目标函数达到最大值的可行解。⑶基：B是矩阵A中m×n阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj(j=12……m)为基向量。∴Xj为基变量，否则为非基变量。（二）、线性规划问题的解当前12页，总共103页。

⑷基本解：满足条件②，但不满足条件③的所有解，最多为个。

⑸基本可行解：满足非负约束条件的基本解，简称基可行解。

⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解当前13页，总共103页。Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。设B=1001，令，则|B|=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基变量令B=1110x1x3

，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化当前14页，总共103页。例2.2某地区有三个矿山A1，A2，A3，生产同一种矿物。另外有四个这种矿物消费地（铁厂）B1，B2，B3，B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-2。问应如何调运，才使总运费最省？（一）运输问题的数学模型当前15页，总共103页。解：该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。设：xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组：（1）各矿山矿物的生产量与运出量平衡方程：当前16页，总共103页。（2）各铁厂矿物供应量与需要量平衡方程（3）矿物的运输量应非负

当前17页，总共103页。（4）目标函数当前18页，总共103页。（二）资源最优利用的数学模型例2.3某厂生产A、B产品1kg需用资源数见表2-3，已知生产A1kg价值7千元，B1kg12千元。应该生产A和B产品各多少才能使总价值最大。当前19页，总共103页。解：设A、B两产品的计划产量为x1、x2则数学模型为：

当前20页，总共103页。（三）机床负荷问题的数学模型例2.4设某车间需加工甲、乙两种零件。这两种零件可以在三种不同机床——铣床、六角车床、自动机床上进行加工。机床数及生产效率如表2-4。当前21页，总共103页。（三）机床负荷问题的数学模型

此表说明，在一台铣床上一个工作日可以加工15件甲零件或20件乙零件，余类同。该车间共有3台铣床，3台六角车床，1台自动机床。问如何合理安排机床的加工任务，使得在产品配套比例条件下（设甲、乙零件1:1配套），使成套产品的数量达到最大。当前22页，总共103页。

解：设xij表示第i种机床用来生产第j种产品的台数，则数学模型为：（1）加工甲、乙产品机床台数平衡方程：

（2）甲、乙零件配套比例平衡方程：

当前23页，总共103页。（3）变量非负：（4）目标函数求成套产品数量最大：

当前24页，总共103页。（四）人员分配的数学模型

例2.5有四件工作，分配给四人，每人能力不同，工作效率也不同如表2-5，规定每项工作由一个人担任和每个工人只分配一项工作。问应分配哪个人去完成哪项工作可使总效率达到最大。当前25页，总共103页。解：设xij表示i个工人分配担任第j项工作的情况，并xij取1和0两个值，

xij=1，表示第i个工人分配担任第j项工作；

xij=0，表示i个工人不担任第j项工作。

数学模型：（1）每个工人只担任一项工作当前26页，总共103页。（2）每项工作必由一个工人担任（3）变量取值：

（4）目标函数求总效率最大：

当前27页，总共103页。（五）合理配料问题的数学模型

例2.6某人每日需服A、B两种维生素，A最少服9个单位，B最少服19个单位，现有六种营养物每克含A、B维生素的单位数和每克价格如表2-6。问此人每天要服用这六种营养物各多少克，才既能获得每日最少所需维生素又使花费最省。当前28页，总共103页。（五）合理配料问题的数学模型

设：六种营养物分别各服用x1g，x2g，x3g，x4g，x5g，x6g。则数学模型：

当前29页，总共103页。（六）合理下料问题的数学模型例2.7某车间有一批长度为180cm的钢管，为着制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问题是应如何下料能使消耗的钢管数量最少？解：设在180cm长的钢管上能够下出U个70cm的零件，V个52cm的零件和W个35cm的零件，则U、V、W个零件必须符合:70U+52V+35W≤180当前30页，总共103页。（六）合理下料问题的数学模型经过试算，可得8种下料方式，见表：当前31页，总共103页。设：x1、x2、x3、x4、x5、x6、x7、x8分别表示这八种下料方式钢管消耗的总根数，则数学模型：当前32页，总共103页。2、解的基本定理⑴线性规划问题的可行域是凸集（凸多边形）。凸集凸集不是凸集顶点⑵最优解一定是在凸集的某一顶点实现（顶点数目不超过个）当前33页，总共103页。⑶先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。3、解的情况唯一解无穷解无界解无可行解有最优解无最优解当前34页，总共103页。

建立直角坐标，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。例一、⑴⑵⑶⑷三、图解法当前35页，总共103页。012345678123456⑴⑵⑶⑷作图∴最优解：x1=4x2=2有唯一最优解，Z=14x2

x1(42)⑴⑵⑶⑷当前36页，总共103页。例二、例三、⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2

x2

当前37页，总共103页。⑴⑵x1x2

无可行解例四、练习1当前38页，总共103页。效产品机床率AB机床台数

Ⅰ304040

Ⅱ553040Ⅲ233720

2、

某车间用三种不同型号的机床Ⅰ、Ⅱ、Ⅲ，加工A、B两种零件，机床台数、生产效率如表所示。问如何合理安排机床的加工任务，才能使生产的零件总数最多？1、某工厂生产A1、A2两种产品，每件可获利润15、20元。每个产品都经过三道工序，资料如表所示。工厂应如何安排生产计划使获得的总利润最多？试写出此问题的数学模型。工产品工序时A1A2可用工时

Ⅰ32800

Ⅱ23800Ⅲ11350习题1当前39页，总共103页。3、用图解法求解下面的线性规划问题：当前40页，总共103页。x1x2

123(2)x1x2

123(1)当前41页，总共103页。（一）、基本思想将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。（二）、线性规划模型的标准形式1、标准形式四、单纯形法当前42页，总共103页。2、特征：⑴.目标函数为求极大值，也可以用求极小值；⑵.所有约束条件（非负条件除外）都是等式，右端常数项为非负；⑶.变量为非负。3、转换方式：⑴.目标函数的转换如果是求极小值即，则可将目标函数乘以（－1），可化为求极大值问题。也就是：令，可得到上式。即当前43页，总共103页。⑵.约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量当前44页，总共103页。⑶.变量的变换若存在取值无约束的变量，可令其中：例一、将下列线性规划问题化为标准形式为无约束（无非负限制）当前45页，总共103页。

解:用替换，且，将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：引入变量当前46页，总共103页。例二、将线性规划问题化为标准型为无约束解：当前47页，总共103页。（三）、单纯形法例一、变成标准型当前48页，总共103页。约束方程的系数矩阵为基变量为非基变量I为单位矩阵且线性独立当前49页，总共103页。Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。设B=1001，令，则|B|=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T回顾：x3x4——基变量令B=1110x1x3

，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化当前50页，总共103页。令：则：∴基本可行解为（001281612）

此时，Z=0然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。当前51页，总共103页。找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代结束其步骤总结如下：当前52页，总共103页。当时，为换入变量确定换出变量为换出变量接下来有下式：当前53页，总共103页。用高斯法，将的系数列向量换为单位列向量，其步骤是：结果是：当前54页，总共103页。代入目标函数：有正系数表明：还有潜力可挖，没有达到最大值；此时：令得到另一个基本可行解

（0，3，6，2，16，0）有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当时，即不再利用这些资源。如此循环进行，直到找到最优为止。本例最优解为：（4，2，0，0，0，4）当前55页，总共103页。（四）、单纯形表当前56页，总共103页。判定标准：若求

或例题：当前57页，总共103页。cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2－12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2当前58页，总共103页。cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4当前59页，总共103页。cj230000cBxBbx1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100-Z-1400-1/2-100000-201/4-13-Z4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj当前60页，总共103页。cj230000cBxBbx1x2x3x4x5x60203x3x1x6x2

0442001-1-1/4010001/40

000-21/210101/2-1/80-Z-14000-3/2-1/80000-201/4-13-Z4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj当前61页，总共103页。练习00-1/12-7/24-33/4-Z

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24当前62页，总共103页。（一）、模型情况

变量：xj≥0xj≤0xj无约束结1、组成约束条件：≥=≤b目标函数：maxmin果2、变量xj≤0令xj′=-xj，xj′≥0

xj≥0不处理

xj无约束令xj=xj′－xj″,xj′≥0,xj″≥0唯一最优无穷最优无界解无可行解五、单纯形法的进一步讨论

当前63页，总共103页。3、约束条件：加入松弛变量加入人工变量先减去再加上例：当前64页，总共103页。当前65页，总共103页。加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。⑴.大M法：当前66页，总共103页。cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－-Z-11-M00M03M-1当前67页，总共103页。cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－-Z-2-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3-Z20001/31/3M-1/3M-2/3∴最优解为（4190000），Z=－2当前68页，总共103页。用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。

第一阶段：在原线性规划问题中加入人工变量，构造如下模型：⑵.两阶段法：当前69页，总共103页。对上述模型求解（单纯形法），若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：第一阶段当前70页，总共103页。cj0000011cBxBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－-Z10-1001030x4123001-22-50x210100-11-20x31-2010000-Z00000011当前71页，总共103页。cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z20001/31/3第二阶段∴最优解为（41900），目标函数Z=-2当前72页，总共103页。1、目标函数：max,min设规划模型约束条件为，需加入人工变量，而得到一个m×m的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当，而还有人工变量（非零）时，则表示原问题无可行解。当前73页，总共103页。3、无可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。当前74页，总共103页。

5、退化：即计算出的θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例是永远达不到最优解。需作如下处理：⑴.当中出现两个以上最大值时，选下标最小的非基变量为换入变量；⑵.当θ中出现两个以上最小值时，选下标最小的基变量为换出变量。当前75页，总共103页。建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解图解法、单纯形法单纯形法不处理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M根据上表列出初始单纯形表A（二）、线性规划小结当前76页，总共103页。A当前77页，总共103页。练习当前78页，总共103页。-M+1/7-1/7-M-16/7-50/700-102/7-Z1/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj0-M0-5+2M3-4M2+3M-Z51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj当前79页，总共103页。作业当前80页，总共103页。当前81页，总共103页。0100x2-4-2/35/3-10/3x1300-Z-1/3-1/300-2/32/3-1/32/3x2-44010-1/31/3105/3-5/310/340/310/3x804-1/31/301-1/31/3-5/34/3x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj4M-4311x2-43-6M-21-4x130-M005-3M3M-52-3M-Z2/31-100-22-12x10-M14\400101-1314\4x8020001-11-22x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj当前82页，总共103页。0100x2-4-31/2-3/25/2-15/2x13-M0-1/2-M+9/200-17/22\7-Z001/21/2001/28\3x2-4001/2-1/21-1[5/2]6\1x65-111/25/200-5/210\5x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-4-13-45-10x13-M00-M+41-1-68-Z-0001-11-22x2-46001-12-2512\2x80--1103-11-54x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj当前83页，总共103页。一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。⑴.要求解问题的目标函数能用数值指标来反映，且为线性函数；⑵.存在着多种方案；⑶.要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。六、线性规划模型的应用当前84页，总共103页。（一）、资源的合理利用

一般提法：某厂计划在下一生产周期内生产B1,B2,…Bn种产品，要消耗A1,A2,…Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？单件产消耗品资源资源限制单件利润当前85页，总共103页。（二）、生产组织与计划问题

一般提法：某工厂用机床A1,A2,…Am加工B1,B2,…Bn种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又