線形計画問題
英: Linear programming problem
有限個の線形等式・線形不等式を満たす変数の組$ (x_1, \dots, x_n)の中で、与えられた線形関数の値を最大化 or 最小化するものを求める問題
最大化: $ c_1x_1 + \cdots + c_nx_n
条件
$ a_{i1}x_1 + \cdots + a_{in}x_n = b_i, \quad i = 1, \dots, k
$ a_{i1}x_1 + \cdots + a_{in}x_n \leq b_i, \quad i = k+1, \dots, l
$ a_{i1}x_1 + \cdots + a_{in}x_n \geq b_i, \quad i = l+1, \dots, m
$ c_1x_1 + \cdots + c_nx_nを目的関数と呼ぶ 英: objective function
変数$ (x_1, \dots, x_n)が満たすべき$ m個の線形等式・線形不等式を制約式・制約条件と呼ぶ 英: constraint