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

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

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

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

(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)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .