Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

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

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

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

.

|Геометрическое |Алгебраическое |
|определение |определение |
| |( симплекс метод ) |
|Пространство решений |Ограничения модели |
| |стандартной формы |
|Угловые точки |Базисное решение задачи в|
| |стандартной форме |

Представление пространства решений стандартной задачи линейного программирования .

Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :

Максимизировать

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 каждой неэкстремальной точке соответствует

не более одной нулевой переменной . Так , любая точка внутренней

Рекомендуем скачать другие рефераты по теме: скачать реферат человек, хозяйство реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата