Tính hai mặt trong các vấn đề lập trình tuyến tính

Tính hai mặt trong các vấn đề lập trình tuyến tính!

Đối với mọi Vấn đề lập trình tuyến tính, có một vấn đề duy nhất tương ứng liên quan đến cùng một dữ liệu và nó cũng mô tả vấn đề ban đầu. Vấn đề ban đầu được gọi là chương trình nguyên thủy và vấn đề duy nhất tương ứng được gọi là chương trình kép. Hai chương trình có liên quan rất chặt chẽ và giải pháp tối ưu của kép cung cấp thông tin đầy đủ về giải pháp tối ưu của nguyên tắc và ngược lại.

Các khía cạnh hữu ích khác nhau của tài sản này là:

(a) Nếu primal có số lượng lớn các hằng số và số lượng biến nhỏ, tính toán có thể được giảm đáng kể bằng cách chuyển đổi vấn đề sang Dual và sau đó giải quyết nó.

(b) Tính hai mặt trong lập trình tuyến tính có một hệ quả sâu rộng nhất định của bản chất kinh tế. Điều này có thể giúp các nhà quản lý trả lời các câu hỏi về các khóa hành động thay thế và các giá trị tương đối của chúng.

(d) Tính hai mặt trong lập trình tuyến tính cho thấy mỗi chương trình tuyến tính tương đương với trò chơi có tổng bằng hai người. Điều này chỉ ra rằng mối quan hệ khá chặt chẽ tồn tại giữa lập trình tuyến tính và lý thuyết về trò chơi.

1. Hình thành kép khi Primal ở dạng Canonical:

Từ hai chương trình trên, các điểm sau đây là rõ ràng:

(i) Vấn đề tối đa hóa trong số nguyên tố trở thành vấn đề tối thiểu hóa trong kép và ngược lại.

(ii) Vấn đề tối đa hóa có () các ràng buộc.

(iii) Nếu số nguyên tố chứa n biến và m ràng buộc, thì nhị phân sẽ chứa m biến và n ràng buộc.

(iv) Các hằng số b ₁ b ₂, b ₃ Mạnh Cách b _m trong các ràng buộc của số nguyên tố xuất hiện trong hàm mục tiêu của đối ngẫu.

(v) Các hằng số c ₁, c ₂, c ₃ c _n trong hàm mục tiêu của số nguyên tố xuất hiện trong các ràng buộc của đối ngẫu.

(vi) Các biến trong cả hai vấn đề đều không âm.

Các mối quan hệ ràng buộc của số nguyên tố và kép được trình bày dưới đây.

Ví dụ 1:

Xây dựng kép cho vấn đề nguyên thủy

Dung dịch:

Đầu tiên, ràng buộc is được chuyển đổi thành ≤ ràng buộc bằng cách nhân cả hai bên với -1.

Ví dụ 2:

Xây dựng kép cho vấn đề nguyên thủy

Dung dịch:

Đặt Y ₁, Y ₂, V ₃ và V ₄ là các biến kép tương ứng, sau đó bài toán kép được đưa ra bởi

Vì bài toán kép có số lượng ràng buộc ít hơn số nguyên tố (2 thay vì 4), nên nó đòi hỏi ít công sức và nỗ lực hơn để giải quyết nó. Điều này xuất phát từ thực tế là khó khăn tính toán trong bài toán lập trình tuyến tính chủ yếu liên quan đến số lượng ràng buộc hơn là số lượng biến.

Ví dụ 3:

Xây dựng kép của vấn đề