Лекция 5. Целочисленное программирование

метод Гомори
4. Пример решения задачи методом Гомори.

между n исполнителями.
Пусть Cij – производительность j-исполнителя на i-работе
Введем переменную

Xij, которая равна 1, если на i-работу назначен j исполнитель, иначе 0

и организации перевозок, чтобы суммарные затраты были бы минимальными)

матрицей расстояний С=(Cij ). Коммивояжер выезжает из некоторого города, объезжает

все города и возвращается назад. Найти для него кратчайший замкнутый маршрут, проходящий каждый пункт по одному разу.

различных мест. В её распоряжении имеется n дней, и она

предполагает провести по одному дню в каждом месте, проведя по aj опросов , j=1,2,..n. Вероятность успешного опроса в каждом месте задаётся матрицей P. Элемент матрицы Pij характеризует вероятность успешного опроса в течении i –го дня в j-м месте, i=1,2,..n.
Определить время проведения опросов, при котором общее число опросов максимально.
Сведём данную задачу к задаче о назначениях.

j-м месте в течение i –го дня.

требования целочисленности.
2. Если есть нецелые числа в оптимальном плане, то

выбираем среди них решение с наибольшей дробной частью и рассматриваем соответствую-щую ему строку симплекс-таблицы.
Допустим, это строка с номером l.

к пункту 2.
Пример.
f(x1, x2)=21x1+10x2 →max
7x1+4x2≤13
x1≥ 0, x2≥ 0

x3=2

x4=1 x5=1 fmax=31