Математические модели с использованием целочисленного программирования

Для создания технологических структур из РТК необходимо приобрести n PTK для участка. Для этого выделен фонд в сумме N рублей. Стоимость РТК j-ro типа — Cj, а производительность — a_j, j = 1,n. Требуется выбрать РТК, обеспечивающие максимальную суммарную производительность в пределах установленного денежного лимита N. Математическая модель:

(13.8)

где x = (x₁, x₂, ..., x_j, …, x_n); a_j 0; Cj 0; N > 0 — целые числа.

Решение ведется методом ветвей и границ.

Если отбросим требования целочисленности, переменные a_j, C_j изменяются непрерывно на отрезке [0, 1]. Решение такой непрерывной задачи будет верхней границей (так как определяется максимум) множества значений целевой функции на соответствующем подмножестве решения. Алгоритм решения непрерывной задачи состоит в следующем. Упорядочим коэффициенты a₁, a₂, ..., a_j ... а_п порядке убывания величин λ_j = a_j /C_j и соответственно этому порядку нумеруем переменные и параметры задачи.

Процедура разбиения (методом ветвей и границ) допустимого множества G, задаваемого ограничениями, такова: разбивают G на два подмножества G₁ и G₂, первому подмножеству принадлежат все решения с х₁=1, а второму — с x₁ = 0. Далее каждое из подмножеств G₁ и G₂ опять разбивают на два: в первом x₁ = 1, во втором х₁ = 0 и т. д.

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