Viết hệ bất phương trình từ miền đa giác

Đa giác lồi là phần chung của các nửa mặt phẳng mà bờ chính là đường thẳng chứa các cạnh, mỗi nửa mặt phẳng chứa cả đa giác. Do đó:

Hệ này đúng là hệ cần tìm vì giao của $n$ nửa mặt phẳng ấy chính là đa giác (đây là tính chất của đa giác lồi). Nếu đa giác bị chặn có $n$ đỉnh thì cũng có $n$ cạnh, tức $n$ bất phương trình.

Cho $A(x_A;\,y_A)$, $B(x_B;\,y_B)$ phân biệt.

• Cắt hai trục tại $(p;\,0)$ và $(0;\,q)$ ($p, q \ne 0$): $\dfrac xp + \dfrac yq = 1$, nhân hai vế để khử mẫu. Ví dụ qua $(4;\,0)$ và $(0;\,3)$: $\dfrac x4 + \dfrac y3 = 1 \Rightarrow 3x + 4y = 12$.
• Tổng quát: vectơ $\overrightarrow{AB} = (u;\,v)$ chỉ phương, nên

• Cạnh song song trục: $x =$ hằng số hoặc $y =$ hằng số.
• Bất cứ khi nào có phương trình, thế lại hai điểm để chắc chắn.

Với cạnh có bờ $d\colon ax + by = c$, lấy một điểm nằm bên trong đa giác (ví dụ trọng tâm tam giác, trung điểm của một đường chéo, hoặc một điểm nguyên rõ ràng), thay vào $ax + by$:

• nếu $ax_I + by_I < c$ thì bất phương trình là $ax + by \le c$;
• nếu $ax_I + by_I > c$ thì là $ax + by \ge c$.

Điểm trong là điểm không nằm trên bất kì cạnh nào, nên cho giá trị khác $c$ rõ ràng.

Tập nghiệm của hệ là giao các nửa mặt phẳng, mà mỗi nửa mặt phẳng lồi, nên miền nghiệm luôn lồi. Một đa giác "lõm" (có góc trong lớn hơn $180^\circ$, như hình chữ L) không là miền nghiệm của hệ nào; muốn mô tả nó phải ghép nhiều hệ (hợp các miền lồi).

• Mỗi cạnh của đa giác lồi $\to$ một bất phương trình; bờ là đường thẳng chứa cạnh.
• Phương trình qua hai điểm: cắt trục $\dfrac xp + \dfrac yq = 1$, hoặc dùng vectơ chỉ phương.
• Chọn chiều bằng một điểm bên trong đa giác.
• Kiểm bằng đỉnh: mỗi đỉnh nằm trên hai bờ và thoả hết các bất phương trình còn lại.
• Chỉ có miền lồi mới là miền nghiệm của một hệ.