Формы записи задач линейного программирования

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

f = max (min) (2.1.)

при линейных ограничениях

и при условиях

,

, , (2.3.)

где J₁ J₂ =(j= ) и а_ij, b_i, c_j — постоянные числа.

Симметричной формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл неравенства вида «≤» и все переменные неотрицательны, т.е.

f = max (2.4.)

(2.5.)

(2.6.)

Канонической формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл равенства и все переменные неотрицательны, т.е.

f = max (2.7.)

(2.8.)

(2.9.)

На практике часто приходится одну форму записи задачи линейного программирования преобразовывать в другую. При этом пользуются следующими соображениями:

1) При необходимости задачу максимизации можно заменить задачей минимизации и наоборот. Экстремум этих функций достигается в одной и той же точке, т.е. min f = - max (-f). После решения задачи max (-f) необходимо изменить на противоположный знак оптимума функции.

2) Если на какую-либо переменную не наложено условие неотрицательности (например х_к), то её можно заменить разностью двух новых неотрицательных переменных (х_к’ и x_к’’), т.е. х_к=х_к’–x_к’’.

3) Любое ограничение неравенство задачи линейной оптимизации вида “ ”, можно преобразовать в равенство добавлением к его левой части дополнительной неотрицательной переменной, а неравенство, вида “ ” ― вычитанием из его левой части дополнительной неотрицательной переменной.

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

Известно, что система "m" уравнений с "n" переменными может быть как совместной, так и несовместной, а уравнения системы как зависимыми, так и независимыми. В дальнейшем условимся, что все "m" уравнений системы линейно не зависимы. Совместная система "m" уравнений с "n" неизвестными имеет бесконечное множество всевозможных решений.

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