ГЛАВА I.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Основные понятия и определения

Стандартной задачей линейного программирования называется задача, которая состоит в нахождении наибольшего или
наименьшего значения функции

(8)

при условиях

(9)

(10)

(11)

где , , – заданные константы и .

Функция (8) называется целевой функцией задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

Симметричной задачей линейного программирования называется задача, которая заключается в нахождении наибольшего значения функции (8) при выполнении условий (9) и (11), где , .

Канонической задачей линейного программирования называется задача, которая заключается в нахождении наибольшего значения функции (8) при выполнении условий (10) и (11), где , .

Множество чисел , удовлетворяющих условиям задачи (9) – (11), называется допустимым решением или планом.

План , при котором целевая функция задачи (8) приобретает свое наибольшее или наименьшее значение, называется оптимальным.

Значение целевой функции (8) при плане будем обозначать через . Таким образом, – оптимальный план задачи, если для произвольного выполняется неравенство

[соответственно ].

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

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

В том случае, когда нужно найти наименьшее значение функции , можно перейти к отысканию наибольшего значения функции ,

так как .

Ограничение-неравенство начальной задачи линейного программирования, имеющее вид « », можно преобразовывать в ограничение-равенство путем прибавления к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида « » – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Значит, ограничение-неравенство

преобразуется в ограничение-равенство

, (12)

а ограничение-неравенство

– в ограничение - равенство

(13)

В это время любое уравнение системы ограничений

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

(14)

Число включаемых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

Заметим, таким образом, что если переменная , не подчинена условию неотрицательности, то ее надо поменять двумя неотрицательными переменными и , приняв .