Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

пространству. Предположим противное: пусть существует точка

Поскольку с и а принадлежат выпуклому множеству С', любая точка Яа + (1 — Я) с для 0 ^ Я ^ 1 также принадлежит С . По предположению минимум расстояния между b и любой точкой отрезка Яа + (1 — Я) с достигается в точке а, т. е. при Я = 1. Если показать, что минимум расстояния от точки b до отрезка Яа + (1 — Я) с достигается при 0 ^ Я < 1, то теорема будет дока­

f (Я) = [Яа + (1 — Я) с — Ь]2 =

= (а2 + с2 - 2ас) Я2 + (2ас — 2с2 + 2Ьс - 2аЬ) Я + (Ь — с)2 =

Таким образом, минимум расстояния от Ь до рассматриваемой

множеству С , что противоречит предположению о наличии мини­

надлежать множеству С . Но поскольку функция/2 (X) — выпуклая

положению о существовании минимума / (х) в точке а. Таким обра­ зом, точка с не может лежать по ту же сторону от гиперплоско­ сти Н , что и точка Ь. я

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

1.5. Базисные, допустимые и оптимальные решения

Нас интересует отыскание неотрицательных решений системы линейных неравенств (или системы линейных уравнений, получен­ ной эквивалентными преобразованиями, рассмотренными в § 1.2). Поскольку нас будут интересовать только такие задачи линейного программирования, у которых существует конечное оптимальное решение, предположим, что выпуклое множество, задаваемое системой линейных ограничений, замкнуто и ограничено. Так как любая точка замкнутого ограниченного выпуклого множества представима в виде выпуклой линейной комбинации крайних точек этого множества, покажем, что крайние точки соответствуют так называемым базисным решёниям.

Пусть дана система линейных уравнений

Говорят, что система линейных уравнений (1) совместна, если она имеет по крайней мере одно решение. Система (1) называется избыточной, если одно из уравнений можно выразить в виде линейной комбинации остальных. Система (1) несовместна, если ранг матрицы А равен г, а ранг матрицы [А, Ь] больше г. Если система (1) неизбыточна и совместна, то ранг А равен т (т ^ п). Если т > п и система неизбыточна, то решений нет. Далее мы будем предполагать, что система совместна и неизбыточна. Иначе говоря, предполагается, что выбрана неизбыточная подсистема уравнений, эквивалентная данной.

базисными переменными, а компоненты x N — небазисными пере­ менными. Базисное решение называется вырожденным, если одна или более компонент вектора хв равна нулю. Вектор-столбцы матрицы В называются базисными векторами. Иногда будем говорить, что т независимых столбцов матрицы В образуют базис.

Дадим общее определение базисного решения системы (1)т где Аесть(лг X ?г)-матрица (т =& п). Решение х системы (1) назы­ вается базисным решением, если вектор-столбцы, соответствую­ щие ненулевым компонентам х, линейно независимы.

Идея базисных решений оказывается полезной применительно к системам линейных неравенств. Мы могли бы, конечно, добавив слабые переменные, превратить неравенства в уравнения и затем применить к ним данное выше определение. Однако можно рас­ смотреть неравенства непосредственно.

Система линейных неравенств совместна, если она имеет хотя бы одно решение. Если одно из неравенств системы является следствием других, то система избыточна. Пусть Ах ^ Ь, х ^ 0 — система линейных неравенств, где А есть (т X н)-матрица. Таким образом, в системе имеется т + п неравенств. Если система совместна, то она определяет непустое выпуклое множество. Базисным допустимым решением является крайняя точка выпук­ лого множества, в которой по крайней мере п из п + т неравенств выполняются как равенства. Более того, эта точка удовлетворяет и остальным т неравенствам. Каждое неравенство определяет замкнутое полупространство по одну сторону от гиперплоскости. Если в крайней точке пересекается более п гиперплоскостей, эта точка дает вырожденное базисное решение. Это один из способов, геометрически поясняющих понятие вырожденное™. Если точка удовлетворяет п неравенствам как равенствам, а остальным нера­ венствам не удовлетворяет, то она-представляет собой точку пере­ сечения п гиперплоскостей, не принадлежащую выпуклому мно­ жеству.

Рассмотрим систему неравенств

— ху -)—2^2^^ 8, Х у -\~ #2 ^^ 10,

Выпуклое множество, определяемое этой системой неравенств, показано на рис. 1.6. Заметим, что в точке Ху = 6, х2 = 4 Пересе-