Phương pháp Gomori là một thuật toán giải chi tiết. Phương pháp Gomori giải các bài toán lập trình số nguyên. Ví dụ về giải quyết vấn đề kinh tế

Bản chất của phương pháp cắt tỉa là bài toán được giải trước tiên mà không cần đến điều kiện nguyên. Nếu phương án kết quả là số nguyên thì bài toán đã được giải quyết. Mặt khác, một ràng buộc mới sẽ được thêm vào các ràng buộc nhiệm vụ với các thuộc tính 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.

Một ràng buộc bổ sung có những đặc tính này được gọi là điểm cắt chính xác.

Về mặt hình học, việc cộng mỗi ràng buộc tuyến tính tương ứng với việc vẽ một đường thẳng (siêu phẳng) cắt một phần của nó khỏi đa giác nghiệm (đa diện) cùng với điểm tối ưu có tọa độ không nguyên, nhưng không ảnh hưởng đến bất kỳ số nguyên nào. điểm của khối đa diện này. Kết quả là, khối đa diện có nghiệm mới chứa tất cả các điểm nguyên có trong khối đa diện có nghiệm ban đầu và theo đó, kết quả thu được với khối đa diện này giải pháp tối ưu sẽ là một số nguyên (Hình 8.1).

nhấn các biến chính *1, *2, các biến mới Xm+1, Xm+2, ..., Xm+1, giải pháp

Xt thông qua neo-x​tối ưu

thành phần không nguyên. Trong trường hợp này có thể chứng minh rằng bất đẳng thức

(P, ) - (a," m+\)xm+1 ■ -~(at )Xn ^ 0, (* )

được hình thành bởi phương trình /th của hệ (8.5), có tất cả các tính chất của điểm cắt đều.

Để giải bài toán quy hoạch tuyến tính số nguyên (8.1)-(8.4) bằng phương pháp Gomori, thuật toán sau được sử dụng:

1. Sử dụng phương pháp đơn hình, giải bài toán (8.1)-(8.3) không xét đến điều kiện nguyên. Nếu tất cả các thành phần của phương án tối ưu đều là số nguyên thì nó là tối ưu cho bài toán quy hoạch số nguyên (8.1)-(8.4). Nếu vấn đề đầu tiên (8.1) -

(8.3) không giải được (nghĩa là không có tối ưu cuối cùng hoặc các điều kiện của nó mâu thuẫn nhau), thì bài toán thứ hai (8.1)-(8.4) cũng không giải được.

2. Nếu trong số các thành phần của nghiệm tối ưu có thành phần không nguyên thì chọn thành phần có phần nguyên lớn nhất và sử dụng phương trình tương ứng của hệ (8.5), tạo thành điểm cắt đúng (8.6).

3. Bằng cách đưa thêm một biến số nguyên không âm, hãy biến đổi bất đẳng thức (8.6) thành phương trình tương đương

(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)

và đưa nó vào hệ thống hạn chế (8.2).

4. Giải bài toán mở rộng thu được bằng phương pháp đơn hình. Nếu phương án tối ưu tìm được là số nguyên,

sau đó nhiệm vụ Lập trình số nguyên(8.1)-(8.4) được giải. Ngược lại, quay lại bước 2 của thuật toán.

Nếu bài toán có thể giải được bằng số nguyên thì sau hữu hạn bước (lặp) sẽ tìm được phương án số nguyên tối ưu.

Nếu trong quá trình giải một phương trình xuất hiện (biểu thị biến chính theo các biến không cơ bản) có số hạng tự do không nguyên và các hệ số còn lại là số nguyên thì phương trình tương ứng không có nghiệm ở dạng số nguyên. Trong trường hợp này, bài toán này không có nghiệm tối ưu nguyên.

^8.1. Để mua thiết bị phân loại ngũ cốc, người nông dân phân bổ 34 den. các đơn vị Thiết bị phải được đặt trên diện tích không quá 60 mét vuông. m.Người nông dân có thể đặt mua hai loại thiết bị: máy loại A kém mạnh hơn có giá 3 den. đơn vị yêu cầu diện tích sản xuất là 3 mét vuông. m (bao gồm cả đường chuyền) và cung cấp năng suất 2 tấn ngũ cốc mỗi ca, và các máy loại B mạnh hơn có giá 4 den. các đơn vị chiếm diện tích 5 mét vuông. m và cung cấp năng suất 3 tấn ngũ cốc chất lượng cao mỗi ca.

Cần lập kế hoạch mua sắm thiết bị tối ưu để đảm bảo năng suất tổng thể tối đa, với điều kiện người nông dân được mua không quá 8 máy loại B.

Giải pháp. Ta ký hiệu x\, x2 lần lượt số lượng ô tô loại A và B là Z - Tổng hiệu suất. Khi đó mô hình toán học của bài toán sẽ có dạng:

Trong bộ lễ phục. 8.2 OKM - vùng các giải pháp khả thi cho bài toán (8.1") - (8.3"), được giới hạn bởi các đường thẳng (1), (2), (3) và các trục tọa độ; />(2/3; 8) - điểm của lời giải tối ưu nhưng không nguyên của bài toán (8.1") - (8.3"); (4) - một đường thẳng cắt nghiệm không nguyên này; 0№М - diện nghiệm khả thi của bài toán mở rộng (8.1’) - (8.3’), (8.61); M2; 7) - điểm của nghiệm số nguyên tối ưu.

Bước I. Các biến chính x3, x4, *5; các biến không cơ bản X\, X2.

Lời giải cơ bản thứ nhất X\ = (0; 0; 60; 34; 8) được chấp nhận. Giá trị hàm tuyến tính tương ứng = 0.

Chúng tôi chuyển đổi biến XI thành các biến chính, được đưa vào biểu thức của hàm tuyến tính có hệ số dương lớn nhất. Chúng ta tìm giá trị lớn nhất có thể có của biến xi mà hệ hạn chế “cho phép” được chấp nhận, từ điều kiện cực tiểu của các quan hệ tương ứng:

Хг = 1ШП|т;т;Т| = 8,

những thứ kia. phương trình giải quyết (được đánh dấu) là phương trình thứ ba. Khi *2 = 8 trong phương trình này X5 = 0, và biến X5 trở thành biến không cơ bản.

Bước II. Các biến chính x2, x3, x*; biến không chính Xx X5.

Bằng cách đưa vào thêm một biến số nguyên x6 > O, ta thu được phương trình tương đương với bất đẳng thức (8,6")

~1*5 + Xb = °" ^8"7 ^

Phương trình (8.7") phải được đưa vào hệ ràng buộc (8.5") của bài toán chính tắc ban đầu, sau đó lặp lại quá trình giải bài toán phương pháp đơn giản liên quan đến một nhiệm vụ mở rộng. Trong trường hợp này, để giảm số bước (lặp lại), nên đưa thêm phương trình (8,7") vào hệ thống thu được bằng cách sử dụng Bước cuối cùng giải bài toán (không có điều kiện nguyên).

Bước IV. Các biến cơ bản X), *2, xs> *b'> các biến không cơ bản *1, *2-

X1 = z - 3*4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z"x5-

Giải pháp cơ bản X4 = (y; 8; 18; 0; 0; -y) là không thể chấp nhận được. (Lưu ý rằng sau khi đưa vào một phương trình bổ sung tương ứng với điểm cắt chính xác trong hệ thống ràng buộc, sẽ luôn thu được nghiệm cơ sở không hợp lệ.)

Để có được hợp lệ giải pháp cơ bản cần phải chuyển sang biến chính, biến này được bao gồm hệ số dương trong phương trình trong đó số hạng tự do là âm, tức là. *1 hoặc x$ (ở giai đoạn này chúng tôi không xem xét hàm tuyến tính). Chúng tôi dịch sang những cái cơ bản, ví dụ, biến X5.

bước V. Các biến chính X\, X2, X3, X5; các biến không cơ bản R], X £

Sau khi biến đổi ta có:

LG| = 2 - x4 + 2x6,

*2 = 7 + 2х* ~ 2Х("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|x4--|x6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Vì không có biến chính nào có hệ số dương trong biểu thức của hàm tuyến tính nên X5 là nghiệm tối ưu.

Vì vậy, 2max = 25 cho nghiệm số nguyên tối ưu X* - X$ =(2; 7; 19; 0; 1; 0), tức là. hiệu suất tối đa Có thể thu được 25 tấn ngũ cốc chất lượng cao mỗi ca bằng cách mua 2 máy loại A và 7 máy loại B, trong khi diện tích trống của cơ sở sẽ là 19 mét vuông. m, còn lại Tiền bạc trong số được cấp bằng 0, dự trữ để mua - 1 máy loại B (thành phần thứ sáu không có ý nghĩa).

Bình luận. Để giải thích hình học trên mặt phẳng Ox\Xr (xem Hình 8.2) của điểm cắt (8.6"), cần biểu thị các biến x4 và x$ có trong nó thông qua các biến XI và x2. Chúng ta thu được (xem phần Phương trình thứ 2 và thứ 3 của hệ ràng buộc (8,5")):

y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 hoặc x, + 2x2 £ 16.

(xem đường cắt (4) trong Hình 8.2)>

^8.2. Có đủ một số lượng lớn khúc gỗ dài 3 m, khúc gỗ phải được cắt thành hai loại phôi: dài 1,2 m và dài 0,9 m, mỗi loại phải lấy ít nhất 50 khúc. và 81 chiếc. tương ứng. Mỗi khúc gỗ có thể được cắt thành các ô trống được chỉ định theo nhiều cách: 1) thành 2 ô trống, mỗi ô 1,2 m; 2) cho 1 mảnh mỗi mảnh 1,2 m và 2 mảnh mỗi mảnh 0,9 m; 3) cho 3 khúc, mỗi khúc 0,9 m. Tìm số khúc gỗ,

được xẻ theo từng phương pháp, sao cho có thể thu được bất kỳ loại phôi nào từ số lượng khúc gỗ nhỏ nhất.

Giải pháp. Chúng ta hãy biểu thị bằng х\, хі, хм, số lượng khúc gỗ được cắt tương ứng theo các phương pháp 1, 2 và 3. Từ chúng, bạn có thể nhận được 2хі + *2 khoảng trống mỗi cái 1,2 m và 2l\ + 3x2 khoảng trống 0,9 m mỗi cái. chúng ta ký hiệu tổng số log là I. Khi đó mô hình toán học của bài toán sẽ có dạng:

Tôi 2x, + x2 - x4 = 50, chúng ta sẽ biểu thị toàn bộ phần của nó, tức là. [ Một] là số nguyên lớn nhất k số không vượt quá Một.

Phần phân đoạn ( Một) số Một gọi là số ( Một} = Một - [Một]. Chúng ta hãy lưu ý tính chất hiển nhiên của phần phân số của một số tùy ý: 0 £ ( Một}<1, причем {Một) = 0 khi và chỉ khi Một - một số nguyên.

Cho phép x*- nghiệm tham khảo của bài toán (1.1), (1.2), không phải là số nguyên, - cơ sở của nó và B- bảng đơn tương ứng ở dạng tọa độ.

Chúng ta hãy xem xét hệ phương trình rút gọn tương ứng với cơ sở này (và bảng B) kế hoạch

x*:

Bởi vì x j *= 0 tại jÎw, thì chỉ số lượng có thể không nguyên x 0 * = <c, x*>, x tôi *, Tôi Là.

Cho phép S- chỉ số như vậy (0 £ S £ N) rằng số đó xs*- không trọn vẹn. Hãy xem xét S dòng thứ trong bảng đơn B (S phương trình trong hệ (3.2), (3.3)) và soạn biểu thức

Định lý 2. Nếu như xÎ X* là phương án nguyên của bài toán (1.1), (1.2), thì

Bằng chứng. Sử dụng mối quan hệ

Mộtsj = [Mộtsj] + {Mộtsj }, j = 0, 1, 2, … , N, từ (3.3) với Tôi= S chúng tôi nhận được

Ở đâu

Vế trái của bất đẳng thức này chứa một số nguyên, do đó số

cũng nguyên vẹn. Từ cái gì x j ³ 0, jÎw, sử dụng tính chất của phần phân số, chúng ta thu được

những thứ kia. - z s(x) < 1, или z s(x) > -1. Xem xét rằng z s(x) - số nguyên, cuối cùng chúng tôi sẽ chấp nhận z s(x) ³ 0.

Kết quả. Nếu như xs*(= Mộts0) - số không nguyên và Đặt X* các kế hoạch bài toán về số nguyên(1.1)-(1.3) không trống thì trong số các số ( Mộtsj}, j=1, 2, …, N, có những cái tích cực.

Thật vậy, mọi số ( Mộtsj) hiển nhiên không âm. Giả sử rằng ( Mộtsj} = 0, j = 1, 2, …, N.

Nếu như X* không trống và x* Î X*, Cái đó z s(x*)= - {Mộts0), cái đó z s(x*) là một số nguyên vì 0< {Mộts0} < 1.

Bình luận. Trong chứng minh Định lý 2, chúng tôi đã sử dụng Giả định II rằng hàm mục tiêu được đảm bảo là số nguyên. Hợp lệ trong trường hợp S= giá trị 0

là số nguyên (với điều kiện là xÎ X*) chỉ khi số x 0 = < c, x> - toàn bộ.

Nó theo sau từ này

Định lý 3. Nếu số xs*- không phải là số nguyên thì bất đẳng thức

là điểm cắt chính xác.

Bằng chứng. Hãy kiểm tra điều kiện cắt trong Định nghĩa 2. Vì xs* = Mộts0, thì từ thực tế là xs*- không phải là số nguyên, ta thu được bất đẳng thức ( Mộts0) > 0. Vì x j *= 0 tại jО w, thì

