建模培训之线性规划

1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题的求解方法线性规划问题的求解方法线性规划的图解法线性规划的图解法线性规划的单纯形法线性规划的单纯形法单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用 为了完成一项任务或达到一定的目的，怎样用最少的为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。达到一定的目的，这个过程就是规划。例一、有一正方形铁皮，如何截取例一、有一

2、正方形铁皮，如何截取 x x 使容积为最大？使容积为最大？xa 22xxav 此为无约束极值问题此为无约束极值问题02222 )()()(xaxxa6ax 0 dxdv一、线性规划问题及其数学模型线性规划问题及其数学模型（一）、问题的提出一）、问题的提出 设设 备备产产 品品 A B C D利润（元）利润（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12 例二、已知资例二、已知资料如下表所示，料如下表所示，问如何安排生产问如何安排生产才能使利润最大？才能使利润最大？或如何考虑利润或如何考虑利润大，产品好销。大，产品好销。模模 型型max Z = 2x1

3、 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12此为带约束的极值问题此为带约束的极值问题问题中总有未知的变量，需要我们去解决。问题中总有未知的变量，需要我们去解决。 要求：有目标函数及约束条件，一般有非负条件要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。存在，由此组成规划数学模型。 如果在规划问题的数学模型中，变量是连续的如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这方），

4、约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。性的规划问题（其中一个条件符合即可）。（二）、数学模型（二）、数学模型 1 1、00 12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ)()(min)max目标函数：目标函数：约束条件：约束条件：2 2、线性规划数学模型的一般形式、线性规划数学模型的一般形式也可以记为如下形式也可以记为如下形式：)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjn

5、jijijnjjj 目标函数：目标函数：约束条件：约束条件：如将上例用表格表示如下：如将上例用表格表示如下：设变量设变量)21( njxj 产产 品品 j 设设 备备 i 有效台时有效台时 利润利润 mnmijnaaaaa 1111n 2 1m 2 1 mbbb 21nccc 21jcib向向 量量 形形 式：式：) (21ncccC nxxX1 mjjjaap1 mbbb1 0 )( (min) maxXbxpCXZjj矩阵形式：矩阵形式： mnmnaaaaA1111 0 )( (min) maxXbAXCXZ规规划划确定型确定型随机型随机型静态规划静态规划动态规划动态规划线线 性规性规 划

6、划非线性规划非线性规划 整数规划整数规划 非整数规划非整数规划整数规划整数规划非整数规划非整数规划3、规划类型、规划类型一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式二、线性规划问题的求解方法二、线性规划问题的求解方法（一）、求解方法（一）、求解方法1 1、解的概念、解的概念 可行解：满足约束条件可行解：满足约束条件、的解为可行解。的解为可行解。所有解的集合为可行解的集或可行域。所有解的集合为可行解的集或可行域。 最优解：

7、使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。 基：基：B B是矩阵是矩阵A A中中m mn n阶非奇异子矩阵阶非奇异子矩阵（ B B 00），则），则B B是一个基。是一个基。) (211111mmmmmpppaaaaB 则称则称 Pj ( j = 1 2 m) 为基向量。为基向量。 Xj 为基变量，否则为非基变量。为基变量，否则为非基变量。（二）、线性规划问题的解（二）、线性规划问题的解 基本解：满足条件基本解：满足条件，但不满足条件，但不满足条件的所有解，最多为的所有解，最多为 个。个。Cmn 基本可行解：满足非负约束条件的基本基本可行解：满足非负约束条件的基本解，

8、简称基可行解。解，简称基可行解。 可行基：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20 Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40A=x1 x2 x3 x41 1 1 01 2 0 1可行解：可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。等。设设B= 1 0 0 1，令令，则 | B |=10,令令 x1=x2 =0，则

9、，则 x3 =3, x4=4，X=(0,0,3,4)T例：例：x3 x4基变量基变量令 B=1 1 1 0 x1 x3 ，则令令 x2=x4 =0，则，则 x3 =-1, x1=4，X=(4,0,-1,0)T| B |=-10,非基本可行解非基本可行解基本可行解基本可行解标准化标准化例例2.2 某地区有三个矿山某地区有三个矿山A1，A2，A3，生产同一种，生产同一种矿物。另外有四个这种矿物消费地（铁厂）矿物。另外有四个这种矿物消费地（铁厂）B1，B2，B3，B4。各矿山产量及铁厂的需要量和矿山。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表将矿物运到铁厂的单位运价如表2-2。问应如

10、何。问应如何调运，才使总运费最省？调运，才使总运费最省？（一）运输问题的数学模型 表 2-2 铁厂 运价（元/t） 矿山 B1 B2 B3 B4 产量 （t） A1 A2 A3 1.5 7 1.2 2 0.8 0.3 0.3 1.4 2 3 2 2.5 100 80 50 需量（t） 50 70 80 30 解：解：该题有两个限制条件：一个是产量，一该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。个是需量。目标是总运费最省。设：设：x xijij表示从第表示从第i i个矿山运往第个矿山运往第j j个铁厂的矿物运个铁厂的矿物运量。这样得到以下两组线性方程组：量。这样得到以下两组线性

11、方程组：（1 1）各矿山矿物的生产量与运出量平衡方程：）各矿山矿物的生产量与运出量平衡方程： 1112131421222324313233341008050 xxxxxxxxxxxx （2 2）各铁厂矿物供应量与需要量平衡方）各铁厂矿物供应量与需要量平衡方程程11213112223213233314243450708030 xxxxxxxxxxxx（3）矿物的运输量应非负）矿物的运输量应非负 0(1,2,3,1,2,3,4)ijxij（4 4）目标函数）目标函数111213142122min1.520.3370.8Zxxxxxx2324313233341.421.20.322.5xxxxxx（

12、二）资源最优利用的数学模型例2.3 某厂生产A、 B产品1kg需用资源数见表2-3 ，已知生产A1kg价值7千元，B1kg12千元。应该生产A和B产品各多少才能使总价值最大。 表 2-3 产 品 资 源 A B 现有资源数 煤/t 电力/kw 劳动力/个 9 4 3 4 5 10 360 200 300 利润（千元） 7 12 解：设解：设A A、B B两产品的计划产量为两产品的计划产量为x x1 1、x x2 2则数学模型为：则数学模型为： 121212129436045200310300,0 xxxxxxxx 12max712Zxx （三）机床负荷问题的数学模型 例例2.4 2.4 设某车

13、间需加工甲、乙两种零件。这设某车间需加工甲、乙两种零件。这两种零件可以在三种不同机床两种零件可以在三种不同机床铣床、六角铣床、六角车床、自动机床上进行加工。机床数及生产效车床、自动机床上进行加工。机床数及生产效率如表率如表2-42-4。 表2-4 机 床 生 产 效 率 （ 件 /日 ） 机 床 台 数 甲 产 品 乙 产 品 铣 床 六 角 车 床 3 3 15 20 20 30 （三）机床负荷问题的数学模型 此表说明，在一台铣床上一个工作日可以加此表说明，在一台铣床上一个工作日可以加工工1515件甲零件或件甲零件或2020件乙零件，余类同。该车间共件乙零件，余类同。该车间共有有3 3台铣床

14、，台铣床，3 3台六角车床，台六角车床，1 1台自动机床。问如何台自动机床。问如何合理安排机床的加工任务，使得在产品配套比例合理安排机床的加工任务，使得在产品配套比例条件下（设甲、乙零件条件下（设甲、乙零件1:11:1配套），使成套产品的配套），使成套产品的数量达到最大。数量达到最大。 解：设xij表示第i种机床用来生产第j种产品的台数，则数学模型为：（1）加工甲、乙产品机床台数平衡方程： 111221222132331xxxxxx（2 2）甲、乙零件配套比例平衡方程：）甲、乙零件配套比例平衡方程： 112131122232152030203055xxxxxx（3 3）变量非负：）变量非负：0

15、(1,2,31,2)ijxij112131max152030Zxxx（4 4）目标函数求成套产品数量最大：）目标函数求成套产品数量最大： （四）人员分配的数学模型 例例2.5 2.5 有四件工作，分配给四人，每人能力不同，有四件工作，分配给四人，每人能力不同，工作效率也不同如表工作效率也不同如表2-52-5，规定每项工作由一，规定每项工作由一个人担任和每个工人只分配一项工作。问应分个人担任和每个工人只分配一项工作。问应分配哪个人去完成哪项工作可使总效率达到最大配哪个人去完成哪项工作可使总效率达到最大。 表2-5 工 作 工 人 A B C D 甲 乙 丙 丁 6 7 8 7 2 4 10 7

16、3 3 7 5 1 2 3 4 解：设解：设x xijij表示表示i i个工人分配担任第个工人分配担任第j j项工作的情况，项工作的情况，并并x xijij取取1 1和和0 0两个值，两个值， x xijij=1=1，表示第，表示第i i个工人分配担任第个工人分配担任第j j项工作；项工作； x xijij=0=0，表示，表示i i个工人不担任第个工人不担任第j j项工作。项工作。 数学模型：数学模型：（1 1）每个工人只担任一项工作）每个工人只担任一项工作 111213142122232431323334414243441111xxxxxxxxxxxxxxxx （2）每项工作必由一个工人担任

17、 112131411222324213233343142434441111xxxxxxxxxxxxxxxx（3）变量取值： 1(1,2, ,1,2, )0ijxim jn（4）目标函数求总效率最大： 111213142122232431323334424344max623743281073754Zxxxxxxxxxxxxxxx（五）合理配料问题的数学模型例例2.6 2.6 某人每日需服某人每日需服A A、B B两种维生素，两种维生素，A A最少服最少服9 9个个单位，单位，B B最少服最少服1919个单位，现有六种营养物每克含个单位，现有六种营养物每克含A A、B B维生素的单位数和每克价格如

18、表维生素的单位数和每克价格如表2-62-6。问此人。问此人每天要服用这六种营养物各多少克，才既能获得每天要服用这六种营养物各多少克，才既能获得每日最少所需维生素又使花费最省。每日最少所需维生素又使花费最省。 表2-6 一 克 营 养 物 所 含 维 生 素 单 位 数 营 养 素 维 生 素 （ 一 ） （ 二 ） （ 三 ） （ 四 ） （ 五 ） （ 六 ） 维 生 素 最 少 需 量 A B 1 0 2 2 1 2 0 1 3 1 3 2 9 19 单 位 价 格 （ 元 /g） 3.5 3 6 5 2.7 2.2 （五）合理配料问题的数学模型 设：六种营养物分别各服用设：六种营养物分别

19、各服用x x1 1g g，x x2 2g g，x x3 3g g，x x4 4g g，x x5 5g g，x x6 6g g。则数学模型：。则数学模型： 12345612345616022290332190 xxxxxxxxxxxxxx 123456min3.53652.72.2Zxxxxxx （六）合理下料问题的数学模型例例2.7 2.7 某车间有一批长度为某车间有一批长度为180cm180cm的钢管，为着的钢管，为着制造零件的需要，要将其截成三种不同长度的制造零件的需要，要将其截成三种不同长度的管料：管料：70cm70cm、52cm52cm、35cm35cm。规定这三种管料的。规定这三种管

20、料的需要量分别不少于需要量分别不少于100100根、根、150150根和根和100100根。问根。问题是应如何下料能使消耗的钢管数量最少？题是应如何下料能使消耗的钢管数量最少？解：设在解：设在180cm180cm长的钢管上能够下出长的钢管上能够下出U U个个70cm70cm的零的零件，件，V V个个52cm52cm的零件和的零件和W W个个35cm35cm的零件，则的零件，则U U、V V、W W个零件必须符合个零件必须符合: :7070U U+52+52V V+35+35W W180180（六）合理下料问题的数学模型 经过试算，可得经过试算，可得8 8种下料方式，见表：种下料方式，见表： 下

21、下 料料 方方 式式 零零 件件 尺尺 寸寸 （ 一一 ） （ 二二 ） （ 三三 ） （ 四四 ） （ 五五 ） （ 六六 ） （ 七七 ） （ 八八 ） 零零 件件 需需 要要 量量 70 2 1 1 1 0 0 0 0 100 52 0 2 1 0 3 2 1 0 150 35 1 0 1 3 0 2 3 5 100 余余 料料 5 6 23 5 24 6 23 5 设：设：x x1 1、x x2 2、x x3 3、x x4 4、x x5 5、x x6 6、x x7 7、x x8 8分别分别表示这八种下料方式钢管消耗的总根数，表示这八种下料方式钢管消耗的总根数，则数学模型则数学模型：12

22、342356713467818210023215032351000 xxxxxxxxxxxxxxxxx12345678min56235246235Zxxxxxxxx2 2、解的基本定理、解的基本定理 线性规划问题的可行域是凸集（凸多边形）。线性规划问题的可行域是凸集（凸多边形）。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 最优解一定是在凸集的某一顶点实现（顶点最优解一定是在凸集的某一顶点实现（顶点数目不超过数目不超过 个）个）Cmn 先找一个基本可行解，与周围顶点比较，如先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。不是最大，继续比较，直到找出最大为止。3 3、解

23、的情况、解的情况唯唯 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行解有最优解有最优解无最优解无最优解 建立直角坐标建立直角坐标 ，图中阴影部分及，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。边界上的点均为其解，是由约束条件来反映的。例一、例一、) 0 , (21xx 0,0124 16 482122232max2121212121xxxxxxxxxxZ三、图三、图 解解 法法01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解：解：x1 = 4 x2 = 2有唯一最优解，有唯一最优解，Z = 14Z = 14x2 x1(4 2) 0012

24、4 16 4821222322121212121xxxxxxxxxxZ,max 例二、例二、 例三、例三、 0,02 1223622max212212121xxxxxxxxxZ无穷多最优解无穷多最优解 0,122min21212121xxxxxxxxZ无界解无界解x1x1x2 x2 0,6321 23min2121211xxxxxxxxZx1x2 无可行解无可行解 0,1505 10032170251810max2121212121xxxxxxxxxxZ 0,4 3 22232max212212121xxxxxxxxxZ例四、例四、练习练习1 效效 产品产品机床机床 率率 A B机床台数机床台

25、数 30 40 40 55 30 40 23 37 20 2 2、 某车间用三种不同型号某车间用三种不同型号的机床的机床、，加工，加工A A、B B两种零件，机床台数、生产两种零件，机床台数、生产效率如表所示。问如何合理效率如表所示。问如何合理安排机床的加工任务，才能安排机床的加工任务，才能使生产的零件总数最多？使生产的零件总数最多？1 1、某工厂生产、某工厂生产A A1 1、A A2 2 两种两种产品，产品， 每件可获利润每件可获利润1515、2020元。每个产品都经过三道元。每个产品都经过三道工序，资料如表所示。工厂工序，资料如表所示。工厂应如何安排生产计划使获得应如何安排生产计划使获得的

26、总利润最多？试写出此问的总利润最多？试写出此问题的数学模型。题的数学模型。 工工 产品产品工序工序 时时 A A1 1 A A2 2可用工时可用工时 3 2 800 2 3 800 1 1 350习习 题题 13 3、用图解法求解下面的线性规划问题：、用图解法求解下面的线性规划问题： 0,6 62310 2 34max2121212121xxxxxxxxxxZ 0,8102284max21212121xxxxxxxxZ 0,10 44318605252max21221212121xxxxxxxxxxxZx1x2 123(2)型型机机床床的的台台数数种种零零件件表表示示生生产产设设变变量量iji

27、jABx323122211211372330554030 xxxxxxZ max ).,.(213210204040323122211211jixxxxxxxij且且为为整整数数x1x2 123(1)（一）、基本思想（一）、基本思想 将模型的一般形式变成标准形式，再根据标准型模型，将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。当目标函数达到最大时，得到最优解。（

28、二）、线性规划模型的标准形式（二）、线性规划模型的标准形式 )n 2 1(j 0 m) 2 1(i jijijjjxbxaxcZmax1 1、标准形式、标准形式四、单纯形法四、单纯形法 2 2、特征：、特征： . .目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值； . .所有约束条件（非负条件除外）都是等式，所有约束条件（非负条件除外）都是等式，右端常数项为非负；右端常数项为非负； . .变量为非负。变量为非负。3、转换方式：、转换方式： . .目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函，则可将目标函数乘以（数乘以（1 1），可化

29、为求极大值问题。），可化为求极大值问题。 jjxcZmin jjxcZZmax也就是：令也就是：令 ，可得到上式。，可得到上式。ZZ 即即. .约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量. .变量的变换变量的变换 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx例例 一、将下列线性规划问题化为标准形式一、将下列线性规划问题化为标准形式 ,0,52324 7 532min3

30、21321321321321xxxxxxxxxxxxxxxZ为无约束（无非负限制）为无约束（无非负限制） 解解: : 用用 替换替换 ，且，且 ， 54xx 3x0,54 xx将第将第3 3个约束方程两边乘以个约束方程两边乘以（1 1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入变量引入变量例二、将线性规划问题化为标准型例二、将线性规划问题化为标准型 ,043 5832max

31、21212121xxxxxxxxZ为无约束为无约束解：解： 0, 4 )(3 5 )(83)(2min6543164315431431xxxxxxxxxxxxxxxxZ（三）、单纯形法（三）、单纯形法例一、例一、 0,124 16 482122232max2121212121xxxxxxxxxxZ变成标准型变成标准型 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ约束方程的系数矩阵约束方程的系数矩阵 654321100040010004001021000122ppppppA IppppB1

32、00001000010000165436543 xxxx,21xx ,为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20 Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40A=x1 x2 x3 x41 1 1 01 2 0 1可行解：可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。等。设设B= 1 0 0 1，令令，则 | B |=10,令令 x1=x2 =0，则，则 x

33、3 =3, x4=4，X=(0,0,3,4)T回顾：回顾：x3 x4基变量基变量令 B=1 1 1 0 x1 x3 ，则令令 x2=x4 =0，则，则 x3 =-1, x1=4，X=(4,0,-1,0)T| B |=-10,非基本可行解非基本可行解基本可行解基本可行解标准化标准化令：令：12x 16x 8x 12x 0654321 xx则：则： 基本可行解为基本可行解为（0 0 12 8 16 120 0 12 8 16 12） 此时，此时，Z = 0Z = 0 然后，找另一个基本可行解。即将非基变量然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环换入基变量中，但

34、保证其余的非负。如此循环下去，直到找到最优解为止。下去，直到找到最优解为止。 注意：为尽快找到最优解，在换入变量时有一定注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。的要求。如将目标系数大的先换入等。找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基本可行解）（找更大的基本可行解）最优解最优解是是否否循循环环直到找出为止，核心是：变量迭代直到找出为止，核心是：变量迭代结束结束其步骤总结如下：其步骤总结如下：当当 时，时， 为换入变量为换入变量01x2x0 4120 160 2 802122652423 xxxx

35、xxx确定换出变量确定换出变量3)412 28 212min( 2x6x为换出变量为换出变量接下来有下式：接下来有下式： 4 124 3 416 2 82 1 212 2 6215124123xxxxxxxxxx 用高斯法，将用高斯法，将 的系数列向量换为单位列向量，的系数列向量换为单位列向量，其步骤是：其步骤是：2x(3)(3,)(42-2)()(2,)(42-(1)(1 ,4)4()4( 结果是：结果是：621561461341 3 416 21 2 2126 xxxxxxxxxx 1 2 3 4 4 12 4 3 416 2 8 2 1 212 2 6215124123xxxxxxxxx

36、x 代入目标函数：代入目标函数：616143294392xxxxZ 有正系数表明：还有潜力可挖，没有达到最大值；有正系数表明：还有潜力可挖，没有达到最大值；此时：令此时：令 得到另一个基本可行解得到另一个基本可行解 （0，3，6，2，16，0）1x 有负系数表明：若要剩余资源发挥作用，就必须有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当支付附加费用。当 时，即不再利用这些资源。时，即不再利用这些资源。6x06 x9 , 061 Zxx如此循环进行，直到找到最优为止。如此循环进行，直到找到最优为止。本例最优解为：本例最优解为： （4，2，0，0，0，4）14maxZ 81231454

37、 xxzjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc 0 0 ijijjacc )min(0kjkjiaab （四）、单纯形表（四）、单纯形表判定标准：判定标准：0 0:min0 0:maxz j jjjjjjjjijijjjczzcczzcaczc 若求若求 或或 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例 题：题：cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5

38、 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 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

39、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 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

40、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 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-Z

41、4412 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 0cji练习练习 0,24261553221212121 xxxxxxxxMaxZ 0,24 2615 532432142132121 xxxxxxxxxxxxMaxZ 0 0 -1/12 -7/24-33/4-Z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cji15/43/4011/4-1/810 -1/125/24（一）、模型情况（一）、模型情况 变

42、变 量：量：xj0 xj0 xj无约束无约束 结结1、组成、组成 约束条件：约束条件： = b 目标函数：目标函数： max min 果果2 、变量、变量 xj0 令令 xj= -xj ， xj0 xj0 不处理不处理 xj 无约束无约束 令令xj = xj xj, xj0 , xj0 唯一最优唯一最优无穷最优无穷最优无界解无界解无可行解无可行解五、单纯形法的进一步讨论五、单纯形法的进一步讨论3 3、约束、约束 条件：条件：bxpbxpbxpjjjjjj 加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上axaxsxsx例：例： 0,1 2324112 3min3213

43、1321321321xxxxxxxxxxxxxxZ 0, 1 2 3 24 11 2 3min32173165 3214321321xxxxxxxxxxxxxxxxxxZ 加入人工变量后，目的是找到一个单位向量，叫人加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大的取值。一般可采用两种方法处理：大M法和两阶段法和两阶段法。法。 即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M M（任意大正数），如果是求极大值，需加（任意大正数），如果是求极大值，需加-

44、 -M；如果；如果是求极小值，需加是求极小值，需加M。如基变量中还存在。如基变量中还存在M，就不能，就不能实现极值。实现极值。76543217654321003max 003min MxMxxxxxxZMxMxxxxxxZ 或或：如如上上例例：. .大大M法：法：来来判判断断计计算算过过程程如如下下：用用 0 jjzccj-31100MMcBxBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1Mx610100-11-21

45、1x31-2010001-Z-11-M00M03M-1iicj-31100MMcBxBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-21x31-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/3ii最优解为最优解为（4 1 9 0 0 0 0），Z = 2 用计算机处理数据时，只能用很大的数用计算机处理数据时，只能用很大的数代替代替M, ,可能造成计算机上的错误，故多

46、采用两阶段可能造成计算机上的错误，故多采用两阶段法。法。 第一阶段：第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型： 0 00min11111111111mnmmnnmnmnnnnmnnxxbxxaxabxxaxaxxxxW.两阶段法：两阶段法： 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若W=0,W=0,说明问题说明问题存在基本可行解，可以进行第二个阶段；否则，原问存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。题无可行解，停止运算。 第二阶段：在第一阶段的最终表中，去掉人工变第二阶段：在第一阶段的最

47、终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。作为第二阶段计算的初始表（用单纯形法计算）。例：例： 0, 1 2 3 24 11 2 3min32173165 3214321321xxxxxxxxxxxxxxxxxxZ第一阶段第一阶段cj0000011cBxBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000 x4103-20100-11x610100-11-210 x31-2010001-Z

48、10-100103i0 x4123001-22-50 x210100-11-20 x31-2010000-Z00000011cj-31100cBxBbx1x2x3x4x50 x4123001-241x210100-11x31-20100-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z20001/31/3i第二阶段第二阶段 最优解为（最优解为（4 1 9 0 04 1 9 0 0），目标函数），目标函数 Z = -2Z = -21 1、目标函数：、目标函数：max , min 设规划模型约束条件为设规划模型约束条件为 ，需加入人工变，需加入人

49、工变量量 ，而得到一个，而得到一个mm的单位矩阵，即基变量组合。的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当人工变量，表示原问题有解。若当 ，而还有人，而还有人工变量（非零）时，则表示原问题无可行解。工变量（非零）时，则表示原问题无可行解。axbxpJJ 0 jjzc3231 323x , 3 :022122xxxbbii，变换有：两端乘如、3 3、无、无可行解的判断：运算到检验数全负

50、为止，可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。仍含有人工变量，无可行解。)0 )0( 0 0 min max 4jjjjjjjjczczzczc（或或、检验数： 5 5、退化：、退化： 即计算出的即计算出的（用于确定换（用于确定换出变量）存在有两个以上相同的最小比值，出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。等于零，这就是退化（会产生退化解）。 虽任意换出变量，目标函数值不变，但虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例此时不同的基却表示为同

51、一顶点，其特例是永远达不到最优解。需作如下处理：是永远达不到最优解。需作如下处理： . .当当 中出现两个以上最大值中出现两个以上最大值时，时，选下标最小的非基变量为换入变量；选下标最小的非基变量为换入变量； . .当当中出现两个以上最小值时，选下中出现两个以上最小值时，选下标最小的基变量为换出变量。标最小的基变量为换出变量。0 jjzc建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加新加变量变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法

52、法单单纯纯形形法法不不处处理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M根据上表列出初始单纯形表根据上表列出初始单纯形表 A（二）、线性规划小结（二）、线性规划小结停止停止Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一)0( lklkiiaab 计计算算lkxx替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含

53、含有有量量中中是是否否基基变变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解练习练习 0,10527532max321321321321xxxxxxxxxxxxZ 0,105270532max654321653214321654321xxxxxxxxxxxxxxxMxxMxxxxZ-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-532

54、cj0-M0-5+2M3-4M2+3M-Z51-101-5210 x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cji作业作业 无无约约束束43214321432143214321 , 0,2232143 22 4 5243xxxxxxxxxxxxxxxxxxxxMinZ0, 02 )( 23214 )( 3 2 )( 2 400)( 5243max0.,1053110965321865321765321109876532165654xxxxxxxxxxxxxxxxxxxxxMxxxMxxxxxxZxxxxx令：0100 x2-4-2/35/3-10/3x

55、1300-Z-1/3-1/300-2/32/3-1/32/3x2-440 10-1/31/3105/3-5/310/340/310/3 x804-1/31/301-1/31/3-5/34/3 x7-Mx10 x9x8x7x6x5x3bxBcB-M00-M5-52cji 3101M 352M 37 M37M34 M344M 4M-4311x2-43-6M-21-4x130-M005-3M3M-52-3M-Z2/31-100-22-12x10-M14 400101-1314 4 x8020001-11-22 x7-Mx10 x9x8x7x6x5x3bxBcB-M00-M5-52cji 0100 x

56、2-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-15/26 1 x65-111/25/200-5/210 5 x90 x10 x9x8x7x6x5x3bxBcB-M00-M5-52cji 0100 x2-4-13-45-10 x13-M00-M+41-1-68-Z-0001-11-22x2-46001-12-2512 2 x80-1103-11-54 x90 x10 x9x8x7x6x5x3bxBcB-M00-M5-52cji 一般而言，一个经济、管理问题凡一般而言，一个经济、管理问题

57、凡是满足以下条件时，才能建立线性规划是满足以下条件时，才能建立线性规划模型。模型。 . .要求解问题的目标函数能用数要求解问题的目标函数能用数值指标来反映，且为线性函数；值指标来反映，且为线性函数； . .存在着多种方案；存在着多种方案； . .要求达到的目标是在一定条件要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不下实现的，这些约束可用线性等式或不等式描述。等式描述。六、线性规划模型的应用六、线性规划模型的应用（一）、资源的合理利用（一）、资源的合理利用 一般提法：一般提法： 某厂计划在下一生产周期内生产某厂计划在下一生产周期内生产B B1 1,B,B2 2, B, Bn n种

58、产品，种产品，要消耗要消耗A A1 1,A,A2 2, A, Am m种资源，已知每件产品所消耗的资源种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？使获得的总利润最大？单件 产 消耗 品资源资源限制单件利润nBB 1mAA 1mbb 1nCC 1mnmnaaaa 1111 0maxjijijjjxbxaxcZ模型（二）、生产组织与计划问题（二）、生产组织与计划问题 一般提法：某工厂用机床一般

59、提法：某工厂用机床A A1 1,A,A2 2, A, Am m 加工加工B B1 1,B,B2 2, , B Bn n 种零件。在一个周期内，各机床可能工作的机时（台种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时件的时间（机时/个）和加工每个零件的成本（元个）和加工每个零件的成本（元/个）如个）如表所示，问如何安排各机床的生产任务，才能完成加工任表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？务，又使总成本最低？加工 零 时间 件机床机时限制必须零件数nBB

60、1mAA 1maa 1nbb 1mnmnaaaa 1111加工 零 成本 件机床nBB 1mAA 1mnmncccc 1111 0 min ( 11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一一组组变变量量）。模模型型：的的数数量量，求求在在一一生生产产周周期期加加工工零零件件为为机机床床设设（三）、合理下料问题（三）、合理下料问题 一般提法一般提法 设用某种原材料截取零件设用某种原材料截取零件A A1 1,A,A2 2, A, Am m的毛坯。根据以的毛坯。根据以往的经验，在一种原材料上可以有往的经验，在一种原材料上可以有B B1 1,B,B2 2, B, B