Giải bài toán lập trình số nguyên: phương pháp và ví dụ

Phương trình số nguyên là các phương trình đại số có hai hoặc nhiều biến chưa biết và hệ số nguyên. Các nghiệm của phương trình như vậy đều là các tập hợp giá trị nguyên (đôi khi tự nhiên hoặc hữu tỉ) của các biến chưa biết thỏa mãn phương trình này. Những phương trình như vậy còn được gọi là diophantin, để vinh danh nhà toán học Hy Lạp cổ đại, người đã nghiên cứu một số loại phương trình như vậy trước thời đại chúng ta.

Chúng ta có công với nhà toán học người Pháp trong việc phát biểu các bài toán Diophantine hiện đại. Chính ông là người đã đặt ra vấn đề giải phương trình bất định chỉ bằng số nguyên trước các nhà toán học châu Âu. Phương trình nổi tiếng nhất về số nguyên là định lý cuối cùng của Fermat: phương trình

không có nghiệm hữu tỉ khác 0 cho mọi số tự nhiên n > 2.

Mối quan tâm về mặt lý thuyết đối với các phương trình số nguyên là khá lớn, vì các phương trình này có liên quan chặt chẽ đến nhiều bài toán trong lý thuyết số.

Năm 1970, nhà toán học Leningrad Yury Vladimirovich Matiyasevich đã chứng minh rằng một phương pháp tổng quát cho phép giải phương trình Diophantine tùy ý bằng số nguyên với số bước hữu hạn là không tồn tại và không thể tồn tại. Vì vậy nó tuân theo cho các loại khác nhau phương trình, chọn phương pháp giải của riêng bạn.

Khi giải phương trình số nguyên và số tự nhiên Có thể phân biệt đại khái các phương pháp sau:

cách sắp xếp các lựa chọn;

ứng dụng thuật toán Euclide;

biểu diễn các số dưới dạng phân số tiếp tục (tiếp theo);

nhân tố hóa;

giải phương trình số nguyên dưới dạng bình phương (hoặc phương trình khác) đối với bất kỳ biến nào;

phương pháp dư lượng;

phương pháp giảm vô hạn.

Vấn đề với giải pháp

1. Giải phương trình x 2 – xy – 2y 2 = 7 dưới dạng số nguyên.

Hãy viết phương trình dưới dạng (x – 2y)(x + y) = 7.

Vì x, y là các số nguyên nên ta tìm nghiệm của phương trình ban đầu là nghiệm của bốn hệ sau:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Giải các hệ này, ta thu được nghiệm của phương trình: (3; –2), (5; 2), (–3; 2) và (–5; –2).

Trả lời: (3; –2), (5; 2), (–3; 2), (–5; –2).

a) 20x + 12y = 2013;

b) 5x + 7y = 19;

c) 201x – 1999y = 12.

a) Vì với mọi giá trị nguyên của x và y bên trái phương trình chia hết cho 2, vế phải là số lẻ thì phương trình không có nghiệm nguyên.

Trả lời: không có giải pháp.

b) Trước tiên hãy chọn một số giải pháp cụ thể. TRONG trong trường hợp này, thật đơn giản, ví dụ,

x 0 = 1, y 0 = 2.

5x 0 + 7y 0 = 19,

5(x – x 0) + 7(y – y 0) = 0,

5(x – x 0) = –7(y – y 0).

Vì số 5 và 7 là số nguyên tố cùng nhau nên

x – x 0 = 7k, y – y 0 = –5k.

Vì vậy, giải pháp chung là:

x = 1 + 7k, y = 2 – 5k,

trong đó k là số nguyên tùy ý.

Trả lời: (1+7k; 2–5k), trong đó k là số nguyên.

c) Việc tìm ra giải pháp cụ thể bằng lựa chọn trong trường hợp này là khá khó khăn. Hãy sử dụng thuật toán Euclide cho các số 1999 và 201:

GCD(1999, 201) = GCD(201, 190) = GCD(190, 11) = GCD(11, 3) = GCD(3, 2) = GCD(2, 1) = 1.

Hãy viết quá trình này theo thứ tự ngược lại:

1 = 2 – 1 = 2 – (3 – 2) = 2 2 – 3 = 2 (11 – 3 3) – 3 = 2 11 – 7 3 = 2 11 – 7(190 – 11 17) =

121 11 – 7 190 = 121(201 – 190) – 7 190 = 121 201 – 128 190 =

121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

Điều này có nghĩa là cặp số (1273, 128) là nghiệm của phương trình 201x – 1999y = 1. Khi đó cặp số

x 0 = 1273 12 = 15276, y 0 = 128 12 = 1536

là nghiệm của phương trình 201x – 1999y = 12.

Nghiệm tổng quát của phương trình này sẽ được viết dưới dạng

x = 15276 + 1999k, y = 1536 + 201k, trong đó k là số nguyên,

hoặc, sau khi thiết kế lại (chúng tôi sử dụng 15276 = 1283 + 7 1999, 1536 = 129 + 7 201),

x = 1283 + 1999n, y = 129 + 201n, trong đó n là số nguyên.

Trả lời: (1283+1999n, 129+201n), trong đó n là số nguyên.