và do đó vectơ x* không thỏa mãn bất đẳng thức (3.5). Điều kiện đúng được suy ra từ câu lệnh z s(x) ³ 0 trong Định lý 2.

3.3 Thuật toán đầu tiên của Gomory

Hãy chuyển sang phần trình bày thuật toán Gomori đầu tiên.

Ta ký hiệu bài toán (1.1), (1.2) bằng L 0 . Gomori đề xuất tìm mức tối đa từ điển của vấn đề ở giai đoạn đầu tiên của thuật toán của mình L 0 . Chúng ta sẽ ký hiệu bằng

x(0) = (x 0 (0), x 1 (0), …, x n(0))

(n+1) vectơ chiều sao cho ( x 1 (0), x 2 (0), …, x n (0)) - lời giải cho bài toán từ điển L 0, một x 0 (0) = - giá trị hình tuyến tính. Trong trường hợp điều này không gây ra sự hiểu lầm, chúng tôi sẽ gọi x(0) - phương án tối ưu cho bài toán từ điển L 0 (mặc dù theo thuật ngữ được chấp nhận rộng rãi, kế hoạch là một vectơ bao gồm phần cuối cùng N tọa độ vector x(0)).

Cũng lưu ý rằng x(0) sẽ là một kế hoạch tham khảo, cũng như một kế hoạch giả được chấp nhận nghiêm ngặt của vấn đề L 0 .

Nếu x(0) là một vectơ nguyên thì rõ ràng nó là nghiệm của bài toán (1.1) - (1.3).

Ngược lại, chúng ta tìm chỉ số tối thiểu s, 0 £ s £ n, mà giá trị của nó xs(0) không phải là số nguyên. Cho phép B(0) - bảng đơn ở dạng tọa độ tương ứng với vectơ x(0). Sử dụng hệ số S hàng của bảng này (tức là các hệ số của hệ rút gọn (3.2), (3.3)), bằng cách sử dụng kỹ thuật được mô tả ở trên, điểm cắt chính xác được xây dựng.

Một biến phụ được giới thiệu x n+1 và nhiệm vụ được xem xét L 1:

Giai đoạn tiếp theo là tìm mức tối đa từ điển của vấn đề L 1 . Một ưu điểm quan trọng của thuật toán Gomori là kế hoạch giả nghiêm ngặt được chấp nhận ban đầu cho ứng dụng đơn giản kép-phương pháp giải quyết vấn đề L 1 được tìm thấy mà không gặp khó khăn. Thật vậy, dễ dàng thấy rằng với một kế hoạch giả như vậy, chúng ta có thể lấy vectơ

Trên thực tế, rõ ràng là y(1) thỏa mãn (cùng với dạng vector x(0)) hạn chế (3.6), (3.7) vấn đề L 1 và chỉ một trong các hạn chế (3.8) bị vi phạm: x n+1 (0)= - (một S 0 } < 0. Кроме того, y(1) là tham chiếu cho hệ phương trình (3.6), (3.7), vì nếu - Căn cứ kế hoạch x(0) thì hệ thống

độc lập tuyến tính và làm cơ sở cho y(1). Hãy thể hiện điều đó y(1) là một kế hoạch giả được chấp nhận hoàn toàn. Với mục đích này, chúng ta sẽ xây dựng một bảng đơn tương ứng với cơ sở vectơ đã chỉ định y(1). Để làm điều này, bạn chỉ cần thêm bên dưới vào bảng B(0) dòng

Trong đó w = ( j 1 , j 2 , …, jn -tôi) - danh sách số lượng các biến không cơ bản tương ứng với bảng B(0) kế hoạch tham khảo x(0). Bởi vì x(0) là một kế hoạch giả được chấp nhận nghiêm ngặt thì mỗi cột b j, jôi, cái bàn B(0) tích cực về mặt từ điển: b j > 0, jôi. Từ đó suy ra rằng trong bảng đơn ở dạng tọa độ tương ứng với vectơ hỗ trợ y(1), mọi cột (trừ cột đầu tiên trùng với y(1)) mang tính tích cực về mặt từ điển:

Vì vậy, chúng ta có sẵn một giải pháp x(0) nhiệm vụ từ điển L 0 và bảng đơn tương ứng ở dạng tọa độ B(0), không cần tính toán bổ sung, chúng ta tìm thấy kế hoạch giả ban đầu được chấp nhận hoàn toàn y(1) cho nhiệm vụ L 1 và xây dựng bảng đơn tương ứng ở dạng tọa độ.

Có thể xảy ra rằng nhiệm vụ từ điển L 1 không có giải pháp. Trong trường hợp này, việc giải bài toán số nguyên (1.1) - (1.3) nên dừng lại vì

Định lý 4. Nếu trong vấn đề L 1 không có mức tối đa từ điển, thì tập hợp X* Điểm nguyên của bài toán (1.1) - (1.3) trống.

Bằng chứng. Vì nhiều X vectơ thỏa mãn điều kiện Cây rìu = b, x³ 0, theo giả sử I bị chặn thì tập phương án giải bài toán cũng bị chặn L 1 . Vì vậy, lý do duy nhất khiến bài toán này không có mức tối thiểu về mặt từ điển là vì tập kế hoạch của nó trống. Hãy chứng minh rằng trong trường hợp này tập hợp X* cũng trống rỗng.

Hãy giả sử điều ngược lại, tức là Cái gì X* ¹ Æ, và để x* = (x 1 * , x 2 * , …, x n*) О X*. Theo Định lý 2 ta thấy rằng số lượng

không tiêu cực. Nhưng điều này có nghĩa là vectơ = ( x 1 * , x 2 * , …, x n * , x n+1 *) là kế hoạch nhiệm vụ L 1, mâu thuẫn với điều trên. Định lý đã được chứng minh.

Cho phép x(1) = (x 0 (1), x 1 (1), …, x n(1), x n+1 (1)) - giải pháp cho vấn đề từ điển L 1 . Rời khỏi nhiệm vụ L 1 và vectơ x(1), các vấn đề được xây dựng theo cách tương tự L r, r= 2, 3, …, và nghiệm x(r) Î Â N +1+r nhiệm vụ từ điển tương ứng.

Lưu ý rằng thuật toán Gomori xác định duy nhất chuỗi x(r), r= 0, 1, 2, …, suy ra tính duy nhất của việc chọn S. Chúng ta cũng hãy chú ý đến thực tế là chỉ số S luôn không vượt quá n: 0 s n. Trên thực tế, nếu mọi thứ x j(r) Tại j= 0, 1, 2, …, n là các số nguyên thì từ Định lý 2 suy ra x n +1 (r), x n +2 (r), … - cũng là số nguyên.

Nếu ở một bước nào đó r vectơ

x(r) = (x 0 (r), x 1 (r), …, x n(r), …, x n +r (r))

hóa ra là một số nguyên thì vectơ ( x 0 (r), x 1 (r), …, x n(r)) là nghiệm của bài toán (1.1) - (1.3). Bằng chứng của tuyên bố này là hiển nhiên.

Chuyển đổi từ vectơ x(r) vào vectơ x(r+1) sử dụng thuật toán Gomori được mô tả được gọi là lần lặp lớn, trái ngược với các lần lặp trung gian phương pháp đơn giản kép, được gọi là nhỏ.

Câu hỏi chính liên quan đến thuật toán đầu tiên của Gomori là: có phải luôn luôn có thể thu được một vectơ số nguyên trong một số hữu hạn các lần lặp lớn? x(r).

Chúng ta hãy chứng minh tính hữu hạn của Thuật toán Gomory đầu tiên. Chúng ta sẽ sử dụng ký hiệu sau:

x(0) = (x 0 (0), x 1 (0), …, x n(0));

Ở đâu ( x 1 (0), …, x n(0)) là lời giải cho bài toán từ điển L0, và x(0) = - giá trị tương ứng của dạng tuyến tính (hàm mục tiêu).

y(1) = (x 0 (0), x 1 (0), …, x n(0), x n +1),

vectơ y(1) đóng vai trò là kế hoạch giả được chấp nhận nghiêm ngặt ban đầu khi giải Bài toán L1 bằng phương pháp đơn giản kép ở dạng tọa độ: ` y(1) = (`y 0 (1), `y 1 (1), …, `năm(1), `năm+1 (1)) là vectơ kết quả từ y(1) là kết quả của lần lặp đầu tiên (nhỏ) của phương pháp đơn giản kép ở dạng tọa độ.

Ký hiệu được giới thiệu tương tự

x(r), y(r + 1), `y(r + 1), r = 1, 2, …

Từ các tính chất của phương pháp đơn giản kép ở dạng tọa độ, ta suy ra

y(r) >`y(r) ³ x(r).

Bổ đề 1. Cho phép S- chỉ số tối thiểu mà số xs(0) không phải là số nguyên. Sau đó

Bằng chứng. Vì từ (3.9) nên suy ra y(1) >`y(1) thì có thể xảy ra hai trường hợp:

Trong trường hợp 1, phát biểu của bổ đề được thỏa mãn một cách tầm thường bằng định nghĩa về thứ tự từ điển.

Xét trường hợp 2. Theo quy tắc của phương pháp đơn hình kép, ở lần lặp (nhỏ) đầu tiên để giải bài toán L 1 biến có thể bắt nguồn từ các biến cơ bản x n+1 vì trong vectơ y(1) x j(0) ³ 0, jồ, x n +1 < 0. Пусть kО w là một chỉ số sao cho

Cho bât ki ai jО w, nếu -(a sj} < 0. По правилам симплексного метода в число базисных вводится переменная xk.

Trường hợp 2 chỉ có thể xảy ra với điều kiện b tôi = 0, Tôi = 0, 1, 2, …, S- 1. Bởi vì x(0) - kế hoạch giả được chấp nhận nghiêm ngặt của nhiệm vụ L 0 , thì tất cả các cột của nó b j, jО w, bảng đơn B(0) tích cực về mặt từ điển; đặc biệt là b k> 0 . Do đó tọa độ b sk của cột này phải không âm. Lưu ý rằng b sk= một sk(tức là 0 £ S £ N Và SО w), theo điều kiện (3.10) số a sk- không bằng không. Đó là lý do tại sao

Một sk> 0 và a sk³(a sk}

Theo công thức biến đổi bảng đơn, ta có

Nhớ rằng xs(0) = as0, ta có:

.

Khi tính đến (3.11), chúng ta có được ước tính sau:

Bổ đề đã được chứng minh.

Bình luận. Nếu như vấn đề ban đầu(1.1) - (1.3) được chấp nhận thì theo hệ quả của Định lý 2 tồn tại chỉ số k thỏa mãn điều kiện (3.10).

Kết quả. Tỷ lệ hợp lý

Có hiệu lực tại r= 1, bất đẳng thức này suy ra từ bổ đề và bất đẳng thức thứ hai (3.9). Để có được tuyên bố này một cách tùy ý r, bạn cần tận dụng thực tế là năm tháng(r) = x j(r) ở mức 0 £ j £ N, và bất đẳng thức y(r) ³ x(r) trong (3.9).

Định lý 5. Nếu Giả định I và II được thỏa mãn thì thuật toán đầu tiên của Gomori chỉ yêu cầu một số hữu hạn các lần lặp lớn.

Để kiểm chứng tính đúng đắn của định lý, cần phải chỉ ra rằng đối với một số r vectơ x(r) = (x 0 (r), x 1 (r), …, x n +r (r)) - số nguyên. Để làm được điều này, chỉ cần chứng minh bản chất nguyên của vectơ ( x 0 (r), x 1 (r), …, x n(r)), vì từ Định lý 2 nên mọi số x n +1 (r), x n +2 (r), …, x n +r (r) cũng là toàn bộ. Chúng ta cũng hãy nhớ lại rằng chỉ số tối thiểu s mà số xs(r) không nguyên luôn không vượt quá n: 0 £ s £ n. Trước khi chuyển sang chứng minh chính, ta chứng minh bổ đề sau:

Bổ đề 2. Cho bât ki ai j, 0 £ j £ N, có một số như vậy Rj, lúc đó r ³ Rj tất cả các số x j(r) - số nguyên và bằng cùng một số nguyên x j(Rj).

Bằng chứng. Cho phép S, 0 £ S £ N, - chỉ số tối thiểu mà tuyên bố của Bổ đề không giữ được. Hãy biểu thị

Trong trường hợp khi S= 0, đặt R = 0.

Cho phép r, tôi- những chỉ số đó R £ r£ l, và những con số xs(r), xs(tôi) - không toàn bộ. Hãy để chúng tôi chứng minh điều đó sau đó [ xs(r)] > [xs(tôi)]. Hợp lệ theo định nghĩa S chúng ta có

Trong trường hợp này S- chỉ số tối thiểu mà số đó xs(r) - số nguyên. Theo hệ quả tất yếu của Bổ đề 1 ta có [ xs(r)] ³ xs(tôi).

Xem xét rằng xs(tôi) không phải là số nguyên nên ta có xs(tôi) > [xs(tôi)], từ đó ta thu được mệnh đề mong muốn. Vì nhiều X phương án bài toán (1.1) - (1.3) bị giới hạn thì giá trị nào cũng bị giới hạn xs(r), 0 £ S £ N, r= 1, 2,… . Do đó, một chuỗi vô hạn các bất đẳng thức có dạng [ xs(r)] > [xs(tôi)] > ... không thể tồn tại, và do đó, trong dãy xs(r), r= 0, 1, …, không thể có vô số số không nguyên. Người ta chứng minh tương tự rằng không thể có vô số số nguyên khác nhau trong dãy này.

Bổ đề đã được chứng minh.

Hãy quay lại chứng minh định lý. Cho phép

