Постановка практической задачи ЛП включает следующие основные этапы: определение показателя эффективности, переменных задачи, задание линейной целевой функции S(x), подлежащей минимизации или максимизации, функциональных h_k(x), g_j(x) и областных x_li <x_i <x_ui ограничений.

Приведем сейчас общую математическую формулировку основной задачи линейного программирования.

Дана система т линейных уравнений с п неизвестными:

a₁₁ x₁ + a₁₁ x₂ +  ……  + a₁₁ x_n  =  b₁ ,

a₂₁ x₁ + a₂₁ x₂ +  ……  + a₂₁ x_n  =  b₂ ,

…………………………………………                          (1.1)

a_m1 x₁ + a_m1 x₂ +  …… + a_m1 x_n =  b_m ,

и линейная функция

f = c₁ x₁ + c₂ x_{2 +}………+ c_n x_n                                             (1.2)

Требуется найти такое неотрицательное решение системы

x₁ ≥0, x₂ ≥0, … … , x_n ≥0                                           (1.3)

при котором функция f принимает наименьшее значение.

Уравнения  (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой). Следует заметить, что систему ограничений в виде неравенств всегда можно свести к системе в виде равенств (способом введения фиктивных добавочных неизвестных). Так, если имеется

a_i1 x₁ + a_i1 x₂ +  ……  + a_i1 x_n  ≥  b_i ,

то, вводя неизвестное х_n+1 ≥ 0, получим

a_i1 x₁ + a_i1 x₂ +  ……  + a_i1 x_n  - х_n+1 = b_i ,

(Значением х_n+1  в окончательном результате можно пренебречь.) Кроме того, так как min f = — max ( — f ), то любая задача на (максимизацию сводится к задаче минимизации (и наоборот). Так что постановку задачи линейного программирования в форме (1.1) — (1.3) вполне можно считать общей.

Источник:
Заварыкин В.М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец. пед.ин-тов/В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик.—М.: Просвещение, 1990.—176 с.: ил.
Раздел: Глава 3 Элементы линейного программирования, 3.1.Постановка задачи