3. Giải phương trình số nguyên:

a) x 3 + y 3 = 3333333;

b) x 3 + y 3 = 4(x 2 y + xy 2 + 1).

a) Vì x 3 và y 3 khi chia cho 9 chỉ có số dư 0, 1 và 8 (xem bảng ở phần mục) nên x 3 + y 3 chỉ có số dư 0, 1, 2, 7 và 8. Nhưng số 3333333 khi chia cho 9 thì dư 3. Do đó phương trình ban đầu không có nghiệm nguyên.

b) Hãy viết lại phương trình ban đầu dưới dạng (x + y) 3 = 7(x 2 y + xy 2) + 4. Vì lập phương của các số nguyên khi chia cho 7 sẽ có số dư là 0, 1 và 6 chứ không phải 4, nên phương trình không có nghiệm là số nguyên.

Trả lời: Không có nghiệm số nguyên.

a) Trong số nguyên tố phương trình x 2 – 7x – 144 = y 2 – 25y;

b) trong số nguyên phương trình x + y = x 2 – xy + y 2.

a) Giải phương trình này dưới dạng phương trình bậc hai theo biến y. Chúng tôi nhận được

y = x + 9 hoặc y = 16 – x.

Vì với x lẻ thì số x + 9 là số chẵn nên cặp duy nhất số nguyên tố, thỏa mãn đẳng thức thứ nhất, là (2; 11).

Vì x, y đơn giản nên từ đẳng thức y = 16 – x ta có

2 x 16,2 Tại 16.

Tìm kiếm qua các phương án, ta tìm được các nghiệm còn lại: (3; 13), (5; 11), (11; 5), (13; 3).

Đáp án: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

b) Coi phương trình này là phương trình bậc hai của x:

x 2 – (y + 1)x + y 2 – y = 0.

Phân biệt của phương trình này là –3y 2 + 6y + 1. Nó chỉ dương với các giá trị sau của y: 0, 1, 2. Đối với mỗi giá trị này, từ phương trình ban đầu, chúng ta thu được phương trình bậc hai cho x , điều này có thể dễ dàng giải quyết được.

Trả lời: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Có không số lượng vô hạn bộ ba số nguyên x, y, z sao cho x 2 + y 2 + z 2 = x 3 + y 3 + z 3?

Hãy thử chọn bộ ba trong đó y = –z. Khi đó y 3 và z 3 sẽ luôn triệt tiêu lẫn nhau và phương trình của chúng ta sẽ có dạng

x 2 + 2y 2 = x 3

hay nói cách khác,

x 2 (x–1) = 2y 2 .

Để một cặp số nguyên (x; y) thỏa mãn điều kiện này, số x–1 phải gấp đôi bình phương của số nguyên đó là đủ. Có vô số số như vậy, tức là chúng đều có dạng 2n 2 +1. Thay số này vào x 2 (x–1) = 2y 2, sau những phép biến đổi đơn giản, chúng ta thu được:

y = xn = n(2n 2 +1) = 2n 3 +n.

Tất cả các bộ ba thu được theo cách này đều có dạng (2n 2 +1; 2n 3 +n; –2n 3 – n).

Trả lời: tồn tại.

6. Tìm các số nguyên x, y, z, u sao cho x 2 + y 2 + z 2 + u 2 = 2xyzu.

Số x 2 + y 2 + z 2 + u 2 là số chẵn nên trong các số x, y, z, u có số chẵn là số lẻ.

Nếu cả bốn số x, y, z, u đều lẻ thì x 2 + y 2 + z 2 + u 2 chia hết cho 4, nhưng 2xyzu không chia hết cho 4 - một sự chênh lệch.

Nếu chính xác hai số x, y, z, u là số lẻ thì x 2 + y 2 + z 2 + u 2 không chia hết cho 4, nhưng 2xyzu chia hết cho 4 – một lần nữa là chênh lệch.

Do đó mọi số x, y, z, u đều là số chẵn. Sau đó chúng ta có thể viết rằng

x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,

và phương trình ban đầu sẽ có dạng

x 1 2 + y 1 2 + z 1 2 + u 1 2 = 8x 1 y 1 z 1 u 1 .

Bây giờ lưu ý rằng (2k + 1) 2 = 4k(k + 1) + 1 khi chia cho 8 thì dư 1. Do đó, nếu tất cả các số x 1 , y 1 , z 1 , u 1 đều lẻ thì x 1 2 + y 1 2 + z 1 2 + u 1 2 không chia hết cho 8. Và nếu chính xác hai trong số những số này là số lẻ thì x 1 2 + y 1 2 + z 1 2 + u 1 2 thậm chí không chia hết cho 4. Điều này có nghĩa là

x 1 = 2x 2, y 1 = 2y 2, z 1 = 2z 2, u 1 = 2u 2,

và chúng ta có được phương trình

x 2 2 + y 2 2 + z 2 2 + u 2 2 = 32x 2 y 2 z 2 u 2 .

Lặp lại lập luận tương tự một lần nữa, chúng ta thấy rằng x, y, z, u chia hết cho 2 n với mọi n tự nhiên, điều này chỉ có thể xảy ra với x = y = z = u = 0.

Trả lời: (0; 0; 0; 0).

