I. СВЕДЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К КАНОНИЧЕСКОЙ ФОРМЕ

 

Считают, что задача линейного программирования записана в канонической форме, если она имеет вид:

(1)

 

(2)

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

Рассмотрим возможные отклонения в записи задачи линейного программирования от канонической формы и пути их устранения.

1. Если в задаче линейного программирования нужно найти максимум линейной формы (1), то, учитывая, что , задача сводится к поиску минимума линейной формы .
2. Если часть или все ограничения имеют вид системы линейных неравенств:

(3)

где , то для приведения задачи линейного программирования к каноническому виду необходимо в систему (3) ввести дополнительные неотрицательные переменные и получить такую систему:

(4)

В результате получаем расширенную задачу с переменными

,

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

1. Если часть или все ограничения имеют вид системы линейных неравенств

(5)

где , то для приведения задачи линейного программирования к виду (1), (2) необходимо в систему (5) ввести дополнительные неотрицательные переменные и вместо системы неравенств (5) получить систему

В результате получим расширенную задачу с переменными

,

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

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

(6)

где

В результате получим расширенную задачу переменными

,

которая (за отсутствием других отклонений) будет записана в канонической форме.

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

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

1. Учитывая пункт 1, перейдем к задаче определения минимума:

1. Используя рекомендации пункта 2, введем дополнительные переменные , тогда вместо неравенств

получим систему уравнений

Таким образом, исходная задача линейного программирования будет иметь вид:

1. На переменную не накладывается условие неотрицательности, тогда, учитывая рекомендации пункта 4, сделаем замену: и окончательно получим задачу линейного программирования, записанную в канонической форме: