Tối -u hoá là một lĩnh vực toán học nghiên cứu lý thuyết về thuật toán giải các bài toán cực trị. Nó là một phần kiến thức không thể thiếu đ-ợc cho những ng-ời làm việc trong các lĩnh vực ứng dụng của khoahọc và kỹ thuật. Trong lý thuyết tối -u, một trong những lớp bài toán đầu tiên đ-ợc nghiên cứu trọn vẹn cả về ph-ơng diện lý thuyết lẫn thuật toán là bài toánquy hoạch tuyến tính. Ngay từ khi ra đời, quy hoạch tuyến tính đQ chiếm một vị trí hết sức quan trọng; nó là môn toán ứng dụng rất cần thiết đối với sinh viên thuộc nhiều ngành học khác nhau. Các thuật toán giải bài toán quy hoạch tuyến tính không những giúp giải quyết các bài toán quy hoạch tuyến tính tổng quát cỡ lớn mà nó còn là điểm xuất phát quan trọng trong việc nghiên cứu lý thuyết giải các bài toán tối -u tổng quát. Trong lý thuyết tối -u ta gặp một lớp bài toán mà đối t-ợng của nó không thể chia cắt nhỏ tuỳ ý, trong lớp bài toán này tất cả (hoặc một bộ phận) các biến chỉ nhận giá trị nguyên, đó là bài toán quy hoạch nguyên. Trong bài toán quy hoạch nguyên, nếu hàm mục tiêu và hệ ràng buộc là các hàm tuyến tính thì ta có bài toán quy hoạch nguyên tuyến tính. Đối với các bài toán quy hoạch nguyên tuyến tính, các thuật toán giải bài toán quy hoạch tuyến tính tổng quát cơ bản hầu hết không thể sử dụng đ-ợc nữa do yêu cầu về tính nguyên của các biến số. Năm 1958 Gomory (nhà toán học ng-ời mỹ) đQ công bố thuật toán cắt nối tiếng để giải bài toán quy hoạch nguyên tuyến tính mở đầucho sự ra đời và phát triển của lý thuyết bài toán quy hoạch nguyên. Tiếp đó, một số kết quả nghiên cứu về tập nghiệm và lời giải cho lớp bài toán này lần l-ợt đ-ợc ra đời. Tuy xuất hiện sau thuật toán đơn hình giải bài toán quy hoạch tuyến tính gần ba thập kỷ nh-ng các thuật toán giải bài toán quy hoạch nguyên tuyếntính đQ có những đóng góp không nhỏ cho lĩnh vực nghiên cứu lý thuyết tối -u tổng quát. Bài toán quy hoạch nguyên tuyến tính là phần kiến thức khá mới mẻ đối với sinh viên s- phạm toán. Với mong muốn khai thácsâu kiến thức môn quy hoạch tuyến tính nói riêng; mở rộng tầm hiểu biết của bản thân về tri thức toán – 3 -nói chung, việc nghiên cứu lý thuyết bài toán quy hoạch nguyên tuyến tính là hết sức cần thiết. Vì những lý do trên chúng tôi chọn “Về bài toán quy hoạch nguyên tuyến tính” làm đề tài nghiên cứu