Опорное решение задачи линейного программирования, его взаимосвязь с угловыми точками

Рассмотрим систему ограничений некоторой конкретной задачи

которая в векторной записи имеет вид

,

где

Векторы называются векторами условий.

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

Положительным координатам допустимых решений ставят в соответствие векторы условий. Для решений и такими будут векторы и , соответственно. Эти системы векторов являются линейно зависимыми, так как число входящих в них векторов (4 и 3) больше размерности векторов (2). Таких решений бесконечное множество. Для базисного решения соответствующие положительным координатам единичные векторы и линейно независимые. Как известно, любая система уравнений имеет конечное число базисных решений, равное , где n – число неизвестных, r – ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, называются опорными. В дальнейшем будет показано, что они являются угловыми точками области допустимых решений задачи.

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

Число отличных от нуля координат опорного решения не может быть больше ранга r-системы векторов условий (числа линейно независимых уравнений системы ограничений). В дальнейшем будем считать, что система ограничений состоит из линейно независимых уравнений, т. е. m = r.

Есличисло отличных от нуля координат опорного решения равно m, то оно называется невырожденным, в противном случае (меньше m) вырожденным.

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

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

Теорема 4.4. Любое опорное решение является угловой точкой области допустимых решений.

Доказательство. Пусть – опорное решение с базисом некоторой задачи с системой ограничений . Предположим, что X – не угловая точка, тогда оно является выпуклой линейной комбинацией каких- либо точек области допустимых решений, например, и , т. е.

.

Так как последние n - m координат вектора X равны нулю, а и положительные, то последние n - m координат векторов и также равны нулю, т. е. и .

Подставим в систему ограничений.

.

Вычтем из первого равенства второе, получим

Так как векторы образуют базис, то они линейно независимые, а потому данное равенство может выполняться только тогда, когда все коэффициенты при векторах равны нулю, т. е.

Отсюда получаем Следовательно, и опорное решение X не является выпуклой линейной комбинацией каких-либо допустимых решений, а является угловой точкой области допустимых решений.

Теорема 4.5. Любая угловая точка области допустимых решений является опорным решением.

Доказательство. Пусть угловая точка области допустимых решений и при j = 1, 2,…, m. Чтобы доказать, что это решение является опорным, достаточно показать, что векторы , соответствующие положительным координатам решения, являются линейно независимыми. Предположим, что эти векторы линейно зависимые. Тогда существует ненулевой набор чисел такой, что

(3.2)

Так как X допустимое решение, то имеет место равенство

(3.3)

Умножим соотношение (3.2) на некоторое число и прибавим к равенству (3.3), получим

,

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

.

Для того чтобы эти векторы и удовлетворяли условиям неотрицательности, достаточно малое число e выбирать таким, что . Это возможно, так как при j = 1, 2,…, m.. При таком выборе числа векторы и считаются допустимыми. Нетрудно увидеть, что , т. е. X – выпуклая линейная комбинация и . Однако это противоречит тому, что X является угловой точкой. Следовательно, векторы линейно независимые, и решение X является опорным.

Лекция№5-6.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ
ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