：整数规划.ppt

考虑被提议工厂的生产能力约束条件，以D1为例，有 ，其余类似； 考虑分销中心的需求量约束条件，以M1为例，有 ，其余类似。 因此，有整数规划模型： 结果表明，在Ｄ４处建立一个分厂，从Ｄ４处运输给Ｍ２的数量为２００００万件，运给Ｍ３的数量为２００００万件。 利用lingo 求解得到： 实际上，这一模型可以应用于含有工厂和仓库间，工厂与零售店之间的直接运输和产品分配系统。利用０－１变量的性质，还可以多种厂址的配置约束，比如，由于Ｄ１和Ｄ４两地距离较近，公司不愿意同时在这两地建厂等。 4.3.2 摄像机安装优化问题 某艺术馆考虑安装一个摄像安全系统以减少其保安费用，右侧图为该艺术馆用以展览的房间示意图， 房间的通道显示为1－13。 一家保安公司建议在一些通道安装双向摄像机，每架双向摄像机都可以监视到其两侧的房间，如，在通道4安装摄像机，房间1和房间4就可以被监视，在通道11处安装摄像机，房间7和房间8就可以被监视。 管理部门决定不在入口处安装摄像机，请给出双向摄像机使用数量最少而能覆盖所有8间房的摄像机安装方案。若房间7的陈列品尤为重要，要求两架摄像机监视该房间，请给出双向摄像机安装的数量及位置。 解：引入变量 ，若通道 i 安装双向摄像机，则 ，否则 。 双向摄像机的数量可表示为 ，目标函数追求使用数量最少的双向摄像机，则有 。 对房间1，通道1，4，6安装双向摄像机可以对该房间设施监控，上述3个通道至少安装1台双向摄像机，有 ； 对房间2，有通道6，8，12可以对该房间实施监控，则有 ； 同理，对其它房间，有相应得双向摄像机设施监控。 由此， 采用lingo7软件计算得到： ， 。即在通道3，6，10，11处安装双向摄像机，共4架。 若房间7需要两架摄像机监控， 则上述约束条件中 改成 ， 模型中其它式子不变，计算得到： ， 即在通道3，6，9，10，11处安装双向摄像机。 * 解：按上述第一步， 将这系数矩阵进行变换。 按第二步，得到： 这里◎的个数 m=4，而 n=5 ； 解题没有完成，应按以下步骤继续进行。 ◎ ◎ ◎ ◎ ? ? ? ? ? 第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。 为此按以下步骤进行： （1）对没有◎的行打√号； （2）对已打√号的行中所有含 元素的列打√号； （3）再对打有√号的列中含◎元素的行打√号； （4）重复（2），（3）直到得不出新的打√号的行、列为止； （5）对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。 令这直线数为l。 若 ln ，说明必须再变换当前的系数矩阵，才能找到 n个独立的0元素，为此转第四步：若 l=n ，而 mn，应回到第二步（4），另行试探。 在例4.7中，对矩阵按以下次序进行： 先在第五行旁打√号，接着在第一列打√号，接着在第三列旁打√号。 经检查不能再打√号了。对没有打√行，画一直线以覆盖0元素，已打√的列画一直线以覆盖0元素。得 ◎ ◎ ? ? ? ? ◎ ◎ ? √ √ √ 由此可见， 应继续对矩阵 进行变换， 转第四步。 第四步：在没有被直线覆盖的部分中找出最小元素； 打√行各元素均减去该最小元素， 打√列各元素均加上该最小元素，得到新系数矩阵。 若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。 在没有被覆盖部分（第3、5行）中找出最小元素为2， 然后在第3、5行各元素分别减2， 给第一列各元素加2，得到新矩阵。 按第二步，找出所有独立的0元素，得到： 它具有n个独立的0元素。 这就得到了最优解，相应的解矩阵为： ◎ ◎ ? ? ? ? ? ◎ ◎ ◎ 由解矩阵得最优指派方案：甲—B，乙—D，丙—E，丁—C，戊—A。本例还可以得到另一最优指派方案：甲—B，乙—C，丙—E，丁—D，戊—A。所需总时间为 。 当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时，这时可以任选一行（列）