những con số ở đâu Rj xuất hiện trong công thức của Bổ đề 2. Khi đó, theo bổ đề này, tất cả các số x j(R), 0 £ j £ N, - trọn. Từ Định lý 2 chúng ta thu được rằng vectơ x(R) - số nguyên. Do đó, thuật toán Gomory không yêu cầu nhiều hơn R lần lặp lại.

Định lý đã được chứng minh.

3.5 Những lưu ý khi triển khai thực tế thuật toán Gomori lần thứ nhất

Tại triển khai thực tế Trong thuật toán Gomori đầu tiên, một vấn đề quan trọng là sự gia tăng số lượng các hạn chế, dẫn đến sự gia tăng kích thước của các bảng đơn giản. Gomori đã đề xuất một cách để loại bỏ nhược điểm này của thuật toán như sau.

) Trong quá trình giải bài toán L r Sử dụng phương pháp đơn hình kép, ở mỗi lần lặp nhỏ cần sử dụng quy tắc suy luận tinh tế từ số vectơ cơ sở để giải bài toán lập trình tuyến tính phương pháp đơn giản: nếu cột đầu tiên của bảng đơn giản có một số phần tử âm b Tôi 0 (= x tôi), Tôi =1, 2, …, N, …, N + r, thì biến có số lượng tối thiểu phải bị loại khỏi số biến cơ bản.

) Nếu trong lần lặp nhỏ tiếp theo khi thực hiện tác vụ L r tất cả các biến chính x 1 , x 2 , …, x n không âm thì tiếp tục áp dụng phương pháp đơn hình kép vào bài toán L r nên dừng lại, mặc dù thực tế là nó có thể chưa đạt đến mức từ điển tối đa. Nếu tất cả các biến x j, j = 1, 2, …, N, hóa ra là số nguyên thì theo Định lý 2 tất cả các biến phụ x n +k , k = 1, 2, …, r, là số nguyên và không âm. Điều này có nghĩa, như đã biết, vectơ ( x 0 , x 1 , x 2 , … , x n) là nghiệm của bài toán số nguyên ban đầu. Nếu không, chúng ta chuyển sang một bước lặp lớn mới.

) Hàng bảng đơn tương ứng với biến phụ x n +r, bị xóa ngay khi biến x n +rđược tuyên bố là không cơ bản. Chúng ta hãy nhớ lại rằng điều này xảy ra ở bước lặp nhỏ đầu tiên của việc giải quyết vấn đề. L r.

) Nếu trong quá trình giải quyết vấn đề L r Biến đổi x n +r lại rơi vào số cơ bản thì hàng tương ứng không được khôi phục.

Rõ ràng là khi tuân theo quy tắc 3), 4), kích thước của bảng đơn trong thuật toán Gomori đầu tiên không tăng - mỗi bảng chứa N+ 2 dòng tương ứng với các biến chính x 0 , x 1 , … , x n và biến phụ hiện tại x n +r tại thời điểm giới thiệu) và N - tôi+1 cột (vì số N - tôi các biến không cơ bản không thay đổi).

) Ở lần lặp lại nhỏ đầu tiên của việc giải quyết vấn đề L r+1 được chọn làm biến xuất phát từ cơ sở x n +r+1, mặc dù thực tế là giá trị của các biến phụ khác tại thời điểm này cũng có thể âm.

Lưu ý rằng quy tắc 5) thực sự là dư thừa, vì khi quy tắc 3) và 4) được đáp ứng, chúng ta không biết gì về giá trị của các biến còn lại x n +1 , …, x n +r tại thời điểm chuyển sang nhiệm vụ L r +1 . Quy tắc này chỉ được đánh dấu để làm nổi bật sự khác biệt giữa các thuật toán đang được xem xét.

Lưu ý rằng khi sử dụng quy tắc 2) trình tự kết quả x ’ (r) có thể không phải là mức tối đa từ điển của bài toán L r, vì giá trị của một số biến phụ có thể âm.

Tuy nhiên, để thống nhất x ’ (r), r= 0, 1, 2, …, thu được bằng cách sử dụng quy tắc 1) và 2), một thuộc tính quan trọng được giữ nguyên: chuỗi này là duy nhất.

Chỉ còn cách chứng minh rằng khi sử dụng quy tắc 1) - 4) thuật toán Gomori vẫn hữu hạn, vì tính hữu hạn của nó sẽ dẫn đến mục tiêu - tìm nghiệm nguyên cho bài toán (1.1) - (1.3). Thật vậy, tính hữu hạn của số R số lần lặp lớn có nghĩa là vectơ x ’ (R) số nguyên.

Trước tiên, chúng ta hãy lưu ý rằng khi sử dụng quy tắc 2) số lần lặp lại nhỏ để giải quyết vấn đề L r tất nhiên - không cần nhiều hơn mức cần thiết để tìm mức tối đa từ điển của nó.

