武汉工程大学 运筹学-线性规划和图解法.ppt

* * 2.1 线性规划问题及其数学模型 (1) 线性规划问题建模 例1、生产组织与计划问题 A, B 各生产多少, 可获最大利润? 可用资源 设备 原料1 原料2 A B 1 2 2 1 0 1 单位利润 50 100 300台时 400kg 250kg 建立线性规划模型的步骤： 1）根据管理层的要求确定决策目标和收集相关数据。 2）确定要做出的决策，引入决策变量。 3）确定对这些决策的约束条件和目标函数。 例2 合理配料问题 求：最低成本的原料混合方案 原料 A B Ｃ 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添 加剂中维生 12 14 8 素最低含量 例3、运输问题 工 厂 1 2 3 库存 仓 1 2 1 3 50 2 2 2 4 30 库 3 3 4 2 10 需求 40 15 35 运输 单价 求：运输费用最小的运输方案。 (2) 线性规划问题的特征： 决策变量： 每个问题都用一组决策变量(X1 …Xn)表示，这组决策变量的值都代表一个具体方案。 目标函数：衡量决策方案优劣的函数，它是决策变量的线性函数，根据问题不同，目标函数实现最大化或最小化。 约束条件：分为两类1）函数约束，一组决策变量的线性函数=/=/=一个给定的数（右端项）。2）决策变量约束。 具备以上三个要素的问题就称为 线性规划问题。 目标函数 约束条件 (3) 线性规划模型一般形式 隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , cj为确定值 2.2 线性规划问题的图解法 定义1：满足约束(2)的X=(X1 …Xn)称为线性规划问题的可行解，全部可行解的集合称为可行域。 定义2：满足(1)的可行解称为线性规划问题的最优解。 x1 x2 z=20000=50x1+100x2 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C B A D E 例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 直观结论 若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）； 若线性规划问题有最优解，则 唯一最优解对应于可行域的一个顶点； 无穷多个最优解对应于可行域的一条边； 若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的； 若线性规划问题无可行解，则可行域必为空集。 2.3 线性规划问题的标准形式 目标函数 约束条件 (1) 线性规划模型一般形式 价值系数 决策变量 技术系数 右端常数 (2) 线性规划模型标准形式 简记形式 (3) 线性规划模型其它形式 矩阵形式 价值向量 决策向量 系数矩阵 右端向量 价值向量 决策向量 右端向量 向量形式 列向量