Lập trình tuyến tính số nguyên là gì?

Các vấn đề lập trình tuyến tính số nguyên phát sinh khi cố gắng giải các hệ thống tuyến tính trong khi chỉ định rằng tất cả các biến chưa biết phải là số nguyên hoặc toàn bộ số.Các hệ thống tuyến tính là các bộ phương trình mô tả một tình huống mà lập trình viên đang cố gắng tìm một giải pháp.Chúng thường bao gồm một phương trình phải được tối đa hóa hoặc giảm thiểu và một hoặc nhiều phương trình hạn chế đặt giới hạn đối với các biến chưa biết.Đối với hệ thống là tuyến tính, mỗi hạn chế phải là một phương trình tuyến tính;Nghĩa là, nó phải chứa các trường hợp của biến chưa biết với số mũ lớn hơn một. Các hệ thống tuyến tính thông thường có thể được giải quyết dễ dàng bằng cách sử dụng máy tính.Chương trình có thể xác định một giải pháp bằng cách tìm đạo hàm và đặt nó bằng không.Sau đó, nó có thể xác minh rằng điểm là tối đa hoặc tối thiểu bằng cách kiểm tra vùng lân cận ngay lập tức của nó trên chức năng.Miễn là đạo hàm được xác định tại mỗi điểm dọc theo hàm, máy tính chỉ có một số lượng hạn chế các giải pháp có thể để kiểm tra. Lập trình tuyến tính trở thành lập trình tuyến tính số nguyên với việc bổ sung hạn chế số nguyên.Điều này có nghĩa là vấn đề vẫn giữ nguyên, nhưng câu trả lời phải bao gồm các giá trị số nguyên cho các giá trị chưa biết: chúng phải là số toàn bộ.Đôi khi, điều này có nghĩa là giải pháp sẽ được tối ưu so với trường hợp cho phép phân số;Tuy nhiên, nó phản ánh thế giới thực, trong đó các vật phẩm thường đến trong các đơn vị riêng biệt, không thể chia cắt.Điều này làm cho lập trình tuyến tính số nguyên trở nên quan trọng đối với các ứng dụng kinh doanh, vì các công ty muốn tối đa hóa lợi nhuận càng nhiều càng tốt nhưng không thể chọn bán một phần của sản phẩm.-hoàn thành.Điều này có nghĩa là thời gian cần thiết cho máy tính để giải quyết hệ thống là không xác định.Với các hạn chế số nguyên, máy tính không thể sử dụng công cụ của đạo hàm vì không có gì đảm bảo rằng điểm số 0 của đạo hàm sẽ rơi vào số nguyên.Giải pháp sẽ là số nguyên với giá trị cao nhất hoặc thấp nhất trong số tất cả các số nguyên, vì vậy máy tính sẽ phải kiểm tra tất cả mdash;Một quá trình có thể mất một lượng thời gian vô hạn. Các lập trình viên đã phát triển các phương pháp phỏng đoán, hoặc phương pháp giải quyết vấn đề, để đối phó với sự phức tạp của những vấn đề này.Một phương pháp giải quyết các vấn đề lập trình tuyến tính số nguyên là thuật toán nhánh và ràng buộc, trong đó máy tính giải quyết một loạt các vấn đề liên quan đến vấn đề ban đầu để thu hẹp phạm vi giá trị có sẵn thành một giải pháp.Tuy nhiên, đối với các vấn đề phức tạp, điều này có thể mất nhiều thời gian.