LỜI GIẢI BAN ĐẦU

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

Bước đầu tiên trong giải thuật đơn hình là xác định lời giải cơ bản khả thi ban đầu. Với các bài toán có ràng buộc dạng ”£” và vế phải không âm, khi chuyển các ràng buộc này về dạng phương trình chuẩn bằng cách cộng thêm biến thiếu ở vế trái, ta sẽ có được 1 hệ phương trình ràng buộc, từ đó có bảng đơn hình chuẩn và có ngay lời giải cơ bản khả thi ban đầu.

Tuy nhiên, trong thực tế có khi ràng buộc có dạng ”=” hay ”³” trong trường hợp này để có lời giải cơ bản khả thi ban đầu ta phải sử dụng biến nhân tạo. Biến nhân tạo đóng vai trò của biến thiếu để tạo lời giải cơ bản khả thi ban đầu ở  bảng đơn hình đầu tiên, sau đó sẽ bị mất đi ở những lần lặp sau.

Hai phương pháp xác định lời giải cơ bản khả thi ban đầu bao gồm:

• Phương pháp số lớn M
• Phương pháp 2 pha.

a. Phương pháp số lớn M

Ở phương pháp số lớn, sau khi chuyển đổi hệ các ràng buộc thành hệ phương trình chuẩn, với các phương trình tương ứng với các ràng buộc nguyên thủy dạng ”=” hay ”³”, ta thêm vào các biến nhân tạo. Để các biến nhân tạo này mất đi, hay bằng 0 trong lời giải tối ưu, ta thêm các biến nhân tạo này vào hàm mục tiêu với hệ số:

• –M với bài toán cực đại
• +M với bài toán cực tiểu

Trong đó M là một số lớn.

b. Phương pháp 2 pha

Phương pháp số lớn có chênh lệch giá trị của các hệ số trong hàm mục tiêu lớn nên dẫn đến ảnh hưởng đến các phép toán đơn hình. Nhằm tránh nhược điểm này ta dùng phương pháp hai pha để xác định lời giải cơ bản khả thi ban đầu và sau đó xác định lời giải tối ưu cho bài toán.

Phương pháp hai pha bao gồm hai pha.

• Pha 1: Xác định lời giải cơ bản khả thi ban đầu.
• Pha 2: Xác định lời giải tối ưu cho bài toán

i. Pha 1: Xác định lời giải cơ bản khả thi ban đầu

Sau khi chuyển các ràng buộc của bài toán thành hệ phương trình chuẩn, thêm các biến nhân tạo vào hệ phương trình ràng buộc như ở phương pháp số lớn. Tuy nhiên mục tiêu ở phương pháp này là cực tiểu hàm mục tiêu là tổng các biến nhân tạo.

Với bài toán vừa xác định, nếu lời giải tối ưu cho giá trị hàm mục tiêu là 0 thì lời giải của bài toán sẽ được sử dụng như lời giải cơ bản khả thi ban đầu cho bài toán gốc. Ngược lại, nếu lời giải tối ưu cho giá trị hàm mục tiêu là dương thì bài toán gốc không có lời giải khả thi để có thể tìm lời giải tối ưu.

ii. Pha 2: Xác định lời giải tối ưu cho bài toán

Khi pha 1 đã tìm ra lời giải cơ bản khả thi ban đầu, ta chuyển qua pha 2 để xác định lời giải tối ưu cho bài toán gốc. Lời giải tìm được ở pha 1 sẽ được dùng làm lời giải ban đầu và xây dựng hệ phương trình ràng buộc. Hàm mục tiêu ban đầu của bài toán gốc sẽ được phục hồi để làm hàm mục tiêu cho bài toán ở pha 2.

TLTK

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