Математические модели с использованием целочисленного программирования. Для создания технологических структур из РТК необходимо приобрести n PTK для участка

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

(13.5)

где ; ; ; - целые числа.

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

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

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

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