Phương pháp phân nhánh và ràng buộc. Phương pháp phân nhánh và ràng buộc của lập trình số nguyên. Các khái niệm cơ bản

Dưới đây là tình trạng của vấn đề và phần văn bản của giải pháp. Toàn bộ giải pháp là định dạng tài liệu trong kho lưu trữ, bạn có thể tải xuống. Một số ký tự có thể không xuất hiện trên trang, nhưng tài liệu văn bản mọi thứ đều được hiển thị. Có thể xem thêm các ví dụ về công việc trên EMMM

XÂY DỰNG VẤN ĐỀ

Công ty xuất bản phải hoàn thành công việc đánh máy trong vòng một tuần (số ngày m = 5) với sự giúp đỡ của công nhân thuộc n loại (cao, trung bình, dưới trung bình, thấp). Cần xác định số lượng nhân viên tối ưu theo hạng mục, đảm bảo hoàn thành công việc với mức chi tối thiểu quỹ tiền lương theo những hạn chế nhất định. Dữ liệu ban đầu được thể hiện trong bảng 1 và 2.

Bảng 1

ban 2

Vấn đề phải được giải quyết bằng phương pháp số nguyên lập trình tuyến tính trong Mathcad 2000/2001.

XÂY DỰNG MÔ HÌNH TOÁN HỌC
CÁC GIẢI PHÁPNHIỆM VỤ

Để tính toán số lượng nhân viên tối ưu, đảm bảo chi tiêu tối thiểu quỹ tiền lương, mô hình toán học lập trình tuyến tính số nguyên, vì số lượng nhân viên không thể là một giá trị phân số.

Giải pháp của vấn đề Lập trình số nguyên thực hiện theo hai giai đoạn.

Ở giai đoạn đầu tiên, bài toán quy hoạch tuyến tính được thực hiện mà không tính đến số nguyên.

Ở giai đoạn thứ hai nó được thực hiện quá trình từng bước thay thế các biến không nguyên bằng các giá trị nguyên trên hoặc dưới gần nhất.

Đầu tiên, bài toán được giải mà không tính đến điều kiện nguyên.

Hàm mục tiêu được xác định theo công thức:

Ở đâu Q- quỹ lương chung để thực hiện công việc;

x 1 , x 2 , …, xn- số lượng nhân viên theo loại;

N - số lượng loại công nhân;

c 1 , c 2 ,…, c n- ban ngày thuế suất một nhân viên theo hạng mục;

tôi- số ngày làm việc mỗi tuần, tôi = 5.

Hàm mục tiêu có thể được viết dưới dạng vector:

Khi giải quyết vấn đề cần thực hiện các yêu cầu sau: những hạn chế sau. Giới hạn trên

x ≤ d (1)

chỉ định số lượng nhân viên tối đa theo danh mục, trong đó d là vectơ xác định số lượng nhân viên theo danh mục.

Trong giới hạn

Cần lưu ý rằng tổng số nhân viên không được vượt quá kmmax.

Trong giới hạn từ bên dưới

R× x ≥P(3)

nó phản ánh rằng tất cả các công nhân cùng nhau phải hoàn thành một khối lượng công việc nhất định R.

BẰNG hạn chế cuối cùngđiều kiện không âm của vectơ biến được viết

x≥0 (4)

Mô hình toán học giải bài toán không xét đến điều kiện nguyên bao gồm các biểu thức sau:

x ≤ d

R× x ≥P,

x ≥ 0 .

Mô hình lập trình số nguyên phải bao gồm các biểu thức (5) cũng như hạn chế bổ sung, với sự trợ giúp của các biến không nguyên Xđược thay thế bằng các giá trị nguyên. Các biểu thức mô hình cụ thể với các biến số nguyên sẽ được thảo luận trong tiểu mục tiếp theo.

GIẢI QUYẾT VẤN ĐỀ TỐI ƯU HÓA TRONGMATHCAD

Dữ liệu nguồn cho ví dụ được đưa ra trong bảng. 1 và 2.

Để giải quyết vấn đề, hãy sử dụng gói Mathcad với chức năng Thu nhỏ. Chức năng này xác định vectơ giải pháp vấn đề:

