Giá trị lớn nhất, nhỏ nhất của F = ax + by trên miền nghiệm

Với mỗi số $k$, tập các điểm có $F(x;\,y) = k$ là đường thẳng $ax + by = k$, gọi là đường mức $k$. Các đường mức song song với nhau (cùng hệ số $a$, $b$) và khi $k$ tăng thì đường thẳng tịnh tiến về phía mà $ax + by$ tăng, tức về phía vectơ $(a;\,b)$ (như bài 2, mục Mở rộng).

Ví dụ $F = 2x + 3y$: đường mức $k = 0$ qua gốc; $k = 6$ qua $(3;\,0)$ và $(0;\,2)$; $k = 11$ qua $\bigl(\tfrac{11}2;\,0\bigr)$ và $\bigl(0;\,\tfrac{11}3\bigr)$. Càng lên phía trên-phải, $k$ càng lớn.

Để tìm max của $F$ trên $\mathcal D$: hình dung đường mức $F = k$ trượt theo hướng $k$ tăng. Chừng nào đường mức còn cắt $\mathcal D$ thì còn điểm của $\mathcal D$ có $F = k$. Giá trị $k$ lớn nhất mà đường mức còn chạm $\mathcal D$ chính là $\max F$, và nơi chạm là điểm đạt max. Vì $\mathcal D$ là đa giác lồi, đường mức chạm nó lần cuối ở một đỉnh (hoặc, nếu đường mức song song với một cạnh, ở cả cạnh đó). Tương tự cho min khi trượt theo hướng ngược lại.

Lí do (cho đoạn thẳng, rồi suy ra cho đa giác): nếu $M$ nằm trên đoạn $PQ$, $\overrightarrow{PM} = t\,\overrightarrow{PQ}$ với $0 \le t \le 1$, thì toạ độ của $M$ là $(1 - t)$ lần toạ độ $P$ cộng $t$ lần toạ độ $Q$. Do $F$ là hàm bậc nhất,

một số nằm giữa $F(P)$ và $F(Q)$. Vậy trên đoạn $PQ$, giá trị lớn nhất, nhỏ nhất ở hai đầu mút. Một điểm bất kì của đa giác nằm trên một đoạn nối hai điểm của biên, rồi hai điểm biên lại nằm trên các cạnh nối hai đỉnh; áp dụng liên tiếp, giá trị $F$ tại điểm bất kì không vượt quá $\max$ và không dưới $\min$ của các giá trị tại đỉnh.

Khi $\mathcal D$ kéo dài vô hạn, định lí chưa dùng được ngay. Hai ý cần nhớ:

• Nếu $F$ có thể lớn tuỳ ý (hoặc nhỏ tuỳ ý) khi đi dọc một hướng ra xa của miền, thì không có max (hoặc không có min).
• Nếu theo mọi hướng ra xa, $F$ đều không giảm thì có min, đạt tại một đỉnh (tính $F$ tại mọi đỉnh rồi so sánh); tương tự cho max.

Với miền trong góc phần tư thứ nhất ($x \ge 0$, $y \ge 0$) kéo dài ra xa, hướng đi ra xa gồm hướng của trục $Ox$ dương ($F$ tăng $a$ cho mỗi đơn vị) và hướng trục $Oy$ dương ($F$ tăng $b$ cho mỗi đơn vị). Do đó với $a \ge 0$ và $b \ge 0$: có min (đạt tại đỉnh), không có max.

• $F = ax + by$; đường mức $ax + by = k$ song song, trượt theo hướng $(a;\,b)$ khi $k$ tăng.
• Miền đa giác lồi: max, min của $F$ đạt tại đỉnh; hai đỉnh liền kề cùng giá trị thì cả cạnh.
• Quy trình: tìm đủ đỉnh $\to$ bảng $F$ $\to$ so sánh $\to$ kết luận (giá trị; điểm).
• Miền không bị chặn: xét hướng ra xa; có khi chỉ có min hoặc chỉ có max, có khi không có.
• Đừng dùng góc ngoài miền; đừng bỏ đỉnh.