Экономика - рефераты, шпаргалки, семинары, лекции, конспекты
- Подробности
-
Категория: Экономика
Алгоритм решения задач целочисленного программирования следующий:
1. Решают задачу линейного программирования без ограничений на целочисленность, например, симплекс-методом.
2. Если оптимальное решение задачи линейного программирования нецелочисленное, то проводят «большую итерацию». Строят линейное ограничение, которому удовлетворяет любое целочисленное решение задачи и не удовлетворяет полученное оптимальное нецелочисленное значение. Геометрически это означает-провести сечение (гиперплоскость), который отсекал бы нецелочисленное вершину, не затрагивая остальные целочисленных точек. Такое сечение называют правильным. Правильный сечение должно удовлетворять следующим условиям:
1) условие отсечения: оптимальное решение задает линейного программирования не удовлетворяет условию отсечения;
2) условие правильности: все целочисленные решения задачи удовлетворяют условию отсечения.
Поскольку для исходной задачи дополнительное ограничение (отсечения) давать недопустимо базисное решение, необходимо провести «малые итерации» для получения оптимального решения. Если полученное оптимальное решение нецелочисленное, то проводят следующее отсечения. В противном случае поиск завершен.
Р. Гомори предложил идею формирования дополнительных ограничений, приводит к решению задач целочисленного программирования за конечное число шагов.
