Раздел 2. Линейное программирование

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или макси­мума) линейной функции при линейных ограничениях. Общая форма задачи имеет вид:

найти   тш сх   при условиях

агж — Ь{ > 0, г £ 1\, агх - Ьг = 0, г £ х3 > 0, 1 е .11,

гдеДи/г = {1,...,т}, 1гГ\12 = 0, Л С {1,..., п}, х = (хг,..., хп)т, с = (с\,..., сп), аг- = (аг1,..., аг)г), г = 1,..., то. Здесь и далее нам удобнее считать с и аг- вектор-строками, а ж и 6 = (Ъ\,..., 6т)т — вектор-столбцами.

Наряду с общей формой широко используются также кано­ническая и стандартная формы. Как в канонической, так и в стандартной форме 3\ = {1,..., га}, т.е. все переменные в любом допустимом решении задачи должны принимать неотрицатель­ные значения (такие переменные принято называть неотрица­тельными, в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не наклады­вается). Отличие же между этими формами состоит в том, что в одном случае 1\ = 0, а в другом — 12 =

Задача ЛП в канонической форме:

ю = сх —> ППП

Ах = Ь ж > 0.

Задача ЛП в стандартной форме:

ю = сх —> ППП

(2.1)

(2.2) (2.3)

8

Ax > b

x > 0.

В обоих случаях А есть матрица размерности т X п, i-я строка которой совпадает с вектором аг-.

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим по­нимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам фор­ме), любое оптимальное решение которой "легко"преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмо­трения задач ЛП будут посвящены, главным образом, задачам в канонической форме.