运筹学线性规划引论.pptVIP

第一章 线性规划引论 1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法 1.3 线性规划问题的建模与应用举例 1.1 线性规划问题及其数学模型 隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , cj为确定值 1.2 线性规划问题的图解法 直观结论 若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）； 若线性规划问题有最优解，则 唯一最优解对应于可行域的一个顶点； 无穷多个最优解对应于可行域的一条边； 若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的； 若线性规划问题无可行解，则可行域必为空集。 1.3 线性规划问题的建模与应用举例 数学规划的建模原则 容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。 容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误、公式错误。 容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。 人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数：Min z =x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 套裁下料问题 假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。 目标函数： Min z=x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3+ 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0 假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上面前 8种方案下料的原材料根数。我们建立如下的数学模型。 目标函数： Min z = 0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8 约束条件： s.t. 2x1+x2+x3+x4 ≥ 100 2x2+x3 +3x5+2x6+x7 ≥ 100 x1 +x3+3x4 +2x6+3x7+4x8 ≥ 100 x1,x2,x3,x4,x5,x6,x7,x8≥ 0，整数 生产计划的问题 解：设 x1 ， x2 ， x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4 ， x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。 求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。 这样我们建立如下数学模型： 目标函数: Max z=15x1+10x2+7x3+13x4+9x5 约束条件： s.t. 5x1+10x2+7x3 ≤ 8000 6x1+4x2+8x3+6x4+4x5 ≤12000 3x1+2x2+2x3+3x4+2x5 ≤ 10000