Nhiều bài toán thực tế được đưa về bài toán tìm giá trị lớn nhất (nhỏ nhất) của biểu thức \(F = ax + by\) trên một miền đa giác – miền nghiệm của một hệ bất phương trình bậc nhất hai ẩn.

Người ta chứng minh được F đạt giá trị lớn nhất hoặc nhỏ nhất tại một trong các đỉnh của đa giác.

Các bước giải

Cho hệ bất phương trình hai ẩn x, y và biểu thức F = ax + by.

Bước 1: Xác định miền đa giác nghiệm và toạ độ đỉnh của đa giác đó.

Bước 2: Tính giá trị của F tại các đỉnh của đa giác. So sánh các giá trị thu được.

Bước 3: Kết luận.

Giải bài toán quy hoạch tuyến tính sau:

F(x; y) = x + 2y → min

với các ràng buộc

\(\left\{ \begin{array}{l}x \ge 0,y \ge 0\\x + y \ge 1\\2{\rm{x}} + 4y \ge 3\end{array} \right.\)

Giải:

Miền nghiệm S của hệ bất phương trình không là miền đa giác và được tô màu như hình vẽ dưới đây:

Có ba điểm cực biên là A(0; 1), B(0,5; 0,5), C(1,5; 0).

Ta có:

F(0; 1) = 2.

F(0,5; 0,5) = 1,5.

F(1,5; 0) = 1,5.

Giá trị nhỏ nhất của F(x; y) = x + 2y là 1,5 và không có giá trị lớn nhất của F(x; y).