Опорные решения задачи линейного программирования

Методы решения задачи линейного программирования

Опорные решения задачи линейного программирования

Пусть дана задача линейного программирования в канонической форме записи

(1)

при условиях

(2)

(3)

Будем обозначать через множество решений системы (2) – (3). Предположим, что , где – ранг матрицы , – количество уравнений в системе (2). Из системы векторов-столбцов матрицы выберем некоторую линейно независимую подсистему из векторов . Она существует, так как . Эта система образует базис в . Обозначим через , . Назовем множеством базисных значений индекса , – базиснойподматрицей матрицы . Координаты вектора будем называть базисными, если , и небазисными в противном случае.

Запишем систему (2) в виде . Разобьем слагаемые левой части на базисные и небазисные, то есть

. (4)

Определим частное решение этой системы следующим образом. Положим в (4) все небазисные переменные равными нулю . Тогда система (4) примет вид

. (5)

Назовем (5) базисной подсистемой системы уравнений (2). Обозначим через вектор, составленный из базисных координат вектора . Тогда систему (2) можно переписать в векторно-матричном виде

. (6)

Так как подматрица является базисной, она

невырождена. Поэтому система (6) имеет единственное решение . Полученное таким образом частное решение системы (2) назовем опорным решением прямой задачи линейного программирования, соответствующим базису . (Иногда опорное решение также называют базисным). Как видим, базису соответствует единственное опорное решение. Очевидно, что число опорных решений конечно.

Для данного базиса определим также и опорное решение двойственной задачи линейного программирования. Напомним, что задача двойственная к канонической имеет вид

(7)

при условиях

. (8)

Запишем систему (8) в виде

. (9)

Напомним, что множество решений системы (8) обозначается через .

Определим вектор двойственных переменных из условия выполнения базисных ограничений в системе (9) как равенств. Получим следующую систему линейных уравнений:

. (10)

Обозначим через вектор, составленный из ба-

зисных координат вектора . Тогда систему (10) можно переписать в векторно-матричном виде

. (11)

Система (11) также имеет единственное решение . Назовем его опорным (базисным) решением двойственной задачи линейного программирования, соответствующим базису . Это опорное решение также определяется однозначно.

Итак, любому базису соответствуют два вектора – два опорных решения и прямой и двойственной задач линейного программирования, соответственно.

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

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

ние называется псевдопланом прямой задачи. Для двойственной допустимости базиса достаточно выполнения только небазисных неравенств . Заметим, что опорный план является допустимым вектором двойственной задачи линейного программирования ().

Разности левых и правых частей неравенств (9) обозначим через , . Тогда двойственную допустимость базиса можно устанавливать, проверяя неотрицательность всех . Заметим, что, как следует непосредственно из определения, все базисные невязки равны нулю (). Поэтому достаточно убедиться в выполнении неравенств для всех .

Познакомимся далее с некоторыми свойствами опорных решений, которые понадобятся нам при отыскании решений задач линейного программирования.

Теорема 1. Пусть и – опорные решения задачи линейного программирования, соответствующие некоторому базису , тогда имеет место равенство .

Доказательство. Из определений опорных решений легко получить равенства

,

откуда и следует справедливость теоремы.

Теорема 2. (Критерий оптимальности опор-ных решений) Если базис одновременно допустим и двойственно допустим, то соответствующие ему опорные решения и являются решениями, соответственно, прямой и двойственной задач линейного программирования.

Доказательство. Справедливость этого утверждения следует из теории двойственности в линейном программировании и теоремы 1.

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

Доказательство. Пусть – опорный план задачи (1) – (3). Докажем, что – вершина множества . По определению опорный план – допустимое опорное решение, соответствующее некоторому базису , то есть – решениесистемы линейных уравнений относительно переменных

Легко увидеть, что эта система имеет единственное решение. Значит, несущая плоскость грани, содержащей точку , имеет размерность 0. Следовательно, – вершина множества .

Обратно. Пусть – вершина множества . Докажем, что – опорный план задачи (1) – (3). Так как – вершина, то она является гранью множества , размерность которой равна нулю. Следовательно, у вектора найдется не менее нулевых компонент, множество номеров которых обозначим . Таким образом, – единственное решение системы

(12)

где . Поэтому осталось доказать, что система векторов линейно независима. Предположим противное. Тогда существуют числа не все равные нулю, такие что . Поэтому

Это означает, что система (12) имеет решение, отличное от , что противоречит единственности ее решения. Таким образом, – базис, а вектор – соответствующий ему опорный план задачи (1) – (3). Что и требовалось.

Заметим, что допустимое решение задачи (7), (8) (двойственной задаче (1) – (3)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .