分配問題（指派問題，assignment problem）
這是個給n個人分配n項工作以獲得某個最高總效果的問題。第i個人完成第j項工作需要平均時間。要求給每個人分配一項工作，並要求分配完這些工作，以使完成全部任務的總時間為最小。
該問題可表示如下：
顯然，此問題可看作是運輸問題的特殊情況。可將此問題看作具有n個源和n個匯的問題，每個源有1單位的可獲量，而每個匯有1單位的需要量。從表面看，這問題要求用整數規劃以保證xij只能取0或1。
然而，幸運的是，此問題是運輸問題的特例，因此即使不限制xij取0或1，最優解也將取0或1。如果把婚姻看作分配問題，丹茨證明，整數性質證明一夫一妻會帶來最美滿幸福的生活！顯然，分配問題可以作為線性規劃問題來求解，儘管模型可能很大。
例如，給100人分配100項工作將使所得的模型具有10000個變數。這時，如採用專門演算法效果會更好。時間複雜度為o(n2)的匈牙利演算法便是好選擇，這是由kuhu（1955）提出的。
model:
!7個人，7個工作的分配問題;
sets:
workers/w1..w7/;
jobs/j1..j7/;
links(workers,jobs): cost,volume;
endsets
!目標函式;
min=@sum(links: cost*volume);
!每個工人只能有乙份工作;
@for(workers(i):
@sum(jobs(j): volume(i,j))=1;
);!每份工作只能有乙個工人;
@for(jobs(j):
@sum(workers(i): volume(i,j))=1;
);data:
cost= 6 2 6 7 4 2 5
4 9 5 3 8 5 8
5 2 1 9 7 4 3
7 6 7 3 9 2 7
2 3 9 5 7 2 6
5 5 2 2 8 11 4
9 2 3 12 4 5 10;
enddata
end計算的部分結果
最短路問題
給定n個點pi，i=1,2，…,n,組成集合,集合中任一點pi到另一點pj的距離用cij表示，如果pi到pj沒有弧聯結，則規定cij=+∞，又規定cii=0(1≤i≤n)，指定乙個終點pn，要求從pi點出發到pn的最短路線。這裡我們用動態規劃方法來做。用所在的點pi表示狀態，決策集合就是除pi以外的點，選定乙個點pj以後，得到效益cij並轉入新狀態pj，當狀態是pn時，過程停止。
顯然這是乙個不定期多階段決策過程。
定義f(i)是由pi點出發至終點pn的最短路程，由最優化原理可得
這是乙個函式方程，用lingo可以方便的解決。
!最短路問題;
model:
data:
n=10;
enddata
sets:
cities/1..n/: f; !10個城市;
roads(cities,cities)/
1,2 1,3
2,4 2,5 2,6
3,4 3,5 3,6
4,7 4,8
5,7 5,8 5,9
6,8 6,9
7,10
8,10
9,10
/: d, p;
endsets
data:
d=6 5
3 6 9
7 5 11
9 1
8 7 5
4 10
579;enddata
f(n)=0;
@for(cities(i) | i #lt# n:
f(i)=@min(roads(i,j): d(i,j)+f(j));
);!顯然，如果p(i,j)=1,則點i到點n的最短路徑的第一步是i --> j，否則就不是。
由此，我們就可方便的確定出最短路徑;
@for(roads(i,j):
p(i,j)=@if(f(i) #eq# d(i,j)+f(j),1,0)
);end計算的部分結果
最短路徑問題 專題
初中數學中最短路徑問題雖然只是乙個課題學習，但它在中學數學中的地位很重要，是大考 小考 競賽中經常涉及的乙個考點。所以我們要對它有足夠的重視。初中最短路徑問題主要針對軸對稱圖形考慮的。那麼只要涉及軸對稱圖形就有可能產生最短路徑問題。在此之前，我們接觸過的最短距離問題是 1 兩點間直線段最短 2 點到...
最短路線問題
考查知識點 兩點之間線段最短 垂線段最短 點關於線對稱 線段的平移 原型 飲馬問題 造橋選址問題 考的較多的還是 飲馬問題 出題背景變式有角 三角形 菱形 矩形 正方形 梯形 圓 座標軸 拋物線等。解題總思路 找點關於線的對稱點實現 折 轉 直 近兩年出現 三折線 轉 直 等變式問題考查。以下主要對...
動態規劃最短路徑問題
首先，我們來觀察上述演算法。在求b1到e的最短路徑的時候，先求出從c2到e的最短路徑 而在求從b2剄e的最短路徑的時候，又求了一遍從c2剄e的最短路徑。也就是說，從c2到e的最短路徑求了兩遍。同樣可以發現，在求從cl c2剄e的最短路徑的過程中，從dl到e的最短路徑也被求了兩遍。而在整個程式中，從d...