Составители:
Рубрика:
63
2.1.10. Опорное решение
Из приведенного в первой части описания общей модели задач линейного
программирования следует, что существенным элементом модели является условие
неотрицательности переменных, входящих в задачу. Поэтому нас будут интересовать
только те решения системы ограничений задачи линейного программирования, в которых
все неизвестные принимают неотрицательные решения. Такие решения называются
допустимыми, а совокупность всевозможных допустимых решений системы ограничений
задачи — областью определения целевой функции. Существует бесчисленное множество
допустимых решений, среди них особое значение в методах линейного программирования
имеют опорные решения, которые в гл. I назывались программами, или опорными
планами.
Опорными решениями называются неотрицательные базисные решения, т. е.
допустимые базисные решения, у которых все базисные неизвестные принимают только
неотрицательные значения.
Опорное решение является некоторым базисным решением, но не всякое базисное
решение является опорным. Поэтому опорных решений у системы не больше чем
базисных, т. е. во всяком случае не больше, чем
r
n
C , где п—число неизвестных и r—ранг
системы.
В теории линейного программирования доказывается теорема об опорных
решениях, которая имеет большое значение. Эта теорема утверждает, что если задача
линейного программирования имеет решение, то она имеет, по крайней мере, одно
оптимальное опорное решение. Из этой теоремы следует, что если задача линейного
программирования имеет одно оптимальное решение, то это единственное оптимальное
решение должно являться одним из опорных решений. Если же задача линейного
программирования имеет бесчисленное множество решений (дающих одно и то же оп-
тимальное значение целевой функции), то среди них найдется, по крайней мере, одно
опорное решение.
Теорема об опорных решениях указывает, что оптимальное решение задачи
линейного программирования следует искать не среди бесчисленного множества
допустимых решений, а среди только конечного числа допустимых решений, которые
являются опорными решениями.
Ниже будем рассматривать невырожденную задачу линейного программирования,
в которой каждое опорное решение является невырожденным, т. е. в каждом опорном
решении все базисные неизвестные положительны. Это значит, что в каждой таблице в
столбце В содержатся только положительные числа. Для того чтобы исходное базисное
решение, связанное с единичным базисом, было опорным, необходимо, чтобы свободные
члены системы уравнений были положительными. Мы всегда можем сделать свободные
члены системы уравнений положительными, изменяя, если это нужно, знаки в обеих
частях уравнений. Поэтому в дальнейшем изложении мы всегда будем считать свободные
члены уравнений положительными числами.
Существующие конечные методы решения задач линейного программирования, в
частности симплексный метод, основаны на упорядоченном переборе опорных решений.
Сначала находится некоторое исходное опорное решение и определяется, не является ли
оно оптимальным. Если да, то задача решена, если нет, то переходят к другому опорному
решению, которое по значению целевой функции лучше, чем исходное опорное решение.
В случае задачи на максимум переход к новому опорному решению должен давать
большее значение целевой функции, а в случае задачи минимизации — меньшее значение
целевой функции. Так, постепенно, переходя от одного опорного решения к другому, мы в
конце концов достигаем оптимального решения. Прежде надо выяснить вопрос, как
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
