Dal ve sınır yöntemiyle gezgin satıcı probleminin çözümüne bir örnek. Ne olduğunu? Gezgin satıcı problemini çözmek için ayrıntılı bir teknik

Taşıma lojistiğinin (ve genel olarak optimizasyon problemlerinin sınıfının) en ünlü ve önemli problemlerinden biri, gezgin satıcı sorunu(ingilizce "Gezgin satıcı sorunu", TSP). Ayrıca bulundu adı " gezgin tüccar sorunu". Problemin özü optimali, yani belirli noktalardan bir kez geçen en kısa yolu bulmaktır. Örneğin, gezgin satıcı problemi, mallarınızla belirli şehirleri bir kez dolaşıp başlangıç ​​noktasına geri dönmenizi sağlayan en karlı rotayı bulmak için kullanılabilir. Rota karlılığının ölçüsü, yolda harcanan minimum süre, yolun minimum maliyeti veya en basit durumda yolun minimum uzunluğu olacaktır.

Gezgin satıcı problemini ilk kimin ve ne zaman incelemeye başladığı bilinmiyor, ancak bir çözüm öneren ilk kişilerden biriydi. benzer sorun 19. yüzyılın seçkin matematikçisi. - William Hamilton. Burada problemin kapalı bir versiyonunu (yani sonunda başlangıç ​​noktasına geri döneceğimiz şekilde) ve çözümünü ele alacağız. dal ve sınır yöntemi.

Gezgin satıcı problemini çözmek için genel plan

Dal ve sınır yöntemini kullanarak gezgin satıcı problemini çözmek için aşağıdakileri yapmanız gerekir: algoritma(sıralama):

1. Başlangıç ​​verileriyle bir matrisin oluşturulması.
2. Satırlarda minimum bulma.
3. Dize azaltma.
4. Sütunlara göre minimumu bulma.
5. Sütun azaltma.
6. Sıfır hücre tahminlerinin hesaplanması.
7. Matris azaltma.
8. Tam yol henüz bulunamadıysa 2. adıma, bulunursa 9. adıma gidin.
9. Toplam yol uzunluğunun hesaplanması ve yol yapımı.

Gezici tüccarın sorununu çözmenin bu aşamaları aşağıda daha ayrıntılı olarak tartışılmaktadır.

Gezgin satıcı problemini çözmek için ayrıntılı bir teknik

Problemi daha iyi anlamak için grafiğin köşeleri vb. kavramlarla değil, basit kavramlarla ve gerçeğe mümkün olduğunca yakın işlem yapacağız: grafiğin köşeleri "şehirler" olarak adlandırılacak, onları birbirine bağlayan kenarlar - "yollar".

Yani, gezgin satıcı problemini çözme tekniği:

1. Başlangıç ​​verileriyle bir matris oluşturma

Öncelikle şehirleri birbirine bağlayan yolların uzunluklarını aşağıdaki tablo şeklinde sunmak gerekiyor:

Örneğimizde 4 şehrimiz var ve tablo seyahat yönüne bağlı olarak her şehirden diğer 3 şehire olan mesafeyi gösteriyor (çünkü bazı demiryolu rayları tek yönlü olabilir, vb.).

Şehirden aynı şehre olan mesafe M harfi ile belirtilir. Sonsuzluk işareti de kullanılır. Bu, yolun bu bölümünün koşullu olarak sonsuz uzun bir bölüm olarak alınması için yapılır. O zaman 1. şehirden 1. şehire, 2. şehirden 2. şehire vb. hareketi seçmek mantıklı olmayacaktır. rota segmenti olarak

2. Satırlarla minimumu bulma

Bulduk Minimum değer her satırda ( di) ve ayrı bir sütuna yazın.

3. İp azaltma

Satırları azaltırız - satırdaki her öğeden bulunan minimumun (di) karşılık gelen değerini çıkarırız.

Sonuç olarak, her satırda en az bir boş hücre.

4. Sütunlara göre minimumu bulma

5. Sütun azaltma

Matrisin her bir elemanından ilgili dj'yi çıkarırız.

Sonuç olarak, her sütunda en az bir boş hücre.

6. Boş hücre tahminlerinin hesaplanması

Elde edilen dönüştürülmüş matrisin her sıfır hücresi için şunu buluruz " değerlendirme". toplamı olacak minimum eleman verilen sıfır hücrenin bulunduğu satıra göre ve sütuna göre minimum öğe. Kendisi dikkate alınmaz. Daha önce bulunan di ve dj dikkate alınmaz. Ortaya çıkan puan, parantez içinde sıfırın yanına yazılır.

Ve böylece tüm sıfır hücreler için:

7. Matris azaltma

En yüksek puana sahip sıfır hücreyi seçiyoruz. "ile değiştiriyoruz. M". Yolun bölümlerinden birini bulduk. Bunu yazıyoruz (4'ten 2'ye kadar olan örneğimizde hangi şehirden taşınıyoruz).

Bu çizgiyi ve iki "M"nin oluştuğu sütunu tamamen çiziyoruz. karşılık gelen bir hücrede dönüş yolu, başka bir "M" harfi koyun (çünkü geri dönmeyeceğiz).

8. Tam yol henüz bulunamadıysa 2. adıma, bulunursa 9. adıma gidin

Yolun tüm bölümlerini henüz bulamadıysak, o zaman 2 -inci nokta ve tekrar satırlarda ve sütunlarda minimumları arayın, azaltmalarını yapın, sıfır hücre tahminlerini hesaplayın, vb.

Yolun tüm bölümleri bulunduysa (veya tüm bölümler henüz bulunamadı, ancak yolun geri kalanı açıksa), adıma gidin 9 .

9. Toplam yol uzunluğunun hesaplanması ve güzergâh yapımı

Yolun tüm bölümlerini bulduktan sonra, yalnızca onları birbirine bağlamak ve yolun toplam uzunluğunu hesaplamak kalır (bu rota boyunca bir yolculuğun maliyeti, harcanan zaman vb.). İlk verilerle ilk tablodan şehirleri birbirine bağlayan yolların uzunluklarını alıyoruz.

Örneğimizde, rota aşağıdaki gibidir: 4 → 2 → 3 → 1 → 4 .

Toplam yol uzunluğu: L=30.

Gezgin satıcı probleminin pratik uygulaması

Gezgin satıcı probleminin pratikteki uygulaması oldukça kapsamlıdır. Özellikle, bir pop grubu şehirleri gezerken en kısa rotayı bulmak, sağlayan bir dizi teknolojik işlemi bulmak için kullanılabilir. en az zaman tüm üretim döngüsünün yürütülmesi vb.

Gezgin satıcı problemini çevrimiçi çözme

Galyautdinov R.R.

© Materyali kopyalamaya yalnızca doğrudan bir köprü belirtirseniz izin verilir.

Gezgin satıcı probleminde, n şehir etrafında optimal bir rota oluşturmak için (n-1) arasından en iyi olanı seçilmelidir! zaman, maliyet veya rota uzunluğu kriterine göre seçenekler. Bu problem Hamilton çevriminin tanımı ile ilgilidir. Minimum uzunluk. Bu gibi durumlarda, tüm küme Muhtemel çözümler bir ağaç olarak temsil edilmelidir - döngüler ve döngüler içermeyen bağlantılı bir grafik. Ağacın kökü, tüm seçenekler kümesini birleştirir ve ağacın tepeleri, kısmen sıralı karar seçeneklerinin alt kümeleridir.

Servis ataması. Hizmeti kullanarak, iki yöntemi kullanarak çözümünüzü kontrol edebilir veya gezgin satıcı sorununa yeni bir çözüm elde edebilirsiniz: dal ve sınır yöntemi ve Macar yöntemi.

Gezgin satıcı probleminin matematiksel modeli

Formüle edilmiş problem bir tamsayı problemidir. Gezgin i. şehirden j. şehire hareket ederse x ij =1 ve durum bu değilse x ij =0 olsun.
İlk şehirle aynı yerde bulunan bir şehri (n+1) resmi olarak tanıtalım, yani. (n+1) şehirlerin ilk şehir dışındaki herhangi bir şehre olan uzaklıkları, ilk şehire olan mesafelere eşittir. Üstelik sadece ilk şehirden ayrılabiliyorsa, o zaman sadece (n+1) şehre gelebilir.
Yolda bu şehre yapılan ziyaretlerin sayısına eşit ek tamsayı değişkenleri sunuyoruz. u 1 \u003d 0, u n +1 \u003d n. Kapalı yollardan kaçınmak için ilk şehri terk edin ve tanıttığımız (n+1)'e dönün. ek kısıtlamalar değişkenler x ij ve değişkenler u i (u i negatif olmayan tam sayılardır).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, i=1 j≠n+1 olduğunda
0≤u ben ≤n, x in+1 =x i1 , i=2..n

Gezgin satıcı problemini çözme yöntemleri

