第2章线性规划与单纯形法资料.ppt

第二章 线性规划与单纯形法 主讲教师:马越峰 第二章 线性规划与单纯形法 2.1线性规划问题与数学模型 2.2图解法 2.3线性规划的应用 2.4单纯形法基本原理及计算步骤 2.5单纯形法的进一步讨论 2.6线性规划的对偶问题 2.1 线形规划(Linear Programming)问题及其数学模型 【引例】某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制如下表所示： 线性规划模型 1.适用条件： （1）优化条件:问题目标最大化、最小化的要求； （2）约束条件:问题目标受一系列条件的限制； （3）选择条件:实现目标存在多种备选方案； （4）非负条件的选择:根据问题的实际意义决定是否非负。 2. 构建线性规划模型的步骤 （1）科学选择决策变量 （2）明确目标要求 （3）根据实际问题的背景材料，找出所有的约束条件 （4）确定是否增加决策变量的非负条件 线性规划模型表示形式 （2）集合形式： 例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 步骤： (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。 （2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。 （3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。 解的几种可能结果 唯一最优解解 无穷多个最优解 无界解(可行域无界，常为模型遗漏了某些必要的约束条件) 无可行解（可行域为空集，约束条件自相矛盾,资源满足不了人们的需求） 无界解 无可行解：可行域为空集 线性规划标准形式 习题 1.用图解法求解下列LP问题 （1）minZ= 6x1+4x2 (2)maxZ= 3x1-2x2 2x1+x2 ≥1 x1+x2 ≤1 3x1+4x2 ≥3 2x1+2x2 ≥ 4 x1，x2 ≥0 x1，x2 ≥0 图解法的灵敏度分析 1、目标函数中的系数Ci的灵敏度分析 分析Ci在什么范围内变化，原最优解不变 C1=50 C2=100 2、约束条件右边b系数的灵敏度分析 2.3 LP的应用 一.人力资源分配问题 例1.某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下： 三 套裁下料问题 例3、某工厂要做100套钢架，每套用2·9m、2·1m和1·5m的原钢各一根。已知原料每根长7·4m，问应如何下料，可使所用原料最省。 五、配料问题 2.4 单纯形法基本原理及计算步骤 一、单纯形法的基本思路 从可行域中某一个顶点开始 判断此顶点是否是最优解，如不是则再找另一个使得目标函数值更优的顶点，称之为迭代。再判断此点是否是最优解。直到找到一个顶点为最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解 最优解一定在可行域的顶点上,将顶点坐标代入目标函数有: (0,0):z=3×0+2×0=0 (5,0):z=3×5+2×0=15 (0,8):z=3×0+2×8=16 (2,6):z=3×2+2×6=18 单纯形法的基本思路就是基本可行解的转移，先找到一个初始基本可行解，如果不是最优解，设法转移到另一个基本可行解，并使目标函数值不断增加，直到找到最优解。 基本概念 基：已知A是约束条件的m×n系数矩阵，其秩 为m，若B是A中m×m阶可逆矩阵，则称B 是线形规划问题中的一个基。B是由A中m个线形无关的系数列向量组成的。 本例中 1 1 1 与 1 0 0 2 1 0 0 1 0 0 1 0