PHƯƠNG PHÁP HÌNH HỌC

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

a. Phương pháp hình học

Phương pháp hình học là phương pháp dùng đồ thị giải bài toán QHTT gồm hai bước:

1. Xác định vùng lời giải khả thi
2. Xác đinh lời giải tối ưu từ các lời giải trong vùng lời giải khả thi.

Để xác định vùng khả thi, ta sử dụng các đường thẳng mà ta gọi là đường khả thi tạo bởi các ràng buộc của bài toán. Từ vùng khả thi, ta xác định lời giải tối ưu theo phương tăng hay giảm của đường thẳng mà ta gọi là đường mục tiêu xác định bởi hàm mục tiêu tùy thuộc vào bài toán là cực đại hay cực tiểu.

b. Tính chất lời giải tối ưu

Từ lời giải cho các bài toán QHTT theo phương pháp đồ thị, trực quan thấy một tính chất quan trọng của lời giải tối ưu của mô hình QHTT là lời giải tối ưu luôn xác định  một trong các điểm góc của vùng khả thi, điểm góc này là giao điểm của hai đường thẳng tương ứng với hai ràng buộc của bài toán.

Điều này vẫn nghiệm đúng khi đường thẳng tương ứng với phương trình hàm mục tiêu song song với đường thẳng tương ứng với một ràng buộc của bài toán, khi này lời giải tối ưu không còn tương ứng với một điểm góc nữa mà là tương ứng với đoạn thẳng tương ứng với ràng buộc đặc biệt trên. Bài toán tối ưu bây giờ là bài toán đa nghiệm.

TLTK

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