线性规划和单纯形法-.pptVIP

运筹学 Operations Research;1.　理解什么是线性规划模型，掌握线性规划在管理及生产中的应用 2.　掌握线性规划数学模型的组成及其特征 3.　清楚线性规划数学模型的一般表达式。;1.1 线性规划数学模型 Mathematical Model of Linear Programming;线性规划（Linear Programming,缩写为LP） 　　是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。 　　线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。;【例1.1】最优生产计划问题。 　　某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？; 产品 资源;【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为：;线性规划的数学模型由 　决策变量 　Decision variables 　　目标函数　 Objective function 　　约束条件 　Constraints 构成。称为三个要素。;【例1.2】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1.2所示。;【解】 设 xj (j=1，2，…，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为 ;1;【例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？ ;设xj ( j = 1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:;1;【例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%~55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。;解: 设xj（j=1,2，…，5）是第j 种矿石数量，得到下列线性规划模型 ;1;第五年：(x7/2+x9)=x8+2x5;1;;;【例1.7】（书上P4例1.1-1题）饼干生产问题。某厂生产两类饼干，需搅拌机A1，成形机A2 ，烘箱A3三种设备，每天的所需机时及机时限制，利润指标如下表，问如何制订生产计划，可使获得最高利润？;约束条件有：;【例1.8】（书上P6例1.1-2题）运输问题。总公司收到上海B1，青岛B2 ，西安B3三家商场的电机订单，需求分别为100台，80台，90-120台，现有北京A1，武汉A2二个仓库，库存分别为200台，150台，所需运费如下表，问如何调运电机，可使总运费最少？;库存约束;小结：建立线性规划数学模型 　　建立数学模型是学习线性规划的第一步也是关键的一步。 　　建立正确的数学模型要掌握3个要素： 　研究的问题是求什么，即设置决策变量； 　问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值； 　限制达到目标的条件是什么，即建立约束条件。;1.1.2 线性规划的一般模型及标准形 一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj, j=1,2…,n，目标函数的变量系数用cj表示, cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成;在实际中一般xj≥0,但有时xj≤0或xj无符号限制。;线性规划的标准型 Standard form of LP;　　在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。;max(或min)Z=c1x1+c2x2+…+cnxn;或写成下列形式：;通常 x 记为：