Тема 8. ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ Лекции 21-22. Учебные вопросы: 1. Основные понятия и определения в целочисленном программировании. - презентация

1 Тема 8. ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ Лекции Учебные вопросы: 1. Основные понятия и определения в целочисленном программировании. 2. Метод ветвей и границ. 3. Классификация алгоритмов ветвей и границ. 4. Структуры дерева вариантов и системы нумерации вершин. 5. Оптимистические оценки и стратегии ветвления вершин. 6. Эффективность алгоритмов. 7. Задачи целочисленного программирования. 8. Алгоритмизация одномерных и многомерных задач.

2 1.Основные понятия и определения в целочисленном программировании Формализация экономических задач в виде моделей целочисленного программирования адекватно отражает ситуацию, когда между затратами ресурсов и приростом эффекта существует дискретная, линейная или нелинейная пропорциональная зависимость. Учёт характера этой зависимости является необходимым условием выработки обоснованного решения. К таким задачам относится достаточно широкий класс задач, формализуемый в виде моделей поиска экстремума линейной или нелинейной функции целочисленных переменных.

3

4 Метод ветвей и границ относится к наиболее общим методам решения дискретных задач математического программирования. Первая версия этого метода был опубликована в 1960 году американскими учеными Ленгом и Дойг в журнале «Эконометрика». В 1963 году Литтл, Мурти, Суини и Кэрел использовали общую схему метода для решения задачи о коммивояжере и назвали его методом ветвей и границ. Специфика метода ветвей и границ состоит в представлении множества вариантов решения задачи в виде дерева альтернатив, и последующей организации направленного перебора вариантов решений на этом дереве для выявления оптимального. 2. Метод ветвей и границ

5 Общая схема метода ветвей и границ Задание структурной схемы дерева вариантов на основе определения числа возможных значений для каждого из компонентов вектора альтернатив; Задание системы нумерации вершин на дереве вариантов с целью установления соответствия между комбинациями альтернатив и результатами решения задач; Задание стратегии ветвления перспективных вершин при поиске оптимального решения на дереве вариантов; Задание способа вычисления оптимистической оценки перспективности вершин (нижняя граница при решении задачи на минимум или верхняя граница при решении задачи на максимум) путем сведения основной задачи к более простым частным подзадачам.

6 С учетом общих принципов метода ветвей и границ признаками классификации алгоритмов являются: структурная схема дерева вариантов, система нумерации вершин, стратегия ветвления дерева вариантов, способ вычисления оптимистической оценки перспективности вершин. По степени априорной информации о структуре дерева вариантов следует различать их типы: стохастические, недетерминированные, детерминированные. 3. Классификация алгоритмов ветвей и границ

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

8 Деревья каскадного и пирамидального типа

9 Деревья лестничного и бивалентного типа

10 Системы нумерации вершин Сквозная Поярусная Векторная

11 Способы определения оптимистической оценки могут базироваться на различных методиках и использовать: линейное программирование, метод множителей Лагранжа, динамическое программирование, принцип декомпозиции, эвристические приемы и др. 5. Оптимистические оценки и стратегии ветвления вершин

12 х1х1 h1(x1)h1(x1)x2x2 h 2 (x 1, x 2 )x3x3 f (x 1, x 2, х 3 ) Оптимистические оценки гипотетического примера

13 Стратегии ветвления дерева вариантов Фланговая Фронтальная Локально-избирательная Глобально-поисковая

14 А л г о р и т м ФЛАНГ. Исходные данные: N; m n, n = 1, …, N; D. Результаты: F*, X* = (x 1 *, x 2 *, …, x n * ). Рабочие массивы: X = (x 1, x 2, …, x N ). Константы: М – число, заведомо больше, чем минимальное значение целевой функции. Используемые подпрограммы: ФУНКЦИЯ (N, X, F) – процедура вычисления значения целевой функции F = f (X) по заданным параметрам N и Х = (x 1, x 2, …, x N ); ОЦЕНКА (X n, H) – процедура расчета значения нижней границы H = h n (X n ) для вершины Х n = (x 1, x 2, …, x n ) на n-ом ярусе дерева вариантов. Начало. Положить n = 0 и F * = M. Ф1. Положить n = n + 1 и x n = 0. Ф2. Если x n = m n, то перейти к метке Ф4. Положить x n = x n + 1. Если (x 1, x 2, …, x n ) D, то возвратиться к метке Ф2. Если n < N, то перейти к метке Ф3. Выполнить процедуру ФУНКЦИЯ (N, X, F). Если F < F *, то положить F * = F и X * = X. Возвратиться к метке Ф2. Ф3. Выполнить процедуру ОЦЕНКА (X n, H). Если H < F *, то возвратиться к метке Ф1. Возвратиться к метке Ф2. Ф4. Если n > 1, то положить n = n – 1 и возвратиться к метке Ф2. Конец.