1. dal ve sınır yöntemi (Little'ın algoritması veya alt döngülerin ortadan kaldırılması). Dal ve bağlı çözüm örneği;
2. macar yöntemi. Macar yöntemini kullanan bir çözüm örneği.

Little'ın Algoritması veya Subloop Eliminasyonu

1. Satır azaltma işlemi: matrisin her satırındaki minimum d min öğesini bulun ve ilgili satırın tüm öğelerinden çıkarın. Alt limit: H=∑d min.
2. Sütun indirgeme işlemi: matrisin her sütununda minimum eleman d min seçilir ve ilgili sütunun tüm elemanlarından çıkarılır. Alt limit: H=H+∑d min .
3. İndirgeme sabiti H, tüm kabul edilebilir Hamilton konturları kümesinin alt sınırıdır.
4. Satır ve sütunlarla indirgenmiş bir matris için sıfır derecelerini bulma. Bunu yapmak için, matristeki sıfırları geçici olarak "∞" işaretiyle değiştirin ve bu sıfıra karşılık gelen satır ve sütunun minimum öğelerinin toplamını bulun.
5. Sıfır elemanının derecesi maksimum değerine ulaşan bir yay (i,j) seçin.
6. Tüm Hamilton konturlarının kümesi iki alt kümeye ayrılır: (i,j) yayı içeren ve onu içermeyen (i*,j*) Hamiltonian konturlarının bir alt kümesi. (i, j) yayı içeren bir kontur matrisi elde etmek için, matristeki i satırı ve j sütununun üzerini çizin. Hamilton olmayan bir kontur oluşumunu önlemek için simetrik elemanı (j, i) "∞" işaretiyle değiştirin. Arkın ortadan kaldırılması, matristeki elemanın ∞ ile değiştirilmesiyle sağlanır.
7. Hamiltonian konturlarının matrisi, indirgeme sabitleri H(i,j) ve H(i*,j*) aranarak indirgenir.
8. Hamiltonian konturları H(i,j) ve H(i*,j*) alt kümesinin alt sınırları karşılaştırılır. H(i,j) ise
9. Dallanma sonucunda bir matris (2x2) elde edilirse, Hamiltoniyenlerin dallanmasıyla elde edilen kontur ve uzunluğu belirlenir.
10. Hamiltonian konturunun uzunluğu, sarkan dalların alt sınırları ile karşılaştırılır. Konturun uzunluğu alt sınırlarını aşmazsa, sorun çözülür. Aksi takdirde, elde edilen konturdan daha düşük bir alt sınıra sahip alt kümelerin dalları, daha kısa uzunlukta bir rota elde edilene kadar geliştirilir.

Örnek. Little'ın algoritmasını kullanarak bir matris ile gezgin satıcı problemini çözün

	1	2	3	4
1	-	5	8	7
2	5	-	6	15
3	8	6	-	10
4	7	15	10	-

Çözüm. Rastgele bir rota olarak alalım: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). O zaman F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Kümenin alt sınırını belirlemek için kullanırız azaltma işlemi veya matrisin, D matrisinin her satırındaki minimum elemanı bulmanın gerekli olduğu satırlarla indirgenmesi: d i = min(j) d ij

ben j	1	2	3	4	5	ben
1	M	20	18	12	8	8
2	5	M	14	7	11	5
3	12	18	M	6	11	6
4	11	17	11	M	12	11
5	5	5	5	5	M	5

Ardından, söz konusu satırın öğelerinden d i çıkarın. Bu bakımdan yeni elde edilen matriste her satırda en az bir sıfır olacaktır.

ben j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Her sütunda minimum elemanı bulduğumuz sütunlar üzerinde aynı indirgeme işlemini yapıyoruz:
d j = min(i) d ij

ben j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M
dj	0	0	0	0	0

Minimum elemanları çıkardıktan sonra, d i ve d j miktarlarının çağrıldığı tamamen indirgenmiş bir matris elde ederiz. döküm sabitleri.

ben j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

İndirgeme sabitlerinin toplamı, H'nin alt sınırını belirler: H = ∑d ben + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Matris elemanları d ij, i noktasından j noktasına olan mesafeye karşılık gelir.
Matriste n tane şehir olduğundan, D negatif olmayan elemanları d ij ≥ 0 olan bir nxn matrisidir.
Her kabul edilebilir rota, satıcının şehri yalnızca bir kez ziyaret ettiği ve orijinal şehre döndüğü bir döngüdür.
Rotanın uzunluğu şu ifadeyle belirlenir: F(M k) = ∑d ij
Ayrıca, her satır ve sütun, d ij öğesiyle yalnızca bir kez rotaya dahil edilir.
Aşama 1.
Dal kenarı tanımlama

ben j	1	2	3	4	5	ben
1	M	12	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	12	M	0(5)	5	5
4	0(0)	6	0(0)	M	1	0
5	0(0)	0(6)	0(0)	0(0)	M	0
dj	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Kenar (5,2) için indirgeme sabitlerinin en büyük toplamı (0 + 6) = 6'dır, bu nedenle küme (5,2) ve (5*,2*) olmak üzere iki alt kümeye ayrılır.
Kenar eleme(5.2) d 52 = 0 öğesini M ile değiştirerek gerçekleştiriyoruz, ardından sonuçta ortaya çıkan alt küme (5*,2*) için mesafe matrisinin bir sonraki indirgemesini gerçekleştiriyoruz, sonuç olarak indirgenmiş bir matris elde ediyoruz.

ben j	1	2	3	4	5	ben
1	M	12	10	4	0	0
2	0	M	9	2	6	0
3	6	12	M	0	5	0
4	0	6	0	M	1	0
5	0	M	0	0	M	0
dj	0	6	0	0	0	6

Bu altkümenin Hamilton döngülerinin alt sınırı: H(5*,2*) = 35 + 6 = 41
Kenar dahil etme(5.2), Hamiltonyen olmayan bir döngünün oluşumunu dışlamak için, d25 öğesinin M ile değiştirildiği 5. sıra ve 2. sütunun tüm öğelerini ortadan kaldırarak gerçekleştirilir.

ben j	1	3	4	5	ben
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	0	M	1	0
dj	0	0	0	0	0

Alt kümenin (5,2) alt sınırı: H(5,2) = 35 + 0 = 35 ≤ 41
Bu alt kümenin (5,2) alt sınırı alt kümeden (5*,2*) küçük olduğundan, (5,2) kenarını yeni bir sınırla H = 35 rotaya dahil ederiz.
Adım 2.
Dal kenarı tanımlama ve bu kenara göre rotaların tamamını iki alt kümeye (i,j) ve (i*,j*) bölün.
Bu amaçla, matrisin sıfır elemanlı tüm hücreleri için, sıfırları dönüşümlü olarak M (sonsuz) ile değiştiririz ve onlar için ortaya çıkan azaltma sabitlerinin toplamını belirleriz, bunlar parantez içinde verilir.

ben j	1	3	4	5	ben
1	M	10	4	0(5)	4
2	0(2)	9	2	M	2
3	6	M	0(7)	5	5
4	0(0)	0(9)	M	1	0
dj	0	9	2	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Kenar (4,3) için indirgeme sabitlerinin en büyük toplamı (0 + 9) = 9'dur, bu nedenle küme (4,3) ve (4*,3*) olmak üzere iki alt kümeye ayrılır.
Kenar eleme(4.3) d 43 = 0 öğesini M ile değiştirerek gerçekleştiriyoruz, ardından sonuçtaki alt küme (4*,3*) için mesafe matrisinin bir sonraki indirgemesini gerçekleştiriyoruz, sonuç olarak indirgenmiş bir matris elde ediyoruz.

ben j	1	3	4	5	ben
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	M	M	1	0
dj	0	9	0	0	9

Bu altkümenin Hamilton döngülerinin alt sınırı: H(4*,3*) = 35 + 9 = 44
Kenar dahil etme(4.3), Hamiltonyen olmayan bir döngünün oluşumunu dışlamak için, d 34 öğesinin M ile değiştirildiği 4. sıra ve 3. sütunun tüm öğelerini ortadan kaldırarak gerçekleştirilir.

İndirgeme işleminden sonra, indirgenmiş matris şöyle görünecektir:

ben j	1	4	5	ben
1	M	4	0	0
2	0	2	M	0
3	6	M	5	5
dj	0	2	0	7

İndirgenmiş matrisin indirgeme sabitlerinin toplamı: ∑d i + ∑d j = 7
(4,3) alt kümesinin alt sınırı: H(4,3) = 35 + 7 = 42 ≤ 44
42 > 41 olduğundan, daha fazla dallanma için alt kümeyi (5,2) hariç tutuyoruz.
Önceki plana dönüyoruz X 1 .
X Planı 1.

ben j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	M	0	0	M

azaltma işlemi.

ben j	1	2	3	4	5
1	M	6	10	4	0
2	0	M	9	2	6
3	6	6	M	0	5
4	0	0	0	M	1
5	0	M	0	0	M

Aşama 1.
Dal kenarı tanımlama ve bu kenara göre rotaların tamamını iki alt kümeye (i,j) ve (i*,j*) bölün.
Bu amaçla, matrisin sıfır elemanlı tüm hücreleri için, sıfırları dönüşümlü olarak M (sonsuz) ile değiştiririz ve onlar için ortaya çıkan azaltma sabitlerinin toplamını belirleriz, bunlar parantez içinde verilir.

ben j	1	2	3	4	5	ben
1	M	6	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	6	M	0(5)	5	5
4	0(0)	0(6)	0(0)	M	1	0
5	0(0)	M	0(0)	0(0)	M	0
dj	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Kenar (4,2) için indirgeme sabitlerinin en büyük toplamı (0 + 6) = 6'dır, bu nedenle küme (4,2) ve (4*,2*) olmak üzere iki alt kümeye ayrılır.
Kenar eleme(4.2) d 42 = 0 öğesini M ile değiştirerek gerçekleştiriyoruz, ardından sonuçtaki alt küme (4*,2*) için mesafe matrisinin bir sonraki indirgemesini gerçekleştiriyoruz, sonuç olarak indirgenmiş bir matris elde ediyoruz.

ben j	1	2	3	4	5	ben
1	M	6	10	4	0	0
2	0	M	9	2	6	0
3	6	6	M	0	5	0
4	0	M	0	M	1	0
5	0	M	0	0	M	0
dj	0	6	0	0	0	6

Bu altkümenin Hamilton döngülerinin alt sınırı: H(4*,2*) = 41 + 6 = 47
Kenar dahil etme(4.2), Hamiltonyen olmayan bir döngünün oluşumunu dışlamak için, d 24 öğesinin M ile değiştirildiği 4. sıra ve 2. sütunun tüm öğelerini ortadan kaldırarak gerçekleştirilir.
Sonuç olarak, indirgeme işlemine tabi olan başka bir indirgenmiş matris (4 x 4) elde ederiz.
İndirgeme işleminden sonra, indirgenmiş matris şöyle görünecektir:

ben j	1	3	4	5	ben
1	M	10	4	0	0
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
dj	0	0	0	0	0

İndirgenmiş matrisin indirgeme sabitlerinin toplamı: ∑d i + ∑d j = 0
(4,2) alt kümesinin alt sınırı: H(4,2) = 41 + 0 = 41 ≤ 47
Bu alt kümenin (4,2) alt sınırı alt kümeden (4*,2*) küçük olduğundan, (4,2) kenarını yeni bir sınırla H = 41 rotaya dahil ederiz.
Adım 2.
Dal kenarı tanımlama ve bu kenara göre rotaların tamamını iki alt kümeye (i,j) ve (i*,j*) bölün.
Bu amaçla, matrisin sıfır elemanlı tüm hücreleri için, sıfırları dönüşümlü olarak M (sonsuz) ile değiştiririz ve onlar için ortaya çıkan azaltma sabitlerinin toplamını belirleriz, bunlar parantez içinde verilir.

ben j	1	3	4	5	ben
1	M	10	4	0(9)	4
2	0(6)	9	M	6	6
3	6	M	0(5)	5	5
5	0(0)	0(9)	0(0)	M	0
dj	0	9	0	5	0

d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Kenar (1,5) için indirgeme sabitlerinin en büyük toplamı (4 + 5) = 9'dur, bu nedenle küme (1,5) ve (1*,5*) olmak üzere iki alt kümeye ayrılır.
Kenar eleme(1.5) d 15 = 0 öğesini M ile değiştirerek gerçekleştiriyoruz, ardından sonuçtaki alt küme (1*,5*) için mesafe matrisinin bir sonraki indirgemesini gerçekleştiriyoruz, sonuç olarak indirgenmiş bir matris elde ediyoruz.

ben j	1	3	4	5	ben
1	M	10	4	M	4
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
dj	0	0	0	5	9

Bu altkümenin Hamilton döngülerinin alt sınırı: H(1*,5*) = 41 + 9 = 50
Kenar dahil etme(1.5), Hamiltonyen olmayan bir döngünün oluşumunu dışlamak için, d51 öğesinin M ile değiştirildiği 1. sıra ve 5. sütunun tüm öğelerini ortadan kaldırarak gerçekleştirilir.
Sonuç olarak, indirgeme işlemine tabi olan başka bir indirgenmiş matris (3 x 3) elde ederiz.
İndirgeme işleminden sonra, indirgenmiş matris şöyle görünecektir:

ben j	1	3	4	ben
2	0	9	M	0
3	6	M	0	0
5	M	0	0	0
dj	0	0	0	0

İndirgenmiş matrisin indirgeme sabitlerinin toplamı: ∑d i + ∑d j = 0
(1.5) alt kümesinin alt sınırı: H(1.5) = 41 + 0 = 41 ≤ 50
Bu alt kümenin (1,5) alt sınırı alt kümeden (1*,5*) küçük olduğundan, kenarı (1,5) yeni bir sınır H = 41 ile rotaya dahil ederiz.
Aşama 3.
Dal kenarı tanımlama ve bu kenara göre rotaların tamamını iki alt kümeye (i,j) ve (i*,j*) bölün.
Bu amaçla, matrisin sıfır elemanlı tüm hücreleri için, sıfırları dönüşümlü olarak M (sonsuz) ile değiştiririz ve onlar için ortaya çıkan azaltma sabitlerinin toplamını belirleriz, bunlar parantez içinde verilir.

ben j	1	3	4	ben
2	0(15)	9	M	9
3	6	M	0(6)	6
5	M	0(9)	0(0)	0
dj	6	9	0	0

d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
(2,1) kenarı için indirgeme sabitlerinin en büyük toplamı (9 + 6) = 15'tir, bu nedenle küme iki alt kümeye (2,1) ve (2*,1*) bölünmüştür.
Kenar eleme(2.1) d 21 = 0 öğesini M ile değiştirerek gerçekleştiriyoruz, ardından sonuçtaki alt küme (2*,1*) için mesafe matrisinin bir sonraki indirgemesini gerçekleştiriyoruz, sonuç olarak indirgenmiş bir matris elde ediyoruz.

ben j	1	3	4	ben
2	M	9	M	9
3	6	M	0	0
5	M	0	0	0
dj	6	0	0	15

Bu altkümenin Hamilton döngülerinin alt sınırı: H(2*,1*) = 41 + 15 = 56
Kenar dahil etme(2.1), Hamiltonyen olmayan bir döngünün oluşumunu dışlamak için, d12 öğesinin M ile değiştirildiği 2. sıra ve 1. sütunun tüm öğelerini ortadan kaldırarak gerçekleştirilir.
Sonuç olarak, indirgeme işlemine tabi olan başka bir indirgenmiş matris (2 x 2) elde ederiz.
İndirgeme işleminden sonra, indirgenmiş matris şöyle görünecektir:

ben j	3	4	ben
3	M	0	0
5	0	0	0
dj	0	0	0

İndirgenmiş matrisin indirgeme sabitlerinin toplamı:
∑d ben + ∑d j = 0
(2,1) alt kümesinin alt sınırı: H(2,1) = 41 + 0 = 41 ≤ 56
Bu alt kümenin (2,1) alt sınırı alt kümeden (2*,1*) küçük olduğundan, (2,1) kenarını yeni sınır H = 41 olan rotaya dahil ederiz.
Bu matrise göre (3,4) ve (5,3) kenarlarını Hamilton yoluna dahil ediyoruz.
Sonuç olarak, Hamiltonian dallanma ağacı boyunca döngü kenarlardan oluşur:
(4.2), (2.1), (1.5), (5.3), (3.4). Rota uzunluğu F(Mk) = 41

Karar ağacı.

																														1
								(5*,2*), H=41																																												(5,2)
(4*,2*), H=47																	(4,2)																															(4*,3*), H=44								(4,3)
								(1*,5*), H=50																	(1,5)
																(2*,1*), H=56																		(2,1)
																												(3,4)												(3*,4*), H=41
																								(5,3)								(5*,3*), H=41

giriiş

1. Teorik kısım 6

1.1 Grafik teorisinin temel kavramları 6

1.2 Gezgin satıcı probleminin çözümü ve bazı özellikleri. sekiz

1.3 Grafik 10'da gezgin satıcı probleminin bir problem olarak ifadesi

1.4 Hamilton konturunun varlığı için koşullar 10

1.5 Dal ve Sınır Yöntemi……………………………………………………. on bir

1.6 Gezgin satıcı probleminin pratik uygulaması……………………… 17

2. Pratik kısım 20

Çözüm

bibliyografya

giriiş

Karar teorisi, matematik, ekonomi, yönetim ve psikoloji kavramlarını ve yöntemlerini içeren bir çalışma alanıdır. İnsanların çeşitli türdeki sorunları çözmek için tercih ettikleri yol kalıplarını inceler ve aynı zamanda en karlı olası çözümleri bulmanın yollarını araştırır.

Ders çalışmasında, gezgin satıcı problemini çözmek için bazı yöntemler, çözüm algoritmaları ele alınmaktadır.

Günlük uygulamada ele alınması gereken birçok görev çok değişkenlidir. Piyasa ilişkileri koşullarında birçok olası seçenek arasından, doğal, ekonomik ve teknolojik fırsatlara getirilen kısıtlamalar altında en iyi çözümleri bulmak zorundadır. Bu bağlamda, ekonomik durumların ve sistemlerin analizi ve sentezi için matematiksel yöntemlerin ve modern bilgisayar teknolojisinin uygulanması gerekli hale geldi.

Bu dönem ödevi gezgin satıcı probleminin ele alınması, onu çözmenin yolları.

Gezgin satıcı problemi ele alınmış ve gezgin satıcı problemini çözmek için dal ve sınır yönteminin algoritması verilmiştir.

teorik kısım

1.1 Grafik teorisinin temel kavramları

Grafik teorisi kullanılarak birçok karar verme problemi çözülebilir.

Grafik temsiller, bir düzlemde incelenen süreç sisteminin veya olgunun görsel temsilleridir: çizimler, çizimler, diyagramlar ve blok diyagramlar, diyagramlar, grafikler. Graf teorisi dilinde birçok problem oluşturulur ve çözülür. teknik görevler, ekonomi, sosyoloji, yönetim vb. alanlardaki görevler. Grafikler, nesneleri ve aralarındaki ilişkiyi görsel olarak temsil etmek için kullanılır.

İzin vermek G-yönsüz grafik. Geometrik olarak, bir grafik, belirli çiftleri çizgilerle birbirine bağlanan bir dizi köşe (nokta) olarak temsil edilebilir. Örneğin, şehirleri birbirine bağlayan bir yol ağı, ,,,, aşağıdaki gibi bir grafik olarak gösterilebilir. Şehirler noktalarla (köşeler) ve yollar yönsüz çizgilerle gösterilir (Şekil 1.1).

Şekil 1.1 Şehirler arası yol ağı.

Yönlendirilmemiş hatlar, ilgili şehir çifti arasında iki yönlü trafik olduğu anlamına gelir. Çizgi kesişimleri köşe olarak kabul edilmez.

Bir grafiği tasvir ederken, köşelerin düzlemdeki konumu, kenarların eğriliği ve uzunluğu (Şekil 1.2) önemli değildir.

