有四项工作要甲、乙、丙、丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如下表所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少？
最优方案为：甲-工作1，乙-工作4，丙-工作3，丁-工作2例试将下面线性规划问题。
min z = x1+2x2-3x3
x1+x2+x3 ≤7
x1-x2+x3 ≥2
-3x1+x2+2x3 = 5
x1,x2 ≥0
max z’= x1-2x2+3x4- 3x5x1+x2+x4-x5+x6=7
x1-x2+x4-x5-x7=2
3x1-x2-2x4+2x5=5
x1,x2,x4,x5,x6,x7≥0
解令 x3= x4 - x5 其中x4、x5 ≥0；
对第一个约束条件加上松弛变量 x6 ；
对第二个约束条件减去松弛变量 x7 ；
对第三个约束条件两边乘以“-1” ；
令 z’=-z 把求 min z 改为求 max z’
例将下列数学模型转化为标准型。
max z =4x1+5x2+2x3
x1+x2≤45
x1+x2+2x3≤80
x1+x2-4x3≥-40
x1,x2 ≥ 0,x3无约束。
max z =4x1+5x2+2x’3+2x’’3x1+x2+x4 = 45
x1+x2+2x3+x5 = 80
x1-x2+4x3+x6 = 40
x1,x2 ,x’3 ,x’’3 ,x4,x5,x6≥01.2 线性规划的**。
max z=x1+3x2
x2≤6-x1+2x2≤8
x1 ≥0, x2≥0
最优解x=(15,10)
最优值z=85
原问题与对偶问题的对应关系。
对偶问题为。
求下述线性规划问题的对偶问题。
min z=2x1+3x2-5x3+x4
x1+x2-3x3+x4≥5
2x1 +2x3-x4≤4
x2+x3+x4=6
x1≤0,x2,x3≥0;x4无约束。
设对应于三个约束条件的对偶变量分别为y1,y2,y3;由于目标函数是求极小值，由上表知其对偶问题为。
max z’=5y1+4y2+6y3
y1+2y22
y1y3≤3
-3y1+2y2+y3≤-5
y1-y2+y3=1
y1≥0，y2≤0,y3无约束。
运筹学复习
运筹学 复习知识点。第二章 线性规划的 法。法的灵敏度分析。第四章 线性规划模型建立。人力资源分配问题。生产计划问题。套裁下料问题。连续性投资问题。第五章 单纯形法的 形式求解线性规划。人工变量法 大m法。线性规划解的几种特殊形式。第六章。单纯形表的灵敏度分析。求一个线性规划的对偶问题。利用对偶规划...
运筹学复习
1.网络计划。根据安排表画出网络图，并从网络图中找出关键路径。根据安排表画出网络图，并从网络图中找出关键路径。2.决策问题。1 挂历订购问题。挂历售价80元 本，成本50 本，若当年最后一天还有挂历没卖出，则剩余只能跳楼甩卖，卖价20元 本。根据往年情况，明年销售情况分别为 150,160,170,...
运筹学复习
一 用 法求解如下线性规划问题。2 用单纯性法或大m法求解 三 线性规划 60页，3,8 四 某研究院有。一 二 三三个区。每年分别需要用煤 吨，由甲 乙两处煤矿负责 质量相同。能力分别为 吨，运价为 由于需大于供，经院研究决定一区 量可减少0 900吨，二区必须满足需求量，三区 量不少于1600吨...