PHƯƠNG PHÁP ĐẠI SỐ

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a.  Biến cơ bản và Lời giải cơ bản

Giải bài toán QHTT bằng phương pháp hình học có ưu điểm trực quan và đơn giản nhưng chỉ giải được với bài toán hai biến, với bài toán nhiều biến phải dùng phương pháp đại số được suy diễn từ phương pháp hình học với các bước như ở bảng sau.

Quan hệ các đại lượng cơ bản giữa hai phương pháp như ở bảng sau:

Vùng lời giải ở phương pháp đại số xác định bởi hệ m phương trình chuẩn với n ẩn số các trường hợp có thể xảy ra như sau:

• m > n: hệ có ít nhất m-n phương trình thừa bài toán có thể vô nghiệm
• m = n: hệ chỉ có 1 nghiệm, và cũng là lời giải tối ưu
• m < n: hệ có vô số nghiệm vấn đề tìm lời giải tối ưu được đặt ra.

Vậy bài toán tối ưu chỉ đặt ra trong trường hợp m < n. Trong trường hợp này bài toán sẽ có vô số nghiệm. Để tìm các nghiệm này, ta chỉ cho trước giá trị của n-m biến và xác định m biến còn lại.

Nếu gọi n-m biến là biến không cơ  bản và gán trị 0 để tìm m biến còn lại mà ta gọi là biến cơ bản thì ta sẽ được lời giải gọi là lời giải cơ  bản.

b. Phương pháp đại số

Khi đã xác định được các lời giải khả thi, đây cũng là những ứng viên cho lời giải tối ưu, ta đánh giá tính tối ưu của các lời giải này qua hàm mục tiêu. Phương pháp đại số gồm các bước:

1. Chuyển đổi các ràng buộc thành hệ m phương trình chuẩn với n biến.
2. Xác định các lời giải cơ bản
   1. Chọn n-m biến không cơ bản, gán trị 0
   2. Xây dựng hệ phương trình các biến cơ bản
   3. Xác định giá trị các biến cơ bản
3. Xác định các lời giải cơ bản khả thi theo ràng buộc
4. Xác định các lời giải cơ bản tối ưu theo hàm mục tiêu

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010