Балашовский филиал

3. Формулировка общей задачи
линейного программирования

В общем виде математическая формулировка основной задачи линейного программирования выглядит следующим образом.
Требуется найти значения действительных переменных x₁, x₂,…, x_n, при которых целевая функция (показатель эффективности)
L(X ) = c₁x₁ + c₂x₂ + ... + c_jx_j + ... + c_nx_n + c
принимает экстремальное значение при ограничениях:

x_k 0,
где a_ij, b_i, c_j, c — заданные постоянные величины, i = 1, 2,…, m, j = 1, 2,…, n, .
Заметим, что знак « » в ограничительных условиях выбран условно (для определенности), так как, например, неравенство a_i1x₁+...+ a_inx_n b_i всегда можно заменить на эквивалентное ему неравенство –(a_i1x₁+...+a_inx_n) –b_i,
а уравнение a_i1x₁+...+a_inx_n = b_i — на систему неравенств a_i1x₁+...+a_inx_n b_i и a_i1x₁+...+ a_inx_n b_i. Стоит, однако, отметить, что на практике сведение уравнений к неравенствам, как правило, осуществляют другим способом (см., например, решение транспортной задачи). Если все ограничительные условия, накладываемые на элементы решения, кроме требования x_j 0, являются уравнениями, то в этом случае задачу линейного программирования называют канонической задачей линейного программирования (сокращенно КЗЛП). Ее примером может служить опять же транспортная задача. Заметим, что любая задача линейного программирования может быть приведена к канонической.
Точку или точки (если их несколько), удовлетворяющие системе ограничений, называют допустимым решением (планом) задачи линейного программирования и обозначают . Множество всех допустимых решений называют областью допустимых решений (сокращенно ОДР). Допустимое решение, в котором достигается экстремальное значение целевой функции, называют оптимальным решением (планом) задачи линейного программирования и обозначают _опт.
Формулировку общей задачи линейного программирования (сокращенно ОЗЛП) можно записать более компактно:
L(X) = + c  max (min)
при ограничениях:
_i, i = 1, 2,…, m, x_k 0, .