運籌學(xué)——整數(shù)規(guī)劃與分配問題(已改無錯字)
2023-06-26 22:11:43 本頁面
【正文】 任務(wù)數(shù)不相等的分配問題 ? 有四項工作分配給六個人去完成，每個人分別完成各項工作的時間如下，依然規(guī)定每個人完成一項工作。每項工作只交給一個人去完成。即六個人中挑選哪四個人去完成，花費時間最少。 工作 人 I II III IV 1 2 3 4 5 6 3 7 3 6 5 5 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 工作 人 I II III IV V VI 1 2 3 4 5 6 3 7 3 6 5 5 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 二、分配問題與匈牙利法 目標(biāo)函數(shù)最大化的分配問題 ? ?? ??mimjijij xa z1 1m a x ? ?? ??mimjijij/ xb z1 1min令 bij = M aij ? ?? ??mimjijij xa z1 1m a x標(biāo)準(zhǔn)化 ? ?? ???mimjijij xa z1 139。m i n M為充分大的常數(shù)，可以得到 bij≥0。根據(jù)定理 1，這種轉(zhuǎn)換是等價的。 bij = ?aij – ui– vj = ?aij + M 若 aij≥0，轉(zhuǎn)換后的效率矩陣不符合匈牙利法的條件。 第四章 整數(shù)規(guī)劃及分配問題 作 業(yè) 一 ? 求下面指派問題的最優(yōu)解 ????????????????9107104106614159141217766698979712第三節(jié) 分枝定界法 第四章 整數(shù)規(guī)劃及分配問題 三、分枝定界法 分枝定界法的基本思想 ? 分枝定界法 可用于 全部類型 的整數(shù)規(guī)劃問題。 ? 設(shè)有最大化的整數(shù)規(guī)劃問題 A，對應(yīng)的 線性規(guī)劃為問題 B，從解問題 B開始，若其最優(yōu)解不符合 A的整數(shù)條件，那么 B的最優(yōu)目標(biāo)函數(shù)必是 A的最優(yōu)目標(biāo)函數(shù) z*的 上界 ，記作 ；而 A的任意可行解的目標(biāo)函數(shù)值將是 z*的 下界 。分支定界法就是將 B的可行域分成子區(qū)域 (稱為 分枝 )的方法，逐步減小和增大上、下界，最終得到整數(shù)規(guī)劃問題 A的 z*。 zz三、分枝定界法 分枝定界法實例 (1) 1. 求解 B： 其最優(yōu)解為 x1 = ， x2 = ，最優(yōu)目標(biāo)函數(shù)值為 z* = ????????????取整數(shù) 0,1432 23m a x :21212121xxxxxxxxzA???????????? 0,1432 23m a x21212121xxxxxxxxzB : 松弛問題 2. 定界： 令 x1 = 0， x2 = 0 作為初始整數(shù)解，其 z = 0，因此 。 ?z0?z3. 分枝： 在 B的最優(yōu)解中，任取一個非整數(shù)變量，如 x2 = ；因 x2 的最近鄰整數(shù)解為 x2 = 2或 x2 = 3， 其最優(yōu)整數(shù)解區(qū)間只能是 x2 ≥ 3或 x2 ≤ 2。對 B分別加上約束條件 x2 ≥ 3和 x2 ≤ 2， 可得到兩個子問題 B1和 B2。 三、分枝定界法 分枝定界法實例 (2) ??????????????? ,xxx.xx xxz B025450143223m a x:2122121211??????????????? xx.xx xxz B035450
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1