第一章-运筹学线性规划.ppt

第一章线性规划与单纯形法第一讲线性规划的数学模型第一节线性规划一般模型第二节线性规划的图解法第三节线性规划的标准型第四节线性规划解的概念第二讲线性规划的单纯形法第一节单纯形法原理第二节表格单纯形法第三节人工变量问题第四节单纯形法补遗第一讲线性规划的数学模型线性规划LinearProgrammingLP规划论中的静态规划解决有限资源的最佳分配问题求解方法：图解法单纯形解法第一讲线性规划的数学模型第一节线性规划一般模型例1.生产计划问题某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。第一节线性规划一般模型(1)决策变量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。(2)约束条件。生产这两种产品受到现有生产能力的制约，用量不能突破。生产单位甲产品的零部件需耗用A车间的生产能力1工时，生产单位乙产品不需耗用A车间的生产能力，A车间的能力总量为8工时，则A车间能力约束条件表述为x1≤8同理，B和C车间能力约束条件为2x2≤123x1+4x2≤36第一节线性规划一般模型(3)目标函数。目标是利润最大化，用Z表示利润，则maxZ=3x1+5x2(4)非负约束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为x1≥0，x2≥0第一节线性规划一般模型某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。第一节线性规划一般模型(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件。产量之和等于销量之和,故要满足：供应平衡条件第一节线性规划一般模型决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。例3.资源配置问题m种资源，各自的数量为bi（第i种资源的数量），生产n种产品，利润为cj（第j种产品的利润）。aij表示第j种产品单位消耗第i资源的数量。如何组织生产使获利最大。第一节线性规划一般模型用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式为：第二节线性规划的图解法图解法即是用图示的方法来求解线性规划问题。图解法的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。图解法的步骤：1.在平面上建立直角坐标系2.图示约束条件，找出可行域3.图示目标函数和寻找最优解第二节线性规划的图解法第二节线性规划的图解法目标函数Z=3x1+5x2代表以Z为参数的一族平行线。第二节线性规划的图解法唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。第二节线性规划的图解法无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）第二节线性规划的图解法无可行解：若约束条件相互矛盾，则可行域为空集第二节线性规划的图解法1.求解线性规划时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。2.若线性规划问题的可行域存在，则可行域一定是凸集。凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。3.若线性规划的最优解存在，则最优解或最优解之一一定是可