浙江大学组合优化期末试题.pdfVIP

浙江大学组合优化往年试卷 设 图 为无 向简单图， 为顶点子集 。若 是一个 完全 图，则称 是的团 （ ）。求给定 图的顶点数最多的团的问 题称为图的最大团。 证 明： 是的团当且仅当 是 的顶点覆盖，这里 对任意的 当且仅当 证 明：图的最大团是 难 问题 求给定 图的顶点数最少的顶点覆盖的 问题称为 图的最小顶点覆 盖 。试利用 图的最大基数匹配 问题 的算法设计 图的最小顶点覆盖 问题的多项式时间近似算法，并证 明其最坏情况界不超过； 基于给 出的图的顶 点覆盖与团的关系，是否可由类似于 （ ） 的思路给 出图的最大团问题最坏情况界为的多项式时间近似算 法，为什么？ 某航空公司计划在全 国选择若干个机场组建基地 。设在机场 组建基地 所需费用为 。若该公司在机场和机场 的基地组建完成， 则可开通往返两地 的航班并获得票款收益 。该航空 公司基地组建费用上限为 ，应选择在哪些机场组建基地才能使获得 的票数收益最大。试写出该 问题的数学规划。 某购书网站推出 “满送礼券”活动，凡单 订单购书金额达到或超 过元可获指定面额礼券一 ，现就购买一批图书，计划分拆若干 订单以使获得的礼券数最多。 试指出该 问题与何经典 问题有密切联系，又与之有哪些区别； 若按任一顺序选择购买图书，当当前订单累计金额达到或超过元 后，立即新启一 订单，试给出该方案的最坏情况紧界。 给定正整数集 记 为 的子集中 所含元 之和， 若为 超增集，即对任意 ，则最相近 子集 问题是多项式时间可解 的。试给 出多项式时间算法并证 明其 最优性； 设对任意 这里 为方程