Giới thiệu

Tối ưu (Optimization) và Vận trù học (Operational Reseach) là những lĩnh vực nghiên cứu có rất nhiều ứng dụng trong thực tế; nó giúp cho chúng ta đưa ra những quyết định hành động tốt nhất có thể. Trong lĩnh vực nghiên cứu này, người ta quan tâm những bài toán về tối ưu (cực đại hóa hoặc cực tiểu hóa) một hàm mục tiêu nào đấy cùng với các ràng buộc kèm theo. Nhìn chung, những bài toán từ thực tế sau khi được mô hình hóa thành bài toán tối ưu thì thường là những bài toán rất khó giải (NP-hard), và có rất nhiều biến cũng như rất nhiều những ràng buộc cần phải thỏa mãn. 

Quy hoạch tuyến tính (Linear Programming) là một phần rất quan trọng trong lĩnh vực Tối ưu và Vận trù học; nó là cơ sở để xây dựng và phát triển những thuật toán hiệu quả để giải những bài toán thực tế có số chiều lớn. Trong quy hoạch tuyến tính thì hàm mục tiêu và các biểu thức hàm trong các ràng buộc là những hàm tuyến tính (tức là các biến có bậc 1). Bài toán quy hoạch tuyến tính có thể phân thành 3 loại : với biến liên tục (continuous variables), với biến nguyên (integer variables) và biến hỗn hợp (mixed : tức là gồm cả biến liên tục và biến nguyên). Một điều thú vị là mặc dù bài toán với biến nguyên và biến hỗn hợp "có ít" nghiệm khả dĩ hơn (hoặc chỉ hữu hạn) bài toán có biến liên tục, nhưng chúng lại khó giải hơn rất nhiều. Môn học này sẽ tập trung vào nghiên cứu bài toán quy hoạch tuyến tính với các biến liên tục.

Với sức mạnh của máy tính điện tử ngày càng được củng cố và phát triển, hiện nay có rất nhiều phần mềm để giải bài toán quy hoạch tuyến tính trên thị trường : gồm cả phần mềm thương mại (chẳng hạn : Matlab, CPLEX,…) và những phần mềm miễn phí (lpsolve, GPLK,…). Những phần mềm này cho phép giải những bài toán tới số chiều rất lớn, từ hàng chục cho đến hàng trăm nghìn biến trong thời gian chấp nhận được. Chúng ta có thể tải về và cài đặt trên máy tính cá nhân, laptop để sử dụng. Ngày nay chúng là những công cụ hết sức cơ bản và không thể tách rời của những người làm tối ưu ứng dụng, để giải các bài toán về quản lý bắt nguồn từ thực tế. Tất nhiên bên cạnh việc chúng ta cần biết cách sử dụng một cách hiệu quả các phần mềm đó, thông dịch các kết quả bài toán được giải ra ; một điều hết sức quan trọng là chúng ta cũng cần phải hiểu cấu trúc của bài toán quy hoạch tuyến tính mà chúng ta đang đối mặt, và cũng như những phương pháp tương thích để giải chúng. Do vậy điều trước tiên cần nắm vững cách mô hình hóa những bài toán thực tế mà chúng ra đang gặp phải thành dạng bài toán quy hoạch tuyến tính, từ đó sử dụng tốt nhất quy hoạch tuyến tính và thông dịch các kết quả thu được.

Nội dung môn học :

Trong mô học này chúng ta sẽ nghiên cứu những kiến thức cơ sở về quy hoạch tuyến tính với biến liên tục trong Chương 1, 2 và 3.

Chương 1 : giới thiệu một số kiến thức cơ sở về quy hoạch tuyến tính, các tính chất cũng như ý nghĩa của chúng.

Chương 2 : dùng để giới thiệu thuật toán đơn hình nổi tiếng của G.B. Dantzig – cha đẻ của môn quy hoạch tuyến tính.

Chương 3 : nghiên cứu một số khái niệm cơ bản về đối ngẫu, một cái có ý nghĩa kinh tế học rất quan trọng, và thiết lập một số mối quan hệ giữa hai bài toán gốc và đối ngẫu. Đồng thời chúng tôi cũng trình bày thuật toán đối ngẫu - một thuật toán khá hữu dụng trong một số trường hợp.

Sau đó chúng ta cũng sẽ học một số kiến thức nâng cao về quy hoạch tuyến tính trong hai chương cuối:

Chương 4 : Thuật toán gốc-đối ngẫu kết hợp và ứng dụng của chúng trong hai bài toán quan trọng : bài toán phân công công việc và bài toán vận tải.

Chương 5 : Phương pháp phân rã Dantzig-Wolfe và thuật toán sinh cột. Những công cụ quan trọng để giải bài toán quy hoạch tuyến tính số chiều lớn. Bài toán cắt nguyên vật liệu và bài toán tìm đường đi ngắn nhất trên một đồ thị với ràng buộc sẽ được dùng để minh hóa ý nghĩa ứng dụng quan trọng của phương pháp này.

Mục lục

Chương 1: Kiến thức cơ sở về Quy hoạch tuyến tính.

1.1  Giới thiệu về bài toán quy hoạch tuyến tính.

1.2  Bài toán dạng chuẩn tắc và bài toán dạng chính tắc

1.3  Một số kiến thức về giải tích lồi

1.4  Đặc tính hình học của nghiệm khả dĩ

1.5  Đặc tính hình học của nghiệm tối ưu

Chương 2 : Phương pháp đơn hình

2.1 Tổng quan về phương pháp đơn hình

2.2 Cơ sở của thuật toán đơn hình

2.3 Các phương pháp liên quan đến Pha 1

2.4 Sự suy biến và xoay vòng

2.5 Dạng chỉnh sửa của thuật toán đơn hình

2.6 Một số phần bổ xung vê thuật toán đơn hình

Chương 3 : Đối ngẫu

3.1 Định nghĩa bài toán đối ngẫu

3.2 Một số định lý về đối ngẫu

3.3 Thuật toán đơn hình đối ngẫu

3.4 Một số vấn đề bổ xung về thuật toán đối ngẫu

Chương 4 : Thuật toán gốc-đối ngẫu

4.1 Cơ sở của thuật toán gốc đối ngẫu

4.2 Bài toán phân việc

4.2.1 Giới thiệu bài toán

4.2.2 Thuật toán Hungari

4.3. Thuật toán gốc-đối ngẫu cho bài toán vận tải

4.3.1 Giới thiệu về bài toán vận tải

4.3.2 Thuật toán gốc-đối ngẫu để giải bài toán vận tải

4.3.3 Phương pháp xấp xỉ để giải bài toán vận tải

Chương 5 : Phân tách Dantzig-Wolfe và thuật toán sinh cột

5.1 Phương pháp sinh cột (Column Generation)

5.2 Phân tách Dantzig – Wolfe

5.3 Một số ứng dụng của phương pháp sinh cột

5.3.1 Bài toán cắt nguyên vật liệu

5.3.2 Bài toán đường đi ngắn nhất với ràng buộc trên một đồ thị