şekil 1.2 Grafiklerin görüntüsü

Grafiklerin köşeleri harflerle veya doğal sayılarla gösterilir. Grafiğin kenarları sayı çiftleridir.

E gitmek G Her iki bitişik kenarın bir bitiş noktası olacak şekilde sonlu veya sonsuz bir kenar dizisine denir. Ayrıca aynı kenar E rotada birkaç kez meydana gelebilir.

Döngüsel rota, başlangıç ​​ve bitiş noktaları aynı olan bir rotadır.

Yol, her bir kenarının en fazla bir kez meydana geldiği bir yoldur; bir zincirdeki köşeler en fazla bir kez tekrarlanabilir. Bir zincirin herhangi bir bölümü bir zincirdir. Döngüsel olmayan bir yol, içinde tekrarlanan bir tepe noktası yoksa basit bir yoldur.

Her köşe çifti arasında , , , bir yol () varsa, bu yolun ilk tepe noktası ve son tepe noktası olacak şekilde bir graf güçlü bağlantılı olarak adlandırılır.

Bir graf, bir çift köşesi arasında, böyle bir eleman dizisi (yaylar veya kenarlar veya hem yaylar hem de kenarlar) varsa, bu dizideki herhangi bir komşu elemanın ortak bir tepe noktasına sahip olması durumunda bağlantılı olarak adlandırılır. Açıktır ki, güçlü bağlantılı herhangi bir grafik bağlıdır. Bağlı bir yönsüz graf, çevrimi yoksa ağaç olarak adlandırılır. Bir ağaçta, herhangi iki köşe tek bir zincirle bağlanır.

1.2 Gezgin satıcı problemine yönelik çözümlerin ifadesi ve bazı özellikleri

Gezgin satıcı (gezgin tüccar) ilk şehri terk etmeli, şehirleri bilinmeyen bir sırayla bir kez ziyaret etmelidir. 2,1,3.. n ve ilk şehre geri dönün. Şehirler arası mesafeler biliniyor. Gezgin satıcının kapalı yolunun (turunun) en kısa olması için şehirler hangi sırayla geçilmelidir?

Sorunu bilimsel bir forma getirmek için bazı terimler veriyoruz. Rakamlarla yeniden numaralandırılmış şehirler j T=(1,2,3..n) . Gezgin satıcı turu, döngüsel bir permütasyon ile tanımlanabilir. t=(j 1 , j 2 ,.., j n , j 1 ) , ve tüm j 1 .. j n – farklı sayılar; başında ve sonunda tekrarlamak j 1 , permütasyonun döngülü olduğunu gösterir. Köşe çiftleri arasındaki mesafeler İTİBAREN ij bir matris oluşturmak İTİBAREN. Görev böyle bir tur bulmak t:

(1)

Gezgin satıcı probleminin matematiksel formülasyonu ile ilgili olarak iki açıklama yapmak uygundur.

1) Aşamalı İTİBAREN ij mesafeler anlamına gelir, bu nedenle negatif olmamalıdırlar, yani. hepsi için j T:

İTİBAREN ij  0; C jj = ∞ (2)

(son eşitlik turda döngü yasağı anlamına gelir), simetrik, yani. hepsi için i, j:

İTİBAREN ij = C ji (3)

ve üçgen eşitsizliğini sağlayın, yani. hepsi için:

İTİBAREN ij + C jk  C ik (4)

Matematiksel formülasyon, keyfi bir matrisi ifade eder. Bu yapılır çünkü birçok uygulamalı görevler, ana model tarafından açıklanan, ancak tüm koşulları (2)-(4) karşılamayan. Koşul (3) özellikle sık sık ihlal edilir (örneğin, İTİBAREN ij- mesafe değil, ücret: genellikle bir biletin orada bir fiyatı vardır ve başka bir fiyat geri alınır). Bu nedenle, gezgin satıcı probleminin iki versiyonu arasında ayrım yapacağız: koşul (3) sağlandığında simetrik bir problem ve aksi halde asimetrik bir problem. Koşullar (2)-(4) varsayılan olarak karşılanmış olarak kabul edilecektir.

2) Asimetrik gezgin satıcı probleminde tüm turlar t=(j 1 , j 2 ,.., j n , j 1 ) ve t’=(j 1 , j n ,.., j 2 , j 1 ) farklı uzunlukları vardır ve her ikisi de sayılmalıdır. farklı turlar açıkçası (n-1)! .

Döngüsel permütasyonda ilk ve son sıradaki sayıyı sabitleyelim. j 1 , ve gerisi n-1 tüm sayıları yeniden düzenle (n-1)! olası yollar. Sonuç olarak tüm asimetrik turları elde ederiz. Simetrik turlar mevcut

iki kat daha az, çünkü her biri iki kez sayılır: t Ve nasıl t’ . C'nin sadece 1'lerden ve 0'lardan oluştuğu düşünülebilir. O zamanlar İTİBAREN bir grafik olarak yorumlanabilir, burada kenar (i, j) gerçekleştirilirse İTİBAREN ij =0 ve eğer yapılmadıysa İTİBAREN ij =1 . Daha sonra, 0 uzunluğunda bir tur varsa, tüm köşeleri bir kez içeren döngüden geçecektir. Böyle bir çevrime Hamilton çevrimi denir. Açık bir Hamilton döngüsüne Hamilton zinciri (Hamilton yolu) denir.

Graf teorisi açısından simetrik gezgin satıcı problemi şu şekilde formüle edilebilir:

Dana tam ağİle birlikte n köşeler, kenar uzunluğu (i, j)= İTİBAREN ij. Minimum uzunlukta bir Hamilton çevrimi bulun. Asimetrik gezgin satıcı probleminde, "döngü" yerine "kontur", "kenar" - "yaylar" veya "oklar" demelidir.

Bazı uygulamalı problemler gezgin satıcı problemleri olarak formüle edilmiştir, ancak bu problemlerde Hamilton döngüsünün değil Hamilton zincirinin uzunluğunu en aza indirmek gerekir. Bu tür görevlere kapalı olmayan denir. Bazı modeller birkaç gezgin satıcı sorununa indirgenmiştir, ancak onları burada ele almayacağız.

1.3 Gezgin satıcı probleminin bir problem olarak grafikte ifadesi

Formülasyon: Birçok şehir:
. i ve j şehirleri arasındaki uzaklık:
. P, A elemanlarının permütasyonları kümesidir, permütasyon

Şehirlere grafik köşeleri ve onları yollara bağlayan yaylar atanırsa, o zaman grafik teorisi açısından sorun, minimum uzunluğun Hamilton konturunu belirlemektir. Bir Hamilton konturu, ilk tepe noktası son tepe noktasıyla çakışan bir grafiğin tüm tepe noktalarından geçen bir yoldur. Burada konturun uzunluğu, konturdaki yayların sayısı olarak değil, uzunluklarının toplamı olarak anlaşılır. Karşılık gelen yolun uzunluğu, kenarın ağırlığıdır. Grafik eksiksiz olmalıdır, yani. tüm olası kenarları içerir. Grafik tam değilse, eksik kenarlarla eşit ağırlıkta tamamlanabilir.
.

1.4 Hamiltonian konturunun varlığı için koşullar

Bulunacak dizi (yol), bir digrafta minimum ağırlıkta yönlendirilmiş, yayılan basit bir döngüdür; bu tür çevrimlere Hamiltonian da denir. Açıktır ki, tam digraf yukarıdaki tipteki döngüleri içerir. Tam digraflar için gezgin satıcı probleminin özel bir durumu olarak bir digrafın Hamilton çevrimi içerip içermediği sorusunu ele almanın yeterli olduğuna dikkat edin. Aslında, verilen digraf tam değilse, eksik kenarları olan tam bir digrafa eklenebilir ve eklenen kenarların her birine bir ağırlık atanabilir - bu "bilgisayar sonsuzluğu"dur, yani. hususlardaki tüm olası sayıların maksimumu. Şimdi yeni oluşturulan tam digrafta en kolay Hamilton çevrimini bulursak, o zaman ağırlığı olan kenarları varsa, verilen orijinal grafikte “gezgin satıcı döngüsü” olmadığını söyleyebiliriz. Tam digrafta en hafif Hamilton çevriminin ağırlık olarak sonlu olduğu ortaya çıkarsa, orijinal grafikte istenen çevrim olacaktır. Bir Hamilton konturu, ilk tepe noktası son tepe noktasıyla çakışan bir grafiğin tüm tepe noktalarından geçen bir yoldur. Burada konturun uzunluğu, konturdaki yayların sayısı olarak değil, uzunluklarının toplamı olarak anlaşılır.

Hamilton döngüsü.

İzin vermek G-grafik. Hamilton döngüsü, verilen bir grafiğin tüm köşelerini içeren basit bir döngüdür.

Teorem 1.

Bir grafiğin Hamilton döngüsüne sahip olması için grafiğin bağlı olması gerekir.

Teorem 2.

Tam grafikte , eğer n>=3 ise, tam çift parçalı bir Hamilton çevrimi vardır.
m>=1 için bir Hamilton çevrimi vardır.

1.5 Dal ve Sınır Yöntemi

Saymak iki alt kümeden oluşan boş olmayan sonlu bir kümedir ve . İlk alt küme
(köşeler) herhangi bir öğe kümesinden oluşur. İkinci alt küme (yaylar), birinci alt kümenin sıralı eleman çiftlerinden oluşur.
. eğer köşeler
ve
öyle ki
, o zaman bunlar bitişik köşelerdir.

