Định lý cơ bản của quy hoạch tuyến tính

Vì $P$ là một khối đa diện bị chặn được xác định bởi hữu hạn bất đẳng thức tuyến tính, nó có hữu hạn đỉnh $v_1,\ldots,v_k$, và một sự kiện cổ điển về khối đa diện (định lý Minkowski) khẳng định rằng mọi điểm của $P$ đều là tổ hợp lồi của các đỉnh này: $x=\sum_{i=1}^{k}\lambda_i v_i$, trong đó $\lambda_i\ge 0$ và $\sum_i \lambda_i=1$.

Vì hàm mục tiêu $c^{\mathsf{T}}x$ tuyến tính, tính giá trị của nó trên một tổ hợp lồi như vậy cho $c^{\mathsf{T}}x=\sum_i \lambda_i\left(c^{\mathsf{T}}v_i\right)\le \left(\max_i c^{\mathsf{T}}v_i\right)\sum_i\lambda_i=\max_i c^{\mathsf{T}}v_i$, vì mỗi $\lambda_i\ge 0$ và chúng có tổng bằng $1$.

Điều này cho thấy mọi $x$ khả thi đều có giá trị mục tiêu không vượt quá giá trị đỉnh tốt nhất $\max_i c^{\mathsf{T}}v_i$. Nhưng đỉnh tốt nhất đó, gọi là $v_{i^*}$, tự nó là một điểm khả thi của $P$, nên nó thực sự đạt được cận trên này: $c^{\mathsf{T}}v_{i^*}=\max_{x\in P} c^{\mathsf{T}}x$. Do đó giá trị tối ưu của bài toán quy hoạch tuyến tính đạt được tại đỉnh $v_{i^*}$, chứng minh khẳng định.