Основные понятия и теоремы линейного программирования

Рассмотрим каноническую задачу линейного программирования. Перепишем её в векторной форме: найти минимум функции L=CX при условиях

где C=(с₁;с₂;…;с_n), X=(х₁;х₂;…;х_n); CX – скалярное произведение векторов; А₁,…,А_n и В – m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

.

Определение 5.1. План X=(х₁;х₂;…х_n) называется опорным планом канонической задачи линейного программирования, если система векторов A_j, входящих в разложение (5.4) с положительными коэффициентами, линейно независима.

Так как векторы A_j являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m.

Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным.

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

Теорема 5.1. Множество планов канонической задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов канонической задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

Теорема 5.2. Если каноническая задача линейного программирования имеет оптимальный план, то максимальное (минимальное) значение целевая функция задачи принимает в одной из вершин многогранника решений. Если максимальное (минимальное) значение целевая функция задачи принимает более, чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной комбинацией его вершин.

Теорема 5.3. Если система векторов А₁,А₂,…,А_k (k≤n) в разложении (5.4) линейно независима и такова, что А₁х₁+А₂х₂+…+А_kx_k=B, где все x_j≥0, то точка X=(х₁;х₂;…;х_k;0;…;0) является вершиной многогранника решений.

Теорема 5.4. Если X=(х₁;х₂;…х_n) – вершина многогранника решений, то вектора A_j, соответствующие положительным x_j в разложении (5.4), линейно независимы.

Сформулированные теоремы позволяют сделать следующие выводы.

Непустое множество планов канонической задачи линейного программирования образуют выпуклый многогранник. Каждая вершина этого многогранника определяет опорный план. В одной из вершин многогранника решений (т.е. для одного из опорных планов) значение целевой функции является максимальным (минимальным) при условии, что функция ограничена сверху (снизу) на множестве планов. Если экстремальное значение функции принимает значение более, чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин, т. е. на отрезке.

Вершину многогранника решений, в которой целевая функция принимает экстремальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более 2-х переменных или задача, записанная в форме канонической, содержит не более 2-х свободных переменных, т.е. n-r≤2, где n – число переменных, r – ранг матрицы, составленной из коэффициентов в системе ограничений задачи.