运筹学第一章.doc

第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1(引例) 配比问题用浓度为45%和92%的硫酸配置100t浓度为80%的硫酸。取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有：请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t，则有： 2. 生产计划问题 A B C每天可利用资源量 工时（单位）1 1 1 3 材料（t）1 4 7 9 产品利润 （元/t）2000 3000 1000如何制定生产计划，使三种产品总利润最大？考虑问题：（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1定义：对于求取一组变量xj (j =1,2,.,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。2.配比问题和生产计划问题的线性规划模型的特点： 用一组未知变量表示要求的方案，这组未知变量称为决策变量； 存在一定的限制条件，且为线性表达式； 有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。3LP的数学描述(数学模型)： （1）一般形式 （2）紧缩形式（3）矩阵形式其中 : （4）向量矩阵形式：其中：三、LP的标准型： 1、LP标准型的概念 （1）什么是LP的标准型？ （2）LP标准型的特点 目标函数约定是极大化Max（或极小化Min）; 约束条件均用等式表示; 决策变量限于取非负值; 右端常数均为非负值 ;2、LP问题的标准化 （1）目标函数的标准化 MinZ=CX 令Z=-Z则MaxZ=-CX（2） 约束条件的标准化 & 约束条件是类型 左边 加 非负松弛变量 & 约束条件是类型 左边 减 非负剩余变量 & 变量符号不限 引入新变量 课堂练习1-2解： x3；令约束1引松弛变量；约束2引剩余变量；约束3变号；目标函数标准化，引入变换Z=-Z；整理；得出： 即： 1-2 线性规划问题解的概念和性质一、LP问题的各种解 1. 可行解：满足约束条件和非负条件的决策变量的一组取值。2. 最优解：使目标函数达到最优值的可行解3、基本解：设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称为LP的基本解。4.基本可行解（对应的基为可行基）：满足非负条件的基本解。5.基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。非可行解 可行解 基本可行解 基本解最优解基本最优解二、 线性规划的图解法1什么是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。2. 图解法举例 例11 maxZ=2x1+3x2s.t.实施图解法，以求出最优生产计划（最优解）。 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。第一步：建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。 用x1轴表示产品A的产量，用x2轴表示产品B的产量。 第二步：对约束条件加以图解。 第三步：画出目标函数等值线，结合目标函数的要求求出最优解最优生产方案。约束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。 以第一个约束条件1/3 x1+1/3 x2 1 为例说明约束条件的图解过程。如果全部的劳动工时都用来生产A 产品而不生产B产品，那么A产品的最大可能产量为3吨，计算过程为：1/3x1+1/301 x13这个结果对应着图中的点A(3,0),同样我们可以找到B产品最大可能生产量对应的点B(0,3)。连接A、B两点得到约束 1/3 x1+1/3 x2 1 所代表的半平面的边界:1/3 x1+1/3 x2 1， 即直线AB。第二个约束条件的边界 直线CD: 1/3x1+4/3 x2 =3两个约束条件及非负条件x1,x2 0所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。 令 Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。 这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c0和c=6，就能看出目标函数值递增的方向，用箭头标出这个方向。图中两条虚线 l1和l2就分别代表目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头表示使两种产品的总利润递增的方向。沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E, E点就是要求的最优点，它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值 Zmax=21+32=8（千元），x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。 尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。 比如E点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。 直线AB: 1/3x1+1/3x2=1 直线CD: 1/3x1+4/3x2=3M ax Z=2 x1 +3 x2 例1-1所描述的是有唯一最优解且可行域是一个非空有界区域的情况。实际上，可行域不仅仅只有这一种可能，解的情况也是各种各样的。(1) 无穷多个最优解例12 max Z= x1 + x2 s.t 该线性规划的可行域为上图中四边形OAED（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AE重合，这个结果表明，该线性规划有无穷多个最优解线段AE上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=3。 (2) 唯一最优解 例1-3 将例1-1中目标要求改为极小化，目标函数和约束条件均不变，则可行域与例1-1相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果是有唯一最优解x1=0,x2=0,对应着图1-6中的坐标原点。 (3)无界解 max Z = x1 +2 x2s.t本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。这种情况通常称为无“有限最优解” 或“最优解无界”。如果一个实际问题抽象成像例14这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重新检查和修改模型，否则就没有实际意义。注意，对于无界可行域的情况，也可能有唯一最优解或无穷多个最优解。比如目标要求为minZ=x1+2x2或 maxZ=2x1+x2，而约束条件不变的例子。3.图解法小结 A.使用条件：仅有两个至多不超过三个决策变量的线性规划。B.基本步骤：第一步建立平面直角坐标系；第二步根据约束条件和非负条件画出可行域。第三步作出目标函数等值线（至少两条）， 结合目标函数优化要求，平移目标函数等值线求出最优解。 C.图解法的优缺点： 简单、直观但有局限性。 三、基本可行解的几何意义如何求得基本解?第一步 模型标准化；第二步 按照基本解的定义找基（非退化3阶方阵）确定基变量和非基变量；令非基变量为0，解出基变量；基变量和相应非基变量搭配构成基本解.四、线性规划解的性质1、基本概念： 凸集设K是n维欧氏空间的一个点集，若任意两点X（1）K，X（2）K的连线上的一切点：X（1）+（1-）X（2） K（01），则称K为凸集。 凸组合设X（1） ，X（2） ，X（k） 是n维欧氏空间中的K个点，若存在k个数1， 2 ， k ,满足 0i1, i=1,2, ,k； 则称X=1X（1）+2X（2）+kX(k)为X（1）, X（2） ，X（k）的凸组合。 顶点设K是凸集，XK；若X不能用 X（1） K，X（2） K 的线性组合表示，即 XX（1）+（1-）X（2） （01） 则称X为K的一个顶点（也称为极点或角点）。 2、线性规划问题解的性质定理： 定理1-1 线性规划问题的可行解集（即可行域） 是凸集。 证明思路：根据凸集定义，采用直接法证明；具体步骤：从D中任取两个不同的点， 应满足 可行解定义中相应的条件； 证明X=X(1)+(1-)X(2)D (利用，证明X满足凸集定义中相应的条件)定理1-2 线性规划几何理论基本定理若 ，则X是D的一个顶点的充分必要条件是X为线性规 划的基本可行解。证明思路：定理1-2是X是D的一个顶点 X为LP的基本可行解; 引理是X为LP的基本可行解X的正分量所对应的系数列向量线性无关; 从而将问题 转化为 X是D的一个顶点 X的正分量所对应的系数列向量线性无关证明要点：（1）引理: X为LP的基本可行解X的正分量所对应的系数列向量线性无关必要性由基本可行解定义直接证得。充分性正分量K个k=m X=(x1,x2,xm,0,0)T即为基本可行解k0因此选x4为出基变量（换出变量）。这种用来确定出基变量的规则称为 “最小比值原则”（或原则）。如果P10，会出现什么问题？ 最小比值原则会失效！基变换新的基变量x1,x5；新的非基变量x2,x3,x4；写出用非基变量表示基变量的表达式：-可得新的基本可行解 X（1）=（3，0，0，0，6）T 写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z（1）=6检验数仍有正的返回进行讨论。第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解! 为什么？分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！三、表格单纯形法： 1、 初始单纯形表的建立(1) 表格结构：qj Cj 2 3 3 0 0b xj x1 x2 x3 x4 x5CB XBXB 0 X4 3 1 1 1 1 0 0 X5 9 1 4 7 0 1-Z 0 2 3 3 0 0（2）表格设计依据： 将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：取出系数写成增广矩阵的形式： -Z X1 X2 Xn Xn+1 Xn+2 Xn+m b-Z，Xn+1，Xn+m所对应的系数列向量构成一个基 用矩阵的初等行变换将该基变成单位阵,这时 变成0，相应的增广矩阵变成如下形式：其中j=1，2，n ； 增广矩阵的最后一行就是用非基变量表示目标函数的表达式, (j=1,2,n)就是非基变量的检验数。（3）检验数的两种计算方法： 利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0； 使用计算公式 2、例1-7的表格单纯形法计算过程： CB XB Cj b xj 2 3 3 0 0 x1 x2 x3 x4 x5 qj 0 0 X4 X5 3 9 1 1 1 1 0 1 4 7 0 13/19/1 -Z 0 2 3 3 0 0 2 0 X1 X5 3 6 1 1 1 1 0 0 3 6 -1 1 3/1 6/3 -Z -6 0 1 1 -2 0 2 3 X1 X2 1 2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 -Z -8 0 0 -1 -5/3 -1/3从最优表可知:该LP的最优解是X*=(1,2,0,0,0)T，相应的目标函数最优值是Zmax=8四、单纯形法的一般描述： 1、 初始可行解的确定 (1)初始可行基的确定 观察法观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型的约束将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；线性规划限制条件都是“”或“=”类型的约束先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；等式约束左端引入人工变量的目的使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。（注意：用非基变量表示基变量的表达式）如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎么办？构造“不完全的人造基”！ 为什么初始可行基一定要选单位阵？ b列正好就是基变量的取值，检验数行和b列交叉处元素也正好对应目标函数值， 因此称b列为解答列（2）写出初始基本可行解 根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。2、建立判别准则：（1）两个基本表达式的一般形式 就LP限制条件中全部是“”类型约束，新增的松弛变量作为初始基变量的情况来描述：此时LP的标准型为 初始可行基 ：初始基本可行解： 一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式 为：用非基变量表示目标函数的表达式： （2）最优性判别定理若 是对应于基B的基本可行解， 是非基变量 的检验数，若对于一切非基变量的角指标j，均有0，则X(0)为最优解。（3）无“有限最优解”的判别定理 若 为一基本可行解，有一非基变量xk,其检验数 , 而对于i=1,2,，m，均有，则该线性规划问题没有“有限最优解”。 证明思路构造性证明：依据用非基变量表示基变量的表达式构造一族可行解，其对应的目标函数值趋于无穷大。几何意义：沿着无界边界前进的一族可行解。举例：用非基变量表示基变量的表达式 代表两个约束条件：x2对应的系数列向量P2=（1，3）T， 当前的换入变量是 X2，按最小比值原则确定换出变量： 要求： 于是：如果x2的系数列变成P2=（-1，0）T,则用非基变量表示基变量的表达式就变成； 可行性自然满足,最小比值原则失效,意即x2的值可以任意增大原线性规划无“有限最优解”。3、进行基变换（1）选择进基变量原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。（2）出基变量的确定按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行称为主元行。主元行和主元列的交叉元素称为主元素。4、主元变换（旋转运算或枢运算） 按照主元素进行矩阵的初等行变换把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）写出新的基本可行解，返回最优性检验。表格单纯形法举例 例1-7 2、例1-7的表格单纯形法计算过程： CB XB Cj b xj 2 3 3 0 0 x1 x2 x3 x4 x5 qj 0 0 X4 X5 3 9 1 1 1 1 0 1 4 7 0 13/19/1 -Z 0 2 3 3 0 0 2 0 X1X5 3 6 1 1 1 1 0 0 3 6 -1 13/16/3 -Z -6 0 1 1 -2 0 2 3 X1 X2 1 2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 -Z -8 0 0 -1 -5/3 -1/3从最优表可知:该LP的最优解是X*=(1,2,0,0,0)T， 相应的目标函数最优值是 Zmax=8单纯形法小结 （1）求解思想顶点的逐步转移，条件是使目标函数值不断得到改善。（2）表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 确定初始可行基，写出初始基本可行解第二步：最优性检验计算检验数，检查：j所有检验数是否 0？ 是结束，写出最优解和目标函数最优值；还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？第三步：基变换选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 最小比值对应的行为主元行，主元行对应的基变量为换出变量。确定进基变量和出基变量。第四步 换基迭代（旋转运算、枢运算)利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基本可行解和相应的目标函数值停止迭代的标志（停机准则）该迭代过程直至下列情况之一发生时停止： 检验数行全部变为非正值；（得到最优解）或主元列 0 （最优解无界），依据：最优性检验的两个定理：最优性判别定理；无“有限最优解”判断定理。五、各种类型线性规划的处理1、分类及处理原则：（1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。（3）类型三：目标要求是“Max”，约束条件是“”类型约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。 （4）类型四：目标要求是“Min” 方法1化为极大化问题 方法2按照极小化问题直接在单纯形表格上计算处理，但 相应的原则要作改动。 2、处理人工变量的方法：（1）大M法在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！结 果 最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值； 最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！（2） 两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。 求解结果W最优值=0即所有人工变量取值全为0（为什么？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；W最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况；如何转化？ 选一个不是人工变量的非基变量进基， 把在基中的人工变量替换出来W最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。第二阶段： 将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论： 如何实施？需要重新建立初始单纯形表吗？实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。 在大M法中，当人工变量出基后能否立即划去该人工变量所在的系数列？ 3、用表格单纯形法直接计算极小化线性规划时要修改哪些原则？（初始表？最优解判别？换入变量？换出变量？旋转运算？引入人工变量？）A）最优性判别：所有检验数非负B）换入变量的选择原则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小；C)用大M法求解时，在目标函数中人工变量的前面添上一个很大的正系数M；六、迭代过程中可能出现的问题及处理方法1、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？（此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无“有限最优解”）2、出现若干个相同的最小比值怎么办？（说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象）3、选择进基变量时，同时有若干个正检验数，怎么选？（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基）课堂练习1-5：直接按极小化问题求解下面的LP： CB XB cj b xj 1 2 0 0 M X1 X2 X3 X4 X5 M 0 X5 X4 2 3 -1 2 -1 0 1 1 0 0 1 0 2/2 _ -Z -2M 1+M M 0 2-2M 0 2 0 X2 X4 1 3 -1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z -2 2 0 1 0 M-1由最优表得：最优解为X*=（0，1，0，3，0）T,相应的目标函数最优值为Zmin=21.4 线性规划的应用 一、使用线性规划方法处理实际问题必须具备的条件(建模条件)：1) 优化条件-问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。2) 选择条件-有多种可供选择的可行方案，以便从中选取最优方案。3）限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。 此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的二、建模步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。 第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。 决策变量的非负要求可以根据问题的实际意义加以确定。三、 经济管理领域中几类典型的LP问题 经济管理领域中有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。 尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。（一）生产组织与计划问题1、产品计划问题问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。如果用 ，单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，如表所示，问应如何组织生产才能使利润最大？单位 产产品 品 所需 资源 资源可 供 应 资 源 单位产品所得利润 设出产品的计划数，可列出这类问题的数学模型如下：一般的产品计划问题举例 例1-8：某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。 生产产品B的同时产出副产品C，每生产一吨产品B，可同时得到2吨产品C而毋需外加任何费用；副产品C一部分可以盈利，剩下的只能报废。 出售产品A每吨能盈利400元、产品B每吨能盈利1000元，每销售一吨副产品C能盈利300元，而剩余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。试列出线性规划模型，决定A、B两种产品的产量，使工厂总的利润最大。信息整理：产 品 加 工 工 时（小时） 盈 利（百元） 工序1 工序2 A 2 3 4 B 3 4 10 1：2 盈利（最大销量为5） 3 C 报废 -2 可供利用工时 12 24数学模型为： 设：x1产品A的产量， x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得2、产品配套问题 例1-9 某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，表中给出了有关信息。试确定各车间生产每种零件的工作时间，使生产产品的件数最多。 例1-9有关信息表 车 间 总 工 时生产效率（件/小时）零件I 零件II 生产工时数 零件I 零件II 1 100 8 6 2 50 10 15 3 75 16 21 分析： 生产出两种零件的数量分别是 组装成的产品数为z=其中：xij表示第i个车间生产第j个零件的时间 注意Z是非线性表达式！ 处理：引入一个新变量Y，令Y= 则目标要求可以写成：Max Z = Y 把Y的表达式改写成两个不等式增添到约束条件中去 于是得到该问题的LP模型为：Max Z=Y (二)合理下料问题 在加工业中，经常遇到这类问题。 问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选取合理的下料方法，使得既满足对截出毛坯的数量要求，又使所用的原材料最少（或废料最少）？ 解决这类问题一般有两个步骤： 步骤一、按照一定的思路设法列出所有的排料方案（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先确定一些筛选原则，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；步骤二、设xi表示按第种方案下料的棒料根数（或板材块数）i=1,2,n，按照问题的要求建立LP模型。 例1-10 某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数最少？ 设xi为按第i种方案下料的棒料根数，建立LP模型如下：（三）合理配料问题 问题的一般提法：由多种原料配置成含有m种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含m种成分的数量，要求给出使产品成本最低的配料方案。如：伙食问题（也称营养问题）、饲料配比问题、化工产品中的混合问题等都属于这类问题。 例1-