投資問題(0-1規劃)
匈牙利算法求解0-1規劃問題
解答:
項目之間是互斥關系,所以使用x1+x2+x3=1;
項目5是以項目1為先驗條件,所以x5<=x1,意味著x1=1時,x5=1或0 ,但x1=0時,x5=0
案例- 互斥約束問題
1)當兩個約束條件是互斥時,新建立一個約束條件y(0-1)
2)如果M取無窮大的數,此時就能讓其中一項約束失去作用
3)這道題是說存在一個約束 4x1+5x2<=200和另一個約束3x1+5x2<=180,這兩個約束互斥,所以引入一個新的約束M
互斥約束的推廣
p-q=yi相加:在p個約束條件中選擇q個
案例-固定費用問題
解答:
可變成本就是成本,利潤=售價-可變成本
最終:
這里還存在一個問題:如果不租用每個產品對應的生產線,則不能夠生產相應的產品
所以要引入M1(無窮大的數),檢驗x1,x2,x3是否有生產
案例-指派問題
解答:
1)因為每一個人可以選擇四項工作中的一個,共有四個人,則一共有4*4=16項
所以,要使用二維數組的樣式xij來表示第i個人是否做第j項工作
指派問題標準形式
數學模型
非標準形式的指派問題
增加新的約束或新的約束條件
1)
最大化指派問題:不是成本和時間最小化指派問題,而是利潤最大化
使用最大元素-所有的值=新的指派系數
2)
人數和工作數不等,代價為0,xii的值為0
3)
一個人可做多件工作,幾個相同的人,不做任何限制
4)
某工作一定不能由某人做,若x13=0,則設x13<=0
指派問題的匈牙利解法的一般步驟
1)系數矩陣:每個人做每項工作所需要付出的代價
2)aij->bij
變為所有的行和所有的列只有一個1,其余元素全為0,意味著整個矩陣的秩=4
第一步:
第二步:
1)獨立0元素:行和列都不相等的0元素
2)
只有一個0元素的行,劃掉所在列
只有一個0元素的列,劃掉所在行
1)
如果還有0元素沒有畫圈,就找到最少的0元素的行或列
2)
畫圈數目=矩陣的階,指派問題的最優解已找到
第三步:
直線數l=畫圈的數目m
第四步:
行減去min,列加上min,之后再回到第二步,去重復過程
匈牙利解法的實例1
解答:
第一步
第二步:
記住反復做
最后:
輸出的矩陣:圈為1,其余為0
最優解=1所對應的原始矩陣元素相加
匈牙利解法的實例2
解答:
第一步和第二步:
第三步:
第四步:
加減最小得到新的指派矩陣,再重復第二步
重復第二步:
最優解=2+4+1+8=15
指派問題的matlab程序
1)向量方便后期計算
2)for循環,使所有的行取值為1,所有的列取值為1
