Thực đơn
trang chủTập tin và thư mục

Phương pháp phân nhánh và ràng buộc. Lý thuyết đồ thị. Giải quyết vấn đề nhân viên bán hàng du lịch. Chúng ta hãy quay lại hình ảnh ở đầu bài. Phương pháp giải các bài toán khó

Xin chào! Hiện thực hóa các thuật toán khác nhauđể tìm chu trình Hamilton với chi phí thấp nhất, tôi đã xem qua một ấn phẩm cung cấp phiên bản riêng của nó. Sau khi thử thì tôi nhận được câu trả lời sai:

Các tìm kiếm sâu hơn trên Internet không mang lại kết quả như mong đợi: hoặc là một mô tả lý thuyết khó đối với những người không phải là nhà toán học, hoặc có thể hiểu được nhưng có sai sót.

Bên dưới phần cắt, bạn sẽ tìm thấy một thuật toán đã sửa và một máy tính trực tuyến.

Bản thân phương pháp này do Little, Murthy, Sweeney, Carel xuất bản năm 1963, có thể áp dụng cho nhiều bài toán NP-đầy đủ, và là một tài liệu rất lý thuyết mà không cần kiến thức tốt bằng tiếng Anh và toán học không thể áp dụng ngay vào bài toán người bán hàng rong của chúng ta.

Nói ngắn gọn về phương pháp - đây là một tìm kiếm đầy đủ về tất cả những lựa chọn khả thi với việc loại bỏ các giải pháp dưới mức tối ưu rõ ràng.

Thuật toán đã sửa để tìm tuyến đường thực sự tối thiểu

Thuật toán bao gồm hai giai đoạn:

Giai đoạn đầu
Giảm ma trận chi phí và tính toán ước tính chi phí tuyến đường thấp hơn r.

1. Tính phần tử nhỏ nhất trong mỗi hàng (hằng số truyền cho hàng)
2. Chúng ta chuyển sang ma trận chi phí mới, trừ hằng số giảm của nó từ mỗi hàng
3. Tính phần tử nhỏ nhất trong mỗi cột (hằng số cưỡng bức cho cột)
4. Chúng ta chuyển sang ma trận chi phí mới, trừ hằng số giảm của nó từ mỗi cột.
Kết quả là chúng ta có một ma trận chi phí trong đó mỗi hàng và mỗi cột có ít nhất một phần tử bằng 0.
5. Tính ranh giới trên ở giai đoạn này là tổng các hằng số rút gọn cho các cột và hàng (giới hạn này sẽ là chi phí dưới mức không thể xây dựng tuyến đường yêu cầu)

Giai đoạn thứ hai (chính)

1. Tính mức phạt không sử dụng đối với từng phần tử 0 của ma trận chi phí đã cho.
Hình phạt cho việc không sử dụng một phần tử có chỉ số (h,k) trong ma trận có nghĩa là cạnh này không được đưa vào tuyến đường của chúng ta, nghĩa là chi phí tối thiểu của việc “không sử dụng” cạnh này bằng tổng các phần tử tối thiểu trong hàng h và cột k.

a) Tìm tất cả các phần tử bằng 0 trong ma trận đã cho
b) Đối với mỗi người trong số họ, chúng tôi tính toán hình phạt nếu không sử dụng.
c) Lựa chọn các yếu tố tương ứng với mức phạt tối đa

2. Bây giờ chúng ta chia tập S thành các tập - chứa cạnh có giá trị lớn nhất (S w i) và không chứa các cạnh này (S w i /o).
3. Tính toán dự toán các tuyến đường trong từng bộ này.
a) Đối với các bộ S w i /o mọi thứ đều đơn giản: vì chúng ta không lấy cạnh tương ứng với mức phạt tối đa (hi ,k i), nên đối với nó, ước tính chi phí bằng với ước tính chi phí của tập S + hình phạt đối với không sử dụng cạnh (hi ,k i)
b) Khi tính chi phí cho tập S w i, chúng ta tính đến việc vì cạnh (hi i,k i) được bao gồm trong tuyến, điều đó có nghĩa là cạnh (k i,hi) không thể được bao gồm trong tuyến, do đó trong ma trận chi phí, chúng ta viết c(k i,hi) =infinity, và vì chúng ta đã “đã rời khỏi” từ điểm hi và chúng ta đã “đã đến” từ điểm ki, nên không một cạnh nào rời khỏi hi, và không một cạnh nào cạnh đến ki, đã có thể được sử dụng, vì vậy chúng ta gạch bỏ khỏi ma trận chi phí, hàng h i và cột k i. Sau đó, chúng ta đưa ra ma trận và khi đó ước tính chi phí cho S w bằng tổng ước tính chi phí cho S và r(hi,k i), trong đó r(hi,k i) là tổng của các hằng số rút gọn cho ma trận chi phí sửa đổi.
4. Trong tất cả các bộ không được phân vùng, bộ nào có điểm thấp nhất sẽ được chọn.

Chúng tôi tiếp tục theo cách này cho đến khi còn lại một hàng không được đánh dấu và một cột không được đánh dấu trong ma trận chi phí.

Tối ưu hóa nhỏ - thêm phương pháp phỏng đoán

Vâng, thực sự thì tại sao chúng ta không giới thiệu phương pháp phỏng đoán? Thật vậy, trong thuật toán nhánh và ràng buộc, chúng ta thực sự xây dựng một cây, tại các nút mà chúng ta quyết định lấy cạnh (hi,k i) hay không, và treo hai hoặc nhiều con - Sw(hi,k i) và Sw/ o(xin chào,k tôi). Nhưng sự lựa chọn tốt nhấtđối với lần lặp tiếp theo, chúng tôi chỉ chọn theo ước tính. Vì vậy, hãy chọn cái tốt nhất không chỉ về mặt đánh giá mà còn về độ sâu của cây, bởi vì... Phần tử được chọn càng sâu thì càng gần đến cuối số đếm. Bằng cách này, cuối cùng chúng ta có thể chờ đợi câu trả lời.

Thực ra, về những sai sót trong ấn phẩm đó

Những lỗi này có một lý do - bỏ qua khả năng xuất hiện một số phần tử 0 với mức phạt tối đa. Trong trường hợp này, cần chia không thành hai tập con mà thành số lượng lớn(2n). Bạn cũng nên chọn phân vùng tập hợp với ranh giới tối thiểu của tất cả những cách có thể, chứ không phải từ hai đứa trẻ có được từ lần chia cuối cùng.

Bằng chứng

Chúng ta quay lại hình ảnh ở đầu bài:


Và đây là giải pháp với thuật toán đã sửa.

Các định nghĩa

là một tập hữu hạn không rỗng gồm hai tập con và . Tập hợp con đầu tiên (đỉnh) bao gồm bất kỳ tập hợp các phần tử nào. Tập hợp con thứ hai (cung) bao gồm các cặp phần tử được sắp xếp của tập hợp con thứ nhất . Nếu các đỉnh và sao cho , thì đây là các đỉnh liền kề.

Lộ trình trong cột

là một dãy các đỉnh không nhất thiết phải phân biệt theo từng cặp, trong đó với bất kỳ liền kề với . Một tuyến đường được gọi là một chuỗi nếu tất cả các cạnh của nó đều phân biệt theo cặp. Nếu sau đó tuyến đường được gọi là đóng cửa. Một mạch kín được gọi là một chu trình.

Xây dựng vấn đề

Người bán hàng du lịch phải đi du lịch N các thành phố. Để giảm chi phí, anh ấy muốn xây dựng một tuyến đường sao cho anh ấy có thể đi vòng quanh tất cả các thành phố đúng một lần và quay trở lại tuyến đường ban đầu với chi phí tối thiểu.

Về mặt lý thuyết đồ thị, bài toán có thể được phát biểu như sau. Bộ Nđỉnh và ma trận ( c ij), ở đâu c ij ≥0 – độ dài (hoặc giá) của cung ( Tôi , j),

. Dưới tuyến đường nhân viên bán hàng du lịch z hãy hiểu chu kỳ Tôi 1 , Tôi 2 ,…, Tôi N , Tôi 1 điểm 1,2,…,n. Như vậy, tuyến đường là một tập hợp các cung. Nếu giữa thành phố Tôi Và j không có sự chuyển tiếp thì ký hiệu “vô cực” được đặt vào ma trận. Nó phải được đặt theo đường chéo, có nghĩa là không được phép quay lại điểm mà bạn đã đi qua tuyến đường nhân viên bán hàng du lịch, chiều dài tuyến đường tôi (z) bằng tổng độ dài của các cung có trong tuyến đường. Cho phép Z– tập hợp tất cả các tuyến đường có thể. Đỉnh ban đầu Tôi 1 – cố định. Chúng ta cần tìm tuyến đường z 0 О Z, như vậy mà tôi (z 0)=phút tôi (z), z Î Z .

Giải pháp của vấn đề

Ý tưởng chính của phương pháp nhánh và ràng buộc là trước tiên, giới hạn dưới φ được xây dựng trên độ dài của tập hợp các tuyến đường Z. Sau đó, tập hợp các tuyến đường được chia thành hai tập hợp con sao cho tập hợp con đầu tiên