15 А л г о р и т м ВЫБОР Исходные данные: N; m n,n=1, …, N; D. Результаты: F*, X* = (x n, n=1, …, N). Рабочие массивы: X = (x n, n=1, …, N); R (r i, i=1, …, P); G = (g ni, i=1, …, m n, n=1, …, N). Константы: М. Используемые подпрограммы: ФУНКЦИЯ (N, X, F); ОЦЕНКА (X n, H). Начало. Положить n = 0 и F* = M. В1. Положить i = 1, n = n + 1 ; H* = F*. В2. Положить xn = i. Если (x 1, …, x n ) D, то положить g ni = F* и перейти к метке В3. Если n < N, то выполнить процедуру ОЦЕНКА (X n, H) и положить g ni = Н. Если n = N, то выполнить процедуру ФУНКЦИЯ (N, X, F) и положить g ni = F. Если g ni < H*, то положить H* = g ni и j = i. В3. Если i < m n, то положить i = i + 1 и возвратиться к метке В2. Если Н > F*, то перейти к метке В5. Положить g ni = F*, x n = j. Если n < N, то возвратиться к метке В1. Если H* < F*, то положить F* = H* и X* = X. Перейти к метке В5. В4. Если g ni < H*, то положить H* = g ni и j = i. Если i < m n, то положить i = i + 1 и возвратиться к метке В4. Если H* < F*, то положить xn = j; g ni = F* и возвратиться к метке В1. В5. Если n > 1, то положить n = n – 1, i = 1; H* = F* и возвратиться к метке В4. Конец.

16 Название алгоритма Стратегия ветвления Система нумерации вершин Используемые процедуры Объём рабочей памяти ФЛАНГФланговаяВекторная ФУНКЦИЯ, ОЦЕНКА 2N2N ФРОНТ Фронтальная Поярусная ФУНКЦИЯ, ОЦЕНКА, ПРИБЛИЖЕНИЕ, РАЗВЕРТКА ВЫБОРЛокально- избирательная Векторная ФУНКЦИЯ, ОЦЕНКА ПОИСКГлобально- поисковая Сквозная ФУНКЦИЯ, ОЦЕНКА, ПРИБЛИЖЕНИЕ, СВЕРТКА, РАЗВЕРТКА Сравнительная оценка алгоритмов

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

18 Временная сложность может быть описана некоторыми аналитико-вероятностными зависимостями на основе анализа возможных циклов, переходов и разветвлений в программе с учетом количества производимых элементарных операций (типа сложения, умножения, сравнения, пересылки) и скорости их выполнения в процессоре. Однако такие зависимости не всегда просто получить, они могут иметь достаточно громоздкий вид и содержать неопределенные вероятностные параметры. Поэтому во многих случаях целесообразнее давать экспериментальную оценку временной сложности. С этой целью проводятся серии вычислительных экспериментов с различными характеристиками исходных данных. Исходные данные могут подготавливаться вручную или моделироваться с помощью датчиков случайных чисел.

19 7. Задачи целочисленного программирования К формальному представлению экономических ситуаций могут быть сведены многочисленные задачи из практики различных видов обеспечения предприятий, разработки и производства промышленных товаров, ремонта и хранения техники, оборудования производственных помещений. Далее приведём содержательное описание и математическую формализацию возможных ситуаций применительно к экономико-хозяйственной деятельности предприятия.

