Курсовая работа: Построение экономической модели с использованием симплекс-метода

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

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

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 пе ременных равны нулю.

Однозначные решения такой системы уравнений, получаемые путем п риравни вания к нулю ( п — т ) переменных, называются базисными решениями. Если базисное реше ние удовлетворяет требованию неотрицательности правых частей, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение, н азываются небазисными переменными, остальные — базисными переменными.

Из вышеи зложенного следует, что при реа ли зации си мп лексметода алгебраическое оп ределение бази сных решени й соответствует иденти фи кации экстремальных точек, осуществляемой при геометрическом представлении пространства решений. Таким образом, максимальное число и тераци й при использовании симплексметода равно максимальному числу бази сных решени й задачи ЛП, представленной в стандартной форме. Это означает, что количество итераци онных процедур си мпле кс-метода не превышает

Cпт= n! / [ ( n m )!m! ]

Вторая из ране е отмеченных закономе рн остей оказывается весьма поле зной для п остроения вычислите льных процедур симплекс-метода, при реали зац ии которого осуществляется последовательный п ере ход от одной э кстре мальной точки к другой, смежной с ней. Так как смежные экстре мальные точк и отличаются только одной п еременн ой, можно определить каждую последующую ( смежную) экстремальную точку путем заме ны одной и з текущих небазисных ( нулевых ) переменных текущей базисн ой переменной. В нашем случае получено решение, соотве тствующее точке А, откуда следует осуществить переход в точку В. Для этого нужно увели чив ать небазисную переменную X2 от исходного н улевого зн ачен ия до значения, соответствующего точке В ( см. рис. 1 ). В точке B переменная S1 ( которая в точке А была бази сной ) автоматическ и обращается в нуль и, следовательно, станови тся небазисной п еремен ной. Таким образом, между множеством небазисных и множество м базисных переменных происходит взаимообме н п еремен ными X2 и S1. Этот процесс можно наглядн о предс тави ть в виде следующей таблицы.

Экстремальная точка	Нулевые переменные	Ненулевые переменные
А	S2, X2	S1, X1
В	S1, X2	S2, X1

Применяя аналогичную процедуру ко всем экстремальным точкам рис. 1, можно убедиться в том, что любую последующую экстремальную точку всегда можно определить путем взаимной замены по одной переменной в составе базисных и небазисных переменных ( предыдущей смежной точки ). Этот фактор существенно упрощает реализацию вычислительных процедур симплекс-метода.

Рассмотренный процесс взаимной замены переменных приводит к необходимости введения двух новых терминов. Включаемой переменной называется небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации ( при переходе к смежной экстремальной точке ). Исключаемая переменная — это та базисная переменная, которая на следующей итерации подлежит исключению из множества базисных переменных.

Вычислительные процедуры симплекс-метода.

симплекс-алгоритм состоит из следующих шагов.

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю п — т ( небазисных ) переменных.

Шаг 1. Из числа текущих небазисных ( равных нулю ) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2.

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

Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1.

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

Z X1 25X2 +0S1 -0S2 = 0 ( Целевая функция )

5X1 + 100X2 + S1 = 1000 ( Ограничение )

-X1 + 2X2 + S2 = 0 ( Ограничение )