线性规划问题的数学模型课件

1、第一章 线性规划及单纯型法1 线性规划问题的数学模型2 图解法3 单纯形法原理4 单纯形法计算步骤5单纯形法的进一步讨论7 应用举例习题课 线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式1 线性规划问题的数学模型问题的提出例: 生产计划问题产品I产品2如何安排生产使利润最大？满足约束条件的决策变量的取值范围基本概念可行域中使目标函数达到最优的决策变量的值问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。决策变量（Decision variables）目标函数（Objective function）约束条件（Constraint

2、conditions）可行域（Feasible region)最优解（Optimal solution)它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步 -确定决策变量设 I的产量 II的产量 利润第2步 -定义目标函数Max Z = x1 + x2决策变量 Max Z = 2 x1 + 3 x2系数第2步 -定义目标函数对我们有何限制?第3步 确定约束条件2x1 + 2 x2 12 4 x1 16 5 x2 15 x1、 x2 0该计划的数学模型 目标函数

3、Max Z = 2x1 + 3x2 约束条件 2x1+2x2 12 4x1 16 5x2 15 x1、 x2 0 x1 x2线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。 求目标函数最大化或最小化. 线性规划模型的一般形式 目标函数最大约束条件等式决策变量非负线性规划问题的标准形式标准形式为: 简写为 用向量表示 用矩阵表示C价值向量b资源向量X决策变量向量 min Z=CX 等价于 max Z = -CX“” 约束：加入非负松驰变量一般线性规划问题的标准形化例： 目标函数 Max Z = 2x1 + 3x2 约束条件 2x1

4、+ 2x2 12 4x1 16 5x2 15 x1、 x2 0 min Z=CX 等价于 max Z = -CX“” 约束：加入非负松驰变量一般线性规划问题的标准形化例： 将下述线性规划模型化为标准形式 解 ：标准形为练习建立LP数学模型一、有两个煤厂A、B，每月分别供应三个居民区X、Y、Z。求运费最少的方案。供需平衡线性规划模型举例(一) 运输问题(二) 布局问题(三) 分派问题(四) 生产计划问题(五) 合理下料问题线性规划模型的条件（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；（2）存在着多种方案；（3）要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等

5、式来描述。(一) 运输问题 设某种物资有m个产地，A1，A2，A m；联合供应n个销地：B1，B2，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位：元吨）如下表所示。应如何调运，才使总运费最少？表中：ai表示产地Ai的产量(i=1，2， ，m)； bj表示产地Bj的产量(j=1，2， ，n)； cij表示AiBj间的单位运价（元吨）(i=1，2， ，m; j=1，2， ，n)；单价（元吨）销 地产 地产量（吨） B1 B2 BnA1A2 Am销量（吨） C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am（二

6、）布局问题作物布局 在n块地上种植m种作物，已知各块土地 亩数、各种作物计划播种面积及各种作 物在各块的单产（每亩的产量）如表 （与运输问题相似），问：如何合理安排种植计划，才使总产量最多。 单价（元吨）销 地产 地产量（吨） B1 B2 BnA1A2 Am销量（吨） C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am（二）布局问题n块土地每亩的产量m种农作物总产量最多(三）分派问题 设有n件工作 分派给n人 去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为 。问：应如何分派才使完成全部工作的总工时最少。解：设 为Bj分派给人Ai情况： Bj分派给Ai时， ； 不分派给Ai时， 。 那末这一问题的数学模型为： 求一组变量 的值，使目标函数 的值最小。(完成全部工作的总工时最少）(三）分派问题(四）生产组织与计划问题() 生产的机器最多() 总的加工成本最低（）生产存储问题(四）生产组织与计划问题 设某车间用机床 生产由 这n个不同零件构成的机器。如果每架机器需要各种零件的数目成比例 ;机床 生产零件 的效率(每日生产零件数)为 。() 生产的机器最多应如何分配机床负荷，才能使生产的机器最多? 求一组变 的值,解：设 为一天机床 生产零件 的时 间（单位：日） 这一问题的数学模型为： 生产的机