Bài toán đối ngẫu quy hoạch tuyến tính năm 2024

Trong quy hoạch tuyến tính, bài toán gốc và bài toán đối ngẫu bổ sung cho nhau. Đáp số của bài này đồng thời là đáp số của bài kia.

Cơ bản[sửa | sửa mã nguồn]

Các bài toán quy hoạch tuyến tính là những bài toán tối ưu hóa trong đó hàm mục tiêu và các điều kiện chế ước đều là tuyến tính.

Kiểu bài toán trong trường hợp tuyến tính[sửa | sửa mã nguồn]

Trong bài toán gốc, hàm mục tiêu là một kết hợp tuyến tính của n biến số. Có m điều kiện chế ước, mỗi điều kiện đặt ra một mức giới hạn trên cho kết hợp tuyến tính của n biến số. Mục tiêu là tối đa hóa giá trị của hàm mục tiêu với những điều kiện chế ước đặt ra. Một đáp số là một vector (một danh sách) của n giá trị cho phép đạt giá trị tối đa của hàm mục tiêu.

Trong bài toán đối ngẫu, hàm mục tiêu là một kết hợp tuyến tính của m giá trị vốn là m điều kiện chế ước trong bài toán gốc. Có n điều kiện chế ước đối ngẫu, mỗi cái đặt ra một giới hạn dưới cho một kết hợp tuyến tính của m biến số đối ngẫu.

Nguyên lý đối ngẫu[sửa | sửa mã nguồn]

Trong lý thuyết tối ưu hóa, nguyên lý đối ngẫu phát biểu rằng các bài toán tối ưu có thể xem từ cả hai phía, phía bài toán gốc và phía bài toán đối ngẫu.

Định lý đối ngẫu[sửa | sửa mã nguồn]

Định lý đối ngẫu phát biểu rằng trong trường hợp tuyến tính sẽ có một đồng trị tính toán trực tiếp giữa đáp số của bài toán gốc và đáp số của bài toán đối ngẫu.

Ví dụ về đồng trị này và cách tính được giới thiệu tại [1] Lưu trữ 2007-03-18 tại Wayback Machine.

Trường hợp phi tuyến[sửa | sửa mã nguồn]

Trong trường hợp quy hoạch phi tuyến tính, các điều kiện chế ước không nhất thiết phải tuyến tính. Tuy nhiên, nhiều nguyên lý chung vẫn được áp dụng.

Để đảm bảo rằng một bài toán phi tuyến tính có một giá trị cực đại toàn cục duy nhất, thông thường người ta sắp xếp theo một tiêu chí đơn giản hóa chẳng hạn như độ lồi. Nếu độ cong của các điều kiện chế ước và của hàm mục tiêu được xem như miền thực hiện (feasible region) luôn lồi, thì sẽ có giá trị tối ưu toàn cục duy nhất.

Đây chính là ý nghĩa của điều kiện Karush-Kuhn-Tucker. Họ cho trước những điều kiện đủ dựa trên độ lồi để xác định bài toán quy hoạch phi tuyến tính có giá trị tối ưu toàn cục duy nhất. Có các điều kiện cần để cho có thể xác định hướng cho đáp án tối ưu. Một đáp án tối ưu có thể là một giá trị tối ưu cục bộ, chứ không nhất thiết phải là một giá trị tối ưu toàn cục.

Chương 2.BÀI TOÁN ĐỐI NGẪU

2.1 Giới thiệu bài toán QHTT đối ngẫu

Bài toán mở đầu. Các sinh viên thường mua thức ăn nhẹ ở một cửa hàng gần trường đại học.

Cửa hàng gần trường cung cấp hai loại thức ăn nhẹ là bánh hạnh nhân socola và kem socola. Mỗi

bánh hạnh nhân có giá 2 đô và mỗi cây kem có giá 1 đô. Mỗi bánh hạnh nhân chứa 4 ounces socola và

3 ounces đường, mỗi cây kem chứa 3 ounces socola và 2 ounces đường. Nhu cầu dinh dưỡng tối thiểu

của mỗi sinh viên là 8 ounces socola và 11 ounces đường. Xác định số lượng bánh hạnh nhân và số

lượng cây kem mà mỗi sinh sẽ mua để đáp ứng nhu cầu dinh dường tối thiểu và chi phí là thấp nhất

(xem Ví dụ 3).

Gọi x1; x2lần lượt là số bánh và kem cần mua. Bài toán trên được mô hình toán thành bài toán

qui hoạch tuyến tính như sau:

(P) : f(x) \= 2x1+x2!min

8

<

:

4x1+ 3x28

3x1+ 2x211

x10; x20:

Bài toán trên có thể được giải bằng phương pháp đơn hình (mở rộng) sau khi đã bài toán đã được

chuyển về dạng chuẩn. Tuy nhiên, với thông tin từ đề bài ta có thể xét một bài toán qui hoạch tuyến

tính đối ngẫu của bài toán trên. Các thông tin về phương án tối ưu và giá trị tối ưu của bài toán đối

ngẫu sẽ cho phép ta suy ra phương án tối ưu và giá trị tối ưu của bài toán ban đầu.

Với thông tin về giá trị dưỡng chất và giá bán mỗi bánh hạnh nhân và cây kem ở trên, nhà cung

cấp nguyên liệu cần xác định giá bán mỗi ounce socola và mỗi ounce đường là bao nhiêu để doanh

thu đạt lớn nhất nhưng vẫn đảm bảo chủ cửa hàng bán bánh và kem theo giá đã định? Khi đó, nhà

cung cấp nguyên liệu sản xuất bánh và kem cần lập mô hình bài toán qui hoạch tuyến tính cho bài

toán doanh thu đạt cực đại như sau:

Gọi y1; y2lần lượt là giá bán mỗi ounce socola và đường

Hàm mục tiêu sẽ là: g(y) \= 8y1+ 11y2!max

Chi phí để tạo ra một bánh hạnh nhân phải dưới 2 đôla, nếu không chủ cửa hàng sẽ không mua

nguyên liệu từ nhà cung cấp, vì chủ cửa hàng có nguy cơ thua lỗ nếu sinh viên mua bánh hạnh nhân.

Do đó, ta có ràng buộc chính thứ nhất: 4y1+ 3y22. Tương tự, chi phí để tạo một muỗng kem sôcôla

phải có giá dưới 1 đô la ta nên có thêm ràng buộc chính thứ hai: 3y1+ 2y21.

Khi đó, ta có bài toán qui hoạch tuyến tính (cho nhà cung cấp nguyên liệu) như sau

(D) : g(y) \= 8y1+ 11y2!max

8

<

:

4y1+ 3y22

3y1+ 2y21

y10; y20:

Cặp bài toán (P) và (D) ở trên được gọi là được gọi là cặp bài toán đối ngẫu. Cặp bài toán trên

có thể được mở rộng cho trường hợp nhiều biến như sau:

(P) : f(x) \= c1x1+::: +cnxn!min (D) : g(y) \= b1y1+::: +bmym!max

a11x1+a12 x2+::: +a1nxnb1a11y1+a21 y2+::: +am1ymc1

a21x1+a22 x2+::: +a2nxnb2a12y1+a22 y2+::: +am2ymc2

::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::

am1x1+am2x2+::: +amnxnbma1ny1+a2ny2+::: +amnyncn

xj0; j \= 1; n: yi0; i \= 1; m:

1