1. Стандартная задача линейного программирования.

Найти значения переменных , удовлетворяющие ограничениям

х₁≥0,…, х_n≥0,

и доставляющие наибольшее (наименьшее) значение критерию качества

f=c₁x₁+…c_nx_n.

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

2. Каноническая задача линейного программирования.

Найти значения переменных , удовлетворяющие ограничениям

х₁≥0,…, х_n≥0,

и доставляющие наибольшее (наименьшее) значение критерию качества

f=c₁x₁+…c_nx_n.

Большая часть методов решения задач линейного программирования разработана для задач в канонической форме.

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

Найти значения переменных , удовлетворяющие ограничениям

х₁≥0,…, х_n≥0,

и доставляющие наибольшее (наименьшее) значение критерию качества

f=c₁x₁+…c_nx_n.

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

Системы уравнений (или неравенств) называются ограничениями данной задачи, функцию f называют критерием качества или целевой функцией. Мы будем писатьf max, если требуется найти наибольшее значение f и f min, если наименьшее.

Неравенства

х₁≥0,…, х_n≥0

тоже, конечно, входят в число ограничений, однако они являются общими для всех задач линейного программирования. Неотрицательность переменных существенно используется при решении задач линейного программирования, однако это не значит, что нельзя решать задачи с отрицательными переменными. Действительно, если х принимает отрицательные значения, то можно ввести неотрицательные переменные у и z так, что х=у-z.

Таким образом, всегда можно привести задачу к такому виду, что все ее переменные неотрицательны (правда, при этом, как мы видели увеличится число переменных – но это уже другая проблема). Мы будем считать, что задача уже приведена к такому виду.

Любое неотрицательное решение системы уравнений называют допустимым. Допустимое решение, доставляющее минимум (максимум) критерию качества , называют оптимальным решением. Оптимальное решение не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Кроме того, оптимальное решение может и не существовать.

Отличие стандартной задачи линейного программирования от канонической заключается в том, что в стандартной задаче линейного программирования ограничения задаются в виде системы неравенств, в канонической задаче – в виде системы равенств. В общей задаче линейного программирования ограничения задаются и равенствами и неравенствами. Однако, как мы сейчас увидим, то, в каком виде задаются ограничения не существенно и все три типа задач эквивалентны друг другу в том смысле, что каждую из них можно преобразовать в любую другую.

В самом деле, любое уравнение

можно записать в виде системы неравенств

Поэтому систему уравнений всегда можно свести к системе неравенств, правда при этом число неравенств увеличивается в два раза.

С другой стороны, систему линейных неравенств всегда можно свести к системе уравнений. Покажем это на примере системы двух неравенств.

.

Введем переменные так что

и теперь уже ограничения задаются системой уравнений, правда, при этом увеличивается число переменных.