Общая постановка задачи линейного программирования

из "Экономико-математические модели и методы "

Задача линейного программирования (ЗЛП) в общей постановке имеет три формы произвольную, симметричную и каноническую. [c.45]
Неравенства и равенства в задаче (4.2) называются ограничениями. Каждое неравенство определяет полупространство, а равенство - плоскость в пространстве переменных (Хь Х2,. . ., Хп). [c.45]
Решение задачи (4.2) называется оптимальным решением (или оптимальным планом и обозначается как Х = (Х Ь Х 2,. .., Х п). Оптимальные решения лежат на границе области D. [c.45]
Если область D ограничена, то задача ЛП имеет либо единственное, либо бесконечно много решений. Если решение единственно, то оно совпадает с одной из вершин многогранника D. [c.45]
Если градиент целевой функции с = (сь с2,. .., сп) коллинеарен градиенту одного из ограничений, то задача имеет бесконечно много решений, лежащих на данном ограничении. [c.45]
Если ограничения несовместны, или целевая функция неограниченна, то задача (4.2) не имеет решения. [c.45]
Если область области D не ограничена, то решение может существовать либо быть неограниченным. [c.45]
Всякая задача на минимум может быть сведена к задаче на максимум и наоборот, умножением целевой функции на —1. Оптимальный план задачи при этом не изменится, а значение целевой функции изменит знак. После решения надо снова изменить знак целевой функции. [c.45]
Из линейной алгебры известно, что количество линейно независимых уравнений не может быть больше числа неизвестных. Поэтому в (4.5) можно считать, что п т. [c.46]
Определение. Если в ограничении задачи (4.5) есть переменная с коэффициентом, равным единице, отсутствующая в других ограничениях, то она называется базисной, остальные переменные ограничения называются свободными. [c.46]
Если базисные переменные есть во всех ограничениях, то такая форма ЗЛП называется канонической с базисными переменными. Каноническая форма с базисными переменными является исходной для решения задачи симплексным алгоритмом. [c.46]
Опорным планом называется любой вектор X=(Xj, X2,. .., Х ), удовлетворяющий условиям (4.5) и имеющий не более чем т ненулевых компонент. [c.47]
Если в канонической форме все Ь О, то задача (4.5) имеет опорный план, в котором базисные переменные равны Ь а остальные (свободные) переменные равны 0. Такой план называется начальным опорным планом. [c.47]
Балансовой называется переменная, которая добавляется или вычитается из левой части неравенства для получения равенства. В задачах (4.3), (4.4) балансовые переменные будут базисными. [c.47]
Искусственная переменная вводится, когда в канонической форме ЗЛП в ограничении нет базисной переменной. В этом случае целевая функция изменяется путем вычитания искусственной переменной с коэффициентом М в задаче на максимум и путем прибавления - в задаче на минимум. Коэффициент М считается большим положительным числом. [c.47]
При вводе искусственных переменных и корректировке целевой функции измененная задача называется М-задачей. [c.47]

Вернуться к основной статье