Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Графический метод линейного программирования

Искусственное начальное решение

В симплекс методе мы предположим, что при начальном базисном решении все остальные решения также допустимы, что, естественно, бывает не всегда. Если у нас есть неравенства, из которых мы видим, что решения будут недопустимыми, то мы вводим дополнительные переменные, которые позволяют нам сформировать допустимое базисное решение. Искусственное решение будем вводить, если в задаче будет стоять знак, < или = для задачи максимизировать, > или = для задачи минимизировать. При вводе искусственных переменных они будут играть роль дополнительных остаточных переменных, в процессе решений от которых мы будем постепенно освобождаться.

Существует 2 метода:

1. М-метод

2. Двухэтапный

1. М-метод: предполагается, что задача у нас записана в стандартной форме, тогда для любого равенства (неравенства), в котором не содержатся дополнительные остаточные переменные, введем искусственную переменную R, которая далее войдет в начальное базисное решение. Но т.к. она не имеет никакого функционального смысла, необходимо, чтобы на следующих интервалах она обратилась в 0, для этого мы вводим штрафы, т.е. в целевую функцию, если максимизируем, добавляем штраф –M×R, если минимизируем, то в целевую функцию добавляем штраф +M×R.

При использовании М-метода необходимо обратить внимание на то, что использование штрафа может и не привести к исключению введенных переменных.

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

 

Теоретически необходимо, чтобы m стремилось к ∞.

Базис   X1   X2  
  Λ1     -4+7μ   -1+4μ
  Λ2      
  S3      
  S4      

 

Благодаря этому, мы можем сравнивать только коэффициенты, стоящие при μ.

 

2. Двухэтапный:

 

1)этап. Ведется поиск начального допустимого базисного решения.

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

 

1)этап: задача линейного программирования записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные аналогично μ-методу. Далее решаются задачи линейного программирования искусственных переменных с исходными ограничениями. Если минимальное значение целевой функции >0, то исходная задача не имеет допустимого решения. Если оно равно 0,то переходим ко 2ому этапу.

 

2)этап: оптимальное базисное решение, полученное на 1 этапе используется как начальное допустимое базисное решение исходной задачи.

 

 

Основан на графическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств линейного программирования определяет по координатной плоскости Х1Х2 некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей.

Область допустимых решений – ОДЗ – это множество точек пересечения данных полуплоскостей. ОДР – выпуклая фигура, т.е.. 2 (..) А иВ принадлежат этой фигуре, то и весь список АВ принадлежит этой фигуре. В случае несовместимости системы ограничений задачи ОДР являются пустым множеством. Все выше заданное относится и к = и к <>вам.

Наша целевая функция L(x) = C1X1+C2X2 при фиксированном значении, равном L, определяет на плоскости прямую линию L = C1X1+C2X2. Изменяя значения L мы получим семейство параллельных прямых, называемых линиями уровня. Вектор С =(с1,с2) перпендикулярен каждой из линий уровня. Благодаря этому направлению вектора С совпадает с направлением возрастания целевой функции. Напрвление убывания целевой функции п/п направлению С.

 

<== предыдущая лекция | следующая лекция ==>
Симплекс метод | Суть графического метода
Поделиться с друзьями:


Дата добавления: 2014-01-14; Просмотров: 302; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.