Способы преобразования задач ЛП

· При необходимости задачу максимизации можно заменить задачей минимизации, и наоборот. Если - точка максимума функции у=f(x), то для функции у=-f(x) она является точкой минимума, т.к. графики у=f(x) и у=-f(x) симметричны относительно Ох.

Итак, если , то .

При этом неравенства типа ≤ можно заменить на неравенства типа ≥, умножая обе части ограничений на -1.

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

1)Ограничения-неравенства типа ≤ преобразуется в равенства добавлением к их левым частям дополнительных переменных , после чего система неравенств примет вид . (22)

При этом число дополнительных неотрицательных переменных равно числу преобразуемых неравенств.

2) Ограничения-неравенства типа ≥ преобразуется в равенства вычитанием из их левых частей дополнительных переменных , после чего система неравенств примет вид . (23)

При этом число дополнительных неотрицательных переменных равно числу преобразуемых неравенств.

3) Дополнительные переменные в целевую функцию вводятся с коэффициентами, равными нулю:

.

Замечание: В реальных практических задачах дополнительные переменные имеют определенный смысл. Например, если левая часть ограничений задачи отражает расход ресурсов на производство продукции в объемах , а правые части – наличие производственных ресурсов, то числовые значения дополнительных переменных означает объем неиспользованных ресурсов i -го вида. Дополнительные переменные еще называют балансовыми.

4) В ряде производственно-экономических задач не на все переменные налагаются условия неотрицательности (любого знака может быть). В подобных ситуациях, даже если ограничения представлены в виде равенств, задача не будет канонической. Для представления такой задачи в каноническом виде каждую из переменных , на которую не наложено условие неотрицательности, заменяют разностью 2-х неотрицательных переменных , т.е.

.

5) если свободные члены в ограничениях-неравенствах, то это ограничение умножают на -1.

· Перейти от канонической формы к стандартной можно, заменив равенства (20) эквивалентной системой неравенств

и

Пример 1: Привести задачу к канонической форме записи: