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

$\{\begin{array}{c}x\ge 0,y\ge 0\\ x+y\ge 1\\ 2x+4y\ge 3\end{array}$

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).