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

• Алгоритм симплекс-метода
• Алгоритм метода ветвей и границ
• Алгоритм метода Гомори
• Алгоритм двойственного симплекс-метода

Другие предметы Колледж Алгоритм метода Гомори алгоритм комбинаторных методов дискретное программирование симплекс-метод метод ветвей и границ метод Гомори двойственный симплекс-метод Новый

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

Алгоритм, который вы описали, называется алгоритм метода Гомори. Этот метод применяется для решения задач целочисленного линейного программирования и основан на использовании гиперплоскости, определяемой целевой функцией.

Теперь давайте рассмотрим, как работает алгоритм метода Гомори:

1. Начало с решения задачи линейного программирования: Сначала мы решаем задачу линейного программирования, игнорируя целочисленные ограничения. Это позволяет найти оптимальное решение, которое может быть нецелым.
2. Анализ решения: Если полученное решение является целым, то мы можем его использовать как оптимальное решение задачи. Если нет, то мы продолжаем.
3. Введение ограничений: Метод Гомори вводит дополнительные ограничения, чтобы "вдавить" гиперплоскость целевой функции внутрь многогранника. Эти ограничения основаны на дробной части текущего решения. Они помогают исключить текущую нецелочисленную точку из области допустимых решений.
4. Переход к новой задаче: После введения новых ограничений мы решаем обновленную задачу линейного программирования. Этот процесс может повторяться несколько раз.
5. Поиск целочисленного решения: Мы продолжаем итерации, пока не найдем целочисленное решение или не поймем, что задача не имеет решения.

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