Toán học lập trình tuyến tính

Lập trình tuyến tính, kỹ thuật mô hình toán học trong đó một hàm tuyến tính được tối đa hóa hoặc tối thiểu hóa khi chịu các ràng buộc khác nhau. Kỹ thuật này rất hữu ích trong việc hướng dẫn các quyết định định lượng trong lập kế hoạch kinh doanh, trong kỹ thuật công nghiệp, và ở mức độ thấp hơn trong các ngành khoa học xã hội và vật lý.

tối ưu hóa: lập trình tuyến tính

Mặc dù được sử dụng rộng rãi hiện nay để giải quyết các vấn đề quyết định hàng ngày, lập trình tuyến tính tương đối không rõ trước năm 1947. Không có công việc nào quan trọng

Giải pháp cho một vấn đề lập trình tuyến tính làm giảm việc tìm giá trị tối ưu (lớn nhất hoặc nhỏ nhất, tùy thuộc vào vấn đề) của biểu thức tuyến tính (được gọi là hàm mục tiêu)

chịu một tập hợp các ràng buộc thể hiện dưới dạng bất đẳng thức:

Các a, b và c là các hằng số được xác định bởi năng lực, nhu cầu, chi phí, lợi nhuận và các yêu cầu và hạn chế khác của vấn đề. Giả định cơ bản trong việc áp dụng phương pháp này là các mối quan hệ khác nhau giữa nhu cầu và tính sẵn có là tuyến tính; nghĩa là, không có bất kỳ x _{i nào} được nâng lên thành công suất nào ngoài 1. Để có được giải pháp cho vấn đề này, cần phải tìm giải pháp của hệ bất phương trình tuyến tính (nghĩa là tập hợp các giá trị n của các biến x _i đồng thời thỏa mãn tất cả các bất đẳng thức). Hàm mục tiêu sau đó được đánh giá bằng cách thay thế các giá trị của x _i trong phương trình xác định f.

Các ứng dụng của phương pháp lập trình tuyến tính lần đầu tiên được thử nghiệm nghiêm túc vào cuối những năm 1930 bởi nhà toán học Liên Xô Leonid Kantorovich và nhà kinh tế học người Mỹ Wassily Leontief trong các lĩnh vực lịch trình sản xuất và kinh tế, nhưng công việc của họ đã bị bỏ qua trong nhiều thập kỷ. Trong Thế chiến II, lập trình tuyến tính đã được sử dụng rộng rãi để đối phó với việc vận chuyển, lên lịch và phân bổ các nguồn lực chịu những hạn chế nhất định như chi phí và tính sẵn có. Các ứng dụng này đã làm nhiều việc để thiết lập khả năng chấp nhận phương pháp này, điều này đã thúc đẩy hơn nữa vào năm 1947 với việc giới thiệu phương pháp đơn giản của nhà toán học người Mỹ George Dantzig, đơn giản hóa rất nhiều giải pháp cho các vấn đề lập trình tuyến tính.

Tuy nhiên, khi các vấn đề ngày càng phức tạp hơn liên quan đến nhiều biến số đã được thử, số lượng các hoạt động cần thiết đã mở rộng theo cấp số nhân và vượt quá khả năng tính toán của ngay cả những máy tính mạnh nhất. Sau đó, vào năm 1979, nhà toán học người Nga Leonid Khachiyan đã phát hiện ra một thuật toán đa thức thời gian, trong đó số bước tính toán tăng lên như một sức mạnh của số lượng các biến thay vì theo cấp số mũ do đó cho phép giải các bài toán không thể truy cập được. Tuy nhiên, thuật toán của Khachiyan (được gọi là phương pháp ellipsoid) chậm hơn phương pháp đơn giản khi áp dụng thực tế. Năm 1984, nhà toán học Ấn Độ Narendra Karmarkar đã phát hiện ra một thuật toán đa thức thời gian khác, phương pháp điểm bên trong, đã chứng minh khả năng cạnh tranh với phương pháp đơn giản.