X:= Giảm thiểu ( Q, x),

Ở đâu Q- sự biểu lộ hàm mục tiêu, xác định quỹ lương tối thiểu, X- vectơ của các biến.

Đầu tiên, bài toán được giải mà không tính đến điều kiện nguyên. Giải pháp này được đưa ra trong Phụ lục 1. Dòng đầu tiên chứa giá trị ban đầu bằng 0 của vectơ X và hàm mục tiêu Q(x) . Sau từ Cho và trước hàm Thu nhỏ, các hạn chế sẽ được biểu thị. Kết quả là đã thu được số tối ưu không nguyên theo danh mục:

X =

có quỹ lương Q= 135 cu. đ.

Từ quyết định này xác định vị trí nghiệm số nguyên phương pháp nhánh và ràng buộc.

Đầu tiên, lời giải thu được sẽ phân tích giá trị phân số x 4 =
= 1.143. Bạn có thể đặt hai giá trị nguyên cho nó: x 4 = 1 và x 4 = 2. Việc xây dựng cây quyết định bắt đầu (Phụ lục 2). Nút 0 ban đầu được đặt sang một bên trên cây quyết định. Sau đó, nó được kết nối bởi nút đầu tiên x4 và từ nút này, hai nhánh được rút ra tương ứng với các ràng buộc: x4 = 1 và x4 = 2.

Đối với nhánh có ràng buộc x 4 = 1, bài toán quy hoạch tuyến tính nêu ở Phụ lục 1 được giải có xét đến ràng buộc này.

Kết quả là đã có được giải pháp cho vấn đề này. Biến x 1 trở thành số nguyên, nhưng biến x 2 trở thành phân số x 2 = 0,9.

Để tiếp tục nhánh, một nút x 3 và một nhánh x 3 = 1 được tạo. Bài toán quy hoạch tuyến tính lại được thực hiện với cả ba ràng buộc: x 4 = 1, x 2 = 1, x 3 = 1. Với những ràng buộc này, vấn đề đã có lời giải x T =
= (1,938 1 1 1).

Để tiếp tục nhánh, tạo một nút x 1 và một nhánh x 1 = 2. Bài toán quy hoạch tuyến tính được thực hiện lại với cả ba ràng buộc: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2 Với các ràng buộc trên thì bài toán có nghiệm x T = = (2 1 1 1).

Quá trình xây dựng cây giải pháp và thực hiện bài toán quy hoạch tuyến tính được lặp lại cho đến khi tất cả các nhánh được xây dựng.

Phụ lục 2 cung cấp cây đầy đủ các nghiệm số nguyên, từ đó suy ra bài toán có 4 nghiệm hữu hiệu.

Phương án tốt nhất được chọn từ các phương án hiệu quả và được chấp nhận là nghiệm nguyên tối ưu của toàn bộ bài toán có giá trị nhỏ nhất Q(x) . Trong trường hợp của chúng tôi, chúng tôi có hai giải pháp số nguyên tối ưu

Q(X) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Do đó, tổ chức xuất bản phải thuê hai công nhân có trình độ cao để đánh máy văn bản, một công nhân hạng trung, một công nhân thuộc loại trung bình và một công nhân thuộc loại thấp. Cũng có thể áp dụng một phương án tương đương khác để thu hút người lao động: một công nhân hạng cao, một công nhân hạng trung, hai công nhân hạng dưới trung bình và hai công nhân hạng thấp. Trong cả hai lựa chọn, chi phí sẽ tối thiểu và lên tới 140 den. các đơn vị

Tải xuống giải pháp cho vấn đề:

Nếu quá trình tải xuống tệp không bắt đầu sau 10 giây, hãy nhấp vào

Giới thiệu

Khi xem xét một số bài toán, cần phải tính đến yêu cầu các biến được sử dụng phải là số nguyên. Các phương pháp giải bài toán quy hoạch tuyến tính không đảm bảo tính toàn vẹn của lời giải.

Đôi khi các bài toán quy hoạch tuyến tính số nguyên được giải gần đúng. Để làm điều này, hãy giải bài toán mà không tính đến các giá trị nguyên của các biến, sau đó trong giải pháp tối ưu thu được, kết quả được làm tròn đến các giá trị nguyên gần nhất. Việc sử dụng các giải pháp như vậy được cho phép trong trường hợp giá trị của các biến đủ lớn và có thể bỏ qua lỗi làm tròn. Nếu giá trị của các biến nhỏ thì việc làm tròn có thể dẫn đến sự khác biệt đáng kể so với giải pháp tối ưu.

Một trong những phương pháp được sử dụng rộng rãi để giải các bài toán số nguyên là phương pháp rẽ nhánh và giới hạn, được Land và Doig đề xuất lần đầu tiên vào năm 1960.

lập trình tuyến tính ranh giới nhánh

Phương thức nhánh và ràng buộc

Thuật toán nhánh và giới hạn liên quan đến việc phân tách bài toán quy hoạch tuyến tính (LPP) ban đầu thành một chuỗi các bài toán chứa các hạn chế bổ sung đối với các biến, sau đó được tối ưu hóa.

1. Quá trình bắt đầu bằng việc giải bài toán bằng cách sử dụng một đơn hình hoặc phương pháp đồ họa mà không tính đến yêu cầu về các biến số nguyên. Vấn đề này được gọi là ZLP-0. Nếu tất cả các biến của phương án tối ưu đều là số nguyên thì phương án này cũng tối ưu cho các bài toán lập trình số nguyên.

2. Nếu biến nào đó chưa nhận được giá trị nguyên thì một nhánh sẽ được tạo thành hai nhiệm vụ mới ZLP-1, ZLP-2. Một trong những vấn đề ZLP-1 là vấn đề ZLP-0, được bổ sung bởi ràng buộc trong đó - Toàn bộ phần những con số. Thứ hai được hình thành bằng cách thêm một ràng buộc vào bài toán ZLP-0. Cần lưu ý rằng việc lựa chọn một biến số nguyên có thể được xác định tùy ý như sau:

chỉ số tăng dần hoặc giảm dần;

biến thể hiện một quyết định quan trọng được thực hiện trong khuôn khổ một vấn đề nhất định;

hệ số trong hàm mục tiêu của biến này vượt trội đáng kể so với tất cả các biến khác.

3. Nhiệm vụ của ZLP-1 và ZLP-2 được giải quyết độc lập. Một nhánh kết thúc nếu vùng giải pháp khả thi trống hoặc giải pháp tối ưu hoàn toàn số nguyên. Mặt khác, cần phải phân nhánh từ điểm 2, chỉ định số nhiệm vụ ZLP sau theo thứ tự tự nhiên là ZLP-3, ZLP-4.

Quá trình giải có thể được biểu diễn dưới dạng cây trong đó đỉnh ZLP-0 tương ứng với phương án ban đầu để giải bài toán và mỗi đỉnh được nối với nó bằng một nhánh tương ứng với phương án tối ưu cho bài toán tiếp theo.

Hãy xem xét ví dụ sau. Tối đa hóa hàm mục tiêu

dưới những hạn chế

Hãy sử dụng phương pháp đồ họa để giải bài toán quy hoạch tuyến tính.

1. Hãy quyết định vấn đề ban đầu mà không tính đến yêu cầu của các biến số nguyên.

Hãy để chúng tôi biểu thị vấn đề tuyến tính này lập trình ZLP-0.

Trong Hình 1.1, đa giác của các giải pháp cho vấn đề này được làm nổi bật bằng cách tô bóng. Đạt giá trị lớn nhất tại điểm Lời giải không phải là số nguyên.

Bước tiếp theo của phương thức rẽ nhánh và giới hạn là phân nhánh dọc theo một trong các biến số nguyên có giá trị phân số, ví dụ: Để thực hiện điều này, chúng tôi thêm hai hạn chế mới cho bài toán ZLP-0 và Những hạn chế này loại bỏ khoảng = trong đó không có giá trị nguyên. Do đó, trong quá trình phân nhánh, hai tác vụ mới ZLP-1 và ZLP-2 được tạo.

Hình 1.1 Giải bài toán ZLP-0

2. Giải bài toán ZLP-1 bằng đồ thị.

Hình 1.2 thể hiện miền khả thi của bài toán ZLP-1. Giá trị tối đa đạt được tại điểm. Giải pháp cho vấn đề là không nguyên.

Hình 1.2 Giải bài toán ZLP-1

3. Hãy giải bài toán ZLP-2 bằng đồ họa.

TRONG trong trường hợp này tập phương án khả thi rỗng (Hình 1.2). Hệ thống các ràng buộc không nhất quán và vấn đề ZLP-2 có thể được loại trừ khỏi việc xem xét thêm.

Hình 1.3 Giải bài toán ZLP-2

Bây giờ chúng ta hãy tiếp tục nghiên cứu bài toán ZLP-1, vì giá trị này không phải là số nguyên. Hãy tạo thêm một nhánh nữa bằng cách đưa ra các hạn chế và. Kết quả là chúng ta thu được hai bài toán mới ZLP-3 và ZLP-4.

Sự phát triển của phương pháp này, được gọi là phương pháp nhánh và giới hạn, bắt đầu từ công trình của Land và Doig (1960). Đúng hơn, đây thậm chí không phải là một phương pháp, mà là một khái niệm hoặc vỏ thủ tục, trên cơ sở đó họ bắt đầu phát triển các thuật toán để giải các bài toán số nguyên có nhiều bản chất khác nhau. Giá trị của ý tưởng được đề xuất trở nên đặc biệt đáng chú ý sau khi xuất hiện thuật toán chính xác đầu tiên để giải bài toán nhân viên bán hàng du lịch, được xây dựng theo sơ đồ nhánh và giới hạn (Little et al., 1963). Phương pháp này có thể áp dụng cho cả bài toán số nguyên đầy đủ và số nguyên một phần.

Bản chất của ý tưởng này tương tự như câu chuyện cười nổi tiếng về việc bắt một con sư tử trên sa mạc: chúng ta chia sa mạc làm đôi; nếu không có con sư tử nào trong nửa đầu, chúng ta tìm kiếm nó trong nửa thứ hai, chúng ta chia làm đôi, v.v. Không giống như con sư tử, con tối ưu không di chuyển và theo nghĩa này, nhiệm vụ của chúng ta dễ dàng hơn.

Phương pháp này bao gồm việc xây dựng một cây các bài toán, gốc của nó là bài toán ban đầu, có thể không có điều kiện nguyên (IC). Các bài toán cơ bản được tạo ra bởi các bài toán cao hơn theo cách mà các tập có thể chấp nhận được (AS) của chúng là các tập con rời rạc của DS của bài toán nằm trên. Sự phát triển của cây xảy ra do các cành có triển vọng. Triển vọng được xác định bởi tiêu chí đánh giá nhiệm vụ thiết bị đầu cuối chi nhánh V. Và ghiZ. Cấp V. là giá trị của tiêu chí, chắc chắn không tệ hơn giá trị tối ưu và Z– giá trị của tiêu chí của bài toán ban đầu đạt được trong quá trình giải (một giá trị rõ ràng là kém hơn giá trị tối ưu có thể được lấy làm giá trị ban đầu). Điều này có nghĩa là bài toán sẽ chỉ mang tính tổng quát nếu ước lượng của nó tốt hơn bản ghi. Trong trường hợp này, cấp độ của nhiệm vụ không thành vấn đề.

Hãy xem xét phương pháp được áp dụng cho bài toán số nguyên tuyến tính. Mặc dù không có hạn chế nào về số lượng nhiệm vụ được tạo ra trực tiếp bởi một nhiệm vụ đầy hứa hẹn, nhưng theo quy luật, các thuật toán sử dụng cách chia thành hai nhiệm vụ, tức là xây dựng một cây nhị phân (Hình 7.5). Trong trường hợp này, đối với các tập hợp số nguyên, các quan hệ sau giữ nguyên:

VỀ rõ ràng là nếu, ví dụ, V. 22 sẽ tệ hơn kỷ lục hoặc D 22 =, nhánh bên phải gãy đi (họ cũng nói là đã bị thăm dò). Nếu việc đánh giá V. 22 sẽ tốt hơn Z, sự phân nhánh xảy ra: nhiều D 22 được chia thành 2 tập con. Giải pháp sẽ hoàn tất khi tất cả các nhánh sẽ bị thăm dò.

Loại đánh giá phụ thuộc vào hướng của tiêu chí: khi tối đa hóa, ước tính trên được sử dụng, khi giảm thiểu, ước tính thấp hơn được sử dụng. Phần trình bày tiếp theo của phương pháp sẽ liên quan đến bài toán lớn nhất.

Để triển khai thuật toán phân nhánh và giới hạn, hai câu hỏi cơ bản cần được giải quyết:

Cách chia một tập hợp có triển vọng thành các tập hợp con;

Cách xác định ước tính trên của một tiêu chí trên tập hợp đang được xem xét.

Câu trả lời cho chúng phụ thuộc vào loại vấn đề (số nguyên một phần hoặc toàn bộ, có thuộc tính đặc biệt hay không, với các biến Boolean hoặc không Boolean). Trường hợp tổng quát được xem xét dưới đây.

Hãy biết phạm vi của các giá trị có thể j biến thứ

0  X j  d j ,

mà trong lời giải tối ưu liên tục hóa ra là không nguyên và bằng x j * . Khi đó giá trị nguyên của biến này có thể đạt được trong khoảng 0  X j 
, hoặc trong khoảng
+1 X j  d j, Ở đâu
- Toàn bộ phần (Hình 7.6).

E sau đó tương ứng với một phân vùng của một tập hợp liên tục D N thành hai tập con rời nhau D 1 N Và D 2 N, sự kết hợp của nó không bằng D N. Đồng thời, việc phân chia tập hợp số nguyên như vậy thỏa mãn quan hệ (7.9). Trong trường hợp này, các tập hợp số nguyên, cả tập gốc và tập được tạo, đều được bao gồm trong các tập liên tục tương ứng. Do đó, việc tìm kiếm nghiệm số nguyên trên tập liên tục sẽ cho kết quả giống như trên tập số nguyên. Dễ dàng thấy rằng việc chọn các khoảng con ở trên theo một biến sẽ dẫn đến việc chia tập hợp ban đầu thành hai tập con cho số lượng biến bất kỳ.

Bây giờ chúng ta hãy chuyển sang câu hỏi thứ hai. Vì tập hợp số nguyên là tập con của tập hợp liên tục tương ứng, giá trị tối ưu tiêu chí trên một tập hợp liên tục sẽ luôn không nhỏ hơn trên một tập hợp số nguyên. Vì vậy, như một giới hạn trên V. bạn có thể lấy giá trị tối ưu của tiêu chí L * nhiệm vụ liên tục.

Việc lựa chọn giá trị bản ghi ban đầu phụ thuộc vào tình huống:

nếu biết giá trị nguyên nào thì bản ghi được lấy bằng tiêu chí trong quyết định này;

nếu tất cả các hệ số của tiêu chí đều dương, chúng ta có thể lấy giá trị rỗng ghi;

trong các trường hợp khác cho giá trị ban đầu hồ sơ được thực hiện - M, Ở đâu M- số lượng tối đa có thể được biểu diễn trong máy tính.

Khi phân vùng tiến triển, các tác vụ được tạo sẽ được hình thành và được đặt trong danh sach cong viec. Danh sách ban đầu chỉ chứa một nhiệm vụ - nhiệm vụ ban đầu không có điều kiện nguyên. Và trong tương lai danh sách sẽ chỉ chứa các nhiệm vụ liên tục.

Do đó, thuật toán cơ bản thực hiện phương thức nhánh và ràng buộc bao gồm các bước sau.

Thuật toán đã cho là cơ bản vì nó không bao gồm các quy tắc rõ ràng để chọn một nhiệm vụ từ danh sách và một biến phân nhánh. Đối với các bài toán về số nguyên từng phần, các biến liên tục bị loại trừ khi chọn một biến thành nhánh.

Ví dụ 7.3 . Hãy áp dụng thuật toán rẽ nhánh và ràng buộc cho bài toán

L= 9x 1 + 5x 2  tối đa;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , trọn.

VỀ Bỏ điều kiện số, chúng ta thu được một nhiệm vụ liên tục, chúng ta đặt nhiệm vụ này vào danh sách các nhiệm vụ. Vì các hệ số tiêu chí là dương nên giá trị ban đầu của bản ghi được lấy bằng 0. Chúng tôi lấy một vấn đề từ danh sách và giải quyết nó. Ta thu được lời giải tối ưu tại đỉnh A (Hình 7.7): x 1 * =4,72; x 2 * = 2,19. Chúng tôi phân nhánh theo biến x 1 . Thêm một ràng buộc vào một vấn đề đã được giải quyết x 1 4, ta lập bài toán 2, và phép cộng x 1 5 đưa ra bài toán 3. Các tập bài toán mới có thể chấp nhận được được trình bày trên Hình 2. 7.7. Chúng tôi đặt những nhiệm vụ này vào danh sách nhiệm vụ. Lời giải của bài toán 2 đạt được ở điểm B và bài toán 3 ở điểm C. Toàn bộ quá trình giải bài toán ban đầu được trình bày dưới dạng cây quyết định trong Hình 2. 7.10. Thứ tự giải các bài toán trong danh sách được phản ánh qua bộ đếm vòng lặp k. Ở lần lặp thứ 3 (nhiệm vụ 4), thu được nghiệm nguyên với giá trị tiêu chí là 41 (điểm D trong Hình 7.8). Do đó hồ sơ thay đổi: Z= 41. Bài toán 6 có nghiệm không nguyên (đỉnh E trong Hình 7.9), bài toán 8 có nghiệm nguyên tại điểm F. Kết quả là sau lần lặp thứ 7, bản ghi trở thành 50.

VỀ Bài toán thép không có lời giải khả thi, tức là danh sách bài toán đã cạn kiệt và do đó, ta khẳng định đã thu được lời giải tối ưu của bài toán ban đầu, ngang bằng với lời giải của bài toán liên tục 8.

Từ cây quyết định trên có thể thấy rằng số lượng nhiệm vụ trong danh sách có thể nhỏ hơn nếu các nhiệm vụ được giải quyết theo một thứ tự khác. Thật vậy, nếu vấn đề của nhánh bên phải với bản ghi được giải quyết trước tiên Z= 50 thì sau khi giải Bài toán 2 sẽ không có sự phân nhánh vì ước lượng trên sẽ thấp hơn bản ghi ( V=L * =45,17<50).

E Câu hỏi nảy sinh một cách tự nhiên: làm thế nào việc chọn một biến khác để phân nhánh có thể ảnh hưởng đến số lượng nhiệm vụ và cây quyết định? Vì vậy, trong ví dụ của chúng ta, nếu sau lần lặp đầu tiên chúng ta phân nhánh theo biến x 2, thì chúng ta sẽ có được cây như trong Hình. 7.11. Nó chứa nhiều hơn 2 nhiệm vụ so với trong Hình. 7.10. Tất nhiên, mọi chuyện cũng có thể khác nếu các vấn đề được giải quyết theo một thứ tự khác.

Vì vậy, số lượng nhiệm vụ cần giải quyết phụ thuộc đáng kể vào việc lựa chọn nhiệm vụ từ danh sách và biến phân nhánh.

Từ thuật toán và ví dụ đã cho, có thể thấy rằng nhánh bị chấm dứt vì một trong ba lý do:

tính không thể giải quyết được của vấn đề;

bài toán có nghiệm nguyên;

ước tính trên không nhiều hơn một kỷ lục.

Bây giờ chúng ta sẽ đưa ra một số nhận xét liên quan đến phương thức nhánh và ràng buộc. Như đã lưu ý, thuật toán cơ bản không chỉ định các quy tắc để chọn tác vụ và biến. Hầu hết việc triển khai phần mềm của phương pháp này đều sử dụng các quy tắc dựa trên đánh giá heuristic về triển vọng của các nhiệm vụ và các biến. Một số gói, ví dụ: “LP trong ACS”, cung cấp một số tùy chọn để quản lý quy trình giải pháp: từ tự động đến thủ công, trong đó người dùng có thể tự lựa chọn cả nhiệm vụ và biến. Ngoài ra, các thuật toán dựa trên phương pháp rẽ nhánh và giới hạn có thể khác nhau đáng kể do đặc điểm của loại bài toán. Ví dụ, đối với bài toán người bán hàng du lịch, việc xác định ước tính được đơn giản hóa rất nhiều (không cần phải giải bài toán tuyến tính liên tục).

Phương pháp nhánh và ràng buộc có ưu điểm hơn phương pháp cắt:

việc tích lũy sai số ít đáng kể hơn vì lời giải đi theo các nhánh khác nhau;

khi quá trình giải quyết buộc phải dừng lại, có khả năng cao là thu được kết quả nguyên nhưng không thiết lập được tính tối ưu của nó;

Khi giải các bài toán liên tục, kích thước của bảng đơn không tăng.

Nhược điểm của phương pháp nhánh và ràng buộc:

Không thể ước tính được số lượng vấn đề sẽ phải giải quyết. Giá trị ban đầu của bản ghi càng gần từ bên dưới và ước tính tiêu chí của bài toán từ trên đến giá trị tối ưu mong muốn của tiêu chí thì cây quyết định sẽ có càng ít đỉnh và do đó càng tiêu tốn ít tài nguyên hơn. Tuy nhiên, việc đánh giá quá cao bản ghi ban đầu có thể dẫn đến vấn đề không thể giải quyết được, điều này cần luôn được ghi nhớ.

Không có dấu hiệu tối ưu. Giải pháp tối ưu có thể đạt được từ rất lâu trước khi thuật toán dừng lại, nhưng trong trường hợp tổng quát thì điều này không thể được phát hiện. Sự tối ưu chỉ được thiết lập khi danh sách nhiệm vụ đã cạn kiệt.

Rõ ràng là hiệu quả của phương pháp tăng lên khi giảm phạm vi giá trị biến và số lượng biến không nguyên trong việc giải bài toán liên tục đầu tiên.

Xét bài toán quy hoạch tuyến tính số nguyên sau đây. Tối đa hóa dưới những ràng buộc

Trong Hình 1, không gian của các lời giải khả thi cho bài toán quy hoạch tuyến tính nguyên được biểu diễn bằng các điểm. Bài toán quy hoạch tuyến tính ban đầu tương ứng (chúng tôi ký hiệu là LP0) thu được bằng cách loại bỏ điều kiện nguyên. Lời giải tối ưu của nó sẽ là =3,75, =1,25, z=23,75.

Hình.1.

Do giải pháp tối ưu cho bài toán LP0 không thỏa mãn điều kiện nguyên, nên phương pháp nhánh và ràng buộc sẽ sửa đổi không gian giải pháp của bài toán quy hoạch tuyến tính để cuối cùng thu được giải pháp tối ưu cho bài toán quy hoạch tuyến tính số nguyên. Để thực hiện việc này, trước tiên hãy chọn một trong các biến số nguyên, giá trị của biến này trong lời giải tối ưu của bài toán LP0 không phải là số nguyên. Ví dụ: chọn (=3,75), ta nhận thấy diện tích là 3? ?4 trong không gian của các nghiệm có thể chấp nhận được đối với bài toán LP0 không chứa các giá trị nguyên của biến và do đó, có thể bị loại khỏi việc coi là không hứa hẹn. Điều này tương đương với việc thay thế bài toán ban đầu LP0 bằng hai bài toán quy hoạch tuyến tính mới LP1 và LP2, được định nghĩa như sau:

Không gian nghiệm chấp nhận được LP1 = không gian nghiệm chấp nhận được LP0 + (), không gian nghiệm nghiệm chấp nhận được LP2 = không gian nghiệm nghiệm chấp nhận được LP0 + ().

Hình 2 cho thấy không gian của các lời giải có thể chấp nhận được đối với các bài toán LP1 VÀ LP2. Cả hai không gian đều chứa tất cả các lời giải khả thi cho bài toán CLP ban đầu. Điều này có nghĩa là bài toán LP1 và LP2 “sẽ không làm mất” lời giải của bài toán LP0 ban đầu.

Hình 2.

Nếu chúng ta tiếp tục loại trừ một cách thông minh khỏi các khu vực xem xét không chứa nghiệm số nguyên (chẳng hạn như) bằng cách đưa ra các hạn chế thích hợp, thì cuối cùng chúng ta sẽ thu được một bài toán quy hoạch tuyến tính có nghiệm tối ưu thỏa mãn các yêu cầu về số nguyên. Nói cách khác, chúng ta sẽ giải bài toán CLP bằng cách giải một dãy các bài toán quy hoạch tuyến tính liên tục.

Các hạn chế mới loại trừ lẫn nhau, vì vậy các bài toán LP1 và LP2 phải được coi là các bài toán quy hoạch tuyến tính độc lập, như trong Hình 3. Sự phân đôi của các bài toán LP là cơ sở của khái niệm phân nhánh trong phương pháp nhánh và ràng buộc. Trong trường hợp này nó được gọi là biến nhánh.

Hình 3.

Lời giải tối ưu cho bài toán CLP nằm trong không gian các lời giải khả thi ở LP1 hoặc LP2. Do đó, cả hai vấn đề phụ đều phải được giải quyết. Đầu tiên chúng ta chọn bài toán LP1 (lựa chọn là tùy ý), bài toán này có thêm một ràng buộc nào nữa không?3.

Tối đa hóa dưới những ràng buộc

Lời giải tối ưu của bài toán LP1 là, và. Lời giải tối ưu của bài toán LP1 thỏa mãn yêu cầu các biến và đều là số nguyên. Trong trường hợp này, họ nói rằng nhiệm vụ đã được thăm dò. Điều này có nghĩa là bài toán LP1 không còn được thăm dò nữa vì nó không thể chứa giải pháp tốt hơn cho bài toán CLP.

Trong tình huống này, chúng ta không thể đánh giá chất lượng của nghiệm số nguyên thu được từ việc xem xét bài toán LP1, vì việc giải bài toán LP2 có thể dẫn đến một nghiệm số nguyên tốt hơn (với nghiệm lớn hơn trong hàm mục tiêu z). Hiện tại, chúng ta chỉ có thể nói rằng giá trị này là giới hạn dưới của giá trị tối ưu (tối đa) của hàm mục tiêu của bài toán CLP ban đầu. Điều này có nghĩa là bất kỳ bài toán con nào chưa được xem xét mà không thể dẫn đến nghiệm số nguyên có giá trị lớn của hàm mục tiêu phải được loại trừ vì không hứa hẹn. Nếu một bài toán con chưa được xem xét có thể dẫn đến một nghiệm số nguyên tốt hơn thì giới hạn dưới phải được điều chỉnh một cách thích hợp.

Ở giá trị của giới hạn dưới, chúng tôi kiểm tra LP2. Vì trong bài toán LP0, giá trị tối ưu của hàm mục tiêu là 23,75 và trọng số của các hệ số của nó là số nguyên nên không thể có được nghiệm số nguyên cho bài toán LP2 tốt hơn nghiệm hiện tại. Do đó, chúng tôi loại bỏ nhiệm vụ con LP2 và coi nó đã được thăm dò.

Việc triển khai phương pháp nhánh và giới hạn đã hoàn tất vì cả hai nhiệm vụ phụ LP1 và LP2 đều đã được thử nghiệm. Vì vậy, ta kết luận rằng lời giải tối ưu cho bài toán CLP là lời giải tương ứng với giới hạn dưới, cụ thể là và.

Nếu chúng ta chọn một biến làm biến phân nhánh thì độ phân nhánh và tốc độ tìm ra giải pháp tối ưu sẽ khác Hình 4.

Hình 4. Cây quyết định nhánh