Целочисленное линейное программирование

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

В математической модели задачи ЦЛП, как целевая функция, так и функции в системе ограничений могут быть линейными и нелинейными. Рассмотрим пример для линейного случая.

Графическое решение задач ЦЛП

Пример.          (Акулич, с. 176)

В цехе надо установить оборудование, для размещения которого выделено 19/3 м² площади. На приобретение оборудования можно израсходовать 10 тыс. руб., при этом можно купить оборудование двух видов: I и II. Оборудование I вида стоит 1 тыс. руб., а II вида – 3 тыс. руб. Приобретение оборудования I вида позволит увеличить выпуск продукции в смену на 2 единицы, а II вида – на 4 единицы. Для установки одного оборудования I вида требуется 2 м², II вида – 1 м².

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

Решение:

Составим математическую модель задачи.

Примем, что предприятие приобретает x₁ оборудования I вида и x₂ – II вида. Тогда x₁ и x₂ должны удовлетворять неравенствам:

I    II

2x₁ + x₂ ≤ 19/3 м²,               (1)

x₁ + 3x₂ ≤ 10 тыс. руб.        (2)

x₁ ≥ 0; x₂ ≥ 0.

Увеличение выпуска продукции составит (целевая функция):

z = 2x₁ + 4x₂ → max.

При этом

x₁, x₂ ³ 0,

x₁, x₂ – целые.

Это задача ЦЛП.

Решим задачу графически.

Координаты всех точек многоугольника ОАВС удовлетворяют условию неотрицательности переменных. Максимум z в точке В (1,8; 2,73).

Нельзя округлять, например, x₁=2, x₂=3, т.к. не выполняются ограничения.

Условию целочисленности удовлетворяют координаты лишь 12 точек многоугольника OKENMF, среди которых надо найти точку максимума функции, которая определяет оптимильный план задачи.

Перемещаем линию целевой функции z, пока она не пройдет через последнюю общую с многоугольником точку Е. Полученное решение: x₁=2, x₂=3, а z =14 ед. (Проверить соседние вершины К и М).

Метод ветвей и границ

Аналитическое решение возможно методами: Гомори и ветвей и границ.

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

Последовательность решения задач ЦЛП:

Шаг 1. Решается задача ЛП-1 и находится значение целевой функции z₁. Если переменные x_i принимают дробные значения, то оптимальное решение целочисленной задачи не совпадают с решением ЛП-1 и величина z₁ является верхней границей оптимального значения целочисленной задачи. (в примере было z =14,53).

Шаг 2.Производится ветвление по одной из переменных, имеющей дробное значение в задаче ЛП-1 по следующему правилу:

1) выбирается переменная, имеющая наибольшее дробное значение;

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

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

x_i £ [x_i]; x_i ³ [x_i] + 1,

где [] – целая часть дроби.

Исходная задача разветвляется на две подзадачи: ЛП-2 и ЛП-3, каждая из которых решается.

Шаг 3

1)Если одно из полученных решений оказывается допустимым для целочисленной задачи, то значение целевой функции z является начальной нижней границей оптимального значения.

2)Если решения дробные, то для дальнейшего ветвления выбирают вершину, соответствующую наибольшему значению целевой функции.

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

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

Пример.

max  z = 3x₁ + 2x₂,

x₁ + x₂ ≤ 3,5,

x₁ ≤ 2; x₂ ≤ 2,

x₁,  x₂ ≥ 0, целые.

Шаг 1. Решается задача ЛП-1.

Верхняя граница целевой функции z₁ = 9

Шаг 2. Т.к. x₂ =1,5 дробное, то просматриваются его целочисленные значения при x₂ £1 и x₂ ³2.

Шаг 3. 1) Решая ЛП-2, находим при x₂ = 1 начальное целочисленное решение. Значение z₂ = 8 является нижней границей.

2) Решая ЛП-3, при x₂ = 2, значение x₁ = 1,5 – дробное, что недопустимо.

Т.к. z₃ = 8,5 > z₂ = 8, то проверяется наличие (зондируем) в допустимой области задачи ЛП-3 целочисленного решения, дающего значение z ³ 8.

Рассмотрим задачи ЛП4 и ЛП5 при целых значениях x₁:

а) при x₁ = 1 решение ЛП-4 целочисленное, но z₄ = 7 < z₂ = 8;

б) при x₁ = 2 нет допустимых решений.

Т.о. точка x₁ = 2, x₂ = 1 является оптимальным целочисленным решением задачи и значение целевой функции равно z = 8.

Шаг 1. ЛП-1.

x₁ = 2,  x₂ =1,5, z₁ =9 (верхняя граница)

                               Шаг 2

ЛП2                                                  ЛП3

       x₂ £ 1                                               x₂ ³ 2

x₁ = 2, x₂ = 1, z₂ = 8                               x₁ = 1,5, x₂ = 2, z₃ = 8,5

Решение начальное (нижняя граница)                z₃³ z₂

Оптимум

ЛП-4                               ЛП-5

x₁ £ 1                                    x₁ ³ 2

                          нет допустимых решений

x₁ = 1, x₂ = 2, z₄ = 7

Решение (не оптимум)