20 Задача экипировки Экипировка – это комплект обмундирования, снаряжения и носимых предметов работника некоторой профессии или отдельно взятого индивида, состоящий из одежды, служебных документов, специального инструмента, приборов, средств мобильной связи, продуктов питания, напитков, воды и личных вещей. Подбор предметов экипировки осуществляется с учетом профессиональных требований для наилучшего выполнения тем или иным работником своих функциональных обязанностей в любой производственной или чрезвычайной ситуации. При этом учитывают «ценность» использования или, так называемый коэффициент важности того или иного предмета при выполнении профессиональных заданий и способность работника (геолога, монтажника, охотника, пожарного, проходчика, путейца, разведчика, туриста, электромонтёра) успешно передвигаться в различных видах обстановки с определенным весом экипировки.

21 Портфель заказов предприятия – перечень работ, включаемых в план производства на некоторый период (год, квартал, месяц). Наполнение портфеля заказов осуществляется с учетом экономико-технических требований для наилучшего выполнения предприятием плана производства. При этом учитывают «ценность» выполнения, ожидаемый доход или, так называемый, коэффициент важности той или иной работы при выполнении плана производства и способность предприятия выполнить план в условиях некоторого ресурсного ограничения. В простейшем случае задачу наполнения портфеля заказов можно сформулировать следующим образом. Имеется перечень из n работ, для каждой из которых определена её важность с j и вес b j, j = 1,2,…,n. Из заданного перечня требуется включить в портфель заказов такие работы, чтобы суммарная важность их С была максимальной, а суммарный расход некоторого ресурса не превосходил заданной величины В.

22 Рыболовецкая артель имеет возможность осуществлять промысел в n районах отлова. Известно математическое ожидание количества рыбопродукта с j, отлавливаемого в каждом районе, и расход горючего b j, потребного рыболовецкому судну для следования в район и осуществления там лова рыбы, j = 1,2,…,n. На весь промысел артели задан допустимый расход горючего В. Требуется составить такой план промысла, чтобы математическое ожидание суммарного количества выловленной рыбы С было максимальным, а суммарный расход горючего не превосходил заданной величины В. Планирование промысла

23 На предприятие технического обслуживания и ремонта поступило n заявок от владельцев транспортных средств на производство некоторых работ. В результате оценки состояния машин установлены цены с j, и определено потребное количество человеко-часов b j для ремонта каждой поврежденной единицы. С учётом ресурсных возможностей предприятия заявки могут включаться или не включаться в план работ. Требуется по поданным заявкам имеющимися на предприятии ресурсами В выполнить ремонтные работы таким образом, чтобы суммарная выручка С от их производства была максимальной. Анализ производственных заявок

24 8. Алгоритмизация одномерных и многомерных задач В простейшем случае на содержательном уровне постановку задачу экипировки можно сформулировать следующим образом. Имеется перечень из n предметов, для каждого из которых определена их важность с j и вес b j, j = 1, 2,…, n. Из заданного перечня требуется включить в экипировку такие предметы, чтобы их суммарная важность С была максимальной, а суммарный вес не превосходил заданной величины В.

25 Математическая формализация одномерной задачи заключается в определении целевой функции при ограничении где: x j = 1, если j-й предмет включается в экипировку; х j = 0, если – не включается.

26 Математическая формализация многомерной задачи заключается в определении целевой функции при ограничении где: m – число ограничений (многомерность); x j = 1, если j-й предмет включается в оснастку; х j = 0, если – не включается.

27 Наиболее распространенным приёмом вычисления верхней границы H n (X n ) для вершин n-го яруса х n, является следующий: Верхняя граница

28 при условиях: г де:

29 Если п ри определении верхней границы, условие не выполняется, то верхняя граница H n (X n ) для вершины х n полагается равной нулю. Определение третьего слагаемого H n (X n ) рассматривают как решение вспомогательной оценочной задачи и обычно производят на основе предварительного упорядочения строк матрицы и элементов с j по невозрастанию отношения c j /a ij, Оценочная задача

30 ЗАКЛЮЧЕНИЕ 1. Одним из наиболее эффективных методов направленного перебора в практически приемлемых алгоритмах решения прикладных экономических задач является метод ветвей и границ. 2. Общими принципами метода ветвей и границ являются: структурная схема дерева вариантов, система нумерации вершин, стратегия ветвления вершин дерева вариантов, способ вычисления верхней или нижней границы решения задачи.