Решение задач целочисленного программирования: методы и примеры

Пример 1. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

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

Дополнительные неизвестные x3 и x4 примем за базисные. Выразим базисные неизвестные и функцию цели через неосновные переменные:

Из коэффициентов составим симплексную таблицу:

Составляем следующие таблицы до получения оптимального плана:

Из таблицы 3 находим оптимальный план . Поскольку этот оптимальный план не удовлетворяет условию целочисленности, нам нужно составить дополнительное условие. Дробной частью координаты является число , а дробной частью координаты - число .

Первое уравнение на основании таблицы запишется так:

.

Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие:

или, введя добавочную переменную ,

.

Получаем новую строку в симплексной таблице, полученной из таблицы 3 и добавления коэффициентов из только что полученного уравнения:

Совершаем шаг симплекс-метода и получаем таблицу:

Получили оптимальный план . Этот план, как и предыдущий, не удовлетворяет условию целочисленности. Поэтому вновь требуется составить дополнительное условие. В данном случае можно использовать первое или третье уравнение. Получится следующее дополнительное условие:

.

Составляем следующую таблицу:

Оптимальный план получаем из следующей, завершающей таблицы:

Так как найденный оптимальный план удовлетворяет условию целочисленности, задача целочисленного программирования решена. Координаты x5 и x6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так:

,

а максимум функции цели равен 9.

Пример 2. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Допустим, что заданы или определены следующие границы оптимальных значений неизвестных:

.

Так как задача задана в нормальной форме, она имеет целочисленный план и нижнюю границу максимального значения целевой функции .

В списке решаемых задач - 1-я задача:

Итерация 1.

Шаг 1. С помощью симплекс-метода получено решение 1-й задачи:

.

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Так как оптимальный план имеет дробную координату 1,2, то и . Применяя границы значений неизвестных 1-й задачи, получаем новые задачи. Во 2-й задаче нижней границей для является , а в 3-й задаче верхней границей для является .

Итак, следует решить 2-ю задачу:

и 3-ю задачу:

Нижняя граница максимального значения целевой функции .

Итерация 2.

Шаг 1. Из списка решаемых задач выбираем 2-ю задачу.

Шаг 2. Констатируем, что 2-я задача не имеет решения, так как её система ограничений несовместна. Тогда и следует следующая итерация.

Итерация 3.

Шаг 1. В списке имеется только одна - 3-я задача.

Шаг 2. Применяя симплекс-метод, получаем решение 3-й задачи:

.

Так как это решение не является целочисленным, следует шаг 4.

Шаг 4. Выбираем дробную координату . Тогда и . Применяя границы значений неизвестных из 3-й задачи, получаем две новых задачи.

4-я задача:

5-я задача:

Нижняя граница максимального значения функции цели

.

Итерация 4.

Шаг 1. Из списка решаемых задач, в котором имеются 4-я и 5-я задачи, выбираем 4-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 4-й задачи:

.

Так как полученное решение не является целочисленным, следует шаг 4.

Шаг 4. Выбираем дробную координату и получаем и . Применяя границы значений переменной , получаем две новые задачи линейного программирования.

6-я задача:

7-я задача:

Итак, в списке решаемых задач имеются 5-я, 6-я и 7-я задачи, а нижняя граница максимального значения функции цели .

Итерация 5.

Шаг 1. Из списка выбираем 5-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 5-й задачи:

.

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Выбираем дробную координату и получаем и . Применяя границы значений неизвестной 5-й задачи, получаем две новые задачи.

8-я задача:

9-я задача:

В списке решаемых задач имеются 6-я, 7-я, 8-я и 9-я задачи, а нижняя граница максимального значения функции цели .

Итерация 6.

Шаг 1. Из списка решаемых задач выбираем 6-ю задачу.

Шаг 2. Констатируем, что 6-я задача не имеет решения. Поэтому нижняя граница максимального значения функции цели и следует следующая итерация.

Итерация 7.

Шаг 1. Из списка решаемых задач выбираем 7-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 7-й задачи:

.

Шаг 3. Так как полученное решение является целочисленным, то нижняя граница максимального значения функции цели и далее следует итерация 8.

Итерация 8.

Шаг 1. Из списка решаемых задач выбираем 8-ю задачу.

Шаг 2. Применяя симплекс-метод, получаем решение 8-й задачи:

.

Нижняя граница максимального значения функции цели , далее - следующая итерация.

Итерация 9.

Шаг 1. В списке решаемых задач имеется лишь 9-я задача.

Шаг 2. Применяем симплекс-метод и получаем решение 9-й задачи:

.

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

Итерация 10.

Шаг 1. В списке решаемых задач нет ни одной задачи. Таким образом, решение данной задачи целочисленного программирования следующее:

.