第2章 线性规划

null目 录目 录第二章 线性规划 第三章 对偶理论 第四章 线性规划进一步讨论 第五章 整数规划 第六章 动态规划 第七章 网络优化模型 第八章 网络 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 第十章 博弈论第一章 线性规划第一章 线性规划 线性规划模型 线性规划的图解法 可行域的性质 线性规划的基本概念 基解、基可行解 单纯形法及单纯形表 null例1、 （1）提出、分析问题线性规划数学模型（1） 问：如何安排生产，使获得的利润最大？null 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1 ,x2 ≥0线性规划数学模型（2）（2）根据已知条件建立数学模型 设：该公司生产产品Ⅰx1件，产品Ⅱx2件，总利润z元max z=2x1+x2st.目标函数约束条件null线性规划数学模型（3）1、线性规划数学模型的一般形式：max(min) z= c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn≤(≥,=)b1 a21x1+a22x2+…+a2nxn≤(≥,=)b2 …… am1x1+am2x2+…+amnxn≤(≥,=)bm x1,x2,…,xn ≥0线性规划数学模型的三个要素： 决策变量、目标函数、约束条件（1）null线性规划数学模型的一般形式的其他表示方式：其中：cj—价值系数； bi—限定系数； aij—工艺系数、技术系数（2）null（3）用向量、矩阵形式表示线性规划的数学模型null线性规划数学模型（6）2、线性规划数学模型的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式：特点： a、目标函数：max b、约束条件：等式 c、决策变量≥0 d、bi≥0线性规划的 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 形式（矩阵形式）线性规划的规范形式（矩阵形式）线性规划的标准形式（矩阵形式）线性规划的标准形式（矩阵形式）null线性规划数学模型（7）3、如何将线性规划数学模型的一般形式转化为标准形式null线性规划数学模型（8）练习题：将线性规划数学模型转化为标准形式线性规划的图解法线性规划的图解法对于只有两个变量的线性规划问题可以用图解法求解： 变量用直角坐标系中的点表示 约束条件用坐标系中的半空间或直线的交表示 可行区域是一个凸多面体 目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。 线性规划的图解法线性规划的图解法基本概念max z = 2x1 + x2 5x2 ≤ 15 s.t. 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 ，x2 ≥ 0null线性规划的图解法可行解: 满足约束条件的变量x 可行域: 满足约束条件的变量x组成的集合 最优解x*：对应目标函数值(z=f(x))最大的变量x 最优值z*: z*=f(x*) 无解:没有满足约束条件的变量。 线性规划问题的解线性规划问题的解解的四种情况: 唯一最优解 无穷多最优解 无界解:建模时漏了必要条件 无解(无可行解):建模有误,条件矛盾 图解法的启示图解法的启示线性规划的可行域是凸集 线性规划的最优解在顶点上 单纯形算法的思路 凸集凸集不是凸集null线性规划定义 求一组变量x1，x2，…，xn的值，使之满足关于这组变量的若干个线性等式或不等式的约束条件，而且使这组变量的一个线性函数取到极大值（或极小值）。这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值的连续变量。这样的问题称为线性规划。线性规划解的基本概念与性质null可行解 满足线性规划所有约束条件的各变量的 一组值X=（x1，x2，…，xn）T，称为线性规划 问题的可行解。全部可行解的集合称为可行域。 最优解 使线性规划的目标函数达到以最优值 （依照具体问题，或者是极大值，或者是极小 值）的可行解称为线性规划问题的最优解。 上述两个概念，对于一般形式、标准形式都适 用，而下述概念，仅适用于标准形式。 nullnull基 设标准形式线性规划的约束方程组为AX=b，X≥0。若B是系数矩阵A的m阶满秩子矩阵，则称B是线性规划问题的一个基。B中的每一个列向量称为基向量，共m个，与基向量对应的变量称为基变量。B以外的列向量称为非基向量，对应的变量称为非基变量，共（n－m）个。 null基解 在标准形式线性规划的约束方程组中，对应基B，令所有非基变量都等于零，求解约束方程组AX=b，可惟一得出基变量的一组值，这些值和取零的非基变量的值合起来，称为线性规划问题的基解或基本解。 基的个数不超过 ，一个基对应一个基解，故基解的个数也不超过 。基解中非零分量的个数不会大于约束方程的个数m。若一个基解的基变量中有取零值的，则此基解称为退化的，否则称为非退化的。null 基可行解 对于标准形式的线性规划，如果一个基解X还满足变量取值非负性的约束条件X≥0，则称此基解为基可行解或基本可行解。 最优基 如果一个基可先行解是最优解，则它所对应的可行基叫做最优基。 null线性规划的基本概念线性规划的基本概念线性规划的基矩阵(基)、基变量、非基变量==目标函数约束条件行列式≠0 基矩阵右边常数线性规划 Linear Programmin（LP）线性规划 Linear Programmin（LP）max z = 2x1 + x2 5x2 ≤ 15 s.t. 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 ，x2 ≥ 0null几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基解可行域的顶点基可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解线性规划的几个基本定理线性规划的几个基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。 定理2：线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。 定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。单纯形法迭代原理单纯形法迭代原理单纯形法迭代步骤：（依据：LP问题的最优解若存在，则一定有一个基可行解为最优解。）已知初始基变量，求初始基可行解已知初始基变量，求初始基可行解以下例说明求法。添加松弛变量后例1可标准化为其中x3, x4, x5为初始基变量，初始基可行解为null不难发现这时每个初始基变量取的值恰好就是包含这个变量的约束方程的右端常数值，非基变量取的值为零。将这个解代入到目标函数，就可得到这个解对应的目标函数值。目标函数目前的值为零，很明显如果能使的变量x1或x2取正值的话，目标函数的值还可以增加。所以目标函数还未达到其最大值。 一般地，若目标函数已经表示成了非基变量的函数，且其中非基变量的系数中还有正数，则目标函数还可能增大。这时目标函数中各变量的系数称为检验数。2.旋转 (从一个基可行解转换为相邻的可行解)2.旋转 (从一个基可行解转换为相邻的可行解)若基可行解不是最优解，则需要转到一个相邻的基可行解，并使得目标函数值增加。所谓相邻的基可行解是指两个基可行解只有一个基变量不同而其它的基变量都相同。要从一个基可行解转到与它相邻的基可行解，意味着需要将一个非基变量变成基变量，而且将一个原来的基变量变为非基变量，前者称为换入变量，后者称为换出变量。确定换入变量确定换入变量目的：新的基变量换入后，会使目标函数值增大（通常还希望增加的越大越好）因此选择在目标函数中系数为正值的非基变量作为换入变量，通常取在目标函数中最大的正系数对应的非基变量为换入变量，即取最大的正检验数对应的非基变量为换入变量。换入变量为 x1确定换出变量确定换出变量由于基变量只有m个，因此将一个非基变量变为基变量后，必须将一个原来的基变量变为非基变量，这个变量就是所谓的换出变量。 换出变量与换入变量是密切相关的。设xk是换入变量。若xk>0，则第i个约束条件可以写成并且由于其余的非基变量保持零值，因此null若确定xk为换入变量，则可估计xk的取值，使得：其余的决策变量都取非负值；并且目标函数得到尽可能的增加。对前者，只须 对所有的i成立，即为了使目标函数尽可能增加，显然应该有null这意味着xl可以是非基变量。因此取xl为换出变量。也就是取使得成立的l 对应的基变量xl为换出变量。null确定换出变量等价于确定了一组新的基变量，为了方便地求出相应的基解，接下来将进行如下的运算：将这组新的基变量的系数矩阵化为单位矩阵（或单位矩阵交换列后得到的矩阵），这等价于使得这组基变量中每个变量只出现在一个方程中并且在该方程中的系数为1，这称为旋转运算。旋转运算可以利用对约束方程组进行加减消元法完成。null例：用单纯形法的基本思路解例1的线性规划问题 null第一次迭代： （1）取初始可行基B10= (p3 , p4 , p5)，那么x3 ，x4 ，x5为基变量，x1 ，x2为非基变量。将基变量和目标函数用非基变量表示： z=2x1+x2 x3 = 15 - 5 x2 x4 = 24 - 6 x1 - 2x2 x5 = 5 – x1 - x2 当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=15，x4=24，x5=5，z = 0，得到当前的基本可行解： x=(0,0,15,24, 5)T，z = 0 。 第一个可行解， 对应利润为零， 显然不是最优解在X1 ，X2 平面上对应的可行域的顶点是 （0，0）。如何寻找下一个可行域的顶点？ 我们再看， null（2）选择进基变量。在目标函数 z = 2x1 + x2中，非基变量x1，x2的系数都是正数，因此 x1 ，x2进基都可以使目标函数z增大，但x1的系数为2，绝对值比x2的系数1大，因此把x1作为进基变量可以使目标函数z增加更快。选择x1为进基变量，使x1的值从0开始增加，另一个非基变量x2保持零值不变。null（3）确定出基变量。在约束条件 x3 =15 - 5 x2 x4 = 24 - 6x1 -2x2 x5 = 5 – x1 - x2 中，由于进基变量x1在2个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3 、x4 、x5的值分别从当前的值15、24和5开始减少，当x1增加到4时，x4首先下降为0成为非基变量。这时，新的基变量为x1 、x3 、x5 ，新的非基变量为x2、x4 ，当前的基本可行解和目标函数值为： x = (4，0，15，0，1)T，z =8。  就是说：产品1最大产量为4；这时设备B用完，（X1 <= 5，并且X1 <= 4 ） 产品2最大产量为3；这时设备A用完 （X2 <= 5，并且X2 <= 3） 由于产品I的单位利润大于产品II的单位利润，因此我们首先考虑尽可能 多地生产产品I， X1 = 4变成基变量， 这时 X4 = 0，变成非基变量null第二次迭代： （1）当前的可行基为B1 = (p1 , p3 , p5)，那么x1 ，x3 ，x5为基变量，x2 ，x4为非基变量。将基变量和目标函数用非基变量表示： z = 8+（1/3）x2– (1/3) x4 x1 = 4– (1/3) x2 – (1/6) x4 x3 = 15 - 5x2 x5 =1 - (2/3) x2 - (1/6) x4  null（2）选择进基变量。在目标函数 z = 8+（1/3）x2– (1/6) x4 中，非基变量x2的系数是正数，因此 x2进基可以使目标函数z增大，于是选择x2进基，使x2的值从0开始增加, 另一个非基变量x4保持零值不变。 (3)确定出基变量。在约束条件 x1 = 4– (1/3) x2 – (1/6) x4 x3 = 15 - 5x2 x5 =1 - (2/3) x2 - (1/6) x4 null中，由于进基变量x2在两个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x1、 x3 、x5的值分别从当前的值4、15、1开始减少，当x1增加到3/2时，x5首先下降为0成为非基变量。这时，新的基变量为x1 、x2 、x3 ，新的非基变量为x4 、x5 ，当前的基本可行解和目标函数值为： x = (7/2，3/2，1，0，0)T，z = 8.5。  null第三次迭代： （1）当前的可行基为B2 = (p1 , p2 , p3)，那么x1 ，x2 ，x3为基变量，x4 ，x5为非基变量。将基变量和目标函数用非基变量表示： z = 8.5 –1/4x4 –3/2x5 x1 = 7/2 – (1/12) x4 + (1/2) x5 x2 = 3/2 –(1/4) x4 - (3/2) x5 x3 = 1 + (5/4) x4 +(15/2) x5 null（2）选择进基变量。在目标函数 z = 8.5 – (½)x4 – (1/12)x5 中，非基变量x3 、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x* = (7/2，3/2，1，0，0)T，最优目标值为z* = 8.5。我们也称相应的基B2 = (p1 , p2 , p3)为最优基。计算结束。  单纯形法求解过程小结单纯形法求解过程小结（1）求出初始基可行解（2）通过非基变量在目标函数中的系数（检验数）是否都小于或等于零，判别该基可行解是否为最优解。若是，结束运算；否则进行下一步。（3）确定换入变量。取最大的正检验数对应的变量为换入变量。（4）确定换出变量。用换入变量在各方程中的正的系数去除该方程的右端常数，在除得的商中取最小者，该最小商所在方程中的基变量就是换出变量。由此得到一组新的基变量。（5）旋转运算。将新的基变量在约束方程中的系数矩阵化为单位矩阵（或单位矩阵交换列后的矩阵）。回到第（2）步。单纯形表的方法单纯形表的方法单纯形法的所有运算实际上都可归结为对LP模型的目标函数系数以及约束方程组的系数（矩阵）的运算。为了简化运算过程，并使运算过程程序化。人们构造了单纯形表来进行运算null初始单纯形表例1 中的模型化为标准形式后为null基变量目标函数系数右端常数基变量在目标函数中的系数约束方程组系数矩阵检验数目标函数值为：z = 0这个基可行解不是最优解null换入变量 24/6 5/1换出变量主元旋转运算的目的：通过矩阵的初等行变换，使主元变为1，主元列的其他数变为0。变换后为01/30-1/30null01/30-1/30基可行解为：目标函数值为：z=815/5 4/(1/3) 1/(2/3)000-1/4-1/2null000-1/4-1/2最优解为：最优目标函数值为：z=8.58 ½因此对例1中的问题，最优的生产计划安排是每天生产甲家电3.5件，乙家电1.5件，每天可以得到的最大利润为8.5元。（按此计划安排生产，每天设备A可富余7.5台时）null初始单纯形表最终单纯形表单纯形表合并的表示无穷多个最优解无穷多个最优解检验数的实际意义：检验数是非基变量每增加一个单位，目标函数的增加值。因此如果在最终单纯形表中，当所有的检验数都小于或等于零，并且存在非基变量的检验数等于零的情况时，LP问题存在无穷多个最优解。实际上，此时可选择检验数为零的非基变量为换入变量，迭代到一个新的基可行解，它的目标函数值等于最优解的目标函数值，从而也是最优解。因此有无穷多个最优解。无界解无界解若换入变量（或正检验数）所在列的所有系数都小于或等于零，则LP问题为无界解。例如，如果单纯形表为则目标函数无界。null实际上换入变量为x1，相应的约束方程组为由于x2仍是非基变量，因此由此可见，不管x1取什么样的正数，x3、x4、x5都保持非负，这意味着x1的取值没有任何限制，从而目标函数值可以无限增加。null 单纯形法求解过程及其经济含意 单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点 确定转轴元 先订列 检验数正中取大（相应产品利润最大） 再定行 相除后正中取小（相应资源约束最厉害） 思路：几何－顶点（计算机不可识别）－代数－基解（计算机可识别） 基－－----------- -基解－－-----------基可行解 A=(B, N) X 非负 AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN ＋0 XBnull( CN - CB B-1 N)是非基变量检验数 如果 非基变量 XN ＝0 则Z = CB B-1b null如何从单纯形表判断线性规划解各种类型 1．唯一最优解 null2 无界最优解： 注意：这时找不到“转轴元” 因为无法进行“再定行相除后正中取小”， 非基X3 产生利润而不消耗资源， 越多越好 null利润Z = 0(非基X1)+ 负(非基X5) 这时非基X1取任何值，都不改变目标函数的值，因此有无穷最优解3 无穷最优解：null求解线性规划问题：写成标准化形式：null1、列出初始单纯形表—5/1x 4换出变量，x 1换入变量，24/6θ基可行解（x1,x2,x3,x4,x5）=（0，0，15，24，5） ∵检验数：σ1 >σ2 >0 ∴非最优解 2、寻找换入变量，换出变量 max σj > 0 ; minθ>0 null3、寻找新的基矩阵和基可行解1/4/6x5换出变量，x2换入变量，x12412/601/601505100104/60-1/6101/30-1/3015/5θ4/2/6基可行解（x1,x2,x3,x4,x5）=（4，0，15，0，1） ∵检验数：σ2 >0 ∴非最优解 4、寻找换入变量，换出变量 max σj > 0 ; minθ>0 null检验：所有的σj≤0 ∴得到最优解，最优解为：（x1,x2,x3,x4,x5）=（7/2，3/2，15/2，0，0，0） max z=8.5x213/2010-1/43/215/20015/4-15/27/21001/4-1/2000-1/4-1/2null列出初始单纯形表 寻找初始基可行解计算σ，进行最优性检验所有σ≤0 是否存在非基变量 检验数=0 否是唯一最优解 无穷多最优解 对某一σj >0 有PJ≤0 否无界解 寻找换入，换出变量 求新基可行解单纯形法计算步骤null如何从单纯形表判断线性规划解各种类型 人工变量法求线性规划的初始可行基： 目的：求初始可行基 原理：人工变量的成本无穷大 1大M法 2二阶段法 原理： 要点： 第一阶段：首先加入人工变量 新的目标函数改变为： min 人工变量 （原来变量的成本为零） 用单纯形表求解 第二阶段：将第一阶段最终单纯形表除去人工变量 新的目标函数＝原来的目标函数单纯形法的进一步讨论null1、人工变量法 例：null写成标准化形式：添加松弛变x4 ，x5系数矩阵：null添加人工变量：x6 ，x7数学模型变为：nullnullnull两阶段法： 第一阶段第一阶段的代换最终必须将人工变量换出，即最终单纯形表的基变量中不能包含人工变量。否则，此线性规划问题无可行解。第二阶段： max z = - 3 x1 + 0 x2 + x3 + 0 x4 + 0 x5null单纯形法中的几点注意的问题： 1、目标函数 min 时，最优性的判断标准： 检验数σj ≥0 时有最优解。 2、解的退化： （1）存在多个相等的σj >0，选取下标最小的变量为换入变量； （2）存在多个最小的θ>0相等时，选择下标最小的变量为换出变量。 3、在最终单纯形表中所有σj≤0 ，而基变量中仍含有非零的人工变量，则此问题无可行解。null线性规划模型特点 1 一个目标函数：线性 2 几个约束条件：线性 3 多个决策变量：非负 世界500强企业中广泛的应用是因为现实中的确存在各种约束： 关键设备生产能力约束 各类能源约束（电力，煤） 工艺流程约束 产品类结构关系约束（例如产品的合金比，钢坯的连铸比） 物流过程上，中，下游产品供需约束 某些产品下限约束（例如必要库存，稳定的用户需求）线性规划（4） 应用四例 null第一章：线性规划（4）应用四例 例1 下料问题 用长度为７.４m的圆钢截断成制造某种机床所许的三个轴坯，长度分别为2.9m,2.1m,1.5m。现需要１００台机床。建立线性规划模型以寻求最佳的截断 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 所需圆钢最少。 我们设Ｘj为第j种方案截断的圆钢根数，截断圆钢的方案有８种： null 企业 下料问题： 按需下料 废料最少原材料7.4米产品2.9米产品2.1米产品1.5米第一章：线性规划（4） 应用四例 null第 一章：线性规划（4）应用四例 在成品规格较多，原料长度较长，截断方案多时，表中的轴坯长度最好按长短从上到下排列，对第一行数字从左到右逐渐减少；在第一行数字相等时，第二行数字从左到右逐渐减少，这样可以避免遗漏。 目标函数是下料最少即：　　   ＭinＺ＝0.1X1+0.3X2+0.9X3+1.1X5+0.2X6+0.8X7+1.4X8   约束条件方程是每种长度的轴坯至少是100根以及非负约束： 2X1+X2+X3+X4≥100 2X2+X3+3X5+2X6+X7≥100 X1+X3+3X4+2X6+3X7+4X8≥100 Xj≥0且为整数，j=1，2，3…8 由此可以解出最少需求。 null 企业 配料问题 比例混 合 CPHABD第一章：线性规划（4） 应用四例 null第一章：线性规划（4）应用四例 例2   配料问题 鸡尾酒 配料 用m种原料配制n种产品，每种产品对各种原料均有一定的比例要求ni(I=1,2,….,m)且原料每天的供应量也有一定的限制ui(I=1,2,…..,m)要求最大利润。null第一章：线性规划（4）应用四例 原料单价（元 公斤） 比 例 混 合 CPHABDnull第一章：线性规划（4）应用四例 AC 代表产品A中原料C的成分 产品A的收入为 50（AC ＋AP＋AH） 产品B的收入为 35（BC ＋BP＋BH） 产品D的收入为 25（DC ＋DP＋DH） 原料C的成本为 65（AC ＋BC＋DC） 原料P的成本为 25（AP ＋BP＋DP） 原料H的成本为 35（AH ＋BH＋DH） 利润最大Z=收入－成本＝50（AC ＋AP＋AH）＋35（BC ＋BP＋BH）＋25（DC ＋DP＋DH）－ 65（AC ＋BC＋DC）－ 25（AP ＋BP＋DP）－ 35（AH ＋BH＋DH） 约束：原料约束AC ＋BC＋DC <=100 AP ＋BP＋DP <=100 AH ＋BH＋DH <=60 产品成分约束：AC >=0.5 A AC ＋AP＋AH =A AP <=0.25 A BC >=0.25 B BP <=0.5 B 非负约束null 企业 生产计划目标 均衡生产原料原料原料产品产品产品第一章：线性规划（4） 应用四例 null第一章：线性规划（4）应用四例 例3：生产计划问题问题→各种企业 Max{设备均衡负荷最大} St. 资源约束 决策变量：各时间段各产品生产量（XjK代表K月份加工j产品的数量）null项目A项目B项目C今年 马年明 年 熊猫年 后 年 大象年 大后年 克隆怪物年决策：：各阶段每个项目投资额第一章：线性规划（4） 应用四例 null第一章：线性规划（4）应用四例 引言：手中有10万元，是否应存入银行？如何让钱变钱？ 投资!! Max {期末本利和} St. 各阶段投资（进=出） 决策变量：各阶段各项目投资额 例4 连续投资问题 如果某公司有100万元用于投资，投资方案有以下四种。 项目A：从第1年到第四年，每年初投资，次年末回收本利115％ 项目B：第3年初投资，第五年末回收本利125％，最大投资额不超过40 万元 项目C：第2年初投资，第五年末回收本利140％，最大投资额不超过30万元 项目D: 五年内每年可以购买国库卷，于当年末归还，并有利息6％ 如何决策，使得到第五年末，资金的本利最大？？ null第一章：线性规划（4）应用四例 null分析：决策变量是什么？ 决策目标是什么？ 目标函数：MAX Z=X1+3X 2 满足的 约束条件： X1A ＋X1D = 100 X2A ＋X2C ＋X2D =1.06X1D X3A ＋X3B ＋X3D =1.15X1A ＋1.06X2D X4A ＋X4D =1.15X2A ＋1.06X3D X5D =1.15X3A ＋1.06X4D X2C<=30 X3B<=40 XIa, , XiB, XiC , XiD >=0 I=1 ,2 ,3 ,4 , 5第一章：线性规划（4）应用四例 null 计算结果： 第1年： X1A ＝34.783 X1D = 65.217 第2年： X2A =39.130 X2C =30 X2D =0 第3年： X3A =0 X3B =40 X3D =0 第4年： X4A =45 X4D = 0 第5年： X5D =0 第五年末，资金的本利达到143.75万元， 利43.75％ 第一章：线性规划（4）应用四例 null看x同学的 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 模型：第一章：线性规划（4）应用四例 一．〈〈运筹学〉〉中“线性规划问题”在现实生活中的一个应用。 商店是商品的流通门，必须买进售出。如果每月进货一次，那么每次进货多少是不能随意决定的。因为若进货太少，不仅造成市场供不应求，而且还会减少商店的盈利；若进货太多，不仅仓库容纳不了，而且造成商品积压，增加损耗与保管费用，同样也会减少商店的盈利。因此，对于每次的进货量，必须有一个数量的控制。  实例：存货控制问题  某商店要制定某种商品第二季度的进货计划，已知该商店仓库容纳此种商品的容量不能超过600件，三月底已存货200件，以后每月初进货一次。假定各月份此种商品买进售出的单价如下表：月份 四月份 五月份 六月份 买进单价（元） 17 16.5 17售出单价（元） 18 18 19 null问各月进货，售货各多少件才能使利润最大？ 为了简单起见，只考虑进货时受到仓库容量的限制，售货时受到存货量的限制这两个.约束 因素，对于货物存放在仓库内的损耗与保管费不作考虑。 分析： 假设四、五、六月份的进货量分别为x1，X2，X3件；售货量分别为Y1，Y2，Y3件，由于各月份的进货量要受到仓库容量的限制。所以， 四月份的进货量应满足： X1≤600-200=400， 即 X1≤400； 五月分的进货量应满足： X2≤600-（200+X1-Y1）=400-X1+Y1， 即 X1+X2-Y1≤400； 六月份的进货量应满足： X3≤600-（200+X1+X2-Y1-Y2）=400-X1-X2+Y1+Y2， 即 X1+X2+X3-Y1-Y2≤400.第一章：线性规划（4）应用四例 null由于售货量要受到成货量的限制，所以四月份的售货量应满足： Y1≤200+X1， 即 Y1-X1≤200； 五月份的售货量应满足： Y2≤200+X1+X2-Y1， 即 Y1+Y2-X1-X2≤200； 六月份的售货量应满足： Y3≤200+X1+X2+X3-Y1-Y2， 即 Y1+Y2+Y3-X1-X2-X3≤200. 第二季度的利润目标函数为： S=18Y1+18Y2+19Y3-17X1-16.5X2-17X3. 第一章：线性规划（4）应用四例 综上所述，这个问题可归结为： 求 Xj与Yj， 满足： X1≤400； X1+X2-Y1≤400； X1+X2+X3-Y1-Y2≤400； Y1-X1≤200； Y1+Y2-X1-X2≤200； Y1+Y2+Y3-X1-X2-X3≤200； Xj≥0；Y≥0；（j=1，2，3）；  使目标函数 S=18Y1+18Y2+19Y3-17X1-16.5X2-17X3 的值达到最大。  易震 99金融 2002年1月14日null作为你的开卷或者锻炼自己的思维， 你是否也发表点什么？