Читайте также:
|
|
Для создания технологических структур из РТК необходимо приобрести n PTK для участка. Для этого выделен фонд в сумме N рублей. Стоимость РТК j -ro типа — Cj, а производительность — aj, j = 1,n. Требуется выбрать РТК, обеспечивающие максимальную суммарную производительность в пределах установленного денежного лимита N. Математическая модель:
(11) |
где x = (x1, x2,..., xj, …, xn); aj >= 0; Cj >= 0; N > 0 — целые числа.
Решение ведется методом ветвей и границ.
Если отбросим требования целочисленности, переменные aj, Cj изменяются непрерывно на отрезке [0, 1]. Решение такой непрерывной задачи будет верхней границей (так как определяется максимум) множества значений целевой функции на соответствующем подмножестве решения. Алгоритм решения непрерывной задачи состоит в следующем. Упорядочим коэффициенты a1, a2,..., aj... ап порядке убывания величин и соответственно этому порядку нумеруем переменные и параметры задачи.
Процедура разбиения (методом ветвей и границ) допустимого множества G, задаваемого ограничениями, такова: разбивают G на два подмножества G1и G2, первому подмножеству принадлежат все решения с х1=1, а второму — с x1 = 0. Далее каждое из подмножеств G1 и G2 опять разбивают на два: в первом x1 = 1, во втором х1 = 0 и т. д.
На каждом шаге очередного разбиения выбирают подмножество, которому соответствует максимальное значение оценки. Поиск решения заканчивают, если на некотором шаге получают допустимое решение значения целевой функции, на котором шаг будет наибольшим по сравнению с оценками для всех подмножеств — кандидатов на разбиение.
Дата добавления: 2015-08-13; просмотров: 64 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Механическая вращательная подсистема | | | Математические модели с использованием систем массового обслуживания |