PHƯƠNG PHÁP ELLIPSOID CẢI TIẾN VÀ ỨNG DỤNG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

Tóm tắt

Trong bài báo này, chúng tôi nghiên cứu phương pháp Ellipsoid và phương pháp Ellipsoid cải tiến để tìm một điểm thỏa mãn hệ bất phương trình tuyến tính, và ứng dụng các phương pháp này vào bài toán quy hoạch tuyến tính. Đầu tiên, chúng tôi trình bày giải thuật Ellipsoid và chứng minh sự hội tụ của nó. Sau khi phân tích những hạn chế của giải thuật này, chúng tôi đưa ra giải thuật Ellipsoid cải tiến và chứng minh sự hội tụ của giải thuật mới này. Sau đó, chúng tôi trình bày cách ứng dụng phương pháp này vào giải bài toán tìm phương án chấp nhận được và phương án tối ưu chấp nhận được trong bài toán quy hoạch tuyến tính. Cuối cùng, một số ví dụ cụ thể được xem xét nhằm minh họa phương pháp Ellipsoid. Các chương trình được viết trong phần mềm Matlab cũng được trình bày chi tiết.