文档介绍：1《运筹学》南华大学经济管理学院曾经莲运筹帷幄决胜千里2定义1第一章线性规划与单纯形法线性规划是运筹学的一个重要分支。1947年丹捷格提出了一般线性规划问题求解的方法——单纯形法。知识点:?线性规划问题的有关概念?LP(linear programming)-SLP(Standard ~)的转换?用单纯形法求解线性规划问题3§1 线性规划问题及其数学模型?例1【经典例题】:某工厂在计划期内要安排生产I、II两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表1-1所示。该工厂每生产一件产品I可获利2元,每生产一件产品II可获利3元。问I、II两种产品的产量各为多少时,使该工厂获取最大利润?12kg40原材料B16kg04原材料A8台时21设备产品II产品I表1- 问题提出4?分析?设x1,x2分别表示在计划期内产品I、II的产量。≤12kg≤16kg≤8台时max2x1+3x23x22x1利润32单位利润x2x1产量4x240原材料B4x104原材料Ax1+2x221设备目标约束条件汇总III5?建模该生产计划问题可用数学模型表示为:目标函数max z=2x1+3x2约束条件x1+2x2≤8 4x1≤16 4x2≤12 x1,x2≥06?性质:线性规划是一个线性的条件极值问题,可分为两类:?当一项任务确定后,如何统筹安排尽量做到以最小的人力、财力、物力等资源去完成。?已知一定数量的人力、物力、财力等资源,如何安排使用它们使完成的任务(或创的价值、实现的利润等)最多。?线性规划定义:对于求取一组变量Xj(j=1,2,3…n)使得它满足线性约束条件的目标函数取得极值的一类最优化问题。7?特征(P10)?每个问题都用一组决策变量(x1,x2,…,xn)表示某一方案;这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。?存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示。?都有一个要求达到的目标,它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同,要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。8?线性规划数学模型的一般形式目标函数: max(min)z=c1x1+ c2x2 +…cnxn ()约束条件:a11x1 + a12x2 + …+ a1nxn≤(=, ≥)b1 a21x1 + a22x2 + …+ a2nxn≤(=, ≥)b2………………………………… () am1x1 +am2x2 + …+ amnxn≤(=, ≥)bm x1, x2, …xn≥0 ()目标函数中cj为价值系数;称为约束条件中aij为技术系数, bi为限额系数;()也称为变量的非负约束条件。 图解法?可行解,可行解集,可行域?图解法的步骤?建立平面直角坐标系?画出可行域?作出目标函数等值线,求最优解?唯一最优解、无穷多最优解、无界解、无可行解10?例1的图解法在以x1、x2为坐标轴的直角坐标系中,非负条件x1,x2≥0是指第一象限。例1的每个约束条件都代表一个半平面。例1的所有约束条件为半平面交成的区域(见图中的阴影部分)。阴影区域中的每一个点(包括边界点)都是这个线性规划问题的解(称可行解)。此阴影区域是例1的线性规划问题的解集合,称为可行域。在这个坐标平面上,目标函数z =2 x1+3 x2可表示以z为参数、-2/3为斜率的一族平行线:x2=-(2/3)x1+z/3 。位于同一直线上的点,具有相同的目标函数值,因而称它为“等值线”。当z值由小变大时,直线x2=-(2/3)x1+z/3 沿其法线方向向右上方移动。当移动到Q2点时,使z值在可行域边界上实现最大化。这就得到了例1的最优解Q2,Q2点的坐标是(4,2)。于是可计算出z=14。