§ 2. СТАНДАРТНЫЕ И КАНОНИЧЕСКИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

Стандартные и канонические задачи.

Всюду ниже А есть -матрица над полем действительных чисел

b и с — соответственно -мерный и -мерный векторы-столбцы над

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

Линейную форму будем записывать в виде произведения строки на столбец

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

Стандартная задача минимизации С. Найти решение системы

которое минимизирует линейную форму задача максимизации С. Найти решение системы

которое максимизирует линейную форму

Условия (1) и (2) называются линейными ограничениями задач С и С соответственно. Задачи С и С* называются взаимно двойственными.

В матричной форме эти задачи формулируются следующим образом:

С. Найти решение системы

которое минимизирует линейную форму

С. Найти решение системы

которое максимизирует линейную форму

Каноническая задача минимизации К. Найти решение системы

которое минимизирует линейную форму

Задача, двойственная к задаче К:

К. Найти решение системы

которое максимизирует линейную форму

Условия (I) и (II) называются линейными ограничениями задач К и К соответственно. Задачи К и К называются взаимно двойственными.

В матричной форме эти задачи формулируются следующим образом:

К. Найти решение системы

которое минимизирует линейную форму

К. Найти решение неравенства

которое максимизирует линейную форму