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

44

Chương III

Bài toán đối ngẫu và một số ứng dụng

1. Phát biểu bài toán đối ngẫu

1.1. Phát biểu bài toán

Tương ứng với mỗi BTQHTT (còn gọi là bài toán gốc) có một bài toán đối ngẫu. Bài toán

đối ngẫu của BTQHTT cũng là một BTQHTT. Như vậy, bài toán gốc và bài toán đối ngẫu của nó

lập thành một cặp BTQHTT, tính chất của bài toán này có thể được khảo sát thông qua bài toán

kia. Nhiều quy trình tính toán hay phân tích được hoàn thiện khi xem xét cặp bài toán trên trong

mối liên quan chặt chẽ của chúng, mang lại lợi ích trong việc giải quyết các vấn đề phát sinh từ

thực tế. Với mục đích tìm hiểu bước đầu, chúng ta xét bài toán gốc là bài toán quy hoạch tuyến

tính (BTQHTT) dạng Max với các ràng buộc chỉ có dấu ≤ và các biến đều thoả mãn điều kiện

không âm.

Bài toán gốc

Max z = c1x1 + c2x2 + .... + cnxn

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.

Lúc đó BTQHTT sau đây được gọi là bài toán đối ngẫu của BTQHTT trên.

Bài toán đối ngẫu

Min u = b1y1 + b2y2 + .... + bmym

45

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

a11y1 + a21y2 + ... + am1ym ≥ c1

a12y1 + a22y2 + ... + am2ym ≥ c2

...

a1ny1 + a2ny2 + ... + amnym ≥ cn

y1, y2, ..., ym ≥ 0.

Các biến y1, y2, ..., ym được gọi là các biến đối ngẫu. Trong trường hợp này, do bài toán gốc

có m ràng buộc, nên bài toán đối ngẫu có m biến đối ngẫu. Biến đối ngẫu yi tương ứng với ràng

buộc thứ i của bài toán gốc.

1.2. Ý nghĩa của bài toán đối ngẫu

Ví dụ 1. Xét bài toán gốc

Max z = 2x1 + 4x2 + 3x3

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

3x1 + 4x2 + 2x3 ≤ 60

2x1 + x2 + 2x3 ≤ 40

x1 + 3x2 + 2x3 ≤ 80

x1, x2, x3 ≥ 0.

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

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

Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất ba loại sản phẩm I,

II và III. Để sản xuất ra một đơn vị sản phẩm I cần có 3 đơn vị nguyên liệu loại A, 2 đơn vị

nguyên liệu loại B và 1 đơn vị nguyên liệu loại C. Các chỉ tiêu đó cho một đơn vị sản phẩm loại II

là 4, 1 và 3. Còn cho đơn vị sản phẩm loại III là 2, 2 và 2. Lượng nguyên liệu dự trữ loại A và B

hiện có là 60, 40 và 80 (đơn vị). Hãy xác định phương án sản xuất đạt lợi nhuận lớn nhất, biết lợi

nhuận / đơn vị sản phẩm bán ra là 2, 4 và 3 (đơn vị tiền tệ) cho các sản phẩm loại I, II và III.

Giả sử có một khách hàng muốn mua lại các đơn vị nguyên liệu loại A, B và C. Bài toán

đặt ra là cần định giá các đơn vị nguyên liệu. Rõ ràng rằng giá các nguyên liệu được quy định bởi

giá trị của sản phẩm mà chúng tạo nên. Nếu các sản phẩm này mang lại lợi nhuận lớn trên thị

trường thì giá ước định của các nguyên liệu này phải cao, còn nếu trái lại thì giá ước định của

chúng là thấp. Mặt khác, lợi nhuận của các sản phẩm thu được trên thị trường lại phụ thuộc vào

nhiều yếu tố như: giá cả các sản phẩm được bán trên thị trường (đã được thị trường chấp nhận),

lượng dự trữ nguyên liệu hiện có, hệ số chi phí sản xuất …

Như vậy, giá ước định của các nguyên liệu A, B và C phụ thuộc vào:

– Hệ số hàm mục tiêu của bài toán gốc: c1 = 8, c2 = 4 và c3 = 63.

– Ma trận ràng buộc các hệ số chi phí sản xuất:

46

A =

342

212

132

⎡ ⎤

⎢ ⎥

⎢ ⎥

⎢ ⎥ ⎣ ⎦

.

– Hệ số dự trữ các loại nguyên liệu:

b =

60

40

80

⎡ ⎤

⎢ ⎥

⎢ ⎥

⎢ ⎥ ⎣ ⎦

.

Tuy nhiên, mối phụ thuộc đó không dễ dàng xác định được. Để giải quyết vấn đề này hoàn

toàn có thể dựa vào việc phân tích bài toán đối ngẫu. Gọi y1 là giá ước định một đơn vị nguyên

liệu loại A, y2 là giá ước định một đơn vị nguyên liệu loại B, còn y3 là giá ước định một đơn vị

nguyên liệu loại C (y1, y2, y3 ≥ 0).

Chúng ta hãy đi xét bài toán đối ngẫu:

Min u = 60y1 + 40y2 + 80y3

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

3y1 + 2y2 + y3 ≥ 2

4y1 + y2 + 3y3 ≥ 4

2y1 + 2y2 + 2y3 ≥ 3

y1, y2, y3 ≥ 0.

Thật vậy, u = 60y1 + 40y2 + 80y3 chính là tổng chi phí phải bỏ ra nếu người khách hàng

muốn mua 60 đơn vị nguyên liệu loại A, 40 đơn vị nguyên liệu loại B và 80 đơn vị nguyên liệu

loại C. Tất nhiên người khách hàng muốn tổng chi phí u càng bé càng tốt.

Xét ràng buộc thứ nhất. Vế trái là 3y1 + 2y2 + y3 chính là số tiền khách hàng phải bỏ ra để

mua 3 đơn vị nguyên liệu loại A, 2 đơn vị nguyên liệu loại B và 1 đơn vị nguyên liệu loại C. Đây

là số nguyên liệu cần thiết để sản xuất ra một đơn vị sản phẩm loại I. Rõ ràng rằng, người khách

hàng không thể mua được số nguyên liệu này thấp hơn lợi nhuận mà một đơn vị sản phẩm loại A

mang lại khi được bán ra trên thị trường (2 đơn vị tiền tệ). Điều này dẫn đến ràng buộc thứ nhất

3y1 + 2y2 + y3 ≥ 2. Tương tự chúng ta có thể lập luận được ý nghĩa kinh tế của ràng buộc thứ hai

cũng như ràng buộc thứ ba của bài toán đối ngẫu.

1.3. Quy tắc viết bài toán đối ngẫu tổng quát

Xét cặp bài toán gốc và bài toán đối ngẫu trong ví dụ 1 được cho trong bảng III.1.

Nhận xét. BTG là bài toán Max ⇒ BTĐN là bài toán Min.

– Các hệ số hàm mục tiêu của BTG ⇒ Các hệ số vế phải của BTĐN.

– Các hệ số vế phải của BTG ⇒ Các hệ số hàm mục tiêu của BTĐN.

– Ma trận hệ số của BTG là A ⇒ Ma trận hệ số của BTĐN là AT

.

– Biến ≥ 0 của BTG (3.2) ⇒ Ràng buộc ≥ của BTĐN (3.2’).