Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Математика » Математические методы в экономике

Метод искусственного базиса (симплекс-метод)

Полезная статья? Пожалуйста, поставьте "+"
Математические методы в экономике - Содержание

Данный метод решения применяется при наличии в системе ограничений и условий-равенств, и условий-неравенств, и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных Ri со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).

Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, адополнительные (xn+m) и искусственные (Ri)- базисными.

Исходная таблица для "Метода искусственного базиса" имеет следующий вид:


x1 x2 ... xn-1 xn b
F -a0,1 -a0,2 ... -a0,n-1 -a0,n -b0
xn+1 a1,1 a1,2 ... a1,n-1 a1,n b1
xn+2 a2,1 a2,2 ... a2,n-1 a2,n b2
Ri ai,1 ai,2 ... ai,n-1 ai,n bi
... ... ... ... ... ... ...
xn+m am,1 am,2 ... am,n-1 am,n bm
M -∑ai,1 -∑ai,2 ... -∑ai,n-1 -∑ai,n -∑bi

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

Алгоритм.

Подготовительный этап.

Приводим задачу ЛП  к каноническому виду

F=a0,1x1+a0,2x2+...a0,nxn +b0 → max

a1,1x1+a1,2x2+...a1,nxn+xn+1=b1

a2,1x1+a2,2x2+...a2,nxn+xn+2=b2

.........................................

ai,1x1+ai,2x2+...ai,nxn+Ri=bi

.......................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, xn+m , к каждому i-му условию-равенству добавляем искусственную переменную Ri.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче:


x1 x2 ... xn-1 xn b
F -a0,1 -a0,2 ... -a0,n-1 -a0,n -b0
xn+1 a1,1 a1,2 ... a1,n-1 a1,n b1
xn+2 a2,1 a2,2 ... a2,n-1 a2,n b2
Ri ai,1 ai,2 ... ai,n-1 ai,n bi
... ... ... ... ... ... ...
xn+m am,1 am,2 ... am,n-1 am,n bm
M -∑ai,1 -∑ai,2 ... -∑ai,n-1 -∑ai,n -∑bi

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

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

Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b0- текущее значение целевой функции и элемент -∑bi) нет отрицательных, то найдено оптимальное решение.

2.1 Положительность строки M

Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑bi)

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

bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2

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

Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2.

2.2 Положительность строки F

Проверяем на положительность элементы строки F. Если имеются отрицательные элементы ( не считая b0), выбираем среди отрицательных элементов строки F максимальный по модулю.

-a0,l=min{-a0,i }

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

bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы

При составлении новой симплекс-таблицы в ней происходят следующие изменения:

  • Вместо базисной переменной xk записываем xl; вместо небазисной переменной xlзаписываем xk.
  • ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l
  • все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l
  • все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l
  • оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,l×ak,j/ ak,l
Категория: Математические методы в экономике | Добавил: Ni-Cd (14 Декабрь 2011)
Просмотров: 3951 | Рейтинг: 2.7/3
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Теория вероятностей и математическая статистика (ТерВер и МатСтат) [17]
Математический анализ (МатАн) [67]
Математические методы в экономике [24]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2017 © Ni-Cd. All Rights Reserved