Ràng buộc Gomori có dạng sau. Vẽ một ràng buộc bổ sung (phần Gomori)

Phương pháp của Gomori để giải các bài toán lập trình số nguyên là phương pháp cắt .

Bản chất của phương pháp này là xây dựng các ràng buộc nhằm loại bỏ các nghiệm không nguyên của bài toán. lập trình tuyến tính, nhưng không cắt bỏ bất kỳ kế hoạch số nguyên nào. Để làm điều này, trước tiên hãy quyết định nhiệm vụ suy yếu quy hoạch tuyến tính mà không tính đến điều kiện của các biến số nguyên.

Nếu nhận được giải pháp của vấn đề lập trình tuyến tính là số nguyên, thì vấn đề Lập trình số nguyên cũng được giải quyết và giải pháp tìm được cũng là tối ưu cho nó. Nếu trong lời giải tìm được của bài toán quy hoạch tuyến tính có một hoặc số lớn hơn các biến không phải là số nguyên, khi đó để tìm nghiệm số nguyên cho bài toán, một ràng buộc tuyến tính mới được thêm vào để loại bỏ các nghiệm không nguyên. Khi tiếp tục giải quyết vấn đề mở rộng bằng phương pháp kép phương pháp đơn giản tính đến ràng buộc này, sẽ thu được một sơ đồ số nguyên.

Để tìm nghiệm số nguyên cho bài toán bằng phương pháp Gomori, thuật toán sau được sử dụng.

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.

Nếu có một số biến cơ sở không nguyên thì để tạo ràng buộc, chúng ta chọn một thành phần của phương án tối ưu với phần phân số lớn nhất (nếu có nhiều biến như vậy thì hãy chọn bất kỳ biến nào).

Biến này tương ứng với một hàng của bảng đơn giản được gọi là đường thực hiện việc cắt (dòng tạo ra ).

Để trình bày phương pháp này, chúng tôi giới thiệu các khái niệm sau. Cho phép Một- số thực.

Dưới Toàn bộ phần một số số MỘTđược hiểu là số nguyên tối đa [ Một], không vượt quá mức này.

Dưới phần phân đoạn một số số MỘT có nghĩa là số không âm nhỏ nhất
sao cho sự khác biệt giữa nó và MỘT Có [ Một] – Toàn bộ phần số).

Đối với biến cơ sở đã chọn với phần phân số lớn nhất chúng ta tìm thấy phần phân đoạn
biến này và phần phân số của tất cả các hệ số của biến Tôi dòng thứ của hệ thống hạn chế
(dây chuyền sản xuất).

Hãy biểu thị
Và
toàn bộ phần của số Và . Giá trị phân số
Và
(
) được định nghĩa như sau

Để làm điều này, một phương trình được viết ra từ hàng sinh của bảng đơn, giả sử rằng phương trình đầu tiên tôi các biến số là cơ bản cho một kế hoạch tối ưu nhất định

hoặc

Chúng ta di chuyển tất cả các phần nguyên của các hệ số theo một hướng, để lại tất cả các phần phân số theo hướng khác:

Bởi vì
<1, то заменяя в правой части
, ta thu được bất đẳng thức chặt chẽ

Vì vế trái của bất đẳng thức phải lấy giá trị nguyên nên điều kiện cần để tính nguyên của nó chỉ có thể được viết dưới dạng sau:

Bất đẳng thức được chuyển đổi thành phương trình bằng cách đưa vào một biến không âm bổ sung và được đưa vào bảng đơn giản tối ưu.

Ta giải bài toán bằng phương pháp đơn hình kép. Nếu phương án tối ưu mới cho bài toán mở rộng là số nguyên thì bài toán được giải. Nếu giải pháp không phải là số nguyên thì bạn cần lặp lại thuật toán phương pháp Gomori cho đến khi thu được giải pháp số nguyên.

Ví dụ. Sử dụng phương pháp Gomori, tìm lời giải cho bài toán lập trình số nguyên trong đó xác định giá trị lớn nhất của hàm số
cho rằng

Giải pháp. Bình đẳng hóa sự bất bình đẳng bằng cách sử dụng các biến phụ trợ X 3 , X 4, ta thu được bài toán quy hoạch tuyến tính ở dạng chính tắc:

Chúng tôi giải quyết vấn đề quy hoạch tuyến tính bằng phương pháp đơn hình, sử dụng quá trình chuyển đổi từng bước từ cơ sở này sang cơ sở khác. Tiến trình giải quyết vấn đề và giải pháp tối ưu thu được được trình bày trong các bảng.

Trong phương án tối ưu đã tìm được, giá trị của biến X 2 bằng một phân số. Chúng ta tìm phần phân số của nó và phần phân số của tất cả các phần tử của dòng chứa biến X 2, cụ thể là:

Bây giờ chúng ta soạn bất đẳng thức Gomori cho các giá trị tìm được của các phần phân số:

.

X 5, chúng ta di chuyển số hạng tự do của phương trình sang vế phải và nhận được một ràng buộc mới:

.

Chúng ta thêm một hàng chứa một ràng buộc mới và một cột chứa một biến mới vào bảng đơn, rồi tiếp tục giải bài toán bằng phương pháp đơn giản kép, vì kế hoạch giả hiện đã được ghi vào bảng.

Lời giải tối ưu thu được cho bài toán mở rộng chứa giá trị không nguyên của biến X 1, vì vậy chúng ta tìm thấy ở dòng này các phần phân số của tất cả các số không nguyên, cụ thể là:

và bất đẳng thức Gomory mới có dạng:

Chúng tôi cân bằng bất đẳng thức Gomori bằng cách sử dụng một biến phụ mới X 6, chúng ta di chuyển số hạng tự do của phương trình sang vế phải và nhận được một ràng buộc mới:
.

Chúng ta thêm nó vào bài toán đang được giải, căn chỉnh nó bằng biến phụ và giải bài toán mở rộng

Như vậy, lời giải tối ưu của bài toán quy hoạch số nguyên đã được tìm ra: Z tối đa= 11 lúc
.

Ghi chú :

Nếu trong quá trình giải quyết bảng đơn một phương trình có thành phần không nguyên sẽ xuất hiện và các hệ số nguyên ở dòng tương ứng của hệ giới hạn
, thì bài toán này không có nghiệm nguyên.

Giới thiệu

Một lớp lớn các bài toán tối ưu hóa ứng dụng sẽ chuyển thành các bài toán quy hoạch tuyến tính số nguyên. Để giải quyết những vấn đề này, các phương pháp cắt được sử dụng rộng rãi, được thiết kế để giải một bài toán số nguyên tổng quát, ghép nó với một số bài toán không nguyên, giải pháp của nó cho phép người ta tìm ra giải pháp.

Phương pháp đầu tiên để giải bài toán quy hoạch tuyến tính số nguyên bằng cách cắt tỉa được đề xuất bởi Gomori và được gọi là thuật toán Gomori.

1. Tuyên bố vấn đề

Phương pháp Gomori được thiết kế để giải các bài toán quy hoạch tuyến tính số nguyên. Khi xem xét phương pháp Gomori, chúng ta sẽ giải bài toán này dưới dạng chính tắc.

1.1 Hình thức kinh điển

Chúng ta sẽ xem xét bài toán lập trình số nguyên chuẩn với N biến và tôiđiều kiện, được bổ sung bởi điều kiện số nguyên:

Ở đâu c = (c 1 , c 2 , … , c n), x = (x 1 , x 2 , … , x n)- vectơ chiều N, - tích vô hướng của chúng (), còn được gọi là hàm mục tiêu, MỘT- ma trận thứ nguyên N´ tôi, b- vectơ cột thứ nguyên tôi.

Điều kiện số nguyên làm phức tạp đáng kể bài toán quy hoạch tuyến tính (1.1), (1.2). Có thể xảy ra trường hợp bài toán (1.1)-(1.3) có phương án (số nguyên) chấp nhận được, hàm mục tiêu bị giới hạn trên tập chấp nhận được nhưng không đạt được cực đại. Ví dụ trong nhiệm vụ:

không có nghiệm số nguyên, trong khi không có điều kiện này thì bất kỳ vectơ nào có dạng đều có thể đóng vai trò là nghiệm

.

Liên quan đến vấn đề trên, khi chứng minh các thuật toán số để giải các bài toán loại (1.1)-(1.3) cần đặt thêm nhiều điều kiện bổ sung. X phương án của bài toán (1.1), (1.2) (không có điều kiện nguyên) bị chặn, tức là khối đa diện.

Từ điều kiện này suy ra tập hợp X* mọi phương án nguyên của bài toán (1.1)-(1.3) đều hữu hạn.. Chúng ta sẽ giả sử rằng mọi hệ số cj, j=1, 2 , …, N, hàm mục tiêu là số nguyên.

Từ điều kiện II, nó tuân theo điều đó đối với bất kỳ kế hoạch số nguyên nào xÎ X* nghĩa<c, x>có thể tối đa hóa hình tuyến tính- một số nguyên. Trong trường hợp này chúng ta nói rằng tính nguyên được đảm bảo hàm mục tiêu.

Mặc dù điều kiện I và II của bài toán (1.1) - (1.3) khá chặt chẽ nhưng chỉ có thể làm suy yếu chúng đi một chút để thu được kết quả cần thiết.

1.2 Rút gọn về dạng kinh điển

Bài toán quy hoạch tuyến tính số nguyên có thể được phát biểu hơi khác so với bài toán đã nêu ở trên. Vì vậy, ví dụ, thay vì điều kiện (1.2), có thể có một dạng hạn chế viết khác

Chúng ta có thể chuyển từ ký hiệu như vậy sang (1.2) bằng cách thêm một biến mới vào mỗi phương trình, khi đó các giới hạn sẽ có dạng

Các biến được thêm vào sẽ có trọng số bằng 0 trong hàm mục tiêu.

Lưu ý rằng để thu được, tùy thuộc vào loại bất đẳng thức, người ta không chỉ cộng mà còn phải trừ một biến tùy theo dấu của bất đẳng thức, có tính đến điều kiện (1.3).

Nếu trong bài toán ban đầu không có biến nào đó x tôiđiều kiện dương không được đáp ứng thì cần thay thế bằng hiệu của hai biến dương mới.

2. Ý tưởng chung về phương pháp cắt

Về cơ bản có khả năng rút gọn nghiệm của bài toán (1.1) - (1.3) để tìm phương án tối ưu cho một số bài toán quy hoạch tuyến tính (không có điều kiện các biến là số nguyên). Cho phép X- một tập hợp đa diện được xác định bởi các điều kiện (1.1), (1.2). Bởi vì X* biểu thị tập hợp tất cả các vectơ số nguyên x*, nằm trong X. Nói cách khác X*được cho bởi các điều kiện (1.1)-(1.3), tức là

A-tu viện X*Í X. Chúng ta sẽ ký hiệu bằng Xz thân lồi của bộ X*. Sau đó XzÍ X.

Như vậy, ta đã liên kết với tập đa diện X một số tập lồi XzÍ X theo quy tắc sau: Xz là tập lồi tối thiểu chứa tất cả các vectơ nguyên từ X.

Theo Giả thiết I, X là một khối đa diện nên tập hợp X* Chắc chắn. Khi đó tập lồi Xz cũng là một khối đa diện, và do đó chúng ta có Xz có thể được xác định bởi một số hữu hạn các bất đẳng thức tuyến tính.

Để làm nổi bật sự khác biệt chính giữa bộ Xz từ nhiều X, ta đưa ra định nghĩa sau.

Định nghĩa 1. Một khối đa diện mà tất cả các điểm cực trị của chúng đều là số nguyên (nghĩa là tất cả tọa độ của chúng đều là số nguyên) được gọi là khối đa diện nguyên.

Rõ ràng là khối đa diện Xz- số nguyên, vì điểm cực trị của nó chỉ là điểm của tập hợp X* kế hoạch số nguyên.

Lý do nghiên cứu sự tuân thủ X® Xz là sự thật đơn giản sau đây.

Định lý 1. Bất kỳ phương án tham chiếu tối ưu nào cho bài toán quy hoạch tuyến tính đều là nghiệm của bài toán (1.1)-(1.3).

Bằng chứng. Hãy` x*- phương án tham chiếu tối ưu của bài toán (2.1), x*- một số nghiệm của bài toán ban đầu (1.1)-(1.3). ` x*Î XzÍ X, Cái đó

<c,`x*> £ <c, x*>.

Mặt khác, kể từ khi x* là một kế hoạch số nguyên, sau đó x*Î X*Í Xz, và do đó

<c,`x*> ³ <c, x*>,

Ở đâu

<c,`x*> = <c, x*>.

Chứng minh định lý đã xong.

Chúng tôi nhấn mạnh rằng Định lý 1 chỉ phát biểu khả năng cơ bản của việc rút gọn lời giải của một bài toán quy hoạch tuyến tính số nguyên về việc tìm kiếm các mặt phẳng tham chiếu của bài toán quy hoạch tuyến tính có dạng (2.1). Khó khăn chính khi sử dụng tính năng này là định nghĩa rõ ràng của khối đa diện. Xz hệ bất đẳng thức tuyến tính để từ đó áp dụng các phương pháp số của quy hoạch tuyến tính để giải bài toán (2.1). Có vẻ như bài toán này khó về mặt tính toán như bài toán ban đầu là tìm thiết kế số nguyên tối ưu.

Mặc dù vậy, ý tưởng “thu hẹp” bộ X hóa ra lại hữu ích và dẫn đến việc tạo ra một số thuật toán để giải các bài toán quy hoạch tuyến tính số nguyên, được gọi là “phương pháp cắt tỉa”.

Hãy để chúng tôi trình bày ý tưởng về phương pháp cắt tỉa. Giả sử rằng chúng ta đã xây dựng được chuỗi ( L r}, r = 0, 1 , 2 , ..., các bài toán quy hoạch tuyến tính, mỗi bài toán được xác định bởi khối đa diện của chính nó Xr và một hàm mục tiêu cho tất cả<c, x>:

Hơn nữa, chuỗi nhiệm vụ này có các thuộc tính sau:

) X 0 = X, I E. BẰNG X 0 lấy tập phương án giải bài toán (1.1), (1.2);

) X r z = X z , r=1,2, …;

) nếu khi giải một bài toán L r vectơ tối ưu kết quả x r * không thỏa mãn điều kiện nguyên thì đó không phải là kế hoạch nhiệm vụ Lr+1, I E. x r *Ï Xr+1.

Lưu ý rằng nếu ở một bước nào đó r vectơ x r *- giải pháp của vấn đề L r- hóa ra là số nguyên thì là nghiệm vấn đề ban đầu(1.1)-(1.3) do tính chất 2) của dãy L r.

Rõ ràng bằng trực giác rằng việc xây dựng tuần tự các nhiệm vụ L r, r=1,2,..., mang lại một ý nghĩa gần đúng của tập hợp Xz với sự giúp đỡ của nhiều người Xr.

Các phương pháp xây dựng trình tự ( L r), đảm bảo tính hữu hạn của quá trình giải bài toán (1.1)-(1.3), được đề xuất lần đầu tiên bởi Gomori.

3. Mô tả phương pháp Gomori

Bây giờ chúng ta hãy xem xét thuật toán Gomori để giải các bài toán quy hoạch tuyến tính nguyên. Phương pháp này thuộc về phương pháp cắt và thực hiện các ý tưởng đã nêu trong đoạn trước.

3.1 Khái niệm cắt đúng và cách thi công đơn giản nhất

Thuật toán quy hoạch tuyến tính của Homer

Hãy để chúng tôi giới thiệu điểm cắt chính xác, làm cơ sở cho nhiều phương pháp số để giải các bài toán quy hoạch tuyến tính số nguyên.

Định nghĩa 2. Cho x* là phương án tối ưu cho bài toán (1.1), (1.2), không phải là số nguyên. Bất bình đẳng

trong đó g = (g 1 , g 2 , …, g N), được gọi là phép cắt đúng nếu thỏa mãn yêu cầu:

a) đối với một vectơ x* sự bất bình đẳng không giữ, tức là x*> > g 0 (điều kiện cắt).

b) nếu x là phương án nguyên của bài toán (1.1), (1.2) (tức là phương án của bài toán (1.1)-(1.3)), thì x- thỏa mãn (3.1) (điều kiện đúng).

Rõ ràng việc cộng bất đẳng thức (3.1) vào điều kiện (1.1), (1.2) sẽ thu hẹp tập chấp nhận được X, trong khi vẫn bảo toàn tất cả các điểm nguyên của nó. Do đó, việc áp dụng nhất quán kỹ thuật này sẽ mang lại phép tính gần đúng nhiều giai đoạn của khối đa diện Xz sử dụng các ràng buộc tuyến tính.

Có hai vấn đề với khái niệm cắt xén thích hợp. Việc đầu tiên trong số này là xây dựng thuật toán chung cắt giảm cho một vấn đề quy hoạch tuyến tính số nguyên tùy ý. Vấn đề thứ hai là xây dựng một điểm cắt chính xác theo cách đảm bảo giải được bài toán (1.1)-(1.3) trong một số bước hữu hạn, tức là. để từ đám đông X mỗi lần các khu vực đủ lớn đều bị cắt bỏ.

Lưu ý rằng yêu cầu thứ hai khá tinh tế. Để xác nhận, hãy xem xét phương pháp xây dựng điểm cắt chính xác do Danzig đề xuất.

Cho phép x*- hỗ trợ phương án tối ưu của bài toán (1.1), (1.2), s và w - danh sách số biến cơ bản và không cơ bản tương ứng với một số cơ sở của phương án x*. Sau đó x j *= 0 tại jôi. Khi tính đến đặc tính này, không khó để xây dựng một điểm cắt chính xác cho thiết kế x* nếu nó không phải là số nguyên: bất đẳng thức có thể đóng vai trò như vậy

Thật vậy, điều kiện cắt được thỏa mãn một cách tầm thường, vì . Điều kiện đúng cũng được thỏa mãn vì nếu x = (x 1,x 2 , …,xn) là phương án nguyên của bài toán (1.1), (1.2) thì giá trị xét đến điều kiện xj ³ 0, jÎ w, chỉ có thể nhỏ hơn đơn vị trong trường hợp khi xj= 0 cho tất cả jÎ w. Nhưng trong trường hợp đó kế hoạch x- tài liệu tham khảo, và cơ sở kế hoạch có thể được lấy làm cơ sở của nó x*. Sơ đồ tham chiếu được xác định duy nhất dựa trên cơ sở của nó, từ đó ta suy ra rằng bất đẳng thức bao hàm x=x *. Tuy nhiên, điều sau là không thể, vì x là một vectơ số nguyên và x* không phải vậy.

Kỹ thuật xây dựng một đường cắt chính xác này, mặc dù đơn giản, hóa ra lại không hiệu quả, vì tính hữu hạn của quá trình giải chỉ được đảm bảo cho một lớp hẹp của các bài toán quy hoạch tuyến tính số nguyên.

Chúng ta hãy mô tả phương pháp xây dựng điểm cắt chính xác do Gomori đề xuất. Đối với một số tùy ý Một, bởi vì [ Một] chúng tôi 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 hàng thứ trong một 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ì xj ³ 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* phương án của bài toán số nguyên (1.1)-(1.3) không rỗ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ị dạng 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 xn+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: xn+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 * , …, xn*) О 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 * , …, xn * , xn+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), …, xn(1), xn+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ứ xj(r) Tại j= 0, 1, 2, …, n là các số nguyên thì từ Định lý 2 suy ra xn +1 (r), xn +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), …, xn(r), …, xn +r (r))

hóa ra là một số nguyên thì vectơ ( x 0 (r), x 1 (r), …, xn(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), …, xn(0));

Ở đâu ( x 1 (0), …, xn(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), …, xn(0), xn +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 xn+1 vì trong vectơ y(1) xj(0) ³ 0, jồ, xn +1 < 0. Пусть kО w là một chỉ số sao cho

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

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 bài toán ban đầu (1.1) - (1.3) được chấp nhận thì theo hệ quả của Định lý 2, chỉ số k thỏa mãn điều kiện (3.10) tồn tại.

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) = xj(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), …, xn +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), …, xn(r)), vì từ Định lý 2 nên mọi số xn +1 (r), xn +2 (r), …, xn +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ố xj(r) - số nguyên và bằng cùng một số nguyên xj(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ố xj(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ỏ, bạn nên sử dụng quy tắc suy luận tinh tế từ số lượng vectơ cơ sở để giải các bài toán quy hoạch tuyến tính bằng phương pháp đơn hình: nếu cột đầu tiên của bảng đơn giản có nhiều 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 , …, xn 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 xj, j = 1, 2, …, N, hóa ra là số nguyên thì theo Định lý 2 tất cả các biến phụ xn +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 , … , xn) 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ụ xn +r, bị xóa ngay khi biến xn +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 xn +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 , … , xn và biến phụ hiện tại xn +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ở xn +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 xn +1 , …, xn +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 của 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 x k 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 x k 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 x k, 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 xn +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 xn +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

Giải thích kinh tế và hình học của vấn đề lập trình số nguyên. Một bài toán cực trị mà các biến chỉ lấy giá trị nguyên được gọi là bài toán lập trình số nguyên.

Trong mô hình toán học của bài toán số nguyên lập trình cả hàm mục tiêu và các hàm trong hệ ràng buộc đều có thể là tuyến tính, phi tuyến và hỗn hợp. Chúng ta hãy giới hạn bản thân trong trường hợp hàm mục tiêu và hệ ràng buộc của bài toán là tuyến tính.

Ví dụ 20.

Người ta đã quyết định lắp đặt thêm thiết bị trong xưởng của doanh nghiệp để phân bổ không gian. Một doanh nghiệp có thể chi 10 nghìn rúp để mua thiết bị và có thể mua hai loại thiết bị. Một bộ thiết bị loại I có giá 1.000 rúp và loại II – 3.000 rúp. Việc mua một bộ thiết bị loại I cho phép bạn tăng sản lượng sản xuất mỗi ca thêm 2 chiếc và một bộ thiết bị loại II – ​​lên 4 chiếc. Biết rằng lắp đặt một bộ thiết bị loại I cần diện tích 2 m2, thiết bị loại II cần diện tích 1 m2, hãy xác định thêm bộ thiết bị đó để có thể tối đa hóa sản lượng sản xuất.

Giải pháp. Hãy tạo một mô hình toán học của vấn đề. Giả sử doanh nghiệp sẽ mua x 1 bộ thiết bị loại I và bộ thiết bị loại II. Khi đó các biến x 1 và phải thỏa mãn các bất đẳng thức sau:

Nếu doanh nghiệp mua số lượng thiết bị quy định thì tổng sản lượng tăng thêm sẽ là

Theo nội dung kinh tế của chúng, các biến x 1 và chỉ có thể lấy giá trị nguyên không âm, tức là.

x 1, – số nguyên. (73)

Vì vậy, chúng ta đi đến những điều sau đây bài toán: tìm giá trị lớn nhất hàm tuyến tính(71) khi điều kiện (70), (72) và (73) được đáp ứng. Vì ẩn số chỉ có thể nhận giá trị nguyên nên bài toán (70) – (73) là bài toán lập trình số nguyên. Vì số ẩn trong bài toán là hai nên lời giải của bài toán này có thể được tìm ra bằng cách giải thích hình học của nó. Để làm được điều này, trước hết chúng ta sẽ xây dựng một đa giác nghiệm của bài toán bao gồm việc xác định giá trị lớn nhất của hàm tuyến tính (71) khi thỏa mãn các điều kiện (70) và (72) (Hình 11). Tọa độ của tất cả các điểm của đa giác nghiệm được xây dựng OAEVS thỏa mãn hệ bất đẳng thức tuyến tính (70) và điều kiện không tiêu cực biến (72). Đồng thời, điều kiện (73), tức là điều kiện chính trực các biến được thỏa mãn bởi tọa độ chỉ có 12 điểm được đánh dấu trong hình. 11. Để tìm điểm có tọa độ xác định nghiệm của bài toán ban đầu, hãy thay đa giác OABCđa giác OKEMNF, chứa tất cả các điểm hợp lệ có tọa độ nguyên và sao cho tọa độ của mỗi đỉnh là số nguyên. Điều này có nghĩa là nếu chúng ta tìm được điểm cực đại của hàm số (71) trên đa giác OKEMNF thì tọa độ của điểm này sẽ xác định phương án tối ưu cho bài toán.

Để làm điều này, chúng ta cũng sẽ dựng một đường thẳng đi qua đa giác nghiệm OKEMNF(số 12 được lấy tùy ý). Chúng ta di chuyển đường đã xây dựng theo hướng của vectơ cho đến khi nó đi qua điểm chung cuối cùng với đa giác đã cho. Tọa độ của điểm này xác định phương án tối ưu và giá trị của hàm mục tiêu tại đó là lớn nhất.

TRONG trong trường hợp nàyđiểm cần tìm là E(1; 3), trong đó hàm mục tiêu lấy giá trị lớn nhất là C nên tọa độ của điểm E xác định phương án tối ưu cho bài toán (70) – (73). Theo phương án này, doanh nghiệp phải mua 1 bộ thiết bị loại 1 và 3 bộ thiết bị loại II. Điều này sẽ cung cấp cho doanh nghiệp những hạn chế hiện có về không gian sản xuất và kinh phí độ phóng đại tối đa sản lượng sản xuất bằng 14 đơn vị. mỗi ca.

Ví dụ 21.

Để thực hiện công việc có thể sử dụng P cơ chế. Hiệu suất Tôi-cơ chế thứ khi thực thi j – công việc thứ đó bằng . Giả sử rằng mỗi cơ chế chỉ có thể được sử dụng cho một công việc và mỗi công việc chỉ có thể được thực hiện bởi một cơ chế, hãy xác định việc phân công các cơ chế cho các công việc đảm bảo năng suất tối đa. Xây dựng mô hình toán học của bài toán.

Giải pháp. Chúng ta hãy giới thiệu một biến x ij có giá trị bằng 1 nếu khi thực hiện thứ-thứ công việc đã sử dụng j – cơ chế thứ, và bằng 0 nếu không. Khi đó các điều kiện để sử dụng mỗi cơ chế chỉ cho một công việc được thể hiện bằng các đẳng thức

(74)

và các điều kiện để thực hiện công chỉ bằng một cơ chế - sự bình đẳng

(75)

Vì vậy, nhiệm vụ là xác định các giá trị như vậy của ẩn số , thỏa mãn hệ phương trình (74) và (75) và điều kiện (76) đạt giá trị cực đại của hàm số

Bài toán được xây dựng là bài toán lập trình số nguyên.

Xác định phương án tối ưu cho bài toán quy hoạch số nguyên. Chúng ta hãy xem xét các bài toán lập trình số nguyên trong đó cả hàm mục tiêu và các hàm trong hệ ràng buộc đều là tuyến tính. Về vấn đề này, chúng tôi xây dựng bài toán quy hoạch tuyến tính cơ bản trong đó các biến chỉ có thể lấy giá trị nguyên. Nói chung, bài toán này có thể viết như sau: tìm giá trị lớn nhất của hàm số

trong những điều kiện

(79)

– toàn bộ (81)

Nếu bạn tìm lời giải của bài toán (78) – (81) bằng phương pháp đơn hình thì nó có thể là số nguyên hoặc không (một ví dụ, nghiệm của nó luôn là số nguyên, là vấn đề vận chuyển). Trong trường hợp tổng quát, để xác định phương án tối ưu cho bài toán (78) – (81) cần có các phương pháp đặc biệt. Hiện nay có nhiều phương pháp như vậy, trong đó phương pháp nổi tiếng nhất là Phương pháp Gomori, dựa trên phương pháp đơn hình được mô tả ở trên.

Phương pháp Gomori. Việc tìm lời giải cho bài toán lập trình số nguyên bằng phương pháp Gomori bắt đầu bằng việc xác định phương án tối ưu của bài toán (78) – (80) bằng phương pháp đơn hình mà không tính đến chính trực biến. Khi kế hoạch này được tìm thấy, các thành phần của nó sẽ được xem xét. Nếu không có phân số nào giữa các thành phần thì phương án tìm được là phương án tối ưu cho bài toán quy hoạch số nguyên (78) – (81). Nếu trong phương án tối ưu của bài toán (78) – (80) biến lấy giá trị phân số thì bất đẳng thức được cộng vào hệ phương trình (79)

(82)

và tìm lời giải cho bài toán (78) – (80), (82).

Trong bất đẳng thức (82) và – số lượng ban đầu được chuyển đổi và giá trị của chúng được lấy từ bảng đơn giản cuối cùng và – phần phân số của số (phần phân số của một số nhất định a là số không âm nhỏ nhất b sao cho sự khác biệt giữa MỘT Và b có một tổng thể). Nếu trong phương án tối ưu của bài toán (78) – (80) các giá trị phân số nhận nhiều biến thì bất đẳng thức bổ sung (82) được xác định phân số lớn nhất phần.

Nếu trong sơ đồ tìm được của bài toán (78) – (80), (82) các biến lấy giá trị phân số thì một ràng buộc bổ sung lại được thêm vào và quá trình tính toán được lặp lại. Thực hiện một số lần lặp hữu hạn, người ta có thể đạt được phương án tối ưu cho bài toán lập trình số nguyên (78) – (81) hoặc thiết lập tính không giải được của nó.

Nếu yêu cầu chính trực(81) chỉ áp dụng cho một số biến, khi đó những bài toán như vậy được gọi là một phần số nguyên. Giải pháp của họ cũng được tìm thấy bằng cách giải quyết các vấn đề một cách tuần tự, mỗi vấn đề được lấy từ vấn đề trước đó bằng cách sử dụng phần giới thiệu hạn chế bổ sung. Trong trường hợp này, hạn chế như vậy có dạng

được xác định từ các quan hệ sau:

1) for , có thể nhận các giá trị không nguyên,

(84)

2) for , chỉ có thể lấy giá trị số nguyên,

(85)

Từ những điều trên, quy trình xác định phương án tối ưu cho bài toán lập trình số nguyên bằng phương pháp Gomori bao gồm các bước sau: những giai đoạn chính:

1. Dùng phương pháp đơn hình tìm lời giải của bài toán (78) – (80) mà không xét đến yêu cầu chính trực biến.

2. Tạo thêm ràng buộc cho biến trong phương án tối ưu của bài toán (78) – (80) có phân số tối đa giá trị và trong phương án tối ưu, bài toán (78) – (81) phải là số nguyên.

3. Sử dụng phép đối kép, tìm lời giải cho bài toán phát sinh từ bài toán (78) – (80) do bổ sung thêm một ràng buộc.

4. Nếu cần, hãy tạo một ràng buộc bổ sung khác và tiếp tục quá trình lặp lại cho đến khi đạt được phương án tối ưu cho bài toán (78) – (81) hoặc tính không thể giải được của nó được thiết lập.

Ví dụ 22.

Sử dụng phương pháp Gomori để tìm giá trị lớn nhất của hàm số

cho rằng

(87)

– toàn bộ (89)

Giải pháp.Để xác định phương án tối ưu cho bài toán (86) – (89), trước tiên ta tìm phương án tối ưu cho bài toán (86) – (88) (Bảng 22).

Bảng 22

		Cb	R 0

Như có thể thấy từ bảng. 22, tìm được phương án tối ưu bài toán (86) – (88) không phải là phương án tối ưu cho bài toán (86) – (89), vì hai thành phần và có giá trị không nguyên. Hơn nữa, các phần phân số của những số này bằng nhau. Do đó, một ràng buộc bổ sung được đưa ra cho một trong các biến này. Ví dụ, chúng ta hãy tạo một ràng buộc như vậy cho biến Từ bảng đơn cuối cùng (Bảng 22), chúng ta có

Như vậy, vào hệ ràng buộc của bài toán (86) – (89) ta cộng bất đẳng thức

hoặc

Bảng 23

		Cb	R 0

Bây giờ chúng ta tìm giá trị lớn nhất của hàm (86) khi các điều kiện (87), (88) và (90) được đáp ứng (Bảng 23).

Từ Bảng 23 có thể thấy bài toán quy hoạch số nguyên ban đầu có phương án tối ưu P Trong kế hoạch này, giá trị của hàm mục tiêu bằng . Hãy để chúng tôi đưa ra một giải thích hình học của giải pháp cho vấn đề. Vùng lời giải khả thi của bài toán (86) – (88) là một đa giác OABCD(Hình 12). Từ hình. 12 có thể thấy hàm mục tiêu đạt giá trị cực đại tại điểm VỚI(19/2; 2/7), tức là Cái gì X =(19/2; 7/2; 0; 0; 34) là phương án tối ưu. Điều này được thể hiện trực tiếp từ Bảng 22. Vì X= (19/2; 7/2; 0; 0; 34) không phải là phương án tối ưu cho bài toán (86) – (89) (là số và là phân số), khi đó đưa ra ràng buộc bổ sung. Loại trừ nó và thay thế các giá trị tương ứng từ các phương trình của hệ ràng buộc (87), chúng ta thu được một điểm cắt khỏi đa giác OABCD Tam giác EFC.

Như có thể thấy từ hình. 12, vùng có lời giải khả thi cho bài toán tìm được là một đa giác OABEFD. Tại điểm E(9; 4) của đa giác này, hàm mục tiêu của bài toán này lấy giá trị lớn nhất. Vì tọa độ của điểm E là các số nguyên và ẩn số, lấy giá trị nguyên khi thay các giá trị vào phương trình (87), khi đó là phương án tối ưu cho bài toán (86) – (89). Điều này cũng theo Bảng 23.

Ví dụ 23.

Sử dụng phương pháp Gomori, tìm lời giải bài toán xác định giá trị lớn nhất của hàm số

trong những điều kiện

- trọn. (94)

Đưa ra cách giải thích hình học của lời giải cho bài toán.

Giải pháp. Chúng ta viết lại bài toán đã nêu như sau: tìm giá trị lớn nhất của hàm số

trong những điều kiện

(96)

- trọn. (98)

Bài toán (95) – (98) là số nguyên một phần, vì các biến và có thể lấy giá trị không nguyên.

Bằng phương pháp đơn hình ta tìm được nghiệm của bài toán (95) – (97) (Bảng 24).

Bảng 24

		Cb	R 0
		Cb	R 0
							–1/3 không phải là phương án của bài toán (95) – (98), vì biến

Trong các bài toán lập trình số nguyên, trái ngược với các bài toán lập trình tuyến tính, một hạn chế bổ sung được đưa ra đối với các biến: chúng chỉ có thể lấy các giá trị nguyên.

Trong một số bài toán, ví dụ như loại hình vận chuyển, điều kiện này được thỏa mãn một cách tự động nếu dữ liệu nguồn (số lượng hàng hóa được gửi và nhận) được biểu thị bằng số nguyên. Nhưng trong một bài toán quy hoạch tuyến tính tổng quát, các phương pháp thông thường để giải các giá trị nguyên không đảm bảo đại lượng ban đầu là số nguyên hay phân số.

Trong ký hiệu toán học nhiệm vụ chung lập trình số nguyên trông như thế này:

tối đa hóa

trong những điều kiện

xj≥ 0, xj - trọn.

Các bài toán quy hoạch tuyến tính kinh tế thường yêu cầu nghiệm số nguyên. Điều này áp dụng cho các bài toán trong đó các biến chỉ số lượng đơn vị sản phẩm, thiết bị, công nhân không thể chia được (bài toán phân bổ nhiệm vụ sản xuất tốt nhất giữa các doanh nghiệp, bài toán tối ưu hóa chương trình sản xuất doanh nghiệp riêng lẻ, các vấn đề về tải thiết bị tối ưu, v.v.). Thông thường, những vấn đề như vậy được giải quyết bằng phương pháp đơn giản thông thường với việc làm tròn các giá trị thu được sau đó. biếnđến số nguyên. Nhưng trong trường hợp này, bạn chỉ có thể nhận được một số giá trị gần đúng với sơ đồ số nguyên thực sự tối ưu.

Trong một nhóm bài toán quy hoạch tuyến tính khác, các đại lượng cần xác định là năng lực sản xuất đáp ứng một cách hiệu quả nhất một nhu cầu nhất định. Vì “người vận chuyển” năng lực sản xuất là các doanh nghiệp riêng lẻ, các bộ phận thiết bị không thể chia cắt, v.v., nên những vấn đề này cũng giảm xuống thành các vấn đề quy hoạch tuyến tính số nguyên.

Các vấn đề về cắt hợp lý vật liệu có kích thước (nhiệm vụ giảm thiểu lãng phí) cũng có giá trị nguyên, vì các biến trong đó, theo quy luật, chỉ ra số lượng khoảng trống ban đầu được cắt theo cách này hay cách khác.

Trong tất cả các vấn đề đã đề cập, có thể tìm thấy giải pháp phương pháp thông thường lập trình tuyến tính với sự điều chỉnh tiếp theo và thu được một sơ đồ số nguyên ít nhiều gần với sơ đồ tối ưu. Nhưng có những vấn đề mà giải pháp không nguyên là vô nghĩa. Chúng bao gồm các bài toán lựa chọn trong đó các giá trị số của các biến chỉ dùng để xác định một phương án thay thế (“hoặc-hoặc”, “có-không”).

Các mô hình lựa chọn số nguyên bao gồm một số vấn đề về lập kế hoạch vận hành, ví dụ, các vấn đề về trình tự tối ưu để đưa các sản phẩm (bộ phận) khác nhau vào sản xuất. Giả sử bạn cần xác định thứ tự khởi động N các bộ phận, mỗi bộ phận được xử lý tuần tự trên một số máy. Biến x ij bằng một nếu phần j phải được chạy sau phần Tôi và bằng 0 - trong tất cả các trường hợp khác. Đối với mỗi cố định j , giống như đối với mọi người Tôi , chỉ một trong N các biến có thể bằng một, do đó các ràng buộc của bài toán bao gồm:

Tổng thời gian xử lý của tất cả các bộ phận trên máy thuộc nhóm này được giảm thiểu. Một giải pháp không nguyên cho một vấn đề như vậy là vô nghĩa.

Có một số phương pháp để giải các bài toán lập trình số nguyên. Biết tốt nhất Phương pháp Gomori, dựa trên việc sử dụng phương pháp đơn giản.

Hãy xem xét khái niệm toán học: sự phù hợp số, trọn Và phần phân số của một số. Con số MỘT phù hợp với số b nếu và chỉ khi sự khác biệt a – b là một số nguyên. Sự phù hợp được biểu thị bằng ba đường ngang ( ≡ ); Như vậy, MỘT ≡ b , Nếu như a – b là một số nguyên.

Ví dụ: 5 / 3 ≡ 2 / 3 , bởi vì 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , bởi vì - 1 / 3 - 2 / 3 = 1.

Tất cả các số nguyên đều bằng nhau và bằng 0. Các phần tử không nguyên có thể được biểu diễn dưới dạng tổng của phần nguyên và phần phân số của số MỘT = [Một ] + {Một ). Dấu ngoặc vuông có nghĩa là lấy phần nguyên của số nằm trong chúng, dấu ngoặc nhọn có nghĩa là lấy phần phân số của số.

Phần nguyên của một số MỘT được gọi là số nguyên lớn nhất [ Một ], không vượt quá MỘT .

Phần phân số của một số MỘT được định nghĩa là số không âm nhỏ nhất ( Một ), đồng dạng với số MỘT . Phần phân số của một số MỘT bằng với sự khác biệt giữa số MỘT và toàn bộ phần của nó: ( Một }=MỘT - [Một ]

Ví dụ, đối với MỘT = 2 1 / 3 [Một ]= 2 (a) = 1 / 3

cho một = - 2 1 / 3 [Một ]= -3 (a) = 2 / 3

Tính chất của sự đồng đẳng số:

1. Nếu MỘT ≡ b , Cái đó ( MỘT } = {b }.

2. {MỘT +b } = {MỘT } + {b }.

3. Nếu N là một số nguyên thì với mọi MỘT

à ≡ {không có } ≡ N {MỘT }.

Khi giải các bài toán lập trình số nguyên bằng phương pháp Gomori, giai đoạn đầu tiên trùng với phép tính thông thường bằng thuật toán đơn hình. Giải pháp thu được trong nhìn chung sẽ thỏa mãn tất cả các điều kiện của bài toán, ngoại trừ yêu cầu về số nguyên (tất nhiên là có thể thu được nghiệm số nguyên ở giai đoạn đầu tiên). Nếu trong số các giá trị của các biến trong phương án tối ưu (điểm A trong Hình 13) có các giá trị phân số, thì một ràng buộc bổ sung sẽ được đưa ra, như thể “cắt bỏ” phần phân số của giải pháp (dòng 1 trong Hình 13), nhưng vẫn giữ nguyên hiệu lực tất cả các hạn chế của bài toán cần thỏa mãn phương án tối ưu. Một ràng buộc bổ sung được thêm vào các ràng buộc ban đầu của bài toán và thủ tục đơn hình lại được áp dụng cho hệ thống mở rộng. Nếu giải pháp tối ưu lại không phải là số nguyên (điểm B trong Hình 13), thì một ràng buộc bổ sung khác sẽ được thêm vào (dòng 2 trong Hình 13) và quá trình tính toán được lặp lại. Thuật toán cho phép chúng ta đi đến một giải pháp số nguyên tối ưu (nếu nó tồn tại) trong một số bước hữu hạn (điểm C trong Hình 13).

Cơm. 13. Phương pháp cắt Gomori

Ví dụ giải một bài toán lập trình số nguyên. Để mua thiết bị mới nơi sản xuấtđược phân bổ 20 đơn vị tiền tệ. Thiết bị phải được đặt trên diện tích không quá 38 m2. Doanh nghiệp có thể đặt hàng hai loại thiết bị: máy loại A mạnh hơn có giá 5 đơn vị tiền tệ, yêu cầu diện tích sản xuất 8 m 2 (bao gồm cả lối đi) và cung cấp năng suất 7 nghìn đơn vị sản xuất mỗi ca; Máy kém mạnh hơn loại B có giá 2 đơn vị tiền tệ, chiếm diện tích 4 m 2 và sản xuất 3 nghìn đơn vị sản xuất mỗi ca.

Hãy ký hiệu bằng X 1 số xe mua từ A trở đi X 2 - số ô tô mua B, ta thu được điều kiện toán học của bài toán:

tối đa hóa 7x 1 + 3x 2 → tối đa

trong điều kiện: 5x 1 + 2x 2 20

8x1 + 4x2 38

x 1, x 2 ≥ 0 (số nguyên).

Với sự trợ giúp của các biến bổ sung x 3 và x 4, các bất đẳng thức ban đầu được chuyển thành phương trình (rút gọn thành hình thức kinh điển):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

Nếu các biến chính x 1 và x 2 là số nguyên thì ngay lập tức theo phương trình, các biến x 3 và x 4 chỉ có thể nhận giá trị nguyên.

Vấn đề được giải quyết trước tiên mà không tính đến yêu cầu về số nguyên.

Một bảng đơn có lượt xem tiếp theo:

Nền tảng	VỚI	Kế hoạch					θ
X 1	X 2	X 3	X4
X 1 → X 3							20/5=4 phút
X4							38/8=4,75
f(x) = 0	-7	-3
X 1				2/5	1/5		4:2/5=10
X 2 → X 4				4/5	-8/5		6:4/5=7,5 phút
f(x) =28		-1/5	7/5
X 1						-1/2
X 2		7,5			-2	5/4
f(x) = 29,5				1/4

Trong phương án tối ưu X 1 = 1, X 2 = 7,5; cực đại của hàm mục tiêu là 29,5. Như vậy cần mua 1 máy loại A và 7 máy loại B (không đủ tiền hoặc không gian cho 8 máy) thì khối lượng sản xuất sẽ là f(x) = 7 × 1 + 3 × 7 = 28 nghìn đơn vị sản xuất.

Hãy tìm nghiệm số nguyên bằng phương pháp Gomori. Đối với biến X2, đã nhận được giá trị không nguyên trong kế hoạch, chúng ta soạn phương trình sau, theo trực tiếp từ bảng đơn đã cho:

7,5 = X 2 – 2X 3 + 1,25X 4.

X 2 = 7,5 + 2X 3 – 1,25X 4.

Rõ ràng, phương trình này cũng phải đúng đối với một nghiệm nguyên có thể chấp nhận được của bài toán.

Vì X 2 là số nguyên nên biểu thức ở vế phải của phương trình cũng là số nguyên; do đó, giá trị của vế phải của phương trình này bằng 0:

7,5 + 2Х 3 – 1,25Х 4 ≡ 0,

–2Х 3 + 1,25Х 4 ≡ 7,5.

Với các tính chất đồng đẳng ở trên và thực tế là X 3 và X 4 là số nguyên, biểu thức này có thể được chuyển đổi thành biểu thức sau:

(-2)X3 + (1,25)X4 ≡ {7,5} ;

từ đây chúng tôi nhận được:

0,25X4 ≡ 0,5.

Vì X 4 là số nguyên không âm nên ta có:

0,25X 4 = 0,5, hoặc 1,5, hoặc 2,5, ...;

kể từ đây,

0,25X4 ≥ 0,5.

Bất đẳng thức kết quả được chuyển đổi thành một phương trình và được thêm vào hệ thống gốc các ràng buộc, hiện chứa ba phương trình sau:

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0,25x4 – x 5 = 0,5.

Bằng cách lặp lại quá trình giải bằng phương pháp đơn hình đối với hệ ràng buộc mở rộng, chúng ta thu được một phương án tối ưu mới trong đó giá trị của các biến có trong cơ sở bằng: X 1 = 2; X2 = 5; X 4 = 2 (diện tích trống còn lại).

Do đó, đã thu được lời giải số nguyên tối ưu cho bài toán: theo những hạn chế này, năng suất tối đa (29 nghìn đơn vị sản xuất) được đảm bảo bằng cách mua 2 máy loại A và 5 máy loại B.

BÀI THỰC HÀNH

PHƯƠNG PHÁP CHI NHÁNH VÀ RIÊNG

Phương pháp này có thể được áp dụng để giải các bài toán quy hoạch rời rạc nguyên toàn phần và một phần.

Hãy xem xét mô hình

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

Giả sử rằng với mỗi biến số nguyên, chúng ta có thể chỉ định giá trị trên và Giơi hạn dươi, tất nhiên, trong đó nó chứa đựng giá trị tối ưu

Hj `X j ` Vj ; j=1,2,…,k,…,n.

Thường xuyên hj = 0, nhưng điều kiện này không cần thiết. Bài toán được giải bằng phương pháp đơn hình. Nếu như Xk lấy các giá trị phân số, chúng tôi tin rằng lời giải tối ưu cho bài toán sẽ thỏa mãn ràng buộc tuyến tính X k ≤ D k hoặc ràng buộc tuyến tính Xk ≤ Dk + 1 , Ở đâu Dk =[Xk ] – số nguyên gần nhất tính từ giá trị Xk ; Dk + 1 – số nguyên gần nhất ở mặt lớn từ Xk . trong đó H j ≤ D k ≤ V j – 1 . Sau đó, cần phải giải một số bài toán quy hoạch tuyến tính bằng phương pháp đơn hình:

MỘT.

TRONG.

Chúng ta thu được một quá trình lặp được biểu diễn dưới dạng cây, phần trên của cây tương ứng với lời giải của bài toán ban đầu và hai nhánh được kết nối với nó là lời giải cho một cặp bài toán quy hoạch tuyến tính A và B. Các giá trị kết quả của hàm mục tiêu có thể nhỏ hơn hoặc bằng giá trị hàm mục tiêu của bài toán ban đầu f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Mỗi đỉnh trong số hai đỉnh nhánh mới thu được có thể có các nhánh tiếp theo của riêng nó.

1) Quá trình phân nhánh lặp lại tiếp tục cho đến khi thu được nghiệm nguyên trong số các phương án thu được và giá trị của hàm mục tiêu phải lớn hơn hoặc bằng giá trị của hàm mục tiêu của các đỉnh phân nhánh khác.

2) Nếu ở bước lặp tiếp theo, cả hai bài toán đều có nghiệm không nguyên, thì để phân nhánh thêm đỉnh tương ứng với bài toán với giá trị lớn các hàm mục tiêu. Đối với một trong các biến đã nhận được giá trị phân số, các ràng buộc mới được đưa ra cho các bài toán quy hoạch tuyến tính sau.

3) Nếu ở bước lặp tiếp theo, một trong các bài toán có nghiệm nguyên và trong số các giá trị của các biến trong bài toán thứ hai có giá trị phân số, thì bài toán đó có giá trị cao nhất các hàm mục tiêu. Nếu đây là bài toán nhận được nghiệm số nguyên thì quá trình kết thúc, nhưng nếu đây là bài toán có giá trị phân số của biến thì quá trình tiếp theo phân nhánh.

4) Nếu ở bước lặp tiếp theo, một trong các bài toán không có lời giải và bài toán thứ hai trong số các giá trị của các biến trong lời giải thu được có giá trị phân số. Sau đó, đối với bài toán đầu tiên, quá trình phân nhánh dừng lại và để biến đổi thêm bài toán thứ hai, một trong các biến không nguyên được chọn, trong đó các ràng buộc bổ sung được rút ra cho một cặp bài toán quy hoạch tuyến tính mới.

5) Nếu ở bước lặp tiếp theo, một trong các vấn đề không có giải pháp và đối với vấn đề kia thu được giải pháp số nguyên và không có tùy chọn nào khác có giá trị nguyên lớn hơn của hàm mục tiêu và có thể tiếp tục phân nhánh , khi đó quá trình kết thúc và giải pháp tìm được là tối ưu nghiệm số nguyên nhiệm vụ ban đầu.

Nếu tác vụ được chọn dẫn đến bị ngắt (bế tắc) hoặc giá trị hàm nhỏ hơn trong tác vụ B.1 f(X) A.4< f(X)­ В,1 ., sau đó xảy ra sự quay trở lại nhiệm vụ B.1 và một nhánh mới xuất hiện.

Hình 14. Sơ đồ thuật toán nhánh và ràng buộc

Cơm. 15. Phương pháp rẽ nhánh và ràng buộc

BỘ GIÁO DỤC LIÊN BANG NGA

TRƯỜNG ĐẠI HỌC KỸ THUẬT BANG KUZBASS

Phòng công nghệ máy tính và công nghệ thông tin

GIẢI BÀI TOÁN LẬP TRÌNH SỐ TIỀN TUYẾN TÍNH BẰNG PHƯƠNG PHÁP GOMORI

Hướng dẫn và nhiệm vụ cho lớp học thực hành theo tỷ lệ

“Phương pháp kinh tế và toán học” dành cho sinh viên chuyên ngành kinh tế

Biên soạn bởi N.Yu Kolomarova

Thông qua tại cuộc họp Sở Biên bản số 5 ngày 30/11/99

Một bản sao điện tử được đặt trong thư viện của tòa nhà chính KuzSTU

Kemerovo 2000

1. BÁO CÁO VẤN ĐỀ

Có một số bài toán quy hoạch tối ưu trong đó các biến chỉ có thể nhận giá trị nguyên. Những công việc như vậy liên quan đến việc xác định số lượng đơn vị sản phẩm không thể chia được, số lượng máy móc khi bốc dỡ thiết bị, số lượng nhân viên trong các bộ phận cơ cấu của doanh nghiệp, v.v. Khá thường xuyên, các vấn đề nảy sinh với cái gọi là biến Boolean, giải pháp của chúng là các phán đoán thuộc loại “có-không”. Nếu hàm và các ràng buộc trong những bài toán như vậy là tuyến tính thì chúng ta đang nói về một bài toán quy hoạch số nguyên tuyến tính.

Bài toán quy hoạch số nguyên tuyến tính được xây dựng

là như sau: tìm một giải pháp như vậy (kế hoạch)

X = (x1, x2, ..., xn),

nhận giá trị tối đa hoặc tối thiểu theo các hạn chế

2. PHƯƠNG PHÁP GOMORI

Một trong những phương pháp giải các bài toán quy hoạch số nguyên tuyến tính là phương pháp Gomori. Bản chất của phương pháp này là xây dựng các ràng buộc nhằm loại bỏ các nghiệm không nguyên cho bài toán quy hoạch tuyến tính, nhưng không cắt bỏ bất kỳ sơ đồ số nguyên nào.

Hãy xem xét một thuật toán để giải bài toán lập trình số nguyên tuyến tính bằng phương pháp này.

1. Chúng ta giải bài toán bằng phương pháp đơn hình mà không tính đế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ì phương án đó là tối ưu cho bài toán lập trình số nguyên. Nếu một bài toán được cho là không thể giải được thì bài toán lập trình số nguyên cũng không thể giải được.

2. Nếu giữa các thành phần giải pháp tối ưu không phải là số nguyên, thì đối với các ràng buộc của bài toán, chúng ta thêm một ràng buộc mới có các thuộc tính sau:

Nó phải tuyến tính; - phải cắt bỏ số nguyên không tối ưu tìm được

kế hoạch; - không được cắt bỏ bất kỳ kế hoạch số nguyên nào.

Để xây dựng một ràng buộc, chúng tôi chọn một thành phần của phương án tối ưu với phần phân số lớn nhất và sử dụng hàng thứ k của bảng đơn tương ứng với thành phần này, chúng ta viết ra ràng buộc Gomori.

		f k = ∑	f kj x j − S * ,S * ≥ 0 ,
ở đâu vậy	Xj - ;
	Zkj - ;
		Biến mới;
Số nguyên gần nhất lần lượt không vượt quá x j và z kj
		Chúng tôi thêm ràng buộc đã tạo vào những ràng buộc có sẵn trong sim-

bảng phức tạp, từ đó thu được một vấn đề mở rộng. Để có được phương án tham khảo cho bài toán này cần phải đi vào cơ sở

	một vectơ mà số lượng				∆ j		tối thiểu. Và nếu trong thế kỷ này -
					f kj
	giá trị hình xuyến θ = phút		hóa ra theo dòng bổ sung, sau đó vào
	z ij> 0

bảng đơn giản sau đây sẽ tạo ra sơ đồ tham khảo. Nếu giá trị θ không tương ứng với dòng bổ sung thì cần thiết

sang bài toán M (đưa biến nhân tạo vào ràng buộc Gomori).

4. Chúng tôi giải quyết vấn đề kết quả bằng cách sử dụng các phép biến đổi đơn giản thông thường. Nếu lời giải của bài toán này dẫn tới một phương án tối ưu số nguyên thì bài toán mong muốn sẽ được giải. Nếu chúng ta nhận được một giải pháp không nguyên thì chúng ta lại thêm một ràng buộc bổ sung và quá trình tính toán được lặp lại. Sau khi hoàn thành một số lần lặp hữu hạn, chúng ta có thể đạt được một phương án tối ưu cho bài toán lập trình số nguyên hoặc thiết lập tính không thể giải được của nó.

Ghi chú:

1. Nếu biến bổ sung S * được đưa vào cơ sở, sau đó sau khi tính toán lại bất kỳ kế hoạch tiếp theo nào, hàng và cột tương ứng có thể bị xóa (do đó làm giảm quy mô của vấn đề).

2. Nếu cho phân số x j hóa ra tất cả các hệ số của phương trình (hàng) tương ứng đều là số nguyên thì bài toán không có nghiệm nguyên.

3. VÍ DỤ GIẢI QUYẾT VẤN ĐỀ SỬ DỤNG PHƯƠNG PHÁP GOMORI

Nhiệm vụ: Để mua thiết bị mới, công ty phân bổ 19 đơn vị tiền tệ. Thiết bị phải được đặt trên diện tích không quá 16 m2. Doanh nghiệp có thể đặt mua hai loại thiết bị: máy loại “A” có giá 2 đơn vị tiền tệ, yêu cầu diện tích sản xuất 4 m2, cho năng suất 8 tấn sản phẩm mỗi ca và máy loại “B” có giá 5 đơn vị tiền tệ, chiếm diện tích 1 m2 và mang lại năng suất 6 tấn sản phẩm mỗi ca.

Cần phải lập kế hoạch mua sắm thiết bị tối ưu để đảm bảo tối đa Tổng hiệu suất.

Giải: Gọi x 1, x 2 lần lượt là số lượng máy loại “A” và “B” và L là tổng năng suất của chúng. Sau đó mô hình toán học nhiệm vụ:

tối đa L = 8 x1 +6 x2

với những hạn chế:

2x1	5x2
4x1
x 1 ≥		0, x2 ≥ 0

x1, x2 - số nguyên

Chúng tôi giải quyết vấn đề bằng phương pháp đơn hình mà không tính đến các giá trị nguyên.

	∆ j
	∆ j
	∆ j

Đã thu được phương án không nguyên tối ưu X opt = (61/18;22/9).

Lmax = 376/9.

Bởi vì thành phần kế hoạch x 2 có phần phân số tối đa: max(4/9;7/18) = 4/9, sau đó chúng ta viết một ràng buộc bổ sung trên dòng đầu tiên.

22/9 - = (2/9 - )x 3 + (-1/9 - [-1/9])x 4 -S 1 , S 1 ≥0 22/9 - 2 = (2/9 - 0) x 3 + (-1/9 - (-1))x 4 -S 1 , S 1 ≥0

4/9 = 2/9x3 + 8/9x4 - S1, S1 ≥ 0 - ràng buộc Gomori thứ nhất

Chúng ta thêm ràng buộc đã tạo vào những ràng buộc hiện có trong bảng đơn giản.

Sau khi xây dựng một ràng buộc bổ sung, chúng ta có nhiệm vụ mới lập trình tuyến tính, trong đó có 3 hạn chế. Để có được phương án tham khảo cho bài toán này cần tìm cơ sở thứ ba

vector này. Để làm điều này, chúng tôi xác định: tối thiểu
	f kj

cơ sở chúng tôi giới thiệu vectơ x 4.							4 / 9
Ta tính giá trị θ =
	z ij> 0						8 / 9

Giá trị tối thiểuθ được lấy từ một dòng bổ sung, có nghĩa là không cần dùng đến biến nhân tạo, chúng ta thu được sơ đồ tham chiếu của bài toán mở rộng.

	∆ j

Phương án tìm được là tối ưu nhưng không nguyên. Chúng tôi đang xây dựng một ràng buộc Gomori mới.

Bởi vì phần phân số tối đa trong số các thành phần kế hoạch là 1/2, viết giới hạn bổ sung trên dòng đầu tiên (bạn cũng có thể viết ở dòng thứ ba).

5/2 - = (1/4 - )x 3 + (-1/8 - [-1/8])S 1 -S 2 , S 2 ≥0

1/2 = 1/4x3 + 7/8S1 - S2, S2 ≥ 0 - ràng buộc Gomori thứ hai

Chúng tôi thêm ràng buộc này vào bảng đơn giản cuối cùng.

Chúng tôi nhận được một bài toán trong đó có 4 ràng buộc, do đó cần có 4 vectơ đơn vị trong cơ sở.

								2. Có thể

nhập x 3 hoặc S 1 . Hãy giới thiệu vectơ S 1 .

1/ 2

4 / 7

tương ứng với bổ sung

7 / 8

hạn chế.

∆ j

Chúng tôi có được một kế hoạch không nguyên tối ưu mới. Xét đến Nhận xét 1, chúng ta gạch bỏ hàng và cột tương ứng với

biến S 1.

Trong sơ đồ kết quả, thành phần x2 có phần phân số tối đa, vì vậy chúng tôi viết ra một ràng buộc bổ sung trên dòng đầu tiên.

	4/7 = 2/7x3 + 6/7S2 - S3, S3 ≥ 0	Hạn chế thứ ba của Gomori.
	Chúng tôi xác định vectơ được đưa vào cơ sở:

vectơ x 3. Giá trị tối thiểu θ = 2, tương ứng với một dòng bổ sung.

Sau khi thực hiện các phép biến đổi đơn giản tiếp theo, chúng tôi nhận được:

	∆ j

Phương án X 5 là phương án không nguyên tối ưu. Chúng tôi viết một hạn chế bổ sung trên dòng thứ hai:

1/2 = 1/4S3 - S4, S4 ≥ 0

Hạn chế thứ tư của Gomori.

Bởi vì thành phần cơ sở có thể là S 3, ta xác định giá trị

0. Giá trị nhỏ nhất của θ đạt được ở 3

chứ không phải dọc theo đường Gomori, do đó, chúng ta chuyển sang bài toán M:

hãy giới thiệu thêm một biến x 5							đến giới hạn Gomori.
C5'	B5'	X5'
	∆ j

∆ j

∆ j

Phần phân số = max(1/3; 2/3) = 2/3

hạn chế bổ sung

Chúng tôi viết nó ra trên dòng thứ hai.

2/3 = 1/3x4 + 2/3S4 - S5

S5 ≥

Hạn chế thứ năm của Gomori.

16 / 3

2 nhập x 4.

Vector được nhập vào cơ sở: tối thiểu

2 / 3

θ =

phù hợp với dòng của Gomori.

∆ j

Phương án X 8 = (3; 2; 3; 2) - số nguyên tối ưu L max = 36.

Giải thích kinh tế:Theo quyết định nhận được, công ty có nhu cầu mua 3 máy loại A và 2 máy loại B. Trong trường hợp này nó sẽ đạt được hiệu suất tối đa vận hành thiết bị tương đương 36 tấn sản phẩm/ca. Kết quả tiết kiệm Tiền bạc với số lượng 3 đơn vị. có thể được gửi đến bất kì các mục đích khác, chẳng hạn như tiền thưởng cho những công nhân sẽ gỡ lỗi thiết bị đã nhận. Bạn có thể đặt một hộp hoa trên diện tích thừa 2 m2.

Giải thích hình học của phương pháp Gomori: chúng tôi đang xây dựng nhiều

số lượng kế hoạch (xem hình). Tại điểm 1 - phương án không nguyên tối ưu.