|
|
|
|
Пространство решений |
Ограничения модели стандартной формы |
|
Угловые точки |
Базисное решение задачи в стандартной форме |
Представление пространства решений стандартной задачи линейного программирования .
Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :
Максимизировать
Z = X1 + 25X2 + 0S1 + 0S2
При ограничениях
5X1 + 100X2 + S1 = 1000
- X1 + 2X2 + S2 = 0
X1=>0 , X2=>0 , S1=>0 , S2=>0
Каждую точку пространства решений данной задачи , представленную на рис.1 , можно определить с помощью переменных X1 , X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0 ограничения модели эквивалентны равенствам , которые представляются соответствующими ребрами пространства решений . Увеличение переменных S1 и S2 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и S2 , ассоциированные с экстремальными точками А , В , и С можно упорядочить , исходя из того , какое значение ( нулевое или ненулевое ) имеет данная переменная в экстремальной точке .
Экстремальная точка
Нулевые переменные
Ненулевые переменные
А
S2 , X2
S1 , X1
В
S1 , X2
S2 , X1
С
S1 , S2
X1 , X2
Анализируя таблицу , легко заметить две закономерности:
1. Стандартная модель содержит два уравнения и четыре
неизвестных , поэтому в каждой из экстремальных точек две ( = 4 - 2 ) переменные должны иметь нулевые
значения .
2. Смежные экстремальные точки отличаются только
одной пе-
ременной в каждой группе ( нулевых и ненулевых переменных ) ,
Первая закономерность свидетельствует о возможности опре-
деления экстремальных точек алгебраическим способом
путем при-
равнивания нулю такого количества переменных , которое равно
разности между количеством неизвестных и числом уравнений .
В этом состоит сущность
свойства однозначности экстремальных
точек . На рис. 1 каждой неэкстремальной
точке соответствует
не более одной нулевой переменной . Так , любая точка внутренней
области пространства решений вообще не имеет ни
одной нулевой
переменной, а любая неэкстремальная точка ,
лежащая на границе ,
всегда имеет лишь одну нулевую переменную .
Свойство однозначности экстремальных точек
позволяет опре-
делить их алгебраическим методом. Будем считать , что линейная
модель стандартной формы содержит т уравнений и п ( т <= п ) не-
известных ( правые части ограничений — неотрицательные ) . Тогда
все допустимые экстремальные точки определяются как все
одно-
значные неотрицательные решения системы m уравнений , в ко-
торых п — m переменных равны нулю.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
При использовании материалов активная ссылка на источник обязательна.