bao gồm các tuyến đường chứa một số cung (i, j) và một tập hợp con khác không chứa cung này. Đối với mỗi tập hợp con, giới hạn dưới được xác định theo quy tắc tương tự như đối với tập hợp tuyến đường ban đầu. Giới hạn dưới thu được của các tập hợp con hóa ra không nhỏ hơn giới hạn dưới của tập hợp tất cả các tuyến đường, tức là. φ(Z)< φ (), φ(Z) �� φ ().

So sánh giới hạn dưới φ (

) Và φ (), chúng ta có thể chọn tập hợp con các tuyến đường có nhiều khả năng chứa tuyến đường có độ dài tối thiểu.

Khi đó một trong các tập con

hoặc theo quy tắc tương tự, được chia thành hai phần mới và . Giới hạn dưới một lần nữa được tìm thấy cho họ φ (), Và φ () vân vân. Quá trình phân nhánh tiếp tục cho đến khi tìm được một tuyến đường duy nhất. Nó được gọi là bản ghi đầu tiên. Sau đó họ nhìn qua những cành cây rách nát. Nếu giới hạn dưới của chúng lớn hơn độ dài của bản ghi đầu tiên thì vấn đề đã được giải quyết. Nếu có những bản ghi có giới hạn dưới nhỏ hơn độ dài của bản ghi đầu tiên thì tập hợp con có giới hạn dưới nhỏ nhất sẽ tiếp tục phân nhánh cho đến khi được thuyết phục rằng nó không chứa bản ghi tốt nhất. tuyến đường .

Nếu tìm thấy một nhánh thì việc phân tích các nhánh bị hỏng sẽ tiếp tục đối với giá trị mới của độ dài tuyến đường. Nó được gọi là kỷ lục thứ hai. Quá trình giải kết thúc khi tất cả các tập hợp con đã được phân tích.

Vì triển khai thực tế của phương pháp nhánh và ràng buộc liên quan đến bài toán người bán hàng du lịch, chúng tôi sẽ chỉ ra một phương pháp xác định giới hạn dưới các tập hợp con và chia một tập hợp các tuyến đường thành các tập hợp con (phân nhánh).

Để tìm giới hạn dưới, chúng ta sử dụng phép xem xét sau: nếu một số nhất định được cộng hoặc trừ khỏi các phần tử của bất kỳ hàng nào trong ma trận của bài toán nhân viên bán hàng du lịch (hàng hoặc cột), thì tính tối ưu của kế hoạch sẽ không thay đổi. Độ dài của bất kỳ tuyến đường nhân viên bán hàng du lịch sẽ thay đổi theo số tiền này.

Trừ từ mỗi dòng một số bằng phần tử nhỏ nhất của dòng này. Trừ mỗi cột một số bằng phần tử nhỏ nhất của cột đó. Ma trận kết quả được gọi là rút gọn theo hàng và cột. Tổng của tất cả các số bị trừ được gọi là hằng số khử.

Hằng số truyền nên được chọn làm giới hạn dưới của độ dài tuyến đường.

Chia một tập hợp các tuyến đường thành các tập hợp con

Để xác định các ứng cử viên để đưa vào tập hợp các cung dọc theo đó việc phân nhánh được thực hiện, chúng tôi xem xét tất cả các phần tử trong ma trận đã cho bằng 0. Chúng ta hãy tìm độ Θ ij của các phần tử 0 của ma trận này. Bậc của phần tử 0 Θ ij bằng tổng phần tử nhỏ nhất trong hàng Tôi và phần tử tối thiểu trong cột j(khi chọn những mức tối thiểu này c ij – không được tính đến). Với xác suất cao nhất, tuyến đường được yêu cầu thuộc về các cung có mức độ tối đa số không.

Để có được ma trận thanh toán của các tuyến đường, bao gồm cả cung ( Tôi , j) chúng ta gạch bỏ hàng trong ma trận Tôi và cột j và để ngăn chặn việc hình thành chu trình trong tuyến đường, chúng tôi thay thế phần tử đóng chuỗi hiện tại thành vô cùng.

Nhiều tuyến đường không bao gồm một vòng cung ( Tôi , j) thu được bằng cách thay thế phần tử c ij đến vô cùng.

Một ví dụ về giải bài toán người bán hàng du lịch bằng phương pháp nhánh và ràng buộc

Một nhân viên bán hàng du lịch phải đi đến 6 thành phố. Để giảm chi phí, anh ấy muốn xây dựng một tuyến đường sao cho anh ấy có thể đi vòng quanh tất cả các thành phố đúng một lần và quay trở lại tuyến đường ban đầu với chi phí tối thiểu. Thành phố nguồn A. Chi phí di chuyển giữa các thành phố được tính theo ma trận sau:

MỘT B C D E F
MỘT ∞ 26 42 15 29 25
B 7 ∞ 16 1 30 25
C 20 13 ∞ 35 5 0
D 21 16 25 ∞ 18 18
E 12 46 27 48 ∞ 5
F 23 5 5 9 5 ∞

Giải pháp của vấn đề

Để thuận tiện cho việc trình bày, ở mọi nơi bên dưới trong ma trận thanh toán, chúng ta sẽ thay thế tên các thành phố (A, B, ..., F) bằng số hàng và cột tương ứng (1, 2, ..., 6).

Hãy tìm giới hạn dưới của độ dài của tập hợp tất cả các tuyến đường. Hãy trừ từ mỗi hàng một số bằng phần tử nhỏ nhất của hàng này, sau đó trừ từ mỗi cột một số bằng phần tử nhỏ nhất của cột này và do đó biểu diễn một ma trận theo hàng và cột. Hàng tối thiểu: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

Sau khi trừ chúng từng dòng, chúng ta nhận được:


1 2 3 4 5 6
1 ∞ 11 27 0 14 10
2 6 ∞ 15 0 29 24
3 20 13 ∞ 35 5 0
4 5 0 9 ∞ 2 2
5 7 41 22 43 ∞ 0
6 18 0 0 4 0 ∞

Cột tối thiểu: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.

Sau khi trừ chúng theo cột, chúng ta nhận được ma trận sau:

1 2 3 4 5 6
1 ∞ 11 27 0 14 10
2 1 ∞ 15 0 29 24
3 15 13 ∞ 35 5 0
4 0 0 9 ∞ 2 2
5 2 41 22 43 ∞ 0
6 13 0 0 4 0 ∞

Hãy tìm giới hạn dưới φ (Z) = 15+1+0+16+5+5+5 = 47.

Để xác định các ứng cử viên để đưa vào tập hợp các cung dọc theo đó việc phân nhánh được thực hiện, chúng ta tìm độ Θ ij của các phần tử 0 của ma trận này (tổng các cực tiểu trong hàng và cột). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Bậc cao nhất là Θ 14 = 10. Ta tiến hành phân nhánh dọc theo cung (1, 4).

EMMIMVL, ISO, MPUR

VẤN ĐỀ NHÂN VIÊN DU LỊCH

Các định nghĩa

Đồ thị là một tập hữu hạn không rỗng gồm hai tập con Và . Tập hợp con đầu tiên
(đỉnh) bao gồm bất kỳ tập hợp các phần tử nào. Tập hợp con thứ hai (arc) bao gồm các cặp phần tử được sắp xếp của tập hợp con đầu tiên
. Nếu các đỉnh
Và
như vậy mà
, thì đây là các đỉnh kề nhau.

Lộ trình trong cột gọi là dãy đỉnh
không nhất thiết phải phân biệt theo cặp, ở đâu đối với bất kỳ
liền kề với . Một tuyến đường được gọi là một chuỗi nếu tất cả các cạnh của nó đều phân biệt theo từng cặp. Nếu như
thì tuyến đường được gọi là đóng. Một mạch kín được gọi là một chu trình.

Xây dựng vấn đề

Người bán hàng du lịch phải đi du lịch N các thành phố. Để giảm chi phí, anh ấy muốn xây dựng một tuyến đường sao cho anh ấy có thể đi vòng quanh tất cả các thành phố đúng một lần và quay trở lại tuyến đường ban đầu với chi phí tối thiểu.

Về mặt lý thuyết đồ thị, bài toán có thể được phát biểu như sau. Bộ Nđỉnh và ma trận ( c ij), ở đâu c ij ≥0 – độ dài (hoặc giá) của cung ( Tôi, j),
. Dưới tuyến đường nhân viên bán hàng du lịchz hãy hiểu chu kỳ Tôi 1 , Tôi 2 ,…, Tôi N , Tôi 1 điểm 1,2,…,n. Như vậy, tuyến đường là một tập hợp các cung. Nếu giữa thành phố Tôi Và j không có sự chuyển tiếp thì ký hiệu “vô cực” được đặt vào ma trận. Nó phải được đặt theo đường chéo, có nghĩa là không được phép quay lại điểm mà bạn đã đi qua tuyến đường nhân viên bán hàng du lịch, chiều dài tuyến đường tôi(z) bằng tổng độ dài của các cung có trong tuyến đường. Cho phép Z– tập hợp tất cả các tuyến đường có thể. Đỉnh ban đầu Tôi 1 – cố định. Bạn cần tìm đường đi z 0  Z, như vậy mà tôi(z 0)=phút tôi(z), zZ.

Giải pháp của vấn đề

Ý tưởng chính của phương pháp nhánh và ràng buộc là trước tiên, giới hạn dưới φ được xây dựng trên độ dài của tập hợp các tuyến đường Z. Sau đó, tập hợp các tuyến đường được chia thành hai tập hợp con sao cho tập hợp con đầu tiên bao gồm các tuyến đường chứa một số cung ( tôi, j) và một tập con khác không chứa cung này. Đối với mỗi tập hợp con, giới hạn dưới được xác định theo quy tắc tương tự như đối với tập hợp tuyến đường ban đầu. Giới hạn dưới kết quả cho các tập hợp con Và hóa ra không nhỏ hơn giới hạn dưới của tập hợp tất cả các tuyến đường, tức là
.

So sánh giới hạn dưới φ () Và φ (), chúng ta có thể chọn tập hợp con các tuyến đường có nhiều khả năng chứa tuyến đường có độ dài tối thiểu.

Khi đó một trong các tập con hoặc theo một quy tắc tương tự, nó được chia thành hai cái mới Và . Giới hạn dưới một lần nữa được tìm thấy cho họ φ (), Và φ () vân vân. Quá trình phân nhánh tiếp tục cho đến khi tìm được một tuyến đường duy nhất. Anh ấy được gọi kỷ lục đầu tiên. Sau đó họ nhìn qua những cành cây rách nát. Nếu giới hạn dưới của chúng lớn hơn độ dài của bản ghi đầu tiên thì vấn đề đã được giải quyết. Nếu có những bản ghi có giới hạn dưới nhỏ hơn độ dài của bản ghi đầu tiên thì tập con có giới hạn dưới nhỏ nhất sẽ tiếp tục phân nhánh cho đến khi được thuyết phục rằng nó không chứa bản ghi tốt nhất. tuyến đường.

Nếu tìm thấy một thì việc phân tích các nhánh bị hỏng sẽ tiếp tục đối với giá trị mới của độ dài tuyến đường. Anh ấy được gọi kỷ lục thứ hai. Quá trình giải kết thúc khi tất cả các tập hợp con đã được phân tích.

Ý tưởng chính của phương pháp rẽ nhánh và ràng buộc là không phải tất cả các đỉnh đều phân nhánh. Đầu tiên, các đỉnh được quét và mỗi đỉnh được tính điểm. Đỉnh nhận được điểm số cao nhất sẽ phân nhánh.

Mỗi đỉnh tương ứng với nhiều giải pháp khả thi. Mỗi phương án giải pháp tương ứng với một giá trị nhất định của tiêu chí hiệu quả
. Thật thuận tiện khi lấy giá trị tốt nhất trong số các giá trị này (tối thiểu hoặc tối đa) làm ước tính cho đỉnh. Tuy nhiên, để tính giá trị chính xác tiêu chí mà không trải qua tất cả các lựa chọn là không thể. Do đó, giá trị chính xác không được sử dụng tiêu chí và ước tính của nó là từ bên dưới (trong trường hợp tối thiểu hóa) hoặc từ trên cao (trong trường hợp tối đa hóa). Giới hạn dưới là ước tính giới hạn dưới của một tập hợp các tùy chọn; giới hạn trên là ước tính giới hạn trên của một tập hợp các tùy chọn.

Việc đánh giá một đỉnh phải thỏa mãn các tính chất sau.

Thuật toán nhánh và ràng buộc

Bước 1 . Đỉnh của cấp độ đầu tiên đang được xây dựng. Đối với mỗi đỉnh, ước tính giới hạn dưới (trên) được tính toán. Đỉnh tương ứng với điểm tốt nhất (tối thiểu hoặc tối đa) sẽ được phân nhánh.

Bước 2 . Đối với tất cả các đỉnh cấp độ thứ (
) điểm được tính toán. Một trong những đỉnh treo của cành cấp
, tương ứng với điểm tốt nhất (tối thiểu hoặc tối đa).

Bước 3 . Các hành động của bước 2 được lặp lại cho đến khi đạt được giải pháp chính xác ở cấp độ cuối cùng. Giá trị chính xác được tính toán cho nó . Nếu giá trị này không tệ hơn so với ước tính của các đỉnh treo còn lại thì giải pháp tối ưu đã được tìm thấy. Nếu giá trị này hoàn toàn tốt hơn thì giải pháp tối ưu là duy nhất. Nếu giá trị hàm cho các đỉnh cấp độ cuối cùng không tốt hơn giá trị đánh giá của các đỉnh treo còn lại thì chuyển sang bước 2.

Phương pháp rẽ nhánh và giới hạn không đảm bảo rằng việc tìm kiếm toàn diện sẽ không được thực hiện khi giải một bài toán.

Để triển khai thực tế phương pháp nhánh và ràng buộc liên quan đến bài toán người bán hàng du lịch, chúng tôi sẽ chỉ ra một kỹ thuật xác định ranh giới dưới của các tập hợp con và phân chia tập hợp các tuyến đường thành các tập hợp con (phân nhánh).

Để tìm giới hạn dưới, chúng ta sử dụng phép xem xét sau: nếu một số nhất định được cộng hoặc trừ khỏi các phần tử của bất kỳ hàng nào trong ma trận của bài toán nhân viên bán hàng du lịch (hàng hoặc cột), thì tính tối ưu của kế hoạch sẽ không thay đổi. Độ dài của bất kỳ tuyến đường nhân viên bán hàng du lịch sẽ thay đổi theo số tiền này.

Trừ từ mỗi dòng một số bằng phần tử nhỏ nhất của dòng này. Trừ mỗi cột một số bằng phần tử nhỏ nhất của cột đó. Ma trận kết quả được gọi là rút gọn theo hàng và cột. Tổng các số bị trừ gọi là đúc liên tục.

Hằng số truyền nên được chọn làm giới hạn dưới của độ dài tuyến đường.

Chia một tập hợp các tuyến đường thành các tập hợp con

Để xác định các ứng cử viên để đưa vào tập hợp các cung dọc theo đó việc phân nhánh được thực hiện, hãy xem xét tất cả các phần tử trong ma trận đã cho bằng 0. Chúng ta hãy tìm độ Θ ij của các phần tử 0 của ma trận này. Bậc của phần tử 0 Θ ij bằng tổng phần tử nhỏ nhất trong hàng Tôi và phần tử tối thiểu trong cột j(khi chọn những mức tối thiểu này c ij – không được tính đến). Với xác suất cao nhất, tuyến đường được yêu cầu thuộc về các cung có bậc tối đa bằng 0.

Để có được ma trận thanh toán của các tuyến đường, bao gồm cả cung ( Tôi, j) chúng ta gạch bỏ hàng trong ma trận Tôi và cột j và để ngăn chặn việc hình thành chu trình trong tuyến đường, chúng tôi thay thế phần tử đóng chuỗi hiện tại thành vô cùng.

Nhiều tuyến đường không bao gồm một vòng cung ( Tôi, j) thu được bằng cách thay thế phần tử c ij đến vô cùng.

Ví dụ (G.I. Prosvetov, 2009, trang 44)

Hãy giải bài toán nhân viên bán hàng du lịch với năm điểm.

Khoảng cách giữa các khu định cư được xác định bằng ma trận

,

Ở đâu - độ dài đường đi từ điểm đó Tôi chỉ j.

Ở mỗi bước một cạnh
hoặc được bao gồm trong phản hồi (chỉ định
) hoặc không có trong phản hồi (ký hiệu
).

Bước 1. Tìm hằng số khử.

Chúng tôi tìm phần tử tối thiểu trong mỗi dòng và trừ nó khỏi tất cả các phần tử của dòng này. Trong ma trận kết quả, chúng ta tìm phần tử nhỏ nhất trong mỗi cột và trừ nó khỏi từng phần tử của cột tương ứng.

Cực tiểu tìm thấy trong hàng và cột tương ứng được gọi là hằng số rút gọn của hàng hoặc cột. Tổng của tất cả các cực tiểu tìm được bằng 18 – hằng số ma trận rút gọn. Cô ấy cho ước tính thấp hơnở một bước có độ dài tuyến đường nhất định.

Bước 2 . Xác định cung có loại trừ tối đa hóa ước tính thu được ở bước trước.

Với mục đích này, chúng ta thay thế từng số 0 bằng .

Yếu tố
Nó có số tiền lớn nhất. Do đó, toàn bộ tập hợp các tuyến đường được chia thành hai lớp:
(không chứa cung
) Và
(chứa cung
).

Bước 3 . Xác định một tập hợp các cung để phân nhánh tiếp theo.

Hãy xem xét tập hợp
. Ngoại lệ vòng cung

TRÊN :

.

Trong ma trận kết quả, bạn cần xác định tổng các hằng số khử:

Giới hạn dưới của tập hợp
, trong đó 18 là số điểm bước trước, 3 – đánh giá bước hiện tại.

Hãy xem xét tập hợp
. Bật vòng cung
được thực hiện bằng cách loại bỏ dòng đầu tiên (trong tập hợp
từ điểm 1 chúng ta chỉ đi đến điểm 3) và cột thứ 3 (trong tập hợp
Chúng ta chỉ có thể đến điểm 3 từ điểm 1). Chúng ta thay phần tử (3.1) bằng (chúng tôi loại trừ khả năng quay trở lại, lặp lại hoặc hình thành chu trình không phải Hamilton):


.

Giới hạn dưới của tập hợp, trong đó 18 là ước tính của bước trước, 1 là ước tính của bước hiện tại. Các số phía trên ma trận là số cột, các số phía trước ma trận là số hàng.

Bởi vì
, sau đó chúng tôi có nhiều chi nhánh hơn nữa
.

Đối với ma trận

Chúng ta hãy xác định cung mà việc loại trừ của nó sẽ tối đa hóa ước tính kết quả
. Để làm điều này, thay thế từng số 0 bằng và tính tổng các phần tử nhỏ nhất trong hàng và cột chứa phần tử mới này :

Đối với phần tử
số tiền này là lớn nhất. Do đó, toàn bộ tập hợp các tuyến đường được chia thành hai lớp:
(không chứa cung
) Và
(chứa cung
).

Hãy xem xét tập hợp
. Ngoại lệ vòng cung
được thực hiện bằng cách thay thế phần tử
TRÊN :

.

Chúng ta hãy xác định hằng số giảm của nó trong ma trận kết quả:

.

    (5x5) (Tính cho 4 nhiệm vụ có điều kiện) thời gian hoàn thành 2 cặp) (Nhân viên bán hàng thuyết trình) Nhiều nhất nhiệm vụ khó khăn hoạt động nghiên cứu

Sử dụng phương pháp nhánh và ràng buộc, bạn cần tìm con đường ngắn nhất để đi qua 5 thành phố và quay trở lại thành phố ban đầu, MỖI THÀNH PHỐ ĐƯỢC THAM QUAN CHÍNH XÁC 1 lần (ma trận hiển thị giá di chuyển từ thành phố “bên trái” đến thành phố "phía trên").

Giải pháp chi nhánh và ràng buộc

      Bước số 0 Chúng tôi ước tính chu kỳ 1-2-3-4-5-1 - đây là phép tính gần đúng đầu tiên của ước tính trên. Hơn nữa, nếu trên bất kỳ nhánh nào của cây phân nhánh, ước tính thấp hơn của tập hợp con của các giải pháp hóa ra lại cao hơn nhánh trên thì nhánh này “chết đi”, bởi vì tất cả các giải pháp của cô ấy đều tệ hơn những giải pháp hiện có.

      Bước số 1a) Viết các hằng số rút gọn theo từng dòng. Đây là những con số tối thiểu trong dòng. Chúng phải được trừ khỏi các phần tử trên dòng của chúng (ít nhất một số 0 sẽ xuất hiện trên mỗi dòng).

      Bước số 1b) Trong ma trận vừa lấy ở bước 1a) (với các số 0 ở các hàng), thực hiện thao tác tương tự dọc theo các cột - tìm các cột có e nhỏ nhất bằng 0 và trừ đi. Ở dạng tự kiểm tra, hãy xác minh rằng hiện tại có ít nhất một số 0 ở mỗi cột và hàng của ma trận giá vé.

      Bước số 1c) Ta tính tổng các hằng số rút gọn thu được ở bước a) và b). Rõ ràng, không có tuyến đường nào có thể có chi phí thấp hơn - vì vậy đây là ước tính thấp hơn. Tiếp theo, chúng tôi sẽ tăng ước tính này lên một lượng Và
      (chúng tôi sẽ mô tả các đại lượng này bên dưới), trong đó - một cặp chỉ số của cạnh mà nó được chọn để phân nhánh.

      Chúng ta hãy mô tả sự phân nhánh sẽ xảy ra như thế nào: chúng ta chọn cạnh i, j (thỏa mãn các yêu cầu của đoạn tiếp theo), tập hợp các tuyến đường Hamilton có thể được coi là một tập hợp lớn các “hạt” duy nhất bao gồm các liên kết như St. Petersburg-Moscow, Moscow-Odessa, Odessa-Belgrade, v.v. Chúng ta hãy áp dụng phương pháp chia toàn bộ tập hợp các con đường đã đóng thành những nơi có đường Odessa-Belgrade và những nơi không có (bộ đầu tiên ít hơn bộ thứ hai).

      Về mặt lý thuyết, có thể phân nhánh dọc theo bất kỳ cạnh nào, nhưng nhiệm vụ của chúng tôi là đảm bảo rằng trên một bộ, ước tính thấp hơn về giá của tuyến đường không thay đổi và mặt khác nó tăng càng nhiều càng tốt - điều này có thể góp phần vào thực tế là trong hầu hết các trường hợp, nói chung, việc tìm kiếm tổ hợp của một thuật toán hàm mũ để giải NP hoàn thành nhiệm vụ sẽ không quá lớn.

      Để thực hiện việc này: Bước số 2. Chúng tôi tính toán chi phí truyền tải cho mỗi phần tử 0 (nếu nó chuyển thành vô cùng ∞) - mức tăng hằng số rút gọn của hàng và cột tương ứng.

      Chúng tôi chia bộ giải pháp hiện tại thành hai:


    1. Quá trình kết thúc một phần sau khi chọn k-2 cạnh, trong đó k là tổng số đỉnh. Trong bài toán 2x2, lời giải là duy nhất; nó (thường) dẫn đến sự điều chỉnh giới hạn trên. Nếu tất cả các giới hạn dưới (khác) tệ hơn thì sẽ có câu trả lời. Trong một ví dụ như ví dụ được đưa ra trong nhiệm vụ này, tình huống này thường xảy ra, nhưng trong một biểu đồ lớn hơn và phức tạp hơn (khi tạo một thuật toán phổ quát), cần phải mô tả các hành động tiếp theo. Nếu không phải tất cả các giới hạn dưới vẫn tệ hơn giới hạn trên đã được điều chỉnh thì các tập hợp không tầm thường còn sót lại sẽ phải được phân nhánh cho đến khi chúng biến mất do giới hạn cao, tức là. ước tính thấp hơn không hợp lệ hoặc (rất hiếm) trước khi nhận được ước tính cao hơn mới - giải pháp mới, chất lượng vượt trội so với phiên bản trước. Quá trình tiếp tục cho đến khi giải pháp thu được không bị tranh cãi.

Xét ma trận chi phí đi lại từ thành phố “bên trái” đến thành phố “trên”

Ước tính toàn cầu ban đầu Zupper=10+10+20+15+10 = 65 thu được thông qua chu trình. (các cạnh tương ứng được khoanh tròn thành các hình vuông trong hình - một ở góc dưới bên trái, phần còn lại phía trên đường chéo).

Hãy bắt đầu vẽ một cái cây phân nhánh

Trong ma trận kết quả

hãy tính toán giá thêm“đường vòng” của mỗi cá nhân số không(nghĩa là tổng các hằng số giảm sẽ tăng bao nhiêu nếu đường không còn tồn tại (giá vé sẽ được thay thế bằng vô cực)) và chọn số “0” có chi phí bỏ qua là tối đa.

(1,2)=0

(1,5)=1

(2,1)=0

(2,3)=5 (Tối đa )

(3,1)=0

(3,4)=2

(4,2)=4

(5,2)=2

Vì vậy, chi phí tối đa của đường vòng  được quan sát thấy khi cạnh (2,3)=5 bị tắt.

Với thuật toán của chúng tôi, việc chia tất cả các chu trình đi vòng thành các chu trình chứa cạnh (2,3) và các chu trình không chứa cạnh đó là điều tự nhiên. Ước tính chi phí thấp hơn của nhóm chu kỳ đầu tiên (chúng ta sẽ tính toán sau) rất có thể sẽ không thay đổi, ước tính thấp hơn của các chu kỳ không bao gồm (2,3) sẽ tăng lên số tiền (2,3)=5.

TRÊN trang riêng Chúng ta bắt đầu vẽ cây phân nhánh.

Ở giai đoạn đầu, nó chứa tập hợp tất cả các chu trình, được chia thành một tập chứa (2,3) (có ít chu trình hơn) ở bên trái và không chứa (2,3) ở bên phải.

Giới hạn dưới của tập hợp bên phải (lớn hơn) được tính bằng tổng giới hạn của đỉnh Z trước đó phút=58 và(2,3)=5:Z phút =58+5=63.

Ở tập bên trái, cạnh (2,3) (nói một cách tương đối, đường St. Petersburg - Moscow) là bắt buộc - theo đó, chúng tôi không còn lựa chọn đi đâu từ thành phố 2 (chúng tôi xóa dòng 2) và làm thế nào để đến thành phố số 3 (chúng tôi xóa cột).

Cây nhánh cuối cùng:

Phương pháp cuối cùng.

Kết quả là một ma trận 2x2.

Ví dụ nhỏ.

Cuối cùng, hãy xem ma trận 3x3.

Khi đó giới hạn trên của độ dài của tất cả các tuyến đường là Z max = 4+9+8 = 21

Do đó, ước tính thấp hơn của Z thấp hơn = 16 (6+3+4+3).

Chúng tôi ước tính các hằng số bỏ qua:

Hãy kết hợp các thành phố 2 và 1 ở nhánh bên trái, ở nhánh bên phải ước tính chi phí thấp hơn sẽ tăng từ 16 lên 5 lên 21.

chúng ta nhận được ma trận

Hãy cấm ngắn mạch- tránh

và giảm ma trận

Ở nhánh bên trái ΔZ_=4, ước tính mới hàm mục tiêu Z_=16+ ΔZ_=16+4=20.

Đã chọn cạnh

Sườn còn lại
.

Sử dụng nguyên tắc domino, chúng ta khôi phục chu kỳ tối thiểu bắt đầu từ cạnh bắt đầu bằng 1, với cạnh này
, như thể đang bước đi như một “tàu hỏa”.

Đây là một đường dẫn cụ thể có độ dài 20, tại thời điểm đó chúng ta có giới hạn trên mới, tốt hơn giới hạn trên cũ là 21.

Trên cây phân nhánh của bộ liệt kê, nhánh có ước tính thấp hơn 21 cao hơn (nhánh bên phải) sẽ biến mất.

Trong trường hợp của chúng tôi, tùy chọn kết quả hóa ra lại tốt hơn tất cả các ước tính thấp hơn cho các nhánh khác.

Trả lời:
.

Bài kiểm tra


Trình bày NHÂN VIÊN DU LỊCH.

Giáo viên kiểm tra nhiệm vụ về thiết kế cây phân nhánh. Để nó trình bày thông tin đầy đủ nhất cần thiết cho việc xác minh tại các đỉnh của cây nhằm hiển thị các ước tính thấp hơn của các hàm mục tiêu, tất cả θ (tăng tổng các hằng số rút gọn khi rẽ phải), tất cả ΔZ (tăng trong tổng các hằng số rút gọn ở lượt rẽ trái) phải được hiển thị trên các cạnh của cây. Trong khi rẽ trái, một cạnh bắt buộc được chọn (được đánh dấu trên cây nhánh) và một cạnh cấm được thêm vào. Để giải thích sự lựa chọn của nó, bên cạnh cây phân nhánh ở cấp độ thích hợp, cần mô tả một chuỗi trong đó cạnh cấm, cùng với các cạnh đã chọn trước đó (bao gồm cả cạnh đã chọn hiện tại), tạo ra một chu trình không đi qua tất cả các các cạnh (được gọi là “ngắn mạch” của chu trình).

Câu trả lời đưa ra một chuỗi các Cạnh có dạng (1,k)(k,l)(l,m)..(r,1)(theo quy mô của bài toán), chi phí của tuyến đường bao gồm ước tính thấp hơn ban đầu và mức tăng của nó ΔZ (nếu chỉ có CROSSOUTS - rẽ trái) và - điều này rất hiếm khi xảy ra - ΔZ và θ, nếu, NGOÀI Rẽ trái, có một hoặc nhiều lượt rẽ phải. Kiểm tra chi phí của giải pháp THU ĐƯỢC bằng cách sử dụng ma trận ban đầu, giải thích lý do chênh lệch - nếu có (không được có sự không khớp).

Gửi công việc tốt của bạn trong cơ sở kiến ​​thức rất đơn giản. Sử dụng mẫu dưới đây

Làm tốt lắm vào trang web">

Các sinh viên, nghiên cứu sinh, các nhà khoa học trẻ sử dụng nền tảng kiến ​​thức trong học tập và công việc sẽ rất biết ơn các bạn.

Đăng trên http://www.allbest.ru/

1 . Mô tả phương phápnhánh và giới hạn

Phương pháp nhánh và ràng buộc dựa trên ý tưởng phân chia tuần tự tập hợp các giải pháp khả thi thành các tập con. Ở mỗi bước của phương pháp, các phần tử phân vùng được kiểm tra để xác định xem tập hợp con đã cho có chứa giải pháp tối ưu hay không. Việc xác minh được thực hiện bằng cách tính toán ước tính thấp hơn cho hàm mục tiêu trên một tập hợp con nhất định. Nếu ước tính thấp hơn không nhỏ hơn ghi- tìm được giải pháp tốt nhất thì tập hợp con đó có thể bị loại bỏ. Tập hợp con được kiểm tra cũng có thể bị loại bỏ nếu có thể tìm thấy giải pháp tốt nhất. Nếu giá trị của hàm mục tiêu trên nghiệm tìm được nhỏ hơn bản ghi thì bản ghi sẽ thay đổi. Khi kết thúc thuật toán, bản ghi là kết quả công việc của nó.

Nếu có thể loại bỏ tất cả các phần tử của phân vùng thì bản ghi là giải pháp tối ưu cho vấn đề. Mặt khác, tập hợp con có triển vọng nhất sẽ được chọn từ các tập con không bị loại bỏ (ví dụ: có giá trị giới hạn dưới thấp nhất) và nó sẽ được phân chia. Các tập hợp con mới được kiểm tra lại, v.v.

Khi áp dụng phương pháp rẽ nhánh và ràng buộc cho từng bài toán cụ thể, trước hết phải xác định hai thủ tục quan trọng nhất của nó: 1) phân nhánh tập hợp phương pháp khả thi; 2) tính toán ước tính dưới và trên của hàm mục tiêu.

1 . 1 Quy tắc phân nhánh

Tùy theo đặc điểm của công việc, người ta thường sử dụng một trong hai phương pháp để tổ chức phân nhánh:

1. Phân nhánh tập hợp các lời giải khả thi của bài toán gốc D;

2. Phân nhánh của tập D" thu được từ D bằng cách loại bỏ điều kiện nguyên trên các biến.

Phương pháp phân nhánh đầu tiên thường được sử dụng cho các nhiệm vụ Lập trình số nguyên và bao gồm việc xác định các lĩnh vực con của các giải pháp khả thi bằng cách cố định các giá trị các thành phần riêng lẻ các biến tối ưu hóa số nguyên (Hình 1). Trong bộ lễ phục. 1-a đưa ra cách diễn giải hình học của vùng nghiệm có thể chấp nhận được của bài toán quy hoạch số nguyên, được xác định bởi hai ràng buộc tuyến tính và điều kiện cho tính không âm của các biến và các vùng con được hình thành bằng cách phân nhánh, và trong Hình. Hình 1-b hiển thị sơ đồ phân nhánh tương ứng.

Phương pháp phân nhánh thứ hai phổ biến hơn phương pháp thứ nhất. Để phân nhánh một vùng D i " theo cách này trên D i " một bài toán tối ưu được giải bằng hàm đích của bài toán ban đầu và các biến thực.

Việc phân nhánh được thực hiện nếu trong lời giải tối ưu giá trị của ít nhất một biến số nguyên theo công thức ban đầu của bài toán không phải là số nguyên. Trong số các biến này, một biến được chọn, ví dụ j - i. Hãy biểu thị giá trị của nó trong nghiệm tối ưu tìm được x 0 [j]. Họ nói rằng việc phân nhánh được thực hiện bởi biến x[j]. Vùng D i " được chia thành hai tiểu vùng D i1 " và D i2 " như sau:

Ở đâu ] - Toàn bộ phần giá trị x 0 [j]

Trong bộ lễ phục. 2 thường đưa ra cách giải thích hình học của sự phân nhánh như vậy.

Đăng trên http://www.allbest.ru/

Cơm. 2. Giải thích hình học của sự phân nhánh

Có thể thấy rằng trong trường hợp này, phần giữa các mặt phẳng của các giới hạn mới đưa ra được loại bỏ khỏi vùng D i”. Vì biến x[j] theo điều kiện của miền nghiệm chấp nhận được của bài toán ban đầu là số nguyên, thì từ miền con của các lời giải có thể chấp nhận được của bài toán ban đầu D i (D i D i ") với ngoại lệ như vậy, không có quyết định nào bị loại trừ.

1 . 2 Hình thành các ước tính dưới và trên của hàm mục tiêu

Trước khi chúng ta bắt đầu cuộc thảo luận vấn đề này, phải nói rằng nhìn chung người ta chấp nhận sử dụng phương pháp nhánh và ràng buộc cho một bài toán trong đó hướng tối ưu hóa được rút gọn về dạng cực tiểu hóa. Để làm cho các ký hiệu và phép tính tiếp theo trở nên gọn gàng hơn, chúng ta sẽ viết bài toán quy hoạch rời rạc mà chúng ta sẽ sử dụng phương pháp rẽ nhánh và giới hạn ở dạng tổng quát sau:

trong đó x là vectơ của các biến tối ưu hóa, một số là số thực và một số là số nguyên; f(x) - trong trường hợp chung hàm mục tiêu phi tuyến; D là vùng các lời giải khả thi cho một bài toán quy hoạch rời rạc tổng quát.

Các ước tính thấp hơn của hướng mục tiêu, tùy thuộc vào phương pháp phân nhánh đã chọn, có thể được xác định cho các vùng con D i D hoặc cho các vùng con D i "D" (D i " và D" được lấy từ các bộ tương ứng D i và D bằng cách loại bỏ điều kiện nguyên trên các biến rời rạc).

Ước lượng thấp hơn của hàm mục tiêu f(x) trên tập D i (hoặc D i ") sẽ là đại lượng:

Việc tính toán giới hạn dưới trong từng trường hợp cụ thể có thể được thực hiện có tính đến đặc điểm của vấn đề đang được giải quyết. Đồng thời, để các ước tính thực hiện chức năng của mình một cách hiệu quả nhất, chúng phải càng lớn càng tốt, tức là. càng gần với giá trị thực của min f(x) càng tốt. Trước hết, điều này là cần thiết để các giới hạn dưới phản ánh chính xác nhất có thể tỷ lệ thực tế min f(x) trên các tập hợp con được hình thành trong quá trình phân nhánh và giúp xác định chính xác hơn hướng tìm kiếm tiếp theo giải pháp tối ưu nhiệm vụ ban đầu.

Trong bộ lễ phục. Hình 3 cho thấy một trường hợp lý tưởng như vậy khi các ước tính thấp hơn (được kết nối bằng một đường đứt nét đứt) phản ánh chính xác mối quan hệ giữa giá trị thực và giá trị thực. giá trị tối thiểu f(x) (được nối bằng một đường đứt nét) cho bốn tập hợp con của các phương án khả thi D 1, D 2, D 3, D 4.

Một trong phương pháp phổ quát Tính giới hạn dưới liên quan đến việc giải quyết vấn đề sau:

O i được xác định theo cách này là ước tính thấp hơn của f(x) trên D i (hoặc D i "), vì D i D i ".

Nếu khi giải bài toán (4) xác lập được điều đó thì về mặt tổng quát chúng ta sẽ giả sử điều đó.

Một điều cần lưu ý tài sản quan trọngước tính thấp hơn, bao gồm thực tế là giá trị của chúng đối với các tập hợp con được hình thành trong quá trình phân nhánh không thể nhỏ hơn ước tính thấp hơn của hàm mục tiêu trên tập hợp được phân nhánh.

Cùng với giới hạn dưới, phương thức nhánh và giới hạn sử dụng giới hạn trên f(x). Theo quy định, chỉ có một giá trị của giới hạn trên được tính toán, giá trị này được định nghĩa là giá trị của hàm mục tiêu cho giải pháp khả thi tốt nhất được tìm thấy cho bài toán ban đầu. Ước tính cao hơn này đôi khi được gọi là bản ghi. Nếu, đối với vấn đề đang được giải quyết, có thể đạt được giới hạn trên f(x) một cách khá đơn giản và chính xác cho các tập hợp riêng lẻ được hình thành trong quá trình phân nhánh, thì chúng phải được sử dụng trong phương pháp để giảm độ phức tạp tính toán của quá trình giải. Khi sử dụng một giới hạn trên duy nhất cho nghĩa gốc thường được coi là bằng vô cùng (), tất nhiên, trừ khi, từ những xem xét tiên nghiệm, không có một giải pháp chấp nhận được nào cho vấn đề ban đầu được biết đến. Khi tìm được giải pháp khả thi đầu tiên:

Sau đó, khi xác định được giải pháp khả thi tốt hơn, giới hạn trên được điều chỉnh:

Như vậy, giá trị của ước lượng trên chỉ có thể giảm đi trong quá trình giải bài toán.

1 .3 Thuật toán rẽ nhánh và ràng buộc

Các quy tắc cơ bản của thuật toán có thể được xây dựng như sau:

1. Trước hết, tập con có số tương ứng với giá trị thấp nhất của ước lượng dưới của hàm mục tiêu chịu sự phân nhánh (I là tập hợp các số của tất cả các tập con, (hoặc) nằm ở cuối các nhánh và việc phân nhánh vẫn chưa bị dừng lại). Nếu phương pháp phân nhánh ở trên được triển khai thì có thể nảy sinh sự mơ hồ liên quan đến việc lựa chọn thành phần mà bước phân nhánh tiếp theo phải được thực hiện. Thật không may, câu hỏi về cách lựa chọn “tốt nhất” theo quan điểm chung vẫn chưa được giải quyết, và do đó trong nhiệm vụ cụ thể Một số quy tắc heuristic được sử dụng.

2. Nếu đối với tập con thứ i nào đó điều kiện được đáp ứng thì việc phân nhánh của nó phải dừng lại, vì khả năng tìm thấy quyết định tốt trong tập hợp con này (đặc trưng cho chúng) hóa ra lại tệ hơn giá trị của hàm mục tiêu đối với hàm thực được tìm thấy bởi tại thời điểm này thời gian, một giải pháp có thể chấp nhận được cho vấn đề ban đầu (nó mô tả).

3. Việc phân nhánh tập hợp con dừng lại nếu tìm thấy giải pháp tối ưu trong bài toán (4). Điều này được chứng minh bởi thực tế là không có giải pháp khả thi nào tốt hơn trong tập hợp con này. Trong trường hợp này, khả năng điều chỉnh được xem xét.

4. Nếu, ở đâu, thì các điều kiện tối ưu được thỏa mãn cho giải pháp khả thi tốt nhất được tìm thấy tại thời điểm đó. Cơ sở lý luận giống như đoạn 2 của các quy tắc này.

5. Sau khi tìm được ít nhất một lời giải khả thi cho bài toán ban đầu, khả năng dừng thuật toán có thể được xem xét bằng cách đánh giá mức độ gần nhau giữa lời giải khả thi tốt nhất thu được với lời giải tối ưu (dựa trên giá trị của hàm mục tiêu). ):

1 .4 Giải bài toán bằng phương pháp rẽ nhánh và giới hạn

Ban đầu chúng tôi tìm thấy phương pháp đơn giản hoặc phương pháp cơ sở nhân tạo phương án tối ưu của bài toán mà không tính đến số nguyên các biến.

Nếu không có số phân số nào trong số các thành phần của kế hoạch này thì giải pháp mong muốn cho vấn đề này đã được tìm thấy.

Nếu trong số các thành phần của kế hoạch có số phân số, khi đó cần phải chuyển sang các kế hoạch mới cho đến khi tìm ra giải pháp cho vấn đề.

Phương pháp rẽ nhánh và giới hạn dựa trên giả định rằng thiết kế không nguyên tối ưu của chúng ta tạo ra một giá trị hàm lớn hơn bất kỳ thiết kế nhánh tiếp theo nào.

Đặt biến trong kế hoạch là một số phân số. Khi đó, trong phương án tối ưu, giá trị của nó ít nhất sẽ nhỏ hơn hoặc bằng số nguyên nhỏ hơn gần nhất hoặc lớn hơn hoặc bằng số nguyên lớn hơn gần nhất.

Bằng cách xác định các số này, chúng ta tìm được lời giải của hai bài toán quy hoạch tuyến tính bằng phương pháp đơn hình

Có 4 trường hợp có thể xảy ra khi giải cặp bài toán này:

Một trong những vấn đề không thể giải quyết được và vấn đề còn lại có một phương án tối ưu số nguyên. Khi đó phương án này và giá trị của hàm mục tiêu sẽ đưa ra lời giải cho bài toán ban đầu.

Một trong những vấn đề không thể giải quyết được và vấn đề còn lại có phương án tối ưu không nguyên. Sau đó, chúng tôi xem xét bài toán thứ hai và trong phương án tối ưu của nó, chọn một trong các thành phần có giá trị bằng một số phân số và xây dựng hai bài toán tương tự như các bài toán trước.

Cả hai vấn đề đều có thể giải quyết được. Một trong các bài toán có phương án số nguyên tối ưu và phương án tối ưu của bài toán kia có phương án số phân số. Sau đó, chúng tôi tính toán các giá trị của hàm mục tiêu từ các kế hoạch và so sánh chúng với nhau. Nếu trên một sơ đồ tối ưu số nguyên, giá trị của hàm mục tiêu lớn hơn hoặc bằng giá trị của nó trên một sơ đồ có các thành phần bao gồm các số phân số, thì sơ đồ số nguyên này là tối ưu cho bài toán ban đầu và đưa ra giải pháp mong muốn.

Cả hai bài toán đều có thể giải được và phương án tối ưu cho cả hai bài toán đều bao gồm các số phân số. Sau đó, chúng ta xem xét bài toán mà giá trị của hàm mục tiêu là lớn nhất. Và chúng tôi xây dựng hai nhiệm vụ.

Như vậy khi giải bài toán ta thu được sơ đồ sau:

Chúng ta tìm ra giải pháp cho bài toán quy hoạch tuyến tính mà không tính đến số nguyên.

Tạo ra các hạn chế bổ sung đối với thành phần phân đoạn của kế hoạch.

Chúng tôi tìm ra giải pháp cho hai vấn đề với các hạn chế đối với thành phần.

Nếu cần thiết, chúng tôi xây dựng các hạn chế bổ sung, theo bốn trường hợp có thể, chúng tôi có được một phương án số nguyên tối ưu hoặc thiết lập tính không thể giải quyết được của bài toán.

Hãy tìm giải pháp cho vấn đề

Giải pháp. Chúng ta tìm lời giải mà không tính đến giá trị nguyên của bài toán bằng phương pháp đơn hình.

Hãy xem xét cặp đôi tiếp theo nhiệm vụ:

Bài toán thứ nhất có phương án tối ưu

thứ hai là không thể giải quyết được.

Chúng tôi kiểm tra tính toàn vẹn của kế hoạch của nhiệm vụ đầu tiên. Điều kiện này không được đáp ứng nên chúng ta xây dựng các nhiệm vụ sau:

Vấn đề 1.1

Vấn đề 1.2

Bài toán 1.2 không giải được và bài toán số 1.1 có phương án tối ưu trên đó giá trị của hàm mục tiêu.

Kết quả là chúng tôi đã có được điều đó vấn đề ban đầu lập trình số nguyên có phương án tối ưu và.

2. Giải bài toán nhân viên bán hàng du lịch bằng phương pháp nhánh và ràng buộc

Bây giờ chúng ta hãy xem xét lớp bài toán ứng dụng tối ưu hóa. Phương pháp nhánh và ràng buộc được sử dụng trong nhiều trong số đó. Người ta đề xuất xem xét một trong những bài toán phổ biến nhất - bài toán người bán hàng du lịch. Đây là từ ngữ của nó. Có một số thành phố được kết nối theo cách nào đó bằng những con đường có độ dài nhất định; cần phải xác định xem có con đường nào mà người ta chỉ có thể ghé thăm mỗi thành phố một lần và đồng thời quay trở lại thành phố nơi con đường đó bắt đầu (“đường vòng của người bán hàng du lịch”) hay không, và nếu có con đường đó, hãy đến thiết lập những con đường ngắn nhất như vậy.

2.1 Tuyên bố vấn đề

Chúng ta hãy hình thức hóa điều kiện theo lý thuyết đồ thị. Các thành phố sẽ là các đỉnh của biểu đồ và các con đường giữa các thành phố sẽ là các cạnh được định hướng (có hướng) của biểu đồ, trên mỗi cạnh đó một hàm trọng số được chỉ định: trọng số của cạnh là chiều dài của con đường tương ứng. Đường đi cần tìm là một chu trình đơn giản định hướng có trọng số nhỏ nhất trong sơ đồ (hãy nhớ: một chu trình được gọi là chu trình bao trùm nếu nó đi qua tất cả các đỉnh của đồ thị; một chu trình được gọi là đơn nếu nó đi qua từng đỉnh của nó. các đỉnh chỉ một lần; một chu trình được gọi là có hướng nếu điểm đầu của mỗi cạnh tiếp theo trùng với điểm cuối của cạnh trước đó; chứa tất cả các cạnh có thể); những chu trình như vậy còn được gọi là Hamiltonian.

Rõ ràng, một sơ đồ hoàn chỉnh chứa các chu trình thuộc loại được chỉ ra ở trên. Lưu ý rằng chỉ cần coi câu hỏi về sự hiện diện của chu trình Hamilton trong đồ thị là đủ trương hợp đặc biệt vấn đề nhân viên bán hàng du lịch cho các đồ thị hoàn chỉnh. Thật vậy, nếu một sơ đồ nhất định không hoàn chỉnh thì nó có thể được bổ sung để hoàn thiện với các cạnh bị thiếu và trọng số Ґ có thể được gán cho mỗi cạnh được thêm vào, coi đó Ґ là "vô cực máy tính", tức là. tối đa của tất cả các số có thể xem xét. Nếu bây giờ chúng ta tìm thấy chu trình Hamilton nhẹ nhất trong sơ đồ hoàn chỉnh mới được xây dựng, thì nếu nó có các cạnh có trọng số Ґ thì chúng ta có thể nói rằng không có “chu trình nhân viên bán hàng du lịch” trong biểu đồ ban đầu này. Nếu trong một đồ thị hoàn chỉnh, chu trình Hamilton nhẹ nhất có trọng lượng hữu hạn thì đó sẽ là chu trình mong muốn trong đồ thị ban đầu.

Do đó, chỉ cần giải bài toán người bán hàng du lịch đối với các đồ thị hoàn chỉnh có hàm trọng số là đủ. Bây giờ chúng ta hãy trình bày điều này ở dạng cuối cùng:

gọi là đồ thị có hướng đầy đủ và là hàm trọng số; tìm một chu trình định hướng kéo dài đơn giản ("chu trình nhân viên bán hàng du lịch") có trọng số tối thiểu.

Đặt thành phần cụ thể của tập hợp các đỉnh và là ma trận trọng số của một đồ thị nhất định, tức là , và cho bất cứ ai.

Việc xem xét phương pháp nhánh và ràng buộc để giải quyết vấn đề nhân viên bán hàng du lịch được thực hiện thuận tiện nhất trong bối cảnh Ví dụ cụ thể. Sử dụng ký hiệu được giới thiệu ở đây, chúng tôi thực hiện mô tả này trong bài giảng tiếp theo.

Hãy giới thiệu một số thuật ngữ. Hãy để có một số ma trận số. Để rút gọn một hàng của ma trận này có nghĩa là chọn phần tử nhỏ nhất trong hàng đó (gọi là hằng số rút gọn) và trừ nó khỏi tất cả các phần tử của hàng này. Rõ ràng, kết quả là trong dòng này phần tử tối thiểu sẽ bằng 0 và tất cả các phần tử khác sẽ không âm. Cụm từ “cho một cột ma trận” cũng có ý nghĩa tương tự.

Từ mang ma trận theo hàng có nghĩa là tất cả các hàng của ma trận đều đã cho. Cụm từ “rút gọn ma trận theo cột” cũng có ý nghĩa tương tự.

Cuối cùng, từ “reduce ma trận” có nghĩa là ma trận đầu tiên được giảm theo hàng và sau đó được giảm theo cột.

Trọng số của một phần tử ma trận là tổng của các hằng số rút gọn ma trận, thu được từ một ma trận nhất định bằng cách thay thế phần tử được đề cập bằng Ґ. Do đó, các từ số 0 nặng nhất trong ma trận có nghĩa là trọng số của mỗi số 0 trong ma trận được tính toán, sau đó số 0 có trọng số lớn nhất được cố định.

Bây giờ chúng ta hãy mô tả phương pháp nhánh và ràng buộc để giải bài toán nhân viên bán hàng du lịch.

Bước đầu tiên. Chúng tôi sửa tập hợp tất cả các lần duyệt của nhân viên bán hàng du lịch (tức là tất cả các chu kỳ kéo dài có định hướng đơn giản). Vì biểu đồ hoàn chỉnh nên tập hợp này chắc chắn không trống. Chúng ta hãy liên kết với nó một số sẽ đóng vai trò là một giá trị trên tập hợp hàm đánh giá này: số này bằng tổng các hằng số rút gọn của ma trận đã cho các trọng số của các cạnh đồ thị. Nếu tập hợp tất cả các vòng của một nhân viên bán hàng du lịch được ký hiệu là G thì tổng các hằng số rút gọn của ma trận trọng số được ký hiệu là j(G). Cần ghi nhớ ma trận trọng số đã cho của biểu đồ này; hãy biểu thị nó bằng M 1; Như vậy, kết quả của bước đầu tiên:

tập G của tất cả các vòng của nhân viên bán hàng du lịch được liên kết với số j(G) và ma trận M 1 .

Bước thứ hai. Hãy chọn số 0 nặng nhất trong ma trận M 1; để anh ta đứng trong lồng; chúng ta cố định một cạnh của đồ thị và chia tập G thành hai phần: một phần gồm các đường đi qua cạnh và một phần gồm các đường đi không đi qua cạnh.

Chúng ta hãy liên kết ma trận M 1,1 sau với tập hợp: trong ma trận M 1, chúng ta thay thế số trong ô bằng Ґ. Sau đó, trong ma trận kết quả, chúng ta gạch bỏ số hàng i và số cột j, đồng thời giữ nguyên các hàng và cột còn lại bằng số ban đầu. Cuối cùng, hãy rút gọn ma trận cuối cùng này và ghi nhớ tổng các hằng số rút gọn. Ma trận rút gọn thu được sẽ là ma trận M 1,1; Chúng ta cộng tổng các hằng số rút gọn vừa nhớ vào j(G) và kết quả, được ký hiệu thêm là j(), có thể so sánh được với tập hợp.

Bây giờ chúng ta cũng liên kết một ma trận M 1,2 nhất định với tập hợp này. Để làm điều này, trong ma trận M 1, chúng ta thay số trong ô bằng Ґ và trình bày ma trận kết quả. Chúng ta hãy nhớ tổng các hằng số khử và ký hiệu ma trận kết quả là M 1,2. Chúng ta hãy cộng tổng đã ghi nhớ của các hằng số rút gọn vào số j(G) và số kết quả, còn được ký hiệu là j(), có thể so sánh được với tập hợp.

Bây giờ, hãy chọn giữa các tập hợp mà hàm j là nhỏ nhất (tức là tập hợp tương ứng với số nhỏ hơn trong các số j() và j()).

Bây giờ chúng ta hãy lưu ý rằng trong lý do trên, chỉ có một đối tượng thực tế được sử dụng làm đối tượng ban đầu - ma trận trọng số rút gọn của một đồ thị nhất định. Bằng cách sử dụng nó, một cạnh nhất định của biểu đồ đã được xác định và các ma trận mới được xây dựng, tất nhiên, điều tương tự có thể được áp dụng.

Với mỗi ứng dụng lặp đi lặp lại như vậy, cạnh tiếp theo của đồ thị sẽ được ghi lại. Hãy đồng ý về hành động tiếp theo: trước khi xóa một hàng và một cột trong ma trận tiếp theo, cần thay thế bằng Ґ các số trong tất cả các ô tương ứng với các cạnh rõ ràng không thuộc về các chu trình Hamilton đi qua các cạnh đã chọn trước đó.

Chúng ta sẽ lặp lại điều tương tự cho tập đã chọn với ma trận và số j liên kết với nó, v.v., miễn là điều này có thể thực hiện được.

Người ta chứng minh rằng kết quả là một tập hợp bao gồm một vòng của nhân viên bán hàng du lịch, có trọng số bằng giá trị tiếp theo của hàm j; do đó, tất cả các điều kiện được thảo luận khi mô tả phương thức nhánh và ràng buộc đều được đáp ứng.

Sau đó, hồ sơ được cải thiện cho đến khi có được câu trả lời cuối cùng.

2.2 Tình trạng của vấn đề

Sinh viên Ivanov được giao nhiệm vụ giao một số tài liệu quan trọng từ tòa nhà thứ 12. Nhưng may mắn thay, anh ấy có rất ít thời gian cho việc này và anh ấy vẫn phải quay lại. Chúng ta cần tìm con đường ngắn nhất. Khoảng cách giữa các vật được cho trong bảng

2.3 Mô hình toán học nhiệm vụ

Để giải quyết vấn đề, chúng ta gán cho mỗi điểm tuyến đường con số cụ thể: Tòa nhà thứ 12 - 1, Nhà Trắng - 2, KRK "Premier" - 3, Hành chính - tòa nhà thứ 4 và 5 - 5. Theo đó, tổng số điểm. Tiếp theo, chúng tôi giới thiệu các biến thay thế lấy giá trị 0 nếu quá trình chuyển đổi từ điểm thứ i sang điểm thứ j không được đưa vào tuyến đường và 1 nếu ngược lại. Điều kiện đến tại mỗi điểm và ra khỏi mỗi điểm chỉ được biểu diễn một lần bằng đẳng thức (8) và (9).

Để đảm bảo tính liên tục của tuyến đường, bổ sung N biến và hạn chế bổ sung (10).

Tổng chiều dài tuyến đường F, cần tối thiểu hóa, sẽ được viết dưới dạng sau:

Trong trường hợp của chúng tôi, các điều kiện này sẽ được viết dưới dạng sau:

2.4 Giải bài toán bằng phương pháp rẽ nhánh và giới hạn

1) Phân tích tập D.

Hãy tìm ước tính thấp hơn N. Để làm điều này, chúng tôi xác định ma trận khoảng cách tối thiểu theo hàng (1 trong đó khoảng cách tối thiểu trong một hàng).

Tương tự, chúng ta xác định ma trận khoảng cách tối thiểu dọc theo các cột.

Hãy chọn phương án ban đầu: . Khi đó giới hạn trên là:

Rõ ràng, ở đâu có nghĩa là sự chuyển đổi từ điểm đầu tiên sang điểm thứ j. Hãy xem xét các tập hợp con này theo thứ tự.

2) Phân tích tập con D 12.

3) Phân tích tập con D 13.

4) Phân tích tập con D 14.

5) Phân tích tập con D 15.

6) Sàng lọc các tập hợp con không có triển vọng.

Các tập con D 13 và D 15 không có triển vọng. Bởi vì , nhưng sau đó chúng ta sẽ xem xét thêm tập con D 14.

7) Phân tích tập hợp con D 142.

8) Phân tích tập hợp con D 143.

9) Phân tích tập hợp con D 145.

10) Sàng lọc các tập hợp con không có triển vọng

Tập hợp con D 143 không hứa hẹn. Bởi vì , nhưng sau đó chúng ta sẽ xem xét thêm tập con D 145.

11) Phân tích tập hợp con D 1452.

thuật toán mục tiêu ranh giới nhánh

12) Phân tích tập hợp con D 1453.

Giải pháp tối ưu: .

Như vậy, lộ trình của sinh viên: Tòa nhà thứ 12 - Tòa nhà Hành chính - Tòa nhà thứ 5 - Nhà Trắng - KRK Premier - Tòa nhà thứ 12.

Đăng trên http://www.allbest.ru/

Danh sách đã sử dụngvăn học

1. Abramov L.A., Kapustin V.F. Lập trình toán học. - L.: Nhà xuất bản Đại học bang Leningrad, 1981. -328 tr.

2. Alekseev O.G. Ứng dụng tích hợp các phương pháp tối ưu hóa rời rạc. - M.: Nauka, 1987. -294 tr.

3. Korbut AA, Finkelgein Yu.Yu. Lập trình rời rạc. M.: Khoa học. 1969. -240 giây

4. Kuznetsov Yu.N. v.v. Lập trình toán học: Hướng dẫn. - Tái bản lần thứ 2, có sửa đổi, bổ sung. - M.: trường sau đại học, 1980. -300 tr.

5. Papadimitriou H., Steiglitz K. Tối ưu hóa tổ hợp. Thuật toán và độ phức tạp. - M.: Mir, 1985. -213 tr.

Đăng trên Allbest.ru

...

Tài liệu tương tự

    Xây dựng và giải các bài toán tối ưu hóa rời rạc bằng phương pháp lập trình rời rạc và phương pháp nhánh và ràng buộc bằng ví dụ về bài toán người bán hàng du lịch cổ điển. Các giai đoạn xây dựng thuật toán nhánh và ràng buộc và tính hiệu quả của nó, xây dựng cây đồ thị.

    bài tập khóa học, được thêm vào ngày 08/11/2009

    Phát biểu của bài toán người bán hàng du lịch. Tìm lời giải tối ưu bằng phương pháp rẽ nhánh và ràng buộc. Nguyên tắc cơ bản của phương pháp này, thứ tự ứng dụng của nó. Sử dụng phương pháp giới hạn trên trong quy trình xây dựng cây các phương án khả thi.

    bài tập khóa học, được thêm vào ngày 01/10/2009

    Đặc điểm của phương pháp rẽ nhánh và ràng buộc là một trong những phương pháp giải phổ biến bài toán về số nguyên. Phân rã bài toán quy hoạch tuyến tính trong thuật toán nhánh và giới hạn. Phương pháp đồ thị đơn giản để giải các bài toán quy hoạch tuyến tính.

    bài tập khóa học, được thêm vào ngày 05/03/2012

    Mô phỏng chuyển động của kiến. Phương pháp nhánh và ràng buộc, hàng xóm gần nhất. Những ràng buộc áp đặt lên người đại diện trong công thức tiêu chuẩn của bài toán người bán hàng lưu động. Sử dụng biểu đồ hiển thị trong thuật toán kiến. Cấu trúc dữ liệu thuật toán Ant.

    luận văn, bổ sung 07/02/2013

    Nhánh thứ nhất và thứ hai và các phương thức ràng buộc. Tìm kiếm tối ưu và thụ động. Nhược điểm của phương pháp Newton. Phương pháp tiết diện vàng. Ví dụ về các hàm đơn thức. Năng động và lập trình tuyến tính. Phương pháp Jordan-Gauss. Giải quyết vấn đề nhân viên bán hàng du lịch.

    bài tập khóa học, được thêm vào ngày 20/07/2012

    Bản chất của lý thuyết đồ thị và mô hình mạng. Lựa chọn đường đi và chi phí tối ưu để di chuyển một nhân viên bán hàng du lịch bằng phương pháp chi nhánh và ràng buộc. Phát triển chương trình lựa chọn tuyến đường có lợi nhất đi qua các thành phố được chỉ định ít nhất một lần.

    bài tập khóa học, được thêm vào ngày 08/08/2013

    Tối ưu hóa lời giải bài toán bằng thuật toán ủ. Phân tích lý thuyết tối ưu hóa như một hàm mục tiêu. Phương pháp giảm độ dốc. Các biến và mô tả thuật toán ủ. Biểu diễn bài toán nhân viên bán hàng qua đồ thị. Giảm vấn đề thành các biến và giải quyết nó.

    bài tập khóa học, được thêm vào ngày 21/05/2015

    Phát biểu của một bài toán số nguyên tuyến tính. Phương pháp cắt mặt phẳng. Thuật toán phân số giải các bài toán hoàn toàn nguyên. Hiệu quả của việc cắt Gomori. So sánh khả năng tính toán của phương pháp mặt phẳng cắt và phương pháp nhánh và giới hạn.

    bài tập khóa học, được thêm vào ngày 25/11/2011

    Bài toán chiếc ba lô là một bài toán tối ưu tổ hợp. Vấn đề chất đồ, ba lô, ba lô. Tuyên bố và NP-đầy đủ của vấn đề. Phân loại các phương pháp giải bài toán ba lô. Lập trình năng động. Phương pháp phân nhánh và ràng buộc. Phân tích so sánh phương pháp.

    bài tập khóa học, được thêm vào ngày 18/01/2011

    Tìm giới hạn trên và giới hạn dưới của giá trị tối ưu trên miền phụ của các giải pháp khả thi. Các phương pháp và bài toán giải các bài toán quy hoạch phi tuyến. Viết và gỡ lỗi một chương trình. Xây dựng chương trình giải bài toán nhân viên bán hàng du lịch bằng thuật toán trực tiếp.