Задача линейного программирования без учета целочисленности

ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ.
Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х* и у* - допустимые решения прямой и двойственной задач и если c^Tx*=b^Ty*, то х* и у* – оптимальные решения пары двойственных задач.

Двойственные задачи линейного программирования (ЛП) Свойства двойственных задач Если целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в ограничениях приводят к виду “ ”, а в задаче на минимум – вид “ ”. Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче являются транспонированными по отношению друг к другу. Число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений двойственной задачи – числу переменных в исходной задаче. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи. Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. Предполагается, что переменные в обеих задачах являются неотрицательными.

О сводимости задачи ЛП общего вида к задаче ЛП в канонической форме.  Правило приведения задачи линейного программирования к каноническому виду состоит в следующем: если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции; если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1; если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства; если некоторая переменная xj не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: