bài toán quy hoạch tuyến tính
Lý thuyết và ví dụ minh họa các bài toán quy hoạch tuyến tính gồm:Bài toán sử dụng nguyên liệu sản xuất. Bài toán vận chuyển trên mạng.
Bài toán chặn của bài toán quy hoạch tuyến tính. Nhân tử Lagrange. Phương pháp dò đường. Giải bài toán quy hoạch tuyến tính trong exel.
Phương pháp đơn hình:
Ví dụ Chúng ta sẽ xem cụ thể phương pháp đơn hình trên bài toán sau. Ràng buộc {Thêm vào các biến phụ để các ràng buộc trở thành dấu =, ta có bài toán. với ràng buộc. Ý tưởng của phương pháp đơn hình là bắt đầu từ một bộ. mãn ràng buộc (2.2); sau đó tìm một bộ ̅
Phương pháp đơn hình
̅Tiếp tục quá trinh này cho đến khi có một bộ mà ta không thể làm tốt hơn.Chúng ta sẽ tìm một bộ khởi đầu. Dễ dàng từ (2.2), chúng ta có được bộ khởi đầu là Gía trị hàm mục tiêu tại bộ này là .Bây giờ chúng ta sẽ xem có thể làm tốt hơn không.
Từ số hạng chứa trong là,chúng ta có thể tăng giá trị của lên nếu tăng giá trị lên nhưng vẫn giữ nguyên giá tri của và , nhưng điều này phải bảo đảm các điều kiện không âm của các biến
phụ khác. Do , gía trị của , từ ràng buộc (2.2) phải bảo đảm rằng.
Phương pháp đơn hình đối ngẫu
Chúng ta vừa hoàn thành một bước trong thuật toán đơn hình, chuyển từ một phương án sang phương án tốt hơn. Để làm điều này, chúng ta có một số biến có giá trị 0 và môt số biến khác, biểu diễn qua các biến này.
Như vậy, đối với phương án mới, chúng ta phải biếu diễn những biến còn lại qua các biến có gía trị 0 là. Điều này có thể làm thông qua ràng buộc (2.2) và rồi chúng ta có bài toán với ràng buộc {
Từ bài toán này, có thể thấy chỉ có thể tăng trong 3 biến mới làm cho hàm mục tiêu tăng lên. Tương tự trên, việc tăng phải bảo đảm giá trị không âm cho các biến khác, điều này thực hiện được nếu . Chọn và ta có phương án mới tại đó .
Chuyển qua bước tiếp, biểu diễn các biến khác và hàm mục tiêu qua. Đến đây, rõ ràng ta không thể tăng biến nào trong các biến mà làm cho hàm mục tiêu tăng lên. Phương án hiện tại là lời giải tối ưu của bài toán.
Bài toán quy hoạch tuyến tính
Chú ý. Trong mỗi bước giải trên, có một số biến được gán giá trị bằng 0 (đgl biến
ngoài cơ sở) và các biến còn lại (đgl biến cơ sở) được tính giá trị theo các biến ngoài
cơ sở thông qua các hệ (2.2), (2.3), (2.4).
Vì vậy, các hệ (2.2)-(2.4) còn đgl các từ điển (biểu diễn hàm mục tiêu và giá trị của các biến cơ sở thông qua các biến ngoài cơ sở).
Xét các từ điển:
Một từ điển là chấp nhận được nếu khi cho các biến ngoài cơ sở bằng 0 thì các biến
cơ sở nhận giá trị không âm.§2.Phương pháp đơn hình. Xét bài toán QHTT dạng 7Ràng buộc.
Bằng cách thêm vào các biến phụ, ta đưa bài toán về dạng ∑Ràng buộc. Đây là từ điển xuất phát. Như trong ví dụ trên, ta sẽ đi từ từ điển này đến một từ điển khác tốt hơn.
Tại mỗi từ điển, ta có biến cơ sở và biến ngoài cơ sở. Kí hiệu là tập chỉ số của các biến trong cơ sở và là tâp chỉ số của các phương án ngoài cơ sở. Như vậy, với từ điển xuất phát ta có và Tại từ điển hiện tại ta có.
Cách thực hiện các bước của phương pháp đơn hình
Tại mỗi bước trong phương pháp đơn hình, chỉ có một biến (đgl biến đưa vào) từ được chuyển vào trong và ngược lại, chỉ có một biến (đgl biến chuyển đi) được chuyển từ vào .Biến đưa vào được chọn với mục đích làm tăng giá trị của hàm hàm mục tiêu. Nghĩa là biến đưa vào được chọn một trong các chỉ số từ tập ̅ .
Phương án tối ưu:
Nếu tập này rỗng thì phương án hiện tại sẽ là phương án tối ưu. Có nhiều cách chọn chỉ số từ tập này, ta sẽ chọn chỉ số sao cho ̅ là số lớn nhất thuộc tập này. Khi đã chọn là biến đưa vào, giá trị của sẽ được thay đổi bằng cách tăng từ 0 đến một giá trị dương.
Điều này làm thay đổi giá trị của các biến cơ sở: Để cho các biến này vẫn thỏa điều kiện không âm, chúng ta cần phải có. Như vậy, sẽ được tăng giá trị nhiều nhất lên đến
P9Xem file PDF GIÁO TRÌNH QUY HOẠCH TUYẾN TÍNH