Bir grafikteki bir rota, bir köşe dizisidir
mutlaka ikili olarak farklı değil, herhangi biri için
bitişik . Tüm kenarları ikili olarak farklıysa bir rotaya zincir denir. Eğer bir
daha sonra rota kapalı olarak adlandırılır. Kapalı bir devreye çevrim denir.

Sorunun formülasyonu

Satıcı seyahat etmeli n şehirler. Maliyetleri düşürmek için tüm şehirleri tam olarak bir kez dolaşan ve minimum maliyetle orijinaline dönen bir rota inşa etmek istiyor.

Graf teorisi açısından, problem aşağıdaki gibi formüle edilebilir. verilen n köşeler ve matris ( c ij ), nerede c ij ≥0 - yayın uzunluğu (veya fiyatı) ( i, j),
. Altında seyyar satıcı rotasız döngüyü anlıyoruz i 1 , i 2 ,…, i n , i 1 puan 1,2,…, n. Böylece, güzergah bir yay kümesidir. şehirler arasında ise i ve j geçiş yoktur, o zaman matrise "sonsuzluk" sembolü yerleştirilir. Çapraz olarak yerleştirilmelidir; bu, daha önce geçtiği bir noktaya geri dönme yasağı anlamına gelir. seyyar satıcı rotası, rota uzunluğu ben(z) rotaya dahil edilen yayların uzunluklarının toplamına eşittir. İzin vermek Z tüm olası yolların kümesidir. Baştan başla i 1 - sabit. Bir rota bulmak gerekiyor z 0  Z, öyle ki ben(z 0)=dk ben(z), z  Z.

sorunun çözümü

Dal ve sınır yönteminin ana fikri, önce Z yollarının uzunluklarının bir alt sınırının φ oluşturulmasıdır. bazı yay (i, j) ve başka bir alt küme içeren rotalardan oluşuyordu bu yayı içermiyordu. Alt kümelerin her biri için alt sınırlar, orijinal yol kümesiyle aynı kurala göre belirlenir. Elde Edilen Alt Kümelerin Alt Sınırları ve tüm rotalar kümesinin alt sınırından daha az olmadığı ortaya çıktı, yani. φ(Z) ≤ φ (), φ(Z) ≤ φ ().

Alt Sınırları Karşılaştırma φ () ve φ (), minimum uzunlukta bir rota içerme olasılığı daha yüksek olan rota alt kümesini seçebiliriz.

Daha sonra alt kümelerden biri veya benzer bir kuralla iki yeni ve . Onlar için alt sınırlar tekrar bulunur φ (), ve φ () vb. Dallanma işlemi tek bir rota bulunana kadar devam eder. İlk kayıt denir. Sonra sarkan dallara bakın. Alt sınırları ilk kaydın uzunluğundan büyükse, sorun çözülür. Alt sınırları ilk kaydın uzunluğundan daha küçük olanlar varsa, o zaman en küçük alt sınırı olan alt küme, en iyi kaydı içermediğine ikna olana kadar daha fazla dallanmaya uğrar. güzergah.

Varsa, rota uzunluğunun yeni değerine göre sarkan dalların analizi devam eder. İkinci kayıt denir. Çözüm süreci, tüm alt kümeler analiz edildiğinde sona erer.

Gezgin satıcı problemine uygulanan dal ve sınır yönteminin pratik uygulaması için, alt kümelerin alt sınırlarını belirleme ve rota kümesini alt kümelere ayırma (dallanma) yöntemini belirtiyoruz.

Alt sınırı bulmak için şu değerlendirmeyi kullanırız: gezgin satıcı problem matrisinin (satır veya sütun) herhangi bir satırının elemanlarından belirli bir sayı eklenir veya çıkarılırsa, planın optimalliği şundan değişmez. Bu. herhangi birinin uzunluğu seyyar satıcı rotası bu miktara göre değişecektir.

Her satırdan bu satırın minimum elemanına eşit bir sayı çıkarın. Her sütundan bu sütunun minimum elemanına eşit bir sayı çıkarın. Ortaya çıkan matris, satırlar ve sütunlar tarafından azaltılmış olarak adlandırılır. Çıkarılan tüm sayıların toplamına döküm sabiti denir.

Döküm sabiti, rotaların uzunluğunun alt sınırı olarak seçilmelidir.

Bir dizi rotayı alt kümelere bölme

Dallanmanın gerçekleştirildiği yay kümesine dahil edilmek üzere başvuranları seçmek için, yukarıdaki matriste tüm öğeleri sıfıra eşit olarak kabul ediyoruz. Bu matrisin sıfır elemanlarının Θ ij derecelerini bulalım. Sıfır elemanının derecesi Θ ij satırdaki minimum elemanın toplamına eşittir i ve sütundaki minimum eleman j(bu minimumları seçerken c ij dikkate alınmaz). Maksimum sıfır dereceli yaylar, en yüksek olasılıkla istenen rotaya aittir.

Bir yay içeren bir ödeme yolu matrisi elde etmek için ( i, j) matristeki satırın üzerini çizin i ve sütun j, ve rotada döngü oluşmasını engellemek için mevcut zinciri sonsuza kapatan elemanı değiştiriyoruz.

Bir yay içermeyen rotalar seti ( i, j) elemanı değiştirilerek elde edilir c ij sonsuza.

Dal ve sınır yöntemini kullanarak gezgin satıcı problemini çözme örneği

Satıcı seyahat etmeli 6 şehirler. Maliyetleri düşürmek için tüm şehirleri tam olarak bir kez dolaşan ve minimum maliyetle orijinaline dönen bir rota inşa etmek istiyor. Kaynak Şehir A. Şehirler arası seyahat maliyetleri aşağıdaki matris ile verilmektedir:

sorunun çözümü

Sunum kolaylığı için, ödeme matrisinin aşağıdaki her yerinde şehir adlarını (A, B, …, F) karşılık gelen satır ve sütunların numaralarıyla (1, 2, …, 6) değiştireceğiz.

Tüm rotaların uzunluklarının alt sınırını bulun. Her satırdan bu satırın minimum elemanına eşit sayıyı çıkarın, ardından her sütundan bu sütunun minimum elemanına eşit sayıyı çıkarın ve böylece matrisi satır ve sütunlarla azaltın. Doğru minimumu: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

Bunları satır satır çıkardıktan sonra şunu elde ederiz:

Sütun minimumu: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

Bunları sütunlarla çıkardıktan sonra, indirgenmiş matrisi elde ederiz:

alt sınırı bulalım φ (Z) = 15+1+0+16+5+5+5 = 47.

Dallanmanın gerçekleştirildiği yay kümesine dahil edilmek üzere başvuranları seçmek için, bu matrisin sıfır öğelerinin Θ ij derecelerini (satır ve sütundaki minimumların toplamı) buluruz. Θ14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 \u003d 0 + 9, Θ 65 \u003d 0 + 2. En büyük derece Θ 14 \u003d 10'dur. Dallanma yay boyunca gerçekleştirilir (1, 4).

Küme için alt sınır
47'ye eşit kalır. Kümenin tüm rotaları için A şehrinden D şehrine geçmiyoruz. Matriste bu, (1, 4) hücresine ∞ işareti yerleştirilerek gösterilir. Bu durumda A şehrinden ayrılmak, alt sınırın tahminine en azından ilk satırın en küçük öğesini ekler. φ () = 47 + 10.

Karşılık gelen matriste, c 14 = ∞.

İndirgeme prosedürünü r 1 =10 ile gerçekleştirdikten sonra 57 + 10 = 67 yeni bir alt sınır elde ederiz.

Karşılık gelen matriste, ilk satırı ve dördüncü sütunu çiziyoruz ve c 41 = ∞ 1→ 4 → 1 döngüsünün oluşmasını önlemek için yeni bir getiri matrisi elde ederiz ( c 1ij ):

İndirgeme için ilk sütunda bir minimum çıkarmak gerekir: h 1 =1. Bu durumda alt sınır 47+1 = 48 olur. Alt sınırların karşılaştırılması
φ () = 67 ve φ () = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

Pirinç. 1.4 İlk adımda dallanma

Ardından, dallanma işlemine devam ediyoruz. Bu matrisin sıfır elemanlarının Θ ij derecelerini bulalım Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. En büyüğü derece Θ 21'dir. Daha sonra küme, yay (2, 1) ile iki yeni parçaya bölünür.
ve .

Matristeki 2. satır ve 1. sütunun üzerini çizin. Yaylar (1, 4) ve (2, 1) bağlantılı bir yol oluşturur (2, 1, 4), biz ayarladık c 42 = ∞ 2→1→ 4→2 döngüsünün oluşmasını önlemek için.

İndirgeme için 4 satırında bir minimum çıkarmak gerekir: r 4 =2. Bu durumda alt limit 48 + 2 = 50 olur.

için alt sınır önceki dallanma adımında olduğu gibi elde edilen , 48 + 16 = 64'tür. Alt sınırların karşılaştırılması φ () = 64 ve φ () = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

Pirinç. 1.5 İkinci adımda dallanma

için azaltılmış getiri matrisi

Bu matrisin sıfır elemanlarının Θ ij dereceleri Θ 36 = 5, Θ 45 = 0, Θ 56 = 22, Θ 62 = 13, Θ 63 =7, Θ 65 = 0'dır. En büyük derece Θ 56'dır. küme, yay (2, 1) tarafından iki yeni ve .

için alt sınır 50 + 22 = 72'ye eşittir. Matriste 5. satır ve 6. sütunun üstünü çizeriz ve c 65 = ∞. Matrisi alıyoruz:

İndirgeme için 3 satırından bir minimum çıkarmak gerekir: r 3 =5. Bu durumda, alt sınır 50+5 = 55'e eşit olacaktır. Daha fazla bölme için bir yol alt kümesi seçiyoruz.

Pirinç. 1.6 Üçüncü adımda dallanma

için azaltılmış getiri matrisi

İndirgeme için 4. satırda bir minimum çıkarmak gerekir: r4=7. Bu durumda alt limit 55 + 7 = 62 olur. İndirgemeden sonra şunu elde ederiz:

22 matrisinden sıfır uzunlukta iki geçiş elde ederiz: (4, 3) ve (6, 2).

Pirinç. 1.7 Dördüncü adımda dallanma

Pirinç. 1.8 Puanlı dal ağacı

Alınan seyyar satıcı rotasız 0 = (1, 4, 3, 5, 6, 2, 1) veya (A-D-C-E-F-B-A).

1.6 Gezgin satıcı probleminin pratik uygulaması

Gezgin satıcı probleminin pratikte bariz uygulamasına ek olarak, gezgin satıcı problemini çözmeye indirgenebilecek bir takım problemler vardır.

Boya üretim sorunu.

Farklı renklerde n adet boya üretimi için üretim hattı bulunmaktadır; bu boyaları 1,2…n sayılarıyla isimlendirelim. Herşey üretim hattı bir işlemciyi ele alacağız.. İşlemcinin bir seferde yalnızca bir boya ürettiğini de varsayacağız, bu nedenle boyalar belirli bir sırayla üretilmelidir j1). Boya i üretimi bittikten sonra ve boya j üretimine başlamadan önce boya i'den ekipmanın yıkanması gerekir. Bu, C zamanını gerektirir. Açıkçası, C hem i hem de j'ye bağlıdır ve genel olarak konuşursak, C≠C'ye bağlıdır. Seçilen bazı siparişlerde, boya üretim döngüsünde zaman harcamanız gerekecek:

Burada t k, k'inci boyanın net üretim süresidir (değişiklikler hariç). Ancak, sağ taraftaki ikinci toplam sabittir, yani tam zamanlıüretim döngüsü başına toplam değiştirme süresi ile birlikte en aza indirilir.

Bu nedenle, gezgin satıcı problemi ve değiştirme süresinin en aza indirilmesi problemi sadece bir problemdir, sadece varyantları farklı kelimelerle açıklanmıştır.

Delme presi sorunu.

Punch pres üretmektedir Büyük sayıözdeş paneller - deliklerin tek tek delindiği metal levhalar farklı şekiller ve büyüklük. Şematik olarak, pres, x, y koordinatları boyunca bağımsız olarak hareket eden bir masa ve çevresi boyunca çeşitli şekil ve boyutlarda zımbalama aletleri bulunan masanın üzerinde dönen bir disk olarak temsil edilebilir. Her araç bir kopya halinde bulunur. Disk iki yönde eşit olarak dönebilir (dönme koordinatı z). Aslında altında asılı olan araca baskı yapan bir pres var. istenen noktaçarşaf.

j-th deliğini delme işlemi dört sayı (x j ,y j ,z j ,t j) ile karakterize edilir, burada x j ,y j tablonun istenen konumunun koordinatlarıdır, z j diskin istenen konumunun koordinatıdır ve t j, j-inci deliği delme zamanıdır.

Panellerin üretimi döngüseldir: her tabakanın işlenmesinin başında ve sonunda, tabla (x 0, y 0) konumlarında ve disk z 0 konumunda olmalıdır ve bu konumda delik açılmaz. Sistemin bu ilk durumu, hayali bir sıfır deliğinin delinmesi olarak düşünülebilir. Parametrelerle (x 0 ,y 0 ,z 0 ,0).

j. deliği i. delikten hemen sonra delmek için aşağıdakileri yapmanız gerekir:

Tabloyu x ekseni boyunca x i konumundan x j konumuna hareket ettirin, zaman harcayarak t (x) (|x i -x j |)=t i , j (x) .

Aynısını y ekseni boyunca yapın, t i , j (y) zamanını harcayın.

Kafayı iki yaydan en kısası boyunca z i konumundan z j konumuna döndürerek ti , j (z) zamanını harcayın.

j. deliği delin, t j zaman harcayın.

t (x), t (y), t (z) işlevlerinin özel biçimi, presin mekanik özelliklerine bağlıdır ve oldukça zahmetlidir. Bu işlevleri açıkça yazmaya gerek yoktur.

Eylem 1-3 (i-inci delikten j-th'e geçiş) aynı anda gerçekleşir ve delme, bu eylemlerin en uzununun tamamlanmasından hemen sonra gerçekleşir. Bu yüzden

C \u003d maks (t (x) , t (y) , t (z))

Şimdi, önceki durumda olduğu gibi, derleme görevi optimal program bir zımbalama presi için gezgin satıcı problemine indirgenir (burada simetrik).

pratik kısım

Toplam 300 bin para birimine sahip bir yatırımcı, sermayesini otomobil endişesi A ve inşaat şirketi B'nin hisselerine yatırabilir. Riski azaltmak için A hisseleri, B hisselerinin en az iki katı kadar ve ikincisi satın alınmalıdır. 100 binden fazla para birimi satın alınabilir. A hisselerindeki temettüler yılda %8, B hisselerindeki - %10'dur. İlk yılda elde edebileceğiniz maksimum kâr nedir?

Hisse senedi fiyatları A ve B için aynı ve eşit olsun: TA = TA B = 1 bin ruble.

Çözüm görevler dal ve sınır yöntemini kullanarak en uygun yolu bulmak için

Kurs >> Matematik

Matematiksel ayar görevler seyyar satıcı 5 1.2.Dal ve sınırların yöntemi. 5 1.3. algoritma çözümler 6 1.4. Şema çözümler görevler 6 ... izin verilen set kararlar(planlar) bazılarına yolçöküyor ... verilen sorun ve o çözümşube yöntemini kullanarak ...

Karınca kolonisi algoritmalarının uygulanması karar görevler optimizasyon

Görev >> Bilişim

merkezi yönetim ve oözellikler değişimdir... koşullar görevler. Çünkü her biri için görevler yol konaklama... karar görevler optimizasyon. 1.1 Karınca kolonisi algoritmalarının uygulanması görevler seyyar satıcı. Bir görev olarak formüle bir görev ...

NP-complete uygulaması görevler asimetrik anahtar kriptografisinde

Kurs >> Bilişim

Resmi yollar çözümler verilen görevler ve giyer... dönüştürme o 1. Tanık böyle bir settir. Bir görev hakkında... çözüm"on beş" beden Bir görev seyyar satıcı Grafik renklendirme sorunu Bir görevüst kapak hakkında Bir görev seti kaplamak hakkında Bir görev klik hakkında Bir görev ...

Programlama dilleri (6)

Özet >> Bilişim

İçinde var olan sanal kavramlar oçerçeve - tablo, tablo alanı... zeka. Bu, geliştirmeyi içerir yollar çözümler görevler benzetme yoluyla, tümdengelim yöntemleri ... için kullanılır çözümler NP-tamamlandı görevler, örneğin, görevler seyyar satıcı. AI yapıyor...

					1.9 OOP 14090 - 07 KR PZ
	Çarşaf	№ belge.	İmza	tarih
Gelişmiş		Koveshnikov D.V.			Gezgin satıcı problemlerini çözme	Literatür			Çarşaf	Çarşaflar
Rukov.		Selyutina O.N.

Birçok araştırmacı dal ve sınır yöntemi fikrini ortaya attı, ancak Little ve bu yöntemi temel alan ortak yazarlar, TPC'yi çözmek için başarılı bir algoritma geliştirdi ve böylece yaklaşımın popülerleşmesine katkıda bulundu. O zamandan beri, dal-ve-sınır yöntemi birçok soruna başarıyla uygulandı ve TPC'yi çözmek için yöntemde başka birkaç değişiklik tasarlandı, ancak ders kitaplarının çoğu Little'ın öncü çalışmalarını sunuyor.

Genel fikir önemsizdir: bir değil seçenekleri atabilmek için çok sayıda seçeneği sınıflara ayırmanız ve bu sınıflar için (aşağıdan - minimizasyon probleminde, yukarıdan - maksimizasyon probleminde) tahminler almanız gerekir. bir, ama bütün sınıflar tarafından. Zorluk, prosedürün verimli olduğu sınıflara (dallara) ve bu tür tahminlere (sınırlara) böyle bir bölünme bulmakta yatmaktadır.

Tablo 2

Tablo 3

Tablo 4

Little'ın algoritmasını önceki bölümün 1. örneğini kullanarak sunalım. Matrisi yeniden yazalım:

C ij'yi i şehrinden j şehrine olan ücret olarak yorumlamak bizim için daha uygun olacaktır. Diyelim ki j şehrinin iyi belediye başkanı, şehre giren her seyyar satıcıya 5 dolar ödenmesine dair bir kararname yayınladı. Bu, herhangi bir tur j şehrine girmenizi gerektirdiğinden, herhangi bir turun 5 $ daha ucuza mal olacağı anlamına gelir. Ancak tüm turların fiyatları eşit olarak düştüğünden, önceki minimum tur artık en az maliyetli olacaktır. Belediye başkanının iyiliği, C matrisinin j. sütunundaki tüm sayıların 5 ile azalması olarak gösterilebilir. 10$, bu, tüm öğelerden 10 çıkarılarak ifade edilebilir. j-th oyuncakçizgiler. Bu, her turun maliyetini yeniden değiştirir, ancak minimum tur minimum kalır. Böylece aşağıdaki lemma ispatlanmış olur.

C matrisinin herhangi bir satırının veya sütununun tüm elemanlarından herhangi bir sabiti çıkararak minimum turu minimum tutarız.

Algoritma için elde etmemiz uygun olacaktır. daha fazla sıfır ancak, C matrisinde oraya varmadan, negatif sayılar. Bunu yapmak için, her satırdan minimum elemanını çıkarırız (buna satırlarla indirgeme denir, bkz. . dört).

Çapraz çizgiler, i şehrinden i şehrine gidemeyeceğiniz anlamına gelir. Satırların üzerindeki döküm sabitlerinin toplamının 27, sütunların üzerindeki toplamın 7 ve toplamların toplamının 34 olduğuna dikkat edin.

Tur, örneğin Tablo'da gösterildiği gibi, matris C'nin altı çizili (farklı bir renkle vurgulanmış) altı öğesinden oluşan bir sistemle ayarlanabilir. 2. Bir öğenin altını çizmek, i-inci öğeden turda tam olarak j-inci öğeye gittikleri anlamına gelir. Altı şehir turunda altı kenar olduğundan altı şehir turu için altı altı çizili öğe olmalıdır. Her sütun tam olarak bir altı çizili öğe içermelidir (satıcı her şehre bir kez girmiştir), her satır tam olarak bir altı çizili öğe içermelidir (satıcı her şehri bir kez terk etmiştir); dahası, altı çizili maddeler birkaç küçük döngüyü değil, bir turu tanımlamalıdır. Altı çizili unsurların sayıları toplamı tur maliyetidir. Masanın üstünde 2 maliyet 36'dır, bu, sözlükbilimsel numaralandırma ile elde edilen minimum turdur.

Şimdi Tablodaki indirgenmiş matristen yola çıkacağız. 2. İnşa etmeyi başarırsa doğru sistem altı çizili öğeler, yani Yukarıda açıklanan üç gereksinimi karşılayan sistem ve bu altı çizili öğeler yalnızca sıfırlarsa, bu matris için minimum tur elde edeceğimiz açıktır. Ama aynı zamanda minimum olacak orijinal matris C, sadece turun doğru maliyetini elde etmek için, tüm indirgeme sabitlerini geri eklemeniz gerekecek ve turun maliyeti 0'dan 34'e değişecektir. Bu nedenle, minimum tur 34'ten az olamaz. tüm turlar için daha düşük bir tahmin aldı.

Şimdi dallanmaya başlayalım. Bunu yapmak için sıfırları tahmin etme adımını atacağız. İndirgenmiş matrisin (1,2) hücresindeki sıfırı düşünün. Bu, 1. şehirden 2. şehire geçmenin maliyetinin 0 olduğu anlamına gelir. Peki ya 1. şehirden 2. şehire gitmezsek? O zaman ikinci sütunda gösterilen fiyatlar için hala 2. şehri girmeniz gerekir; sadece 1 için daha ucuz (şehir 6'dan). Ayrıca, birinci satırda belirtilen fiyat için yine de 1. şehirden ayrılmanız gerekecek; en ucuz yol 0 için şehir 3'tür. Bu iki minimumu toplarsak, 1+0=1'dir: 1. şehirden 2. şehre “sıfır” gitmezseniz, en az 1 ödemeniz gerekir. Bu sıfırın tahminidir. Tüm sıfırların tahminleri Tablo'da verilmiştir. 5 sağda ve sıfırın üzerinde (sıfıra eşit sıfır puanlar atanmamıştır).

Bu tahminlerin maksimumunu seçiyoruz (örnekte birkaç tahmin var, bire eşit, hücrede bunlardan ilkini seçiyoruz (1,2)).

Böylece sıfır kenar (1,2) seçilir. Tüm turları iki sınıfa ayıralım - kenar (1,2) dahil ve kenar (1,2) hariç. İkinci sınıf için 1 fazla ödemeniz gerektiğini söyleyebiliriz, yani bu sınıftaki turlar 35 ve üzeri bir ücrete tabidir.

Birinci sınıfa gelince, Tablodaki matrisi dikkate almak gerekir. 6, ilk satır ve ikinci sütunun üstü çizili olarak.

Tablo 5

Tablo 7

Ek olarak, indirgenmiş matriste, hücreye (2,1) bir yasak yerleştirilir, çünkü kenar (1,2) seçilir ve turun kenar (2,1) ile zamanından önce kapatılması mümkün değildir. İndirgenmiş matris, ilk sütun boyunca 1 azaltılabilir, böylece ona karşılık gelen her tur en az 35'e mal olur. Dallanma ve tahmin almamızın sonucu Şekil 2'de gösterilmektedir. 6.

Daireler sınıfları temsil eder: en üstteki daire tüm turların sınıfıdır; sol alt - kenarı (1,2) içeren tüm turların sınıfı; sağ alt - kenarı (1,2) içermeyen tüm turların sınıfı. Dairelerin üzerindeki sayılar aşağıdan tahminlerdir.

Pozitif yönde dallanmaya devam edelim: sola - aşağı. Bunu yapmak için, Tablodaki indirgenmiş C matrisindeki sıfırları tahmin ediyoruz. 7. Hücredeki (3,1) maksimum puan 3'tür. Bu nedenle, şek. 7, 35+3=38'dir. Şekil 2'deki sol alt köşeyi tahmin etmek için. 7, Tablodaki C[(1,2), (3,1)] matrisini alarak C matrisinden satır 3 ve sütun 1'i silmeniz gerekir. 8. Bu matriste, (2,3) hücresine bir yasak koymanız gerekir, çünkü turun bir parçası zaten (1,2) ve (3,1) kenarlarından oluşturulmuştur, yani. ve erken kapatmayı yasaklamanız gerekir (2,3). Bu matris sütun tarafından 1 azaltılır (Tablo 9), bu nedenle ilgili sınıfın her turu (yani, kenarları (1,2) ve (3,1) içeren bir tur) 36 veya daha fazla tutar.

Tablo 9

Tablo 11

Şimdi indirgenmiş matristeki sıfırları tahmin edin C[(1,2), (3,1)] maksimum tahmini 3 olan sıfır hücre (6,5) içindedir. Negatif seçeneğin puanı 38+3=41'dir. Olumlu seçeneğin bir tahminini elde etmek için, 6. satırı ve 5. sütunu kaldırırız, hücreye (5.6) bir yasak koyarız, bkz. Tablo. 10. Bu matris indirgenemez. Dolayısıyla pozitif seçeneğin puanı artmamaktadır (Şekil 8).

Tablodaki matristeki sıfırların değerlendirilmesi. Şekil 10'da kenar (2,6) seçimiyle dallanma elde ediyoruz, negatif değişken 36+3=39 tahminini alıyor ve pozitif değişkenin tahminini elde etmek için ikinci satırı ve altıncı sütunu çiziyoruz, Tablodaki matrisin elde edilmesi. on bir.

Hücredeki matrise (5,3) bir yasak eklenmelidir, çünkü turun bir parçası zaten oluşturulmuş ve erken dönüşü (5,3) yasaklamak gerekiyor. Şimdi köşegen yasaklı bir 2x2 matrisi olduğunda, turu (4,3) ve (5,4) kenarları ile tamamlıyoruz. Olumlu seçeneklere göre dallanmamız boşuna değildi. Şimdi tur alınır: 1>2>6>5>4>3>1 36 maliyetle. Numaralandırma ağacının dibine ulaşıldığında, tur sınıfı bir tura daralır ve aşağıdan tahmin döndü kesin bir maliyete dönüştürülür.

Bu nedenle 36 ve üzeri puan alan tüm sınıflar en iyi turu içermez. Bu nedenle, karşılık gelen köşelerin üstü çizilir. Her ikisinin de soyundan gelenlerin üstü çizili olan tepe noktası da çizilir. Toplam numaralandırmayı büyük ölçüde azalttık. C matrisine karşılık gelen sınıfın en iyi turu içerip içermediğini kontrol etmek için kalır, yani. 1,2 hücresindeki yasaklı indirgenmiş matris C, sütunda 1 azaltıldı (34+1=35 tahmini verdi). Sıfırların değerlendirilmesi, hücrede (1,3) sıfır için 3'ü verir, bu nedenle 35+3 negatif seçeneğinin değerlendirilmesi, halihazırda alınan tur 36'nın maliyetini aşar ve negatif seçenek kesilir.

Pozitif değişkenin bir tahminini elde etmek için, ilk satırı ve üçüncü sütunu matristen çıkarırız, yasağı (3,1) ayarlar ve matrisi alırız. Bu matris dördüncü satırda 1 ile verilir, sınıf puanı 36'ya ulaşır ve dairenin üzeri çizilir. "Herkes" köşesinin her iki çocuğu da öldürüldüğünden, o da öldürülür. Köşe kalmadı, numaralandırma bitti. Tabloda altı çizili olarak gösterilen aynı minimal turu elde ettik. 2.

Little algoritmasının ve ilgili algoritmaların performansına ilişkin tatmin edici teorik tahminler yoktur, ancak uygulama şunu göstermektedir: modern bilgisayarlar genellikle sorunu n = 100 ile çözerler. Bu, kaba kuvvete göre çok büyük bir gelişmedir. Ayrıca, dal-sınır algoritmaları, onları sonuna kadar taşımak mümkün değilse, etkili buluşsal prosedürlerdir.

Dal ve sınır yöntemini kullanarak gezgin satıcı problemini çözme

Tanımlar

Grafik, iki alt kümeden oluşan boş olmayan sonlu bir kümedir ve . İlk alt küme
(köşeler) herhangi bir öğe kümesinden oluşur. İkinci alt küme (yaylar), birinci alt kümenin sıralı eleman çiftlerinden oluşur.
. Eğer üstler ve
öyle ki, bunlar bitişik köşelerdir.

Bir grafikteki bir rota, bir köşe dizisidir
mutlaka ikili olarak farklı değil, herhangi biri için
bitişik . Tüm kenarları ikili olarak farklıysa bir rotaya zincir denir. O zaman rota kapalı olarak adlandırılır. Kapalı bir devreye çevrim denir.

Sorunun formülasyonu

Satıcı seyahat etmeli n şehirler. Maliyetleri düşürmek için tüm şehirleri tam olarak bir kez dolaşan ve minimum maliyetle orijinaline dönen bir rota inşa etmek istiyor.

Graf teorisi açısından, problem aşağıdaki gibi formüle edilebilir. verilen n köşeler ve matris ( c ij ), nerede c ij ≥0 - yayın uzunluğu (veya fiyatı) ( i, j),
. Altında seyyar satıcı rotasız döngüyü anlıyoruz i 1 , i 2 ,…, i n , i 1 puan 1,2,…, n. Böylece, güzergah bir yay kümesidir. şehirler arasında ise i ve j geçiş yoktur, o zaman matrise "sonsuzluk" sembolü yerleştirilir. Çapraz olarak yerleştirilmelidir; bu, daha önce geçtiği bir noktaya geri dönme yasağı anlamına gelir. seyyar satıcı rotası, rota uzunluğu ben(z) rotaya dahil edilen yayların uzunluklarının toplamına eşittir. İzin vermek Z tüm olası yolların kümesidir. Baştan başla i 1 - sabit. Bir rota bulmak gerekiyor z 0  Z, öyle ki ben(z 0)=dk ben(z), z  Z.

sorunun çözümü

Dal ve sınır yönteminin ana fikri, önce Z yollarının uzunluklarının bir alt sınırının φ oluşturulmasıdır. bazı yay (i, j) ve başka bir alt küme içeren rotalardan oluşuyordu bu yayı içermiyordu. Alt kümelerin her biri için alt sınırlar, orijinal yol kümesiyle aynı kurala göre belirlenir. Elde Edilen Alt Kümelerin Alt Sınırları ve tüm rotalar kümesinin alt sınırından daha az olmadığı ortaya çıktı, yani. φ(Z) ≤ φ (), φ(Z) ≤ φ ().

Alt Sınırları Karşılaştırma φ () ve φ (), minimum uzunlukta bir rota içerme olasılığı daha yüksek olan rota alt kümesini seçebiliriz.

Daha sonra alt kümelerden biri veya benzer bir kuralla iki yenisine bölünür. ve . Onlar için alt sınırlar tekrar bulunur φ (), ve φ () vb. Dallanma işlemi tek bir rota bulunana kadar devam eder. İlk kayıt denir. Sonra sarkan dallara bakın. Alt sınırları ilk kaydın uzunluğundan büyükse, sorun çözülür. Alt sınırları ilk kaydın uzunluğundan daha küçük olanlar varsa, o zaman en küçük alt sınırı olan alt küme, en iyi kaydı içermediğine ikna olana kadar daha fazla dallanmaya uğrar. güzergah.

Varsa, rota uzunluğunun yeni değerine göre sarkan dalların analizi devam eder. İkinci kayıt denir. Çözüm süreci, tüm alt kümeler analiz edildiğinde sona erer.

Gezgin satıcı problemine uygulanan dal ve sınır yönteminin pratik uygulaması için, alt kümelerin alt sınırlarını belirleme ve rota kümesini alt kümelere ayırma (dallanma) yöntemini belirtiyoruz.

Alt sınırı bulmak için şu değerlendirmeyi kullanırız: gezgin satıcı problem matrisinin (satır veya sütun) herhangi bir satırının elemanlarından belirli bir sayı eklenir veya çıkarılırsa, planın optimalliği şundan değişmez. Bu. herhangi birinin uzunluğu seyyar satıcı rotası bu miktara göre değişecektir.

Her satırdan bu satırın minimum elemanına eşit bir sayı çıkarın. Her sütundan bu sütunun minimum elemanına eşit bir sayı çıkarın. Ortaya çıkan matris, satırlar ve sütunlar tarafından azaltılmış olarak adlandırılır. Çıkarılan tüm sayıların toplamına döküm sabiti denir.

Döküm sabiti, rotaların uzunluğunun alt sınırı olarak seçilmelidir.

Bir dizi rotayı alt kümelere bölme

Dallanmanın gerçekleştirildiği yay kümesine dahil edilmek üzere başvuranları seçmek için, yukarıdaki matriste tüm öğeleri sıfıra eşit olarak kabul ediyoruz. Bu matrisin sıfır elemanlarının Θ ij derecelerini bulalım. Sıfır elemanının derecesi Θ ij satırdaki minimum elemanın toplamına eşittir i ve sütundaki minimum eleman j(bu minimumları seçerken c ij dikkate alınmaz). Maksimum sıfır dereceli yaylar, en yüksek olasılıkla istenen rotaya aittir.

Bir yay içeren bir ödeme yolu matrisi elde etmek için ( i, j) matristeki satırın üzerini çizin i ve sütun j, ve rotada döngü oluşmasını engellemek için mevcut zinciri sonsuza kapatan elemanı değiştiriyoruz.

Bir yay içermeyen rotalar seti ( i, j) elemanı değiştirilerek elde edilir c ij sonsuza.

Dal ve sınır yöntemini kullanarak gezgin satıcı problemini çözme örneği

Satıcı seyahat etmeli 6 şehirler. Maliyetleri düşürmek için tüm şehirleri tam olarak bir kez dolaşan ve minimum maliyetle orijinaline dönen bir rota inşa etmek istiyor. Kaynak Şehir A. Şehirler arası seyahat maliyetleri aşağıdaki matris ile verilmektedir:

sorunun çözümü

Sunum kolaylığı için, ödeme matrisinin aşağıdaki her yerinde şehir adlarını (A, B, …, F) karşılık gelen satır ve sütunların numaralarıyla (1, 2, …, 6) değiştireceğiz.

Tüm rotaların uzunluklarının alt sınırını bulun. Her satırdan bu satırın minimum elemanına eşit sayıyı çıkarın, ardından her sütundan bu sütunun minimum elemanına eşit sayıyı çıkarın ve böylece matrisi satır ve sütunlarla azaltın. Doğru minimumu: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

Bunları satır satır çıkardıktan sonra şunu elde ederiz:

Sütun minimumu: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

Bunları sütunlarla çıkardıktan sonra, indirgenmiş matrisi elde ederiz:

alt sınırı bulalım φ (Z) = 15+1+0+16+5+5+5 = 47.

Dallanmanın gerçekleştirildiği yay kümesine dahil edilmek üzere başvuranları seçmek için, bu matrisin sıfır öğelerinin Θ ij derecelerini (satır ve sütundaki minimumların toplamı) buluruz. Θ14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 \u003d 0 + 9, Θ 65 \u003d 0 + 2. En büyük derece Θ 14 \u003d 10'dur. Dallanma yay boyunca gerçekleştirilir (1, 4).

Küme için alt sınır
47'ye eşit kalır. Kümenin tüm rotaları için A şehrinden D şehrine geçmiyoruz. Matriste bu, (1, 4) hücresine ∞ işareti yerleştirilerek gösterilir. Bu durumda A şehrinden ayrılmak, alt sınırın tahminine en azından ilk satırın en küçük öğesini ekler. φ () = 47 + 10.

Karşılık gelen matriste, c 14 = ∞.

İndirgeme prosedürünü r 1 =10 ile gerçekleştirdikten sonra 57 + 10 = 67 yeni bir alt sınır elde ederiz.

Karşılık gelen matriste, ilk satırı ve dördüncü sütunu çiziyoruz ve c 41 = ∞ 1→ 4 → 1 döngüsünün oluşmasını önlemek için yeni bir getiri matrisi elde ederiz ( c 1ij ):

İndirgeme için ilk sütunda bir minimum çıkarmak gerekir: h 1 =1. Bu durumda alt sınır 47+1 = 48 olur. Alt sınırların karşılaştırılması
φ () = 67 ve φ () = 48 , minimum uzunluk rotasını içermesi daha olasıdır.

Pirinç. 1 İlk adımda dallanma

Ardından, dallanma işlemine devam ediyoruz. Bu matrisin sıfır elemanlarının Θ ij derecelerini bulalım Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. En büyüğü derece Θ 21'dir. Daha sonra küme, yay (2, 1) ile iki yeni parçaya bölünür.
ve .

Matristeki 2. satır ve 1. sütunun üzerini çizin. Yaylar (1, 4) ve (2, 1) bağlantılı bir yol oluşturur (2, 1, 4), biz ayarladık c 42 = ∞ 2→1→ 4→2 döngüsünün oluşmasını önlemek için.

İndirgeme için 4 satırında bir minimum çıkarmak gerekir: r 4 =2. Bu durumda alt limit 48 + 2 = 50 olur.

için alt sınır önceki dallanma adımında olduğu gibi elde edilen , 48 + 16 = 64'tür. Alt sınırların karşılaştırılması φ () = 64 ve φ () = 50 .

Pirinç. 2 İkinci adımda dallanma

için azaltılmış getiri matrisi

İndirgeme için 3 satırından bir minimum çıkarmak gerekir: r 3 =5. Bu durumda, alt sınır 50+5 = 55'e eşit olacaktır. Daha fazla bölme için bir yol alt kümesi seçiyoruz.

Pirinç. 3 Üçüncü adımda dallanma

için azaltılmış getiri matrisi

			0 Hile sayfası >> Muhasebe ve denetim Etkinlik, etki, katılım karar görevler. Hayatın farklı durumlarında... Özel görevler matematiksel programlamaÖzel görevler matematiksel programlama Bir görev hakkında seyyar satıcı.Yöntem dallar ve sınırlar. Bir görev hakkında seyyar satıcıİzin vermek...