7. Chứng minh phương trình

(x – y) 3 + (y – z) 3 + (z – x) 3 = 30

không có nghiệm nào là số nguyên.

Chúng ta hãy sử dụng danh tính sau:

(x – y) 3 + (y – z) 3 + (z – x) 3 = 3(x – y)(y – z)(z – x).

Khi đó phương trình ban đầu có thể được viết là

(x – y)(y – z)(z – x) = 10.

Chúng ta hãy ký hiệu a = x – y, b = y – z, c = z – x và viết đẳng thức thu được dưới dạng

Ngoài ra, hiển nhiên a + b + c = 0. Dễ dàng chứng minh rằng, theo hoán vị, đẳng thức abc = 10 ngụ ý rằng các số |a|, |b|, |c| đều bằng 1, 2, 5 hoặc 1, 1, 10. Nhưng trong tất cả các trường hợp này, với bất kỳ cách chọn dấu a, b, c nào, tổng a + b + c đều khác 0. Vậy phương trình ban đầu không có nghiệm nguyên.

8. Giải phương trình 1 với số nguyên! + 2! + . . . +x! = y 2 .

Hiển nhiên là

nếu x = 1 thì y 2 = 1,

nếu x = 3 thì y 2 = 9.

Những trường hợp này tương ứng với cặp tiếp theo số:

x 1 = 1, y 1 = 1;

x 2 = 1, y 2 = –1;

x 3 = 3, y 3 = 3;

x 4 = 3, y 4 = –3.

Lưu ý rằng với x = 2 chúng ta có 1! + 2! = 3, với x = 4 ta có 1! + 2! + 3! + 4! = 33 và cả 3 và 33 đều không phải là số bình phương. Nếu x > 5 thì vì

5! + 6! + . . . +x! = 10n,

chúng ta có thể viết điều đó

1! + 2! + 3! + 4! + 5! + . . . +x! = 33 + 10n.

Vì 33 + 10n là số tận cùng bằng 3 nên nó không phải là bình phương của một số nguyên.

Trả lời: (1; 1), (1; –1), (3; 3), (3; –3).

9. Quyết định hệ thống sau các phương trình trong số tự nhiên:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0 thì a 3 > b 3 + c 3 ;

do đó chúng tôi có

Cộng các bất đẳng thức này, ta được

Xét bất đẳng thức cuối cùng, từ phương trình thứ hai của hệ ta thu được

Nhưng phương trình thứ hai của hệ cũng chứng tỏ a là số chẵn. Như vậy, a = 2, b = c = 1.

Trả lời: (2; 1; 1)

10. Tìm tất cả các cặp số nguyên x và y thỏa mãn phương trình x 2 + x = y 4 + y 3 + y 2 + y.

Phân tích thành nhân tử cả hai vế của phương trình này, ta được:

x(x + 1) = y(y + 1)(y 2 + 1),

x(x + 1) = (y 2 + y)(y 2 + 1)

Sự đẳng thức như vậy có thể xảy ra nếu bên trái và bên phải bằng 0 hoặc là tích của hai số nguyên liên tiếp. Do đó, đánh đồng các yếu tố nhất định bằng 0, chúng ta thu được 4 cặp giá trị biến mong muốn:

x 1 = 0, y 1 = 0;

x 2 = 0, y 2 = –1;

x 3 = –1, y 3 = 0;

x 4 = –1, y 4 = –1.

Tích (y 2 + y)(y 2 + 1) chỉ có thể coi là tích của hai số nguyên khác 0 liên tiếp khi y = 2. Do đó x(x + 1) = 30, do đó x 5 = 5, x 6 = –6. Điều này có nghĩa là có thêm hai cặp số nguyên thỏa mãn phương trình ban đầu:

x 5 = 5, y 5 = 2;

x 6 = –6, y 6 = 2.

Trả lời: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Những vấn đề không có giải pháp

1. Giải phương trình số nguyên:

a) xy = x + y + 3;

b) x 2 + y 2 = x + y + 2.

2. Giải phương trình số nguyên:

a) x 3 + 21y 2 + 5 = 0;

b) 15x 2 – 7y 2 = 9.

3. Giải phương trình số tự nhiên:

a) 2 x + 1 = y 2;

b) 3 2 x + 1 = y 2.

4. Chứng minh phương trình x 3 + 3y 3 + 9z 3 = 9xyz trong số hữu tỉ có nghiệm duy nhất

5. Chứng minh phương trình x 2 + 5 = y 3 nguyên vô nghiệm.

Thông thường trong các nhiệm vụ lập trình tuyến tính Tọa độ kế hoạch không bắt buộc phải là số nguyên. Tuy nhiên, trong thực tế người ta thường gặp các bài toán trong đó tọa độ của phương án tối ưu phải là số nguyên và những bài toán như vậy gọi là bài toán. . Khi giải các bài toán quy hoạch tuyến tính bằng phương pháp đồ thị và phương pháp đơn hình, không có gì đảm bảo rằng tọa độ của phương án tối ưu sẽ là số nguyên.

Trong một số trường hợp, kết quả có thể được làm tròn. Ví dụ: nếu kế hoạch tối ưu quy định rằng phải sản xuất 499683,3 ô tô thì việc làm tròn kết quả thành 499683 hoặc thậm chí thành 500000 là hợp lý về mặt kinh tế.

Tuy nhiên, có những vấn đề trong đó việc làm tròn như vậy có thể tạo ra sai số lớn. Ví dụ: nếu kế hoạch tối ưu quy định phải xây dựng 0,67 nhà máy thì việc làm tròn chính thức thành 0 hoặc 1 là không thể chấp nhận được.

Vì vậy, các phương pháp giải bài toán quy hoạch tuyến tính có tầm quan trọng thực tiễn rất lớn, với sự trợ giúp của chúng, bạn có thể tìm ra phương án tối ưu có tọa độ là số nguyên. Nhiệm vụ Lập trình số nguyên được giải quyết bằng cách sử dụng chính xác các phương pháp này.

Nếu như bài toán lập trình số nguyên đặt vào hình thức kinh điển, nó được biểu diễn như sau:

tìm cực đại của hàm mục tiêu (dạng tuyến tính)

theo một hệ thống hạn chế

Như vậy, nhiệm vụ Lập trình số nguyên và bài toán quy hoạch tuyến tính tương ứng chỉ khác nhau ở điều kiện các ẩn số là số nguyên.

Giống như các bài toán quy hoạch tuyến tính, các bài toán quy hoạch số nguyên yêu cầu phương án tối ưu cực đại hóa hàm mục tiêu (dạng tuyến tính).

Phương pháp Gomori giải các bài toán lập trình số nguyên

Phương pháp Gomori là phương pháp phổ quát giải các bài toán lập trình số nguyên, với sự trợ giúp của nó, sau một số lần lặp hữu hạn, bạn có thể tìm ra phương án tối ưu hoặc đảm bảo rằng bài toán không có lời giải. Tuy nhiên, giá trị thực tế của phương pháp Gomori rất hạn chế, vì cần phải thực hiện khá nhiều bước lặp khi giải bài toán.

Khi giải các bài toán lập trình số nguyên bằng phương pháp Gomori, các tập con không chứa các sơ đồ số nguyên sẽ dần bị loại khỏi tập các phương án tối ưu cho bài toán quy hoạch tuyến tính.

Ở lần lặp đầu tiên, bạn cần giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. Nếu các ẩn số được tìm thấy thỏa mãn yêu cầu về số nguyên thì bài toán lập trình số nguyên được giải quyết. Nếu trong số các ẩn số chưa biết có ít nhất một số là phân số thì phải soạn Điều kiện bổ sung(cách soạn nó - xem thêm ở bên dưới) và gắn nó vào hệ ràng buộc của bài toán lập trình số nguyên. Do đó, khỏi tập hợp các kế hoạch, tập hợp con không chứa các kế hoạch số nguyên sẽ bị loại bỏ. Nếu phương án tối ưu của bài toán được tăng cường theo cách này là số nguyên thì bài toán lập trình số nguyên được giải. Quá trình giải tiếp tục cho đến khi tại một số lần lặp, một phương án tối ưu số nguyên được tìm thấy hoặc có thể xác minh được rằng bài toán không có lời giải.

Bây giờ hãy nói về cách tạo điều kiện bổ sung được đề cập. Nó, một điều kiện bổ sung, được lấy từ một trong các phương trình của hệ giới hạn từ các hệ số của ẩn số và chính các ẩn số theo công thức

, trong đó trong ngoặc nhọn lần lượt là phần phân số của số hạng tự do và hệ số của ẩn số.

Ví dụ, từ bảng đơn chúng ta thu được phương trình sau:

.

Chúng ta thu được phần phân số của số hạng tự do bằng cách trừ phần nguyên của nó khỏi chính số đó như sau:

Tương tự, chúng ta thu được phần phân số của các hệ số cho ẩn số:

(Tại x3 ),

(Tại x4 ).

MỘT nguyên tắc chung tìm phần phân số như sau: Toàn bộ phần số thực Một Số nguyên lớn nhất được gọi là [ Một], không vượt quá Một; phần phân số của số thực Một gọi là sự khác biệt {Một} = Một - [Một] chính con số đó Một và toàn bộ phần của nó [ Một] .

.

Trong ví dụ của chúng tôi, sử dụng công thức trên, ta thu được phương trình sau:

.

Ví dụ 1. Giải bài toán lập trình số nguyên sau bằng phương pháp Gomori. Tìm mức tối đa hàm mục tiêu

theo một hệ thống hạn chế

Giải pháp. Ta giải bài toán bằng phương pháp đơn hình. Vì chúng tôi có bài giảng giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình, bản thân phương thức này sẽ không được giải thích ở đây mà chỉ đưa ra các bảng đơn giản.

Những ẩn số bổ sung x3 Và x4 Hãy coi nó là cơ bản. Chúng ta hãy biểu diễn các ẩn số cơ bản và hàm mục tiêu theo các biến không cơ bản:

Hãy tạo một bảng đơn giản từ các hệ số:

Chúng tôi tổng hợp các bảng sau cho đến khi có được phương án tối ưu:

bàn số 3
Những ẩn số cơ bản	Thành viên miễn phí	Những ẩn số miễn phí		Các hệ số phụ
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
VỚI	65/7	10/7	1/7	1/2

Từ Bảng 3 ta tìm được phương án tối ưu . Vì phương án tối ưu này không thỏa mãn điều kiện nguyên nên chúng ta cần tạo thêm một điều kiện. Phần phân đoạn tọa độ là một số và phần phân số của tọa độ là một số.

Phương trình đầu tiên dựa trên bảng sẽ được viết như sau:

.

Sau khi xác định phần phân số của các hệ số đối với ẩn số và số hạng tự do, chúng ta thu được điều kiện bổ sung sau:

hoặc, bằng cách giới thiệu một biến bổ sung,

.

Chúng tôi nhận được dòng mới trong bảng đơn thu được ở Bảng 3 và cộng các hệ số theo phương trình vừa thu được:

Bảng 4
Những ẩn số cơ bản	Thành viên miễn phí	Những ẩn số miễn phí		Các hệ số phụ
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
VỚI	65/7	10/7	1/7	1/2

Chúng tôi hoàn thành bước phương pháp đơn giản và nhận được bảng:

Bảng 5
Những ẩn số cơ bản	Thành viên miễn phí	Những ẩn số miễn phí		Các hệ số phụ
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
VỚI	55/6	4/3	1/6	-1/7

Chúng tôi đã nhận được phương án tối ưu . Kế hoạch này, giống như kế hoạch trước, không thỏa mãn điều kiện số nguyên. Vì vậy, một điều kiện bổ sung lại được yêu cầu. Trong trường hợp này, bạn có thể sử dụng phương trình thứ nhất hoặc thứ ba. Chúng ta nhận được điều kiện bổ sung sau:

.

Hãy tạo bảng sau:

Bảng 6
Những ẩn số cơ bản	Thành viên miễn phí	Những ẩn số miễn phí		Các hệ số phụ
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
VỚI	55/6	4/3	1/6	-1/7

Phương án tối ưu chúng tôi nhận được từ bảng cuối cùng sau đây:

Bảng 7
Những ẩn số cơ bản	Thành viên miễn phí	Những ẩn số miễn phí		Các hệ số phụ
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
VỚI	9	6/5	1/5	-1/6

Vì phương án tối ưu tìm được thỏa mãn điều kiện số nguyên nên bài toán quy hoạch số nguyên được giải quyết. tọa độ x5 Và x6 có thể được bỏ qua vì điều kiện ban đầu của bài toán chỉ chứa bốn ẩn số. Vì vậy, phương án tối ưu cuối cùng sẽ được viết như sau:

,

và hàm mục tiêu lớn nhất là 9.

Phương pháp rẽ nhánh và ràng buộc để giải các bài toán lập trình số nguyên

Phương pháp nhánh và giới hạn thuận tiện cho việc giải các bài toán lập trình số nguyên trong đó số ẩn số nhỏ hoặc yêu cầu số nguyên không áp dụng cho tất cả các ẩn số. Bản chất của phương pháp nhánh và ràng buộc là đối với những ẩn số mà yêu cầu số nguyên áp dụng, cần phải xác định ranh giới trong đó các giá trị của những ẩn số này có thể nằm. Khi đó các bài toán quy hoạch tuyến tính tương ứng sẽ được giải.

Việc chỉ định các ranh giới trong đó các giá trị của ẩn số phải nằm trong một bài toán lập trình số nguyên có thể được viết như sau:

Trong thực tế, trong nhiều trường hợp, ranh giới của các giá trị chưa biết đã được đưa vào hệ ràng buộc của bài toán quy hoạch số nguyên hoặc chúng có thể được xác định dựa trên nội dung kinh tế của bài toán. Mặt khác, chúng ta có thể giả sử rằng giới hạn dưới là , và giới hạn trên là , trong đó M- một con số dương khá lớn.

Cách thức phân nhánh và ràng buộc cho phép bạn tinh chỉnh ranh giới giá trị chấp nhận được không xác định?

Đầu tiên, một bài toán quy hoạch tuyến tính tương ứng với một bài toán quy hoạch số nguyên được giải bằng cách sử dụng phương pháp đơn hình. Hãy tìm phương án tối ưu trong bài toán này và giá trị của bất kỳ tọa độ nào của nó là một số phân số. Sau đó, bạn sẽ cần tạo ra hai bài toán quy hoạch tuyến tính mới. Làm thế nào để làm nó?

Chúng ta hãy biểu thị phần nguyên của tọa độ là . Một trong những bài toán quy hoạch tuyến tính mới Giơi hạn dươi giá trị tọa độ sẽ là một số, nghĩa là phần nguyên của giá trị tọa độ tăng thêm một. Nó sẽ được viết như sau:

.

Ở một nơi khác nhiệm vụ mới lập trình tuyến tính, giới hạn trên của giá trị tọa độ sẽ là phần nguyên của chính giá trị tọa độ. Nó sẽ được viết như thế này:

Như vậy, hai bài toán mới đã được “phân nhánh” từ bài toán quy hoạch tuyến tính đầu tiên, trong đó ranh giới các giá trị cho phép của một ẩn số đã thay đổi. Khi giải quyết từng vấn đề này, có thể xảy ra ba trường hợp:

