Характеристика метода Гомори
Основной анализ построения алгоритма метода Гомори. Использование симплексной концепции при решении заданий. Особенность способа построения правильного отсечения без учета условия целочисленности. Характеристика решения задач линейного программирования.
| Рубрика | Математика |
| Вид | доклад |
| Язык | русский |
| Дата добавления | 08.06.2015 |
| Размер файла | 13,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Методы отсечений. Метод Гомори
Сущность состоит в следующем. Сначала задача решается без условия целочисленности. Если полученный план целочислен, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами (правильное ограничение):
оно должно быть минимальным;
· должно отсекать найденный оптимальный нецелочисленный план;
· не должно отсекать ни одного целочисленного плана.
Далее задачу решают с учётом нового ограничения. После этого в случае необходимости добавляют ещё одно ограничение и т.д.
Метод Гомори основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.
Алгоритм метода Гомори:
1. Решить задачу симплекс-методом без учёта условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если задача ЛП неразрешима, то и задача ЦЛП неразрешима.
2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и для неё сформулировать правильные отсечения.
3. Полученное неравенство (6.1) введением дополнительной неотрицательной целой переменной преобразовать в равносильные уравнения:
{i}-{im+1}xm+1-…-{in}xn+хn+1=0,
и включить его в систему ограничений задачи ЛП.
Расширенную задачу решить симплекс-методом. Если найденный оптимальный план целый, то задача ЦЛП решена, в противном случае вернуться к шагу 2.
Если задача разрешима в целых числах, то после некоторого числа шагов, оптимальное целый план будет найден.
Задача ЛП - это задача выбора таких неотрицательных значений переменных, подчиненных системе ограничений в форме линейных неравенств, при которых достигается максимум или минимум данной линейного функции: гомори симплексный отсечение целочисленность
F(x)=cxmax max Axb, bi, i=1m,
x0 xj0, j=1n
Пусть x=(x1,…,xj,…,xn) - вектор инструментальных переменных, n - n-мерное Евклидово пространство. Допустимое множество решений задачи ЛП Х={xnAxb, x0} представляет собой замкнутое выпуклое многогранное множество, расположенное в неотрицательном ортанте n-мерного Евклидова пространства. Граничные гиперплоскости называют гранями, а точки, в которых пересекаются n или более граней, называют вершинами. Поверхность уровня целевой функции {xncx = const} представляет собой гиперплоскость в n. Если придать этой const различные значения, то получим семейство параллельных гиперплоскостей. Для n=2 примером такого семейства являются параллельные грани. Направление наискорейшего роста задается градиентом , т.е. вектором-строкой из n, ортогональным к поверхности уровня.
С геометрической точки зрения задача ЛП состоит в отыскании точки (или множества точек) в n, принадлежащих допустимому выпуклому многогранному множеству, в которой достигается поверхность наибольшего уровня. Из геометрических представлений ясно, что если решение существует, оно не может быть внутренней точкой, а должно принадлежать границе допустимого множества. В трехмерном случае решением может быть точка вершины (пересечение трех или более граней), отрезок прямой (пересечение двух граней), часть некоторой плоскости (грань). Хотя решение может быть неединственным, максимальное значение целевой функции единственно. Действительно, поскольку допустимое множество выпукло, а целевая функция линейна, то по теореме о достаточных условиях существования максимума локальный максимум является глобальным.
Кроме того, если n>m, то решение непременно достигается в такой вершине допустимого множества, в которой по меньшей мере n-m переменных равны 0.
Поскольку целевая функция непрерывна, а допустимое множество замкнуто, по теореме Вейерштрасса решение существует в том случае, если допустимое множество непусто и ограничено. Следовательно, возможны 2 случая, когда задача ЛП не может иметь решения:
1) ограничения являются несовместными и допустимое множество пусто;
2) неограниченность допустимого множества.
Итак, задача ЛП либо имеет единственное решение (в вершине), либо бесконечное множество решений, либо не имеет решений (если допустимое множество пусто или не ограничено).
Размещено на Allbest.ru
...Подобные документы
Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Теоретические основы метода отсечения, его назначение и функции в решении задач целочисленного линейного программирования. Сущность и практическая реализация первого и второго алгоритма Гомори. Применение алгоритма Дальтона, Ллевелина и Данцига.
курсовая работа [208,1 K], добавлен 12.10.2009Целочисленные задачи математического программирования. Постановка транспортной задачи по критерию стоимости в матричной форме. Задача о назначении (проблема выбора, задача о женихах и невестах). Алгоритм метода Гомори. Формирование правильного отсечения.
курсовая работа [868,8 K], добавлен 05.12.2012Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Поиск корней нелинейных САУ с помощью метода продолжения решения по параметру. Математическое описание метода. Программное обеспечение для построения графиков сходимости метода. Требования к программному обеспечению и описание логической структуры.
курсовая работа [365,5 K], добавлен 27.04.2011Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Проектирование методов математического моделирования и оптимизации проектных решений. Использование кусочной интерполяции при решении задач строительства автомобильных дорог. Методы линейного программирования. Решение специальных транспортных задач.
методичка [690,6 K], добавлен 26.01.2015Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Синтез вариационного исчисления и метода функций Ляпунова в основе принципа динамического программирования. Метод знакопостоянных функций Ляпунова в решении задач о стабилизации и синтезе управления для нелинейной и автономной управляемых систем.
курсовая работа [1,2 M], добавлен 17.06.2011Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлен 11.12.2011Метод Зейделя как модификация метода простой итерации. Особенности решения систем линейных алгебраических уравнений. Анализ способов построения графика функций. Основное назначение формул Симпсона. Характеристика модифицированного метода Эйлера.
контрольная работа [191,3 K], добавлен 30.01.2014Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
контрольная работа [79,4 K], добавлен 04.06.2010Обзор и характеристика различных методов построения сечений многогранников, определение их сильных и слабых сторон. Метод вспомогательных сечений как универсальный способ построения сечений многогранников. Примеры решения задач по теме исследования.
презентация [364,3 K], добавлен 19.01.2014Сущность метода системосовокупностей как одного из распространенных и универсальных методов решения неравенств любого типа. Обобщение метода интервалов на тригонометрической окружности. Эффективность и наглядность графического метода решения задач.
методичка [303,7 K], добавлен 14.03.2011Составление уравнения Эйлера, нахождение его общего решения. Нахождение с использованием уравнения Эйлера-Лагранжа оптимального управления, минимизирующего функционал для системы. Использование метода динамического программирования для решения уравнений.
контрольная работа [170,3 K], добавлен 01.04.2010Рассмотрение особенностей метода построения полного проверяющего теста для недетерминированных автоматов относительно неразделимости для модели "черного ящика" и разработка предложений по его модификации. Исследование условий усечения дерева преемников.
курсовая работа [1,3 M], добавлен 20.08.2010Предназначена библиотеки "simplex" для оптимизации линейных систем с использованием симплексного алгоритма. Построение экономико-математической модели формирования плана производства. Основные виды транспортных задач, пример и способы ее решения.
курсовая работа [477,9 K], добавлен 12.01.2011
