![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод Гомори ⇐ ПредыдущаяСтр 2 из 2
Ясно, что когда задача целочисленного программирования имеет более двух переменных, её необходимо решать аналитическими методами. Одним из таких методов является метод Гомори. Он заключается в следующем. 1. Задача решается как обычная (симплекс-методом или методом искусственного базиса). Если в результате получилось целочисленное решение, то задача решена. В противном случае идём к шагу 1. 2. Допустим, bi - нецелочисленная компонента решения, полученного на 1-м шаге, { Здесь { a } - дробная часть числа a, n - количество переменных задачи в последней симплекс-таблице. Идём к пункту 1. Если нецелочисленных компонент в оптимальном решении, полученном на первом шаге, несколько, то берём ту, у которой дробная часть наибольшая. Если bi - дробное, а все коэффициенты Пример 2. Решить задачу целочисленного программирования методом Гомори: 2 x 1+4 x 2®max Решение. Решая первоначальную задачу, как обычную, получим следующие симплекс-таблицы:
Таким образом, X 0=
Поэтому составляем дополнительное ограничение по первой компоненте оптимального решения, которой в последней симплекс-таблице соответствует ограничение
Полученную задачу снова решаем как обычную:
Получили оптимальное решение X 0= Ответ: X цел.=(1, 3), F max цел.=14. Метод Гомори - не единственный аналитический метод решения целочисленной задачи. Разработан целый ряд аналитических методов, отличных от данного. В учебной литературе можно найти, например, метод ветвей и границ.
|