• phương án tối ưu không phải là số nguyên,
• phương án tối ưu là số nguyên,
• vấn đề không có giải pháp.

Chỉ trong trường hợp đầu tiên mới có thể “phân nhánh” các nhiệm vụ mới theo cách được trình bày ở trên. Trong trường hợp thứ hai và thứ ba, quá trình “phân nhánh” dừng lại.

Tại mỗi lần lặp lại việc giải một bài toán lập trình số nguyên, một bài toán được giải. Hãy giới thiệu khái niệm: danh sách các bài toán quy hoạch tuyến tính cần giải. Từ danh sách, chọn vấn đề cần giải quyết ở lần lặp tương ứng. Ở những lần lặp lại tiếp theo, danh sách sẽ thay đổi, vì các vấn đề đã giải quyết không còn được đưa vào danh sách nữa và thay vào đó là các nhiệm vụ mới “phân nhánh” từ các nhiệm vụ trước đó sẽ được đưa vào danh sách.

Để hạn chế “phân nhánh”, tức là giảm số lượng bài toán cần giải, tại mỗi lần lặp cần xác định giới hạn dưới của giá trị cực đại của hàm mục tiêu. Điều này được thực hiện như sau:

Theo thuật toán giải bài toán lập trình số nguyên bằng phương pháp rẽ nhánh và giới hạn, trên mỗi P Lần lặp thứ này yêu cầu 4 bước.

Ví dụ 2. Giải bài toán lập trình số nguyên sau bằng phương pháp rẽ nhánh và giới hạn. Tìm cực đại của hàm mục tiêu

theo một hệ thống hạn chế

Giải pháp. Giả sử rằng các ranh giới sau đây của các giá trị tối ưu của ẩn số được đưa ra hoặc xác định:

.

Vì nhiệm vụ được giao trong dạng bình thường, nó có thiết kế nguyên và giới hạn dưới của giá trị lớn nhất của hàm mục tiêu.

Danh sách các nhiệm vụ cần giải quyết bao gồm nhiệm vụ 1:

Lặp lại 1.

Bước 1. Bằng cách sử dụng phương pháp đơn giảnđã thu được lời giải cho vấn đề thứ nhất:

Vì phương án tìm được không phải là số nguyên nên tiếp theo là bước 4.

Bước 4. Vì phương án tối ưu có tọa độ phân số là 1,2 nên . Áp dụng giới hạn cho các giá trị của ẩn của bài toán 1, ta thu được bài toán mới. Ở bài toán thứ 2, giới hạn dưới của là , và ở bài toán thứ 3, giới hạn trên của là .

6 câu trả lời

Làm theo ví dụ sau: giả sử các phương trình là:

7 = x + 3y + 4z + 9w 12 = 4x + 2y + 3z + 7w

Có 2 phương trình và 4 ẩn số. Bạn có thể đặt 2 ẩn số làm tham số, do đó hệ thống sẽ có số phương trình có số ẩn số:

7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y

Chúng ta sẽ sử dụng x và y làm ẩn số. Nó có thể được giải và để lại w và z làm tham số trong nghiệm tuyến tính:

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

Bây giờ bạn cần lấy tử số chia hết cho 10 làm mẫu số. Nếu có giải pháp, bạn có thể kiểm tra tất cả các tham số từ 1 đến 10.

Nói chung, bạn làm điều này:

• Chọn các tham số sao cho có nhiều ẩn số như phương trình. Cố gắng để lại những ẩn số tạo ra giá trị tuyệt đối nhỏ nhất cho định thức (trong ví dụ là 10, nhưng chọn y và z sẽ tốt hơn vì nó sẽ là |det|=3)
• Quyết định hệ thống tuyến tính và tạo phản hồi tùy thuộc vào các tham số
• Kiểm tra các giá trị tham số từ 1 đến giá trị tuyệt đối det (nếu có một nghiệm, bạn sẽ tìm thấy nó ở điểm này) cho đến khi có một nghiệm nguyên cho tất cả các ẩn số (đó là lý do tại sao bạn chọn giá trị định thức nhỏ nhất trước đó) và kiểm tra xem nó có dương hay không (điều này không được minh họa trong phần ví dụ).

Xin lỗi nếu anh ấy là lực lượng vũ phu TRÊN Bước cuối cùng, nhưng ít nhất có thể giảm thiểu phạm vi thử nghiệm. Có lẽ Cách tốt nhất giải hệ phương trình Diophantine cuối cùng, nhưng tôi không biết phương pháp nào.

EDIT1

Có một phương pháp để tránh sự ép buộc ở phần cuối cùng. Một lần nữa, trong ví dụ bạn cần làm:

22 = 3w + z (đồng đẳng, mod 10) 16 = 29w + 13z (đồng đẳng, mod 10)

Ứng dụng của mô-đun:

2 = 3w + z (đồng đẳng, mod 10) 6 = 9w + 3z (đồng đẳng, mod 10)

Bạn có thể làm cho hệ đồng dư thành tam giác (loại bỏ Gaussian) bằng cách nhân hệ đồng dư với modulo nghịch đảo 10 của nó và tính tổng với các hệ khác. Nghịch đảo của 9 modulo 10 là -1, vì vậy chúng ta nhân phương trình cuối cùng:

2 = 3w + z (đồng đẳng, mod 10) -6 = -9w + -3z (đồng đẳng, mod 10)

Tương đương:

2 = 3w + z (đồng đẳng, mod 10) 4 = w + 7z (đồng đẳng, mod 10)

Sau đó nhân với -3 và cộng với số đầu tiên:

2 - 3*4 = 3w + z -3w - 21z (đồng dư, mod 10) 4 = w + 7z (đồng dư, mod 10)

Tương đương:

10 = -20z (đồng đẳng, mod 10) 4 = w + 7z (đồng đẳng, mod 10)

Sau đó, bạn giải từ trên xuống dưới (ví dụ này có vẻ đúng với mọi giá trị của z). Có thể có một mức độ nhất định tự do nếu bạn có nhiều tham số hơn đồng dư, nhưng chúng tương đương nhau và bạn có thể đặt tham số dư thừa thành bất kỳ giá trị nào, tốt nhất là giá trị nhỏ nhất là 1.

Hãy cho tôi biết nếu có điều gì khác chưa rõ ràng!

Nếu tôi hiểu chính xác vấn đề thì bạn có nhiều gói, mỗi gói có các gói khác nhau bưu phí. Bạn muốn trả bưu phí này từ kho tem bạn có. Bạn có thể giải quyết vấn đề với toàn bộ chương trình. Giải pháp dưới đây giải quyết tất cả các gói cùng một lúc. Bạn sẽ có một số biến bằng numPackages * numStampDenominations (có thể bất tiện cho số lượng lớn gói).

Ràng buộc đẳng thức có dạng Aeqx = beq. Ma trận Aeq cho hai gói có bốn nhãn hiệu (numVarsnumPackages) trông như thế này:

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

Hàng đầu tiên là các hệ số ràng buộc (giá trị tem) cho lô 1. Các hệ số khác 0 là giá trị tem. Biến null liên quan đến các gói khác không được quan tâm.

Nhóm hạn chế thứ hai (bất bình đẳng) liên quan đến nhóm thương hiệu mà tôi có. Ràng buộc bất đẳng thức có dạng A * x = b. Ma trận A cho 4 tem và 8 biến (numPackages * numStampDenominations) trông như thế này:

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

Hàm chi phí là f"*x, đại diện cho tổng số khuôn. Các hệ số của nó đơn giản là các đơn vị, được chỉ định dưới dạng vectơ cột.

Có một tập lệnh chạy trong Matlab giải quyết vấn đề theo cách được mô tả. Nó có thể sẽ được xây dựng theo cách tương tự như trong các quãng tám mà GNU cung cấp, tương tự như Matlab. Matlab hoặc Octave có thể không phải là giải pháp phù hợp với bạn, nhưng ít nhất chúng cũng cho bạn biết giải pháp nào hiệu quả và cung cấp cho bạn hộp cát để phát triển giải pháp.

% Giá trị của mỗi tem có sẵn dưới dạng ma trận 4x1 sv = [.21; 0,68; 0,47; .01]; % Số lượng mỗi tem có sẵn dưới dạng ma trận 4x1 sq = ; % Số lần trình diễn m = size(sv, 1); % Bưu phí cần thiết cho mỗi gói hàng dưới dạng ma trận 4x1 % -- có thể được đọc từ một tệp bưu phí = [.89;.50;1.01;.47;.47]; % Số lượng gói hàng -- chỉ là số hàng bưu phí packageCount = size(postage, 1); % Số biến là m*packageCount numVar = m*packageCount; % giới hạn dưới -- số 0 tem của mệnh giá nhất định lb = zeros(numVar,1); % giới hạn trên -- sử dụng các ràng buộc cho giới hạn trên ub = ; % Hàm chi phí -- giảm thiểu số lượng tem được sử dụng % min(f"*x) f = one(numVar,1); % ràng buộc số nguyên intcon = 1:numVar; % Xây dựng ma trận ràng buộc bưu phí Aeq = zeros(numVar, packageCount ); for i = 1:packageCount first = i*m - 3; end = first + 3; Aeq(first:last,i) = sv(:); end % Xây dựng ma trận ràng buộc đếm tem A = zeros(numVar, m ); với r = 1:m với j = 1:m c = (j-1)*m + 1; A(c,r) = 1; đầu cuối x = intlinprog(f, intcon, A", b, Aeq ", beq, lb, ub)

Tôi sẽ thử cách tiếp cận sau (lưu ý rằng tôi chưa bao giờ phải giải quyết vấn đề này, vì vậy hãy coi câu trả lời này như một nỗ lực để cùng bạn giải quyết vấn đề thay vì một câu trả lời phân tích thực tế).

Bạn chỉ cần tìm giải pháp như thể đó là một hệ thống bình thường, vì vậy bạn có thể tìm thấy vô số giải pháp:

Ví dụ:

Y=x+3

thì cặp số thực (2,5) là một nghiệm thực khả thi cho hệ thống này, khi bạn có vô số nghiệm, bạn chỉ cần giới hạn tập con các nghiệm được tạo ra bởi các số nguyên.

Tất nhiên bạn có những hạn chế, trong trường hợp của chúng tôi, giải pháp chỉ có 1 biến miễn phí, vì vậy chúng tôi có thể viết tất cả các giải pháp như thế này:

(x, x+3)

Sự kinh ngạc:

Nếu có một số vô tỷ ở đâu đó thì không có nghiệm số nguyên:

(x, x+pi) => cả số 1 và số 2 ở đây đều không thể là số nguyên cùng một lúc

Vì vậy bạn có thể tìm thấy nghiệm số nguyên khi và chỉ khi "vô số nghiệm" của bạn bị giới hạn ở số nguyên hoặc số hữu tỷ.

Giả sử bạn có vectơ sau:

(3x, (2/5)y, y, x, x+y)

Sau đó, toàn bộ giải pháp có thể là:

X=3 y=10/2

Nếu bạn cảm thấy câu trả lời không phù hợp với mình, chỉ cần nói: Tôi sẽ xóa nó để không nhận điểm thưởng.

Trong một số bài toán kinh tế liên quan đến bài toán quy hoạch tuyến tính, các phần tử của lời giải phải được biểu diễn dưới dạng số nguyên. Trong những bài toán này, các biến có nghĩa là số đơn vị của sản phẩm không thể chia được.

Bài toán lập trình số nguyên được phát biểu như sau:

Tìm phương án giải pháp như vậy X=(x 1 , X 2 ,…, X N ) , trong đó hàm tuyến tính nhận giá trị tối đa hoặc tối thiểu tuân theo các hạn chế

vấn đề được giải quyết bằng phương pháp quy hoạch tuyến tính. Nếu các biến của lời giải tối ưu không phải là số nguyên thì sử dụng phương pháp cắt hoặc phương pháp liệt kê các lời giải số nguyên.

Khái niệm nhánh và ràng buộc .

Phương pháp nhánh và ràng buộc bao gồm việc tìm kiếm có thứ tự các phương án và chỉ xem xét những phương án có triển vọng theo các tiêu chí nhất định và loại bỏ các phương án không có triển vọng.

Phương pháp nhánh và ràng buộc bao gồm các phần sau: tập hợp các giải pháp (kế hoạch) khả thi được chia theo một cách nào đó thành các tập hợp con, mỗi tập hợp lại được chia thành các tập hợp con theo cùng một cách. Quá trình tiếp tục cho đến lúc đó. Lời giải số nguyên tối ưu cho bài toán ban đầu vẫn chưa được tìm ra.

Tên gọi của phương thức rẽ nhánh và ràng buộc xuất phát từ việc trong quá trình giải bài toán lần lượt được “phân nhánh”, thay thế bằng những phương pháp đơn giản hơn. Quá trình giải có thể được tiếp tục dưới dạng cây, các số trong các nút (đỉnh) của cây biểu thị kế hoạch giải quyết vấn đề (các biến mong muốn).

5. 2 Phương pháp đồ thị giải các bài toán lập trình số nguyên.

Nếu có hai biến trong một bài toán quy hoạch tuyến tính và các bất đẳng thức trong hệ ràng buộc, thì nó có thể được giải bằng đồ thị mà không cần đến các biến số nguyên.

Nếu nghiệm tối ưu của bài toán này là số nguyên thì nó là tối ưu cho bài toán ban đầu.

Nếu nghiệm tối ưu thu được không phải là số nguyên thì một ràng buộc tuyến tính bổ sung sẽ được xây dựng. Nó có các tính chất sau:

Nó phải tuyến tính;

Nên cắt bỏ phương án phi nguyên tối ưu đã tìm được;

Không nên cắt bớt bất kỳ kế hoạch số nguyên nào.

Thuật toán giải bài toán bằng đồ họa

Lập trình số nguyên.

Xây dựng hệ tọa độ x 1 0x 2 và chọn tỷ lệ.

Tìm vùng lời giải khả thi (ADS) của hệ các ràng buộc của bài toán.

Xây dựng hàm mục tiêu là một đường mức và chỉ ra hướng của pháp tuyến trên đó.

Di chuyển đường của hàm mục tiêu theo hướng pháp tuyến qua ODR sao cho nó thay đổi từ cát tuyến sang tiếp tuyến với ODF và đi qua điểm xa gốc tọa độ nhất. Điểm này sẽ là điểm cực trị, tức là giải quyết vấn đề.

Nếu đường của hàm mục tiêu song song với một trong các cạnh của ODP, thì trong trường hợp này đạt cực trị tại tất cả các điểm của cạnh tương ứng và bài toán quy hoạch tuyến tính sẽ có vô số nghiệm .

Tìm tọa độ, điểm cực trị và giá trị của hàm mục tiêu trong đó. Nếu các giá trị thu được không phải là số nguyên thì hãy chuyển sang bước tiếp theo.

Chọn vùng có giá trị nguyên tại các tọa độ này.

Xác định tọa độ mới và xây dựng đồ thị.

Tìm các điểm có giá trị nguyên của các biến mong muốn, thay chúng vào phương trình của hàm mục tiêu và tìm giá trị của nó. Giá trị lớn nhất thu được của hàm mục tiêu sẽ là lời giải của bài toán.