![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Метод ветвей и границ
Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, который может быть использован как для задач линейного программирования, так и для задач, не сводимых к задачам линейного программирования. Рассмотрим идею метода ветвей и границ на примере общей задачи дискретного программирования f(X) -> max, (7.9) Х€D (7.10) где D — конечное множество.
Сначала найдем оценку £(D) (границу) функции f(X), X е D: f(X) ≤ £(D) для V X е D. Если для некоторого плана Х° задачи (7.9)-(7.10) справедливо равенствоf(X0) = £(D), то Х° = X* является решением задачи. Если указанное условие не выполняется, то возможно разбиение (ветвление) множества D на конечное число непересекающихся подмножеств D1i: ỤD1i. = D, ∩D1i = Ө, и вычисление оценки £(D1i) (границ), 1≤i≤m (рис 7.1)
Рис. 7.1
Если для некоторого плана X1i е Di1, 1 ≤ / ≤ m выполняется условие f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m то Xk1=X* является оптимальным планом (решением) задачи (7.9)-(7.10). Если такого плана нет, то выбирается подмножество Dkl с наибольшей оценкой £(D1i):
и разбивается на конечное число непересекающихся подмножеств D2kj: UD2kj=D1k, ∩D2kj=Ө. Для каждого подмножества находится оценка £(D2kj), 1≤j≤n (рис 7.2) (рис. 7.2).
(рис. 7.2). Если при этом найдется план X2j е D2kJ, 1 ≤j ≤n, такой, что f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n, то X2r= X* является решением задачи (7.9)-(7.10). Если такого плана нет, то процедуру ветвления осуществляют для множества D2kj с наибольшей оценкой £(D2kj), 1≤j≤n. Способ ветвления определяется спецификой конкретной задачи. Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования. Пример. Контейнер объемом 5 м3 помещен на контейнеровоз грузоподъемностью 12 т. Контейнер требуется заполнить грузом двух наименований. Масса единицы груза mj (в тоннах), объем единицы груза Vj (в м3), стоимости Cj (в условных денежных единицах) приведены в табл. 7.3. Таблица 7.3
Требуется загрузить контейнер таким образом, чтобы стоимость перевозимого груза была максимальной. Решение. Математическая модель задачи имеет вид Z(X) = 10x1+12x2→max, (7.11) 3x1+x2≤12, x1+2x2≤5 x1≥0 (7.12) x2≥0 x1, x2- целые числа (7.13)
где x1, x2 - число единиц соответственно первого и второго груза. Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (рис. 7.3). Рис. 7.3 Сначала решаем задачу (7.11)—(7.13) без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптимальном плане Х° = (19/5, 3/5): ТочкаXнеявляется оптимальным планом задачи (7.1 1)— (7.13). Поэтому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x1=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D11 и D22. Линии x1=3 (L3) и x4= (L3) являются линиями разбиения.
Рис. 7.4
Найдем оценки £(D11) и £(D12), для чего решим задачи линейного программирования Z(X)=10x1+12x2→max,
3x1+x2≤12 x1+2x2≤5 x1≤3 x1≥0, x2 – целые числа Z(X)=10x1+12x2→max, 3x1+ x2≤12 x1+2x2≤5 x1≥4 x1≥0, x2 – целые числа
Например, графическим методом: X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); £(D12)=40. Результат ветвления приведен на рис. 7.5
План X01 удовлетворяет условиям задачи (7.11)-(7.13), и для него выполняется условие: Z(X11)= £(D11)=42 > £(/)/) = 42 >£(D12) = 40. Следовательно, план X°1= (3, 1) является решением задачи (7.11)-(7.13), т.е. надо взять три единицы первого груза и одну единицу второго груза.
Алгоритм метода ветвей и границ
Date: 2015-07-17; view: 508; Нарушение авторских прав |