《运筹学：2线性规划》由会员分享，可在线阅读，更多相关《运筹学：2线性规划（82页珍藏版）》请在金锄头文库上搜索。
1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题的求解方法线性规划问题的求解方法线性规划的图解法线性规划的图解法线性规划的单纯形法线性规划的单纯形法单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用 为了完成一项任务或达到一定的目的，怎样用最少的为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。达到一定的目的，这个过程就是规划。例一、有一正方形铁皮，如何截取例一、有一
2、正方形铁皮，如何截取 x x 使容积为最大？使容积为最大？xa此为无约束极值问题此为无约束极值问题一、线性规划问题及其数学模型线性规划问题及其数学模型（一）、问题的提出一）、问题的提出 设设 备备产产 品品 A B C D利润（元）利润（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12 例二、已知资例二、已知资料如下表所示，料如下表所示，问如何安排生产问如何安排生产才能使利润最大才能使利润最大？或如何考虑利？或如何考虑利润大，产品好销。润大，产品好销。模模 型型max Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12
3、 x1 + 2x2 8 4x1 16 4x2 12此为带约束的极值问题此为带约束的极值问题问题中总有未知的变量，需要我们去解决。问题中总有未知的变量，需要我们去解决。 要求：有目标函数及约束条件，一般有非负条件要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。存在，由此组成规划数学模型。 如果在规划问题的数学模型中，变量是连续的如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次方）（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性
4、的。反之，就是非线性的规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。规划问题（其中一个条件符合即可）。（二）、数学模型（二）、数学模型 1 1、目标函数：目标函数：约束条件：约束条件：2 2、线性规划数学模型的一般形式、线性规划数学模型的一般形式也可以记为如下形式也可以记为如下形式：目标函数：目标函数：约束条件：约束条件：如将上例用表格表示如下：如将上例用表格表示如下：设变量设变量 产产 品品 j 设设 备备 i 有效台时有效台时 利润利润 向向 量量 形形 式：式：矩阵形式：矩阵形式：规规划划确定型确定型随机型随机型静态规划静态规划动态规划动态规划线线 性规
5、性规 划划非线性规划非线性规划 整数规划整数规划 非整数规划非整数规划整数规划整数规划非整数规划非整数规划3、规划类型、规划类型一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式二、线性规划问题的求解方法二、线性规划问题的求解方法（一）、求解方法（一）、求解方法1 1、解的概念、解的概念 可行解：满足约束条件可行解：满足约束条件、的解为可行解。的解为可行解。所有解的集合为可行解的集或可行域。所有解的集合为可行解的集或可行域。
6、最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。 基：基：B B是矩阵是矩阵A A中中m mn n阶非奇异子矩阵阶非奇异子矩阵（B0B0），则），则B B是一个基。是一个基。则称则称 Pj ( j = 1 2 m) 为基向量。为基向量。 Xj 为基变量，否则为非基变量。为基变量，否则为非基变量。（二）、线性规划问题的解（二）、线性规划问题的解 基本解：满足条件基本解：满足条件，但不满足条件，但不满足条件的的所有解，最多为所有解，最多为 个。个。 基本可行解：满足非负约束条件的基本基本可行解：满足非负约束条件的基本解，简称基可行解。解，简称基可行解。 可行基：对应于基
7、可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解2 2、解的基本定理、解的基本定理 线性规划问题的可行域是凸集（凸多边形）。线性规划问题的可行域是凸集（凸多边形）。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 最优解一定是在凸集的某一顶点实现（顶点最优解一定是在凸集的某一顶点实现（顶点数目不超过数目不超过 个）个） 先找一个基本可行解，与周围顶点比较，如先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。不是最大，继续比较，直到找出最大为止。3 3、解的情况、解的情况唯唯 一一 解解无无 穷穷 解解无无 界界
8、 解解无可行解无可行解有最优解有最优解无最优解无最优解 建立直角坐标建立直角坐标 ，图中阴影部分及边，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。界上的点均为其解，是由约束条件来反映的。例一、例一、三、图三、图 解解 法法01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解：解：x1 = 4 x2 = 2有唯一最优解，有唯一最优解，Z = 14Z = 14x2 x1(4 2) 例二、例二、 例三、例三、无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 x1x2 无可行解无可行解例四、例四、练习练习1 效效 产品产品机床机床 率率 A B机床台数
9、机床台数 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元。每个产品都经过三道元。每个产品都经过三道工序，资料如表所示。工厂工序，资料如表所示。工厂应如何安排生产计划使获得应如何安排生产计划使
10、获得的总利润最多？试写出此问的总利润最多？试写出此问题的数学模型。题的数学模型。 工工 产品产品工序工序 时时 A A1 1 A A2 2可用工时可用工时 3 2 800 2 3 800 1 1 350习习 题题 13 3、用图解法求解下面的线性规划问题：、用图解法求解下面的线性规划问题：x1x2 123(2)x1x2 123(1)（一）、基本思想（一）、基本思想 将模型的一般形式变成标准形式，再根据标准型模型，将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一
11、个基本可行解，是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。当目标函数达到最大时，得到最优解。（二）、线性规划模型的标准形式（二）、线性规划模型的标准形式1 1、标准形式、标准形式四、单纯形法四、单纯形法 2 2、特征：、特征： . .目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值； . .所有约束条件（非负条件除外）都是等式，所有约束条件（非负条件除外）都是等式，右端常数项为非负；右端常数项为非负； . .变量为非负。变量为非负。3、转换方式：、转换方式： . .目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即
12、，则可将目标函，则可将目标函数乘以（数乘以（1 1），可化为求极大值问题。），可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即.约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量.变量的变换变量的变换 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：例例 一、将下列线性规划问题化为标准形式一、将下列线性规划问题化为标准形式为无约束（无非负限制）为无约束（无非负限制） 解解: : 用用 替换替换 ，且，且 ， 将第将第3 3个约束方程两边乘以个约束方程两边乘以（1 1）将极小值
13、问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：引入变量引入变量例二、将线性规划问题化为标准型例二、将线性规划问题化为标准型为无约束为无约束解：解：（三）、单纯形法（三）、单纯形法例一、例一、变成标准型变成标准型约束方程的系数矩阵约束方程的系数矩阵为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立令：令：则：则： 基本可行解为基本可行解为（0 0 12 8 16 120 0 12 8 16 12） 此时，此时，Z = 0Z = 0 然后，找另一个基本可行解。即将非基变量然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其
14、余的非负。如此循环换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。下去，直到找到最优解为止。 注意：为尽快找到最优解，在换入变量时有一定注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。的要求。如将目标系数大的先换入等。找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基本可行解）（找更大的基本可行解）最优解最优解是是否否循循环环直到找出为止，核心是：变量迭代直到找出为止，核心是：变量迭代结束结束其步骤总结如下：其步骤总结如下：当当 时，时， 为换入变量为换入变量确定换出变量确定换出变量为换出变量为
15、换出变量接下来有下式：接下来有下式： 用高斯法，将用高斯法，将 的系数列向量换为单位列向量，的系数列向量换为单位列向量，其步骤是：其步骤是：结果是：结果是：代入目标函数：代入目标函数： 有正系数表明：还有潜力可挖，没有达到最大值；有正系数表明：还有潜力可挖，没有达到最大值；此时：令此时：令 得到另一个基本可行解得到另一个基本可行解 （0，3，6，2，16，0） 有负系数表明：若要剩余资源发挥作用，就必须有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当支付附加费用。当 时，即不再利用这些资源。时，即不再利用这些资源。如此循环进行，直到找到最优为止。如此循环进行，直到找到最优为止。本例最
16、优解为：本例最优解为： （4，2，0，0，0，4）（四）、单纯形表（四）、单纯形表判定标准：判定标准：若求若求 或或例例 题：题：cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000x3x4x5x61281612 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 2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000x3x4x516 4 0 0 0 1 0 -Z3x23010001/42620100-1/210010 0-1/2cj 2 3 0
17、 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 2 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/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x
18、60203x6 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 0 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 0cjcj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4
19、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 0 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 0cj练习练习 0 0 -1/12 -7/24-33/4-Z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810 -1/125/24（一）、模型
20、情况（一）、模型情况 变变 量：量：xj0 xj0 xj无约束无约束 结结1、组成、组成 约束条件：约束条件： = b 目标函数：目标函数： max min 果果2 、变量、变量 xj0 令令 xj= -xj ， xj0 xj0 不处理不处理 xj 无约束无约束 令令xj = xj xj, xj0 , xj0 唯一最优唯一最优无穷最优无穷最优无界解无界解无可行解无可行解五、单纯形法的进一步讨论五、单纯形法的进一步讨论3 3、约束、约束 条件：条件：加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上例：例：4 4、目标函数：、目标函数：max , min 设规划模型约束条
21、件为设规划模型约束条件为 ，需加入人工变量，需加入人工变量 ，而得到一个，而得到一个mm的单位矩阵，即基变量组合。因人工的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当量，表示原问题有解。若当 ，而还有人工变量，而还有人工变量（非零）时，则表示原问题无可行解。（非零）时，则表示原问题无可行解。 加入人工变量后，目的是找到一个单位向量，叫人加入人工变量后，目的是找到一个单位向量，叫人工基。其
22、目标价值系数要确定，但不能影响目标函数工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大的取值。一般可采用两种方法处理：大M法和两阶段法和两阶段法。法。 即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M M（任意大正数），如果是求极大值，需加（任意大正数），如果是求极大值，需加- -M；如果；如果是求极小值，需加是求极小值，需加M。如基变量中还存在。如基变量中还存在M，就不能，就不能实现极值。实现极值。.大大M法：法：cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx7
23、1-20100011-Z-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1Mx610100-11-211x31-2010001-Z-11-M00M03M-1cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-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/3最优解为最优解为（4 1 9 0
24、 0 0 0），Z = 2 用计算机处理数据时，只能用很大的数用计算机处理数据时，只能用很大的数代替代替M, ,可能造成计算机上的错误，故多采用两阶段法。可能造成计算机上的错误，故多采用两阶段法。 第一阶段：第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：.两阶段法：两阶段法： 对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若W=0,W=0,说明问题说明问题存在基本可行解，可以进行第二个阶段；否则，原问存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。题无可行解，停止运算。 第二阶段：在第一阶段的最终表中，去
25、掉人工变第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。作为第二阶段计算的初始表（用单纯形法计算）。例：例：第一阶段第一阶段cj0000011cBxBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000x4103-20100-11x610100-11-210x31-2010001-Z10-1001030x4123001-22-50x210100-11-20x31-201000
26、0-Z00000011cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-11x31-20100-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z20001/31/3第二阶段第二阶段 最优解为（最优解为（4 1 9 0 04 1 9 0 0），目标函数），目标函数 Z = -2Z = -26 6、无、无可行解的判断：运算到检验数全负为止，可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。仍含有人工变量，无可行解。 8 8、退化：、退化： 即计算出的即计算出的（用于确定换（用于确定换出变量）存在有
27、两个以上相同的最小比值，出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。等于零，这就是退化（会产生退化解）。 虽任意换出变量，目标函数值不变，但虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例此时不同的基却表示为同一顶点，其特例是永远达不到最优解。需作如下处理：是永远达不到最优解。需作如下处理： . .当当 中出现两个以上最大值中出现两个以上最大值时，时，选下标最小的非基变量为换入变量；选下标最小的非基变量为换入变量； . .当当中出现两个以上最小值时，选下中出现两个以上最小
28、值时，选下标最小的基变量为换出变量。标最小的基变量为换出变量。建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加新加变量变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj = xj - xj xj 0xj 0令令 xj =- xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M根据
29、上表列出初始单纯形表根据上表列出初始单纯形表 A（二）、线性规划小结（二）、线性规划小结A练习练习-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作业作业0100x2-4-2/35/3-10/3x1300-Z-1/3-1/300-2/32/3-1/32/3x2-440 10-1/31/3105
30、/3-5/310/340/310/3 x804-1/31/301-1/31/3-5/34/3 x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj4M-4311x2-43-6M-21-4x130-M005-3M3M-52-3M-Z2/31-100-22-12x10-M14 400101-1314 4 x8020001-11-22 x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-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/2
31、6 1 x65-111/25/200-5/210 5 x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-4-13-45-10x13-M00-M+41-1-68-Z-0001-11-22x2-46001-12-2512 2 x80-1103-11-54 x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj 一般而言，一个经济、管理问题凡一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划是满足以下条件时，才能建立线性规划模型。模型。 . .要求解问题的目标函数能用数要求解问题的目标函数能用数值指标来反映，且为线性函数；值指标来反映，
32、且为线性函数； . .存在着多种方案；存在着多种方案； . .要求达到的目标是在一定条件要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不下实现的，这些约束可用线性等式或不等式描述。等式描述。六、线性规划模型的应用六、线性规划模型的应用（一）、资源的合理利用（一）、资源的合理利用 一般提法：一般提法： 某厂计划在下一生产周期内生产某厂计划在下一生产周期内生产B B1 1,B,B2 2, , B Bn n种产品，要种产品，要消耗消耗A A1 1,A,A2 2, , A Am m种资源，已知每件产品所消耗的资源数、种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的
33、利润如表所示，每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？的总利润最大？单件 产 消耗 品资源资源限制单件利润（二）、生产组织与计划问题（二）、生产组织与计划问题 一般提法：某工厂用机床一般提法：某工厂用机床A A1 1,A,A2 2, , A Am m 加工加工B B1 1,B,B2 2, , B Bn n 种零件。在一个周期内，各机床可能工作的机时（台时）种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的，工厂必须完成各
34、种零件的数量、各机床加工每个零件的时间（机时时间（机时/个）和加工每个零件的成本（元个）和加工每个零件的成本（元/个）如表所个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？又使总成本最低？加工 零 时间 件机床机时限制必须零件数加工 零 成本 件机床（三）、合理下料问题（三）、合理下料问题 一般提法一般提法 设用某种原材料截取零件设用某种原材料截取零件A A1 1,A,A2 2, , A Am m的毛坯。根据以的毛坯。根据以往的经验，在一种原材料上可以有往的经验，在一种原材料上可以有B B1 1,B,B2 2, ,
35、B Bn n种不同的下种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又使原件的需要量如表所示，问应如下料才能既满足需要又使原材料消耗最少？材料消耗最少？下料 下料毛 件数 方式坯型号需 要毛坯数 现有一批某种型号的圆钢长现有一批某种型号的圆钢长8 8米，需要截取米，需要截取2.52.5米米长的毛坯长的毛坯100100根，长根，长1.31.3米的毛坯米的毛坯200200根。问如何才能既满足需根。问如何才能既满足需要，又能使总的用料最少？要，又能使总的用料最少？100200 3 2 1 0
36、0 2 4 62.5米米1.3米米需要需要根数根数 一一 二二 三三 四四下料下料 下料下料毛毛 件数件数 方式方式坯型号坯型号设变量为设变量为 第第 j 种方法的所有种方法的所有原料件数原料件数例题例题1 1： （四）、合理配料问题（四）、合理配料问题 一般提法一般提法 某饲养场用某饲养场用n n种饲料种饲料B B1 1,B,B2 2, , B Bn n配置成含有配置成含有m m种营种营养成分养成分A A1 1,A,A2 2, , A Am m的混合饲料，其余资料如表所示。的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总问应如何配料，才能既满足需要，又使混合饲料的
37、总成本最低？成本最低？ 含 饲 量 料成分最 低需要量原料单价例题例题2 2：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，问两种食物各食用多少，才能既满足需要、又使才能既满足需要、又使总费用最省？总费用最省？设：设：Xj 表示表示Bj 种食种食物用量。物用量。 2 1.5原料单价原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 甲甲 乙乙 含含 食食 量量 物物成分成分（五）、运（五）、运 输输 问问 题题已知资料如表所示：已知
38、资料如表所示：单位 销 运价 地产地产量销 量模型如下：模型如下：某运输问题的资料如下：某运输问题的资料如下：6483销量7524852431921092产量单位 销地 运价产地例题例题3：（六）、作物布局问题（六）、作物布局问题单 土 产 地作物播种面积土地面积此外，还有连续投资、投入产出等模型问题。此外，还有连续投资、投入产出等模型问题。1、用图解法求下列线性规划的最优解：、用图解法求下列线性规划的最优解：2、求下列线性规划的解：、求下列线性规划的解： 3、用大、用大M法或两阶段法求下列线性规划问题：法或两阶段法求下列线性规划问题： -1-Z-a+8-12a4x1-21-11x22-1212x5x6x5x4x3x2x1bxBcB22cj1 1、把表中缺少的项目填上适当的数或式子、把表中缺少的项目填上适当的数或式子2 2、要使上表成为最优表，、要使上表成为最优表，a应满足什么条件应满足什么条件3 3、何时有无多最优解、何时有无多最优解4 4、何时无穷多最优解、何时无穷多最优解5 5、何时以、何时以x3替换替换x1
