川大运筹学》课件-4整数规划课件.ppt

显然可将效率矩阵提出一个公因子100，得到等价的效率矩阵: 然后对这个效率矩阵用匈牙利法求解即可。 31.1 28.5 29.6 26.4 29.2 自由泳 33.6 30.4 38.9 28.5 33.3 蝶泳 41.8 34.7 42.2 33.1 43.4 蛙泳 35.4 37 33.8 32.9 37.7 仰泳 戊 丁 丙 乙 甲 解：该问题可看作指派问题。添加一个虚拟项目，得到如下效率矩阵 0 0 0 0 0 虚拟 31.1 28.5 29.6 26.4 29.2 自由泳 33.6 30.4 38.9 28.5 33.3 蝶泳 41.8 34.7 42.2 33.1 43.4 蛙泳 35.4 37 33.8 32.9 37.7 仰泳 戊 丁 丙 乙 甲 　 等价化简→ √ 0 0 0 0 0 虚拟 √ 4.7 2.1 3.2 0 2.8 自由泳 √ 5.1 1.9 10.4 0 4.8 蝶泳 √ 8.7 1.6 9.1 0 10.3 蛙泳 2.5 4.1 0.9 0 4.8 仰泳 戊 丁 丙 乙 甲 　 →……, 最后的效率矩阵为 0 0.9 0 2.8 0 虚拟 1.9 0.2 0.4 0 0 自由泳 2.3 0 7.6 0 2 蝶泳 6.2 0 6.6 0.3 7.8 蛙泳 1.6 4.1 0 1.9 3.9 仰泳 戊 丁 丙 乙 甲 作业 1，分配甲、乙、丙、丁四个人完成ABCDE五项任务，每个人完成各项任务的时间如表所示： 45 23 36 42 24 丁 32 4 0 28 27 34 丙 33 2 0 26 38 39 乙 37 42 31 29 25 甲 E D C B A 由于任务多于人数，故考虑： （a）任务E必须完成，其他各项可任意选3项完成； （b）其中有一人完成2项，其他每人完成一项。 分别确定最优方案，使完成任务总时间最少 2，用割平面法求解 对偶理论 作业答案 1. 已知线性规划问题： 要求：a)写出对偶问题，b)已知原问题最有解X*=(2,2,4,0),用互补松弛性求出对偶问题的最优解。 * 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运 筹 学 课 件 整数线性规划 Integer Linear Programming 第一节 整数规划问题的特点及应用 在整数规划模型中，逻辑变量起着很大的作用，下面说明逻辑变量的应用： 第二节 割平面法 问题： 解：用割平面法。 1。先解去掉取整条件的线性规划问题 3/4 -1/4 0 1 13/4 x1 3 -1/2 1/2 1 0 5/2 x2 2 0 0 2 3 cj -5/4 -1/4 0 0 cj-zj x4 x3 x2 x1 b xB cB 设其最终单纯形表为 2。找出非正数解变量中分数部基变量（此处为x2），并写出这一行的约束 将上式中所有常数写成正数和一个正分数之和 分数项移到右边，整数项移到左边 由于左边为整数，所以右边也为整数，所以 所以 由于 加入松弛变量 放入单纯形表 由上表用同样的方法，得 放入单纯形表，得 得最优解 第三节 分枝定界法 Max z=14.47059 x1=3.705882, x2=2.352941 Max z=14, x1=3, x2=2.66667 Max z=14.42857 x1=4, 2=2.142857 Max z=12 x1=3, x2=2 Max z=13.5 x1=2.25, x2=3 Max z=14.4 x1=4.2, x2=2 无解 x1≤3 x1≥4 x2≤2 x2≥3 × × x2≤2 x2≥3 Max z=12 x1=6, x2=0 Max z=14 x1=4, x2=2 Max z=14.28571 x1=5, x2=1.428571 Max z=14.2 x1=5.6,x2=1 无解 Max z=13 x1=5, x2=1 Max z=14.14286 x1=6, x2=0.714286 x1=4 x1≥5 x2≤1 x2=2 x1=5 x1≥6 x2=0 x2=1 × × Max z=14.4 x1=4.2, x2=2 无解 分配（指派）问题与匈牙利法 指派问题的数学模型一般形式如下： 例：有一份说明书，分别译成英、日、德、俄四种语言，现打算交给甲、乙、丙、丁四人完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表所示，应如何分配，才使这四个人分别完成这四项任务总的时间为最小。 9 13 15 4 译俄文 11 16 14 13 译德文 8 14 4 15 译日文 7