整数规划模型.ppt

《整数规划模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、决策问题与0-1变量10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事例1（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区12345610101628272021002432171031624012272142832120152552717271501462010212514

2、0请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型：最优解x2=1,x4=1最优值Z=2二、过滤隐枚举法（适合于变量个数较少的0-1规划）（x1x2x3)Z值约束条件（1）（2）（3）（4）过滤条件（000）（001）（010）（100）（101）（110）（011）（111）√√√√0Z≥0枚举法：检验可行解：32次运算-25√√√√Z≥5318×36运算次数：21计算目标函数值：8次√√√√例有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指

3、派哪个人完成哪项工作，使所需的总时间最少？一般地，有n项任务、n个完成人，第i人完成第j项任务的代价为cij（i,j＝1,2,…,n）。为了求得总代价最小的指派方案，引入0-1型变量xij，并令1指派第i人去完成第j项任务xij＝0不指派第i人去完成第j项任务二、指派问题指派问题的求解，最简便易行的方法是匈牙利法。可见指派问题是0-1型整数规划的特例。不难发现，指派问题也是运输问题的特例，其产地和销地数都为n，各产地的产量和各销地的销量都为1。数学模型为Minz＝∑∑cijxijn∑xij＝1j=1,2,…,ni=1n∑xij＝1i=1,2,…,nj=1xij＝0或1匈牙利法

4、基于下面的效率矩阵：c11c12…c1n（cij）=c21c22…c2n……………….cn1cn2…cnn匈牙利法基于这样一个明显的事实：如果系数矩阵的所有元素满足cij≥0，而其中有n个位于不同行不同列的一组0元素，则只要令对应于这些0元素位置的xij＝1，其余的xij＝0，就得到最优解。匈牙利法求解指派问题的步骤如下：0420例如：（cij）=207831500603第一步：变换系数矩阵，使每行每列都出现0元素。(1)系数矩阵的各行分别减去各行中的最小元素；(2)所得系数矩阵的各列再分别减去各列中的最小元素。第二步：试求最优解。(1)给只有一个0元素（不含划去的0）的行中

5、的“0”画○，划去与◎同列的其它“0”；(2)给只有一个0元素（不含划去的0）的列中的“0”画○，划去与◎同行的其它“0”；(3)重复(1)、(2)，直到无新的◎画出。若系数矩阵中已无未画○也未划去的“0”，则已得到最多的◎，转(5)；否则，便出现了0元素的闭回路，转(4)。(4)从0元素的闭回路上任选一个“0”画○，划去其同行同列的其它“0”，转(1)。(5)显然，按上述步骤得到的◎是位于不同行不同列的。若◎已达n个，则指派问题的最优解已得到，结束计算；否则，转第三步。第三步：用最少的直线覆盖所有0元素。(1)给无◎的行打“√”；(2)给打√行中含有0元素的列打“√”；(3

6、)给打√列中含有◎元素的行打“√”；(4)重复(2)、(3)，直到无新的“√”打出。(5)给没有打√的行画横线，给打√的列画纵线。第四步：变换系数矩阵，增加0元素。在未被画线覆盖的其它元素中找出最小元素，各打“√”行减去最小元素，各打“√”列加上最小元素，转第二步。指派问题的数学模型为：克尼格定理:如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵[bij]，则以[bij]为效率矩阵的分配问题与以[aij]为效率矩阵的分配问题具有相同的最优解。指派问题的求解步骤：1)变换指派问题的系数矩

7、阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即从(cij)的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。2)进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所在列的其它0元素，记作Ø；这表示该列所代表的任务已指派完，不必再考虑别人了。依