💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Метод Гомори

Ясно, что когда задача целочисленного программирования имеет более двух переменных, её необходимо решать аналитическими методами. Одним из таких методов является метод Гомори. Он заключается в следующем.

1. Задача решается как обычная (симплекс-методом или методом искусственного базиса). Если в результате получилось целочисленное решение, то задача решена. В противном случае идём к шагу 1.

2. Допустим, b_i - нецелочисленная компонента решения, полученного на 1-м шаге, , , …, - коэффициенты при свободных переменных , , …, соответствующего ограничения, из которых хотя бы один – не целый. Тогда к ограничениям, полученным в последней симплекс-таблице, добавляется дополнительное ограничение { } +{ } +…+{ } ³ { b_i }, которое после введения очередной дополнительной переменной примет вид

{ } +{ } +…+{ } - x_{n +1}={ b_i }. (1.1)

Здесь { a } - дробная часть числа a, n - количество переменных задачи в последней симплекс-таблице. Идём к пункту 1.

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

Если b_i - дробное, а все коэффициенты , , …, при свободных переменных (в последней симплекс-таблице)являются целыми, то задача целочисленного программирования не имеет решения. Ясно, что задача целочисленного программирования решения не будет иметь, если задача решений не имеет вообще.

Пример 2. Решить задачу целочисленного программирования методом Гомори:

2 x ₁+4 x ₂®max

Решение. Решая первоначальную задачу, как обычную, получим следующие симплекс-таблицы:

Базис	Сб	Св. чл.					q 1	q 2
x 1	x 2	x 3	x 4
x 3
x 4
D j		-2	-4
x 3						-
x 2
D j		-				-
x 1						-
x 2					-
D j

Таким образом, X ₀= - оптимальное решение, то есть нецелочисленных компонент в оптимальном решении, полученном на первом шаге, два. Найдём их дробные части и сравним:

, и

Поэтому составляем дополнительное ограничение по первой компоненте оптимального решения, которой в последней симплекс-таблице соответствует ограничение . Имеем , . Поэтому дополнительное ограничение (1.1) в нашем случае принимает вид

.

Полученную задачу снова решаем как обычную:

Базис	Сб	Св. чл.						q 3
x 1	x 2	x 3	x 4	x 5
x 1						-
x 2					-
-	-						-1
x 1						-1
x 2							-
x 3							-
D j

Получили оптимальное решение X ₀= данной задачи. Но так как исходная задача зависит только от двух переменных x ₁ и x ₂, которые принимают в этом решении целочисленные значения, то задача целочисленного программирования решена.

Ответ: X _цел.=(1, 3), F _{max цел.}=14.

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