Định lý 6. Dãy số x'(r) phát sinh trong quá trình áp dụng thuật toán Gomori, quy tắc tinh chỉnh 1) - 4), là hữu hạn.

Bằng chứng. Lưu ý rằng trong chứng minh Định lý 5 về tính hữu hạn của chuỗi x(r), chỉ có hai trường hợp được sử dụng để điều chỉnh sự xuất hiện của chuỗi này: phương pháp xây dựng phép cắt đúng và thực tế là trong bất kỳ bảng đơn hiện tại nào tất cả các cột b j, jÎw, mang tính tích cực về mặt từ điển. Vì vậy, việc xóa dòng tương ứng với biến phụ chỉ có thể ảnh hưởng đến trường hợp sau. Tuy nhiên, điều này không thể xảy ra, như được chỉ ra trong bổ đề sau.

Bổ đề 3. Trong bất kỳ bảng đơn nào phát sinh trong thuật toán Gomori, được tinh chỉnh theo quy tắc 1) - 4), cho bất kỳ cột nào

có sự bất bình đẳng

Bằng chứng. Chúng ta hãy giả sử rằng phát biểu của bổ đề không đúng đối với một số kО w. Vì b k, thì giả định này có nghĩa là

Theo định nghĩa bảng đơn dạng tọa độ, ta có

Cho bât ki ai x Î Rn +1+r, nếu phát biểu của bổ đề bị vi phạm trong quá trình giải bài toán L r. Công thức (3.13) xét đến (3.12) có nghĩa là sự thay đổi giá trị của biến xk không ảnh hưởng đến giá trị x tôi, Tôi = 0, 1, 2, …, N. Nói cách khác, với cùng một tập giá trị x tôi, 0£ Tôi£ N, Biến đổi xk có thể nhận một giá trị tùy ý. Trước tiên, nó theo sau rằng k ³ N+ 1, và thứ hai, giả định được chấp nhận (3.13) là không chính xác, vì giá trị của bất kỳ biến phụ nào xk, k ³ N+ 1 như sau từ (3.7), được xác định duy nhất bởi giá trị của các biến chính.

Vì việc xóa hàng tương ứng với biến phụ không ảnh hưởng tới tính chất của cột b j, jÎ w, tích cực về mặt từ vựng thì những dòng này không cần thiết chút nào. Thật vậy, có tính đến quy tắc 1) - 2) biến x n +r, đã trở thành một trong những biến cơ bản, vẫn cơ bản cho đến khi kết thúc phép tính và dòng của nó không bắt buộc phải xác định biến được đưa vào cơ sở theo các quy tắc của phương pháp đơn hình.

Do đó, các phần tử hàng tương ứng với biến x n +r, không tham gia vào các công thức của phương pháp đơn hình kép để tính giá trị của tất cả các biến khác.

Vì, như đã lưu ý, chỉ số Sđiều chỉnh sự hình thành điểm cắt chính xác không vượt quá N, 0 £ S £ N, thì các biến phụ trợ không cần thiết cho các mục đích này.

4. Thực hiện trên máy tính

Trong này dự án khóa học Chương trình được thiết kế để tìm giải pháp cho bài toán quy hoạch tuyến tính số nguyên bằng phương pháp Gomori.

Mô-đun phần mềm sử dụng thuật toán được mô tả trong phần lý thuyết, có tính đến các nhận xét về ứng dụng thực tế phương pháp được thực hiện bởi Gomori.

Việc nhập dữ liệu vào mô-đun chương trình được thực hiện từ một tệp. Kết quả của chương trình có thể được xuất ra tệp, màn hình hoặc máy in. Định dạng tập tin đầu vào:

…

…

…

…

Ở đâu N- số lượng biến, tôi- số lượng hạn chế, c 1 , c 2 , … , c n- các hệ số của dạng tuyến tính cực đại, một ij- phần tử ma trận A, b j- thành phần vectơ b. A, b - mô tả các hạn chế [xem. (1.2)].

Tệp đầu vào ví dụ:

2 5 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

Thư mụ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.

Belousova G.S. Lập trình tuyến tính. Hướng dẫn. -Krasnoyarsk: Khoa học, 1975. -107 tr.

Kuznetsov Yu.N. và những thứ khác Lập trình toán học: Sách giáo khoa. - Tái bản lần thứ 2, có sửa đổi. và bổ sung -M.: trường sau đại học, 1980. -300 tr.

Ashmanov S.A., Lập trình tuyến tính. M.: Khoa học. 1969. -240 giây

Gabasov R.I. Kirillova F.M., Phương pháp quy hoạch tuyến tính. Minsk: Khoa học. 1977. -174 giây