Построение экономической модели с использованием симплекс-метода
| Категория реферата: Рефераты по математике
| Теги реферата: оформление дипломной работы, ответы по контрольной
| Добавил(а) на сайт: Шибалкин.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
|
Экстремальная точка |
Нулевые переменные |
Ненулевые переменные |
|
А |
S2, X2 |
S1, X1 |
|
В |
S1, X2 |
S2, X1 |
|
С |
S1, S2 |
X1, X2 |
Анали зи руя табли цу, легко замети ть две з акономерности:
1. Стандартная модель содержи т два уравнения и четыре неизвестных, поэтому в каждой и з экстрема льных точек две ( = 4 2 ) переменные должны и меть нулевые значения.
2. Смежные экстремальные точки отличаются только одн ой переменной в каждой группе ( нулевых и нен уле вых переменных ),
Первая закономерность св идетельствует о возможности определения экстремальных точек алгебраически м способом путем при равнивания нулю такого коли чества пере менных, которое равно разности между количеством неизвестных и чи слом уравнений. В этом состои т сущн ость свойства однозна чности экстремальных точек. На ри с. 1 каждой неэкстремальной точке соответствует не более одной нулевой переменной. Так, любая точка внутренней области пространства решений вообще не и меет ни одной нулевой переменной, а любая неэкстремальная точка, лежащая на границе, всегда имеет лишь одну нулевую переменную.
Свойство однозначности экстремальных точек позволяет определить их алгебраическим методом. Буд ем счи тать, что линейная модель стандартной формы содержи т т уравнени й и п ( т <= п ) неизвестных ( п равые части ограничений — неотри цательные ). Тогда все допустимые экстремальные точки оп реде ляются как все однозначные неотрицательные решения си стемы m уравнени й, в которых п — m пе ременных равны нулю.
Однозначные решения такой системы уравнений, получаемые путем п риравни вания к нулю ( п — т ) переменных, называются базисными решениями. Если базисное реше ние удовлетворяет требованию неотрицательности правых частей, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение, н азываются небазисными переменными, остальные — базисными переменными.
Из вышеи зложенного следует, что при реа ли зации си мп лексметода алгебраическое оп ределение бази сных решени й соответствует иденти фи кации экстремальных точек, осуществляемой при геометрическом представлении пространства решений. Таким образом, максимальное число и тераци й при использовании симплексметода равно максимальному числу бази сных решени й задачи ЛП, представленной в стандартной форме. Это означает, что количество итераци онных процедур си мпле кс-метода не превышает
Cпт= n! / [ ( n m )!m! ]
Вторая из ране е отмеченных закономе рн остей оказывается весьма поле зной для п остроения вычислите льных процедур симплекс-метода, при реали зац ии которого осуществляется последовательный п ере ход от одной кстре мальной точки к другой, смежной с ней. Так как смежные экстре мальные точк и отличаются только одной п еременн ой, можно определить каждую последующую ( смежную) экстремальную точку путем заме ны одной и з текущих небазисных ( нулевых ) переменных текущей базисн ой переменной. В нашем случае получено решение, соотве тствующее точке А, откуда следует осуществить переход в точку В. Для этого нужно увели чив ать небазисную переменную X2 от исходного н улевого зн ачен ия до значения, соответствующего точке В ( см. рис. 1 ). В точке B переменная S1 ( которая в точке А была бази сной ) автоматическ и обращается в нуль и, следовательно, станови тся небазисной еремен ной. Таким образом, между множеством небазисных множество м базисных переменных происходит взаимообме н п еремен ными X2 и S1. Этот процесс можно наглядн о предс тави ть в виде следующей таблицы.
|
Экстремальная точка |
Нулевые переменные |
Ненулевые переменные |
|
А Рекомендуем скачать другие рефераты по теме: мировая война реферат, конспект урока 3. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная