Каноническая форма задач ЛП

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

Определение. Задача ЛП имеет каноническую форму, если:

1) все ограничения системы состоят только из уравнений,

2) переменные неотрицательны,

3) целевую функцию необходимо максимизировать.

Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, но и неравенства, как было у нас в задачах 2, 3, 4, 5.

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

(9)

Эти дополнительные переменные имеют конкретный экономический смысл, а именно означают величину неиспользованного времени работы (простоя) машины го вида. Например, если бы машины первого вида работали все 18 ч., то следовательно, Но мы допускаем возможность неполного использования времени работы 1-й машины В этом случае приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из результатов § 2.3, мы можем из системы ограничений (9) сделать вывод, что а . То есть машины 1-го, 2-го, 3-го вида используют свое рабочее время полностью, а вот 4-я машина загружена лишь наполовину: 3 часа при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т. д.

Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси (4 из §2.1). Система ограничений имела вид

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

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

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

Рис. 2.6

Посмотрите на рис. 2.6, если в какой-то точке функция достигает своего максимума, то функция , симметричная ей относительно оси OX, в этой же точке достигнет минимума, причем при .

Вып

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