Giáo trình tối ưu hóa - Chương 4 docx

81

Chương IV

Quy hoạch nguyên

1. Phương pháp cắt Gomory giải bài toán quy hoạch tuyến tính nguyên

1.1. Phát biểu bài toán quy hoạch tuyến tính nguyên

Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy

hoạch tuyến tính nguyên hay bài toán quy hoạch tuyến tính nguyên (BTQHTT nguyên), mà trong

đó chúng ta muốn tối ưu hoá / cực đại hoá hay cực tiểu hoá hàm mục tiêu với điều kiện các biến

quyết định là các biến nguyên:

z = c1x1 + c2x2 + .... + cnxn → Max (Min),

với các điều kiện ràng buộc

a11x1 + a12x2 + ... + a1nxn ≤ b1

a21x1 + a22x2 + ... + a2nxn ≤ b2

...

am1x1 + am2x2 + ... + amnxn ≤ bm

x1, x2, ..., xn ≥ 0 (điều kiện không âm)

x1, x2, ..., xn nguyên (điều kiện nguyên).

Trong trường hợp tổng quát, BTQHTT nguyên có thể bao gồm các ràng buộc dạng ≥, ≤

hoặc dạng =, các biến có thể có dấu ≥ 0, ≤ 0 hoặc dấu tùy ý.

Ví dụ 1. Xét BTQHTT: Max z = x1 + 4x2

với các ràng buộc

2x1 + 4x2 ≤ 7

10x1 + 3x2 ≤ 15

x1, x2 ≥ 0

x1, x2 nguyên .

82

Cần tìm các giá trị nguyên của các biến quyết định x1, x2 để các ràng buộc được thoả mãn

và hàm mục tiêu đạt giá trị lớn nhất.

1.2. Minh họa phương pháp Gomory bằng đồ thị

Chúng ta đi tìm phương án tối ưu cho BTQHTT nguyên trong ví dụ 1 bằng

đồ thị.

Bước 1: Vẽ miền các phương án khả thi (còn gọi là miền ràng buộc) là tập hợp các phương

án khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ số

(x1, x2), thoả mãn tất cả các ràng buộc đã có kể cả điều kiện không âm và điều kiện nguyên của

các biến (xem hình IV.1).

– Trước hết chúng ta vẽ đường thẳng có phương trình là 2x1 + 4x2 = 7. Đường thẳng này

chia mặt phẳng làm hai nửa mặt phẳng. Một phần gồm các điểm (x1, x2) thoả mãn: 2x1 + 4x2 ≤ 7,

phần còn lại thoả mãn: 2x1 + 4x2 ≥ 7. Ta tìm được nửa mặt phẳng thoả mãn: 2x1 + 4x2 ≤ 7.

– Tương tự, có thể tìm nửa mặt phẳng thoả mãn: 2x1 + 4x2 ≤ 48.

– Lúc này, giao của hai nửa mặt phẳng tìm được trên cho ta tập hợp các điểm (x1, x2) thoả

mãn các ràng buộc. Tuy nhiên, để thoả mãn điều kiện không âm và điều kiện nguyên của các

biến, ta chỉ xét các điểm nằm trong góc phần tư thứ nhất có các tọa độ đều nguyên. Vậy miền các

phương án khả thi là miền gồm các điểm với tọa độ nguyên được giới hạn bởi tứ giác OABC.

Bước 2: Trong miền (OABC) ta tìm điểm (x1, x2) với các tọa độ nguyên sao cho

z = x1 + 4x2 đạt giá trị lớn nhất. Dễ thấy đó là điểm F(1, 1)

Kết luận. Trong các phương án khả thi thì phương án tối ưu là (x1 = 1, x2 = 1). Tại phương

án này, giá trị hàm mục tiêu là lớn nhất zmax = 1 × 1 + 4 × 1 = 5.

Tóm tắt phương pháp Gomory

Chúng ta quy định gọi BTQHTT như cho trong ví dụ 1 nhưng bỏ qua điều kiện nguyên của

các biến là BTQHTT không nguyên tương ứng với BTQHTT nguyên đã cho. Trước khi giải

10x1 + 3x2 = 15

O

1

7/4

x1

2x1 + 4x2 = 7

x2

1 1,5 7/2

A B(39/34;20/17)

C

Hình IV.1. Phương pháp đồ thị giải BTQHTT nguyên

F E

G

D