数学运筹学问答题每日一练(2019.11.05)

问答题
用Ford-Fulkerson的标号算法求下图中所示各容量网络中从vs到vt的最大流，并标出其最小割集。图中各弧旁数字为容量cij，括弧中为流量fij。
答案：
问答题
甲乙丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿供应。煤炭供应量分别为：A，400万吨；B，450万吨；运价如下表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少0~30万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。
答案：此问题的供应量小于需求量，假设供应地C，产量为70万吨。
用伏格尔法求解得：

使用位势法...
问答题
某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：
答案：
问答题
已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y*1=6/5，y*2=1/5。试用互补松弛定理求该线性规划问题的最优解。
答案：
问答题
有以下目标规划问题（1）用单纯形法求解；（2）若目标函数变成,问原问题的解有什么变化？（3）若第一个目标约束的右端改为120，原满意解有何变化？
答案：（1）单纯形法计算得到：
x₁=70，x₂=45是满意解