Метод дробления шага 3 страница

операций, что при больших п и b существенно меньше, чем в первом случае. Например, если п = 6 и b = 30, то непосредствен­ный перебор потребует выполнения 324 632 операций, а метод динамического программирования — только 2511.

28. Задача о распределении средств между предприятиями.

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

Рассмотрим схему решения задачи методом динамического программирования.

Задача: Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: S₀ = 5 у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства х, выделенные i-тому предприятию (i = 1,2,3,4), приносят в конце года прибыль . Функция заданы таблично (таблица 1).

Таблица 1.

х

Принято считать, что:

1). Прибыль не зависит от вложения средств в другие предприятия;

2). Прибыль от каждого предприятия выражается в одних условных единицах;

3). Суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.

Определить какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

Решение: Пусть - количество средств, выделенных i- тому предприятию. Суммарная прибыль . Переменные х удовлетворяют ограничениям . Математическая формулировка задачи: Найти переменные Х, удовлетворяющие системе ограничений и обращающие в максимум целевую функцию Z. Схема решения методом динамического программирования: Процесс решения распределения средств S₀ = 5 у.е. можно рассматривать как четырех шаговый: номер шага соответствует номеру предприятия. - управление на 1 шаге, - управление на 2 шаге, - управление на 3 шаге, - управление на 4 шаге. S_кон = 0, т.к. все средства должны быть вложены в производство.

в общем виде . - состояния системы.

выражают количество средств оставшихся после i-ого шага. Это те средства, которые остается распределить между оставшимися 4-i предприятиями.

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

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

4 шаг. В таблице 1 прибыли монотонно возрастают, поэтому все средства, оставшиеся к 4 шагу, следует вложить в 4-е предприятие. При этом для возможных значений s₃ = 0,1,2,3,4,5 получим: и .

3 шаг. Делаем все предположения относительно остатка средств s₂ к 3 шагу(т.е. после выбора х₁ и х₂). s₂ может принимать значения 0,1,2,3,4,5 (например, s₂ = 0, если все средства отданы 1-му и 2-му предприятиям, s₂ = 5, если 1-е и 2-е предприятия ничего не получили, и т.д.). В зависимости от этого выбираем , находим и сравниваем для разных х₃ при фиксированном s₂ значения суммы . Для каждого s₂ наибольшее из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств s₂ между 3-м и 4-м предприятиями. Оптимизация дана в таблице2 при i = 3. Для каждого значения s₂ и помещены в графах 5 и 6 соответственно.

2 шаг Условная оптимизация проведена в таблице2 при i = 2. для всех возможных значений s₁ значения и находятся в столбцах 8 и 9 соответственно; первые слагаемые столбце 7 – значения , взяты из таблицы 1, а вторые слагаемые взяты из столбца 5 таблицы2 при .

1 шаг Условная оптимизация проведена в таблице2 при i = 1 для S₀ = 5. Если х₁ = 0, то s₁ = 5, прибыль, полученная от четырех предприятий при условии, что s₁ = 5 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна ( взято из столбца 9 таблицы2 при s₁ = 5). Если х₁ = 1, то s₂=4. Суммарная прибыль при условии, что s₂ = 4 ед. средств между оставшимися предприятиями будут распределены оптимально, равна ( взято из таблицы 1, а - из 9 столбца таблицы2). Аналогично при

и

Сравнивая полученные числа, получим у.е.= при . Получим по таблице2 в столбце 9 находим . Далее находим , а по таблице2 в столбце 6 .Наконец, и , т.е.

Ответ: при

Таблица2

si-1	xk	sk	i=3	i=2	i=1
			0+1=1 3+0=3			0+4=4 6+0=6			0+6=6 8+0=8
			0+6=6 3+4=7 4+0=4			0+7=7 6+4=10 9+0=9			0+10=10 8+6=14 10+0=10
			0+8=8 3+6=9 4+4=8 7+0=7			0+9=9 6+7=13 9+4=13 11+0=11			0+13=13 8+10=18 10+6=16 11+0=11
			0+13=13 3+8=11 4+6=10 7+4=11 11+0=11			0+13=13 6+9=15 9+7=16 11+4=15 13+0=13			0+16=16 8+13=21 10+10=20 11+6=17 12+0=12
			0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18			0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15			0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18

Практическое задание: Найти оптимальное распределение средств между n предприятиями при условии, что прибыль , полученная от каждого предприятия, является функцией от вложенных в него средств х. Вложения кратны Δх, а функции заданы таблично. S₀=5, n=4, Δх = 1.

х
	0,2	1,0	2,1
	0,9	1,1	2,5	2,0
	1,0	1,3	2,9	2,5
	1,2	1,4	3,9	3,0
	2,0	1,8	4,9	4,0

Оформить таблицей, записать ответ

29. Задача о замене оборудования.

Оборудование эксплуатируется в течении 5 лет, после этого продается. В начале каждого года можно принять решение сохранить оборудование или заменить его новым. Стоимость нового оборудования р₀ = 4000руб. После t эксплуатации () оборудование можно продать за (ликвидная стоимость). Затраты на содержание в течение года зависят от возраста t оборудования и равны . Определить оптимальную стратегию эксплуатации оборудования, чтобы суммарные затраты с учетом начальной покупки и заключительной продажи были минимальны.

Решение Делим управление на шаги по годам n = 5. Параметр состояния – возраст машины - - машина новая в начале первого года эксплуатации. Управление на каждом шаге зависит от двух переменных Х^с и Х^з.

Управления зависят от управления:

Показатель эффективности к-того шага:

Пусть - условные оптимальные затраты на эксплуатацию машины, начиная с к-го шага до конца, при условии, что к началу к-го шага машина имеет возраст t лет. Запишем для функции уравнения Беллмана:

Величина 4000*2^-(t+1) – стоимость машины возраста t лет (по условию машина после 5 лет продается).

Из определения функций следует

Геометрическое решение задачи. На оси абсцисс откладывается номер шага к, на оси ординат – возраст t машины. Точка (к-1,t) на плоскости соответствует началу к-го года эксплуатации машины возраста t лет.

Состояние эксплуатации машины соответствует точке , конец - точкам .любая траектория переводящая точку s(k-1,t) из в , состоит из отрезков – шагов, соответствующих годам эксплуатации. Надо выбрать такую траекторию, при которой затраты на эксплуатацию машины окажутся минимальными.

рис.1

Над каждым отрезком, соединяющим точки (к-1,t) и (k,t+1), запишем соответствующие управлению Х^с затраты, найденные из 600(t+1), а над отрезком соединяющим точки (к-1,t) и (к,t) запишем затраты, соответствующие управлению Х^з, т.е. 4600-4000*2^-t. Таким образом мы разметим все отрезки, соединяющие точки на графике, соответствующие переходам из любого состояния s_k-1 в состояние s_k.

Проведем условную оптимизацию на размеченном графе состояний (рис.2).

4 шаг. Начальные состояния – точки (4;t), конечные (5;t). В состояниях (5;t) машина продается, условный оптимальный доход от продажи равен 4000*2^-t, но поскольку целевая функция связана с затратами, то в кружках точек (5,t) поставим величину дохода со знаком минус.

Состояние (4,1). Из него можно попасть в состояние (5,2), затратив на эксплуатацию машины 1200 и выручив затем от продажи 1000, т.е. суммарные затраты равны 200, и в состояние (5,1) с затратами 2600-2000=600. Значит, если к последнему шагу система находилась в точке (4,1), то следует идти в точку (5,2) (укажем это направление двойной стрелкой), а неизбежные минимальные затраты, соответствующие этому переходу, равны 200 (поместим эту величину в кружке (4,1).

Состояние (4,2).Из него можно попасть в точку (5,3) с затратами 1800-500 = 1300 и в точку (5,1) с затратами 3600-2000=1600. Выбираем первое управление, отмечаем его двойной стрелкой, а проставляем в кружке точки (4,2).

Рассуждая таким образом для каждой точки предпоследнего шага, найдем для любого исхода 4 шага оптимальное управление на 5 шаге, отметим его на рис.2 двойной стрелкой. Далее планируем 4 шаг, анализируя каждое состояние, в котором может оказаться система в конце 3-го шага с учетом оптимального продолжения конца процесса. Например, если начало 4 шага соответствует состоянию (3,1), то при управлении Х^с система переходит в точку (4,2), затраты на этом шаге 1200, а суммарные затраты за два последних шага равны 1200+1300=2500. При управлении Х^з затраты за два шага равны 2600+200=2800. Выбираем минимальные затраты 2500,ставим их в кружок точки (3,1), а соответствующие управления на этом шаге выделены двойной стрелкой, ведущей из состояния (3,1), в состояние (4,2). Так поступаем для каждого состояния (3,t).

Продолжая условную оптимизацию 3, 2,и1 шагов получим на рис.2 следующую ситуацию: из каждой точки (состояния) выходит стрелка, указывающая, куда следует перемещаться на данном шаге, если система оказалась в этой точке, а в кружках записаны минимальные затраты на переход из этой точки в конечное состояние.

После проведения условной оптимизации получим в точке (0,0) минимальные затраты на эксплуатацию машины в течение 5 лет с последующей продажей: Z_min = 11900. далее строится оптимальную траекторию, перемещаясь из точки s₀(0,0) по двойным стрелкам в . Получаем набор точек: , который соответствует оптимальному управлению . Оптимальный режим эксплуатации состоит в том, чтобы заменить машину новой в начале 3-го года.

Таким образом, размеченный график (сеть) позволяет наглядно интерпретировать расчетную схему и решить задачу методом динамического программирования.

Практическая часть: Для задач 1), 2) составить математическую модель, записать уравнения Беллмана и решить графически следующие задачи на определение оптимальных сроков замены оборудования. Даны: первоначальная стоимость оборудования р₀, его ликвидная стоимость φ(t), стоимость содержания r(t) в течение года оборудования возраста t лет, n – срок эксплуатации, в конце которого оборудование продается. Критерий оптимальности – суммарные затраты на эксплуатацию оборудования в течение n лет с учетом первоначальной покупки и последующей продажи.

1). р₀ = 8000, φ(t) = р₀*2^-t, r(t) = 0,1* р₀*(t+1), n = 5

2). Дополнительное задание: n = 5. Стоимость нового оборудования зависит от года покупки р_к = 5000 + 500(к-1), (к = 1, 2,…,5), φ(t) = р_к*2^-t, r_k(t) = 0,1*р_к(t+1).

30. Алгоритмы в графах.

Граф определяется как пара (двойка) множеств — множество вершин W и множество ребер L: G = (W, L).

Вершины графа изображаются точками, ребра — линиями связи любой формы (граф — объект не геометрический, а топологический).

Количество вершин графа, т.е. мощность (количество элементов множества W, — это его порядок n: |W| = n.

Любой граф может быть однозначно задан с помощью матрицы смежности MS.

Свойства матрицы смежности:

— матрица квадратная порядка

— матрица бинарная (двоичная);

— на главной диагонали MS только нули (в графе не должно быть

петель);

— матрица симметрична относительно главной диагонали.

Мультиграфы, когда смежные вершины могут быть связаны несколькими ребрами (имеет смысл для отмеченных графов), и псевдографы, где есть петли и, возможно, расщепление ребер.

Вторая разновидность матричного представления графов — матрица инциденций MI: строки в Ml отображают ребра и вершины, с ними связанные (им инцидентные).

Свойства матрицы инциденций:

— в общем случае матрица прямоугольная;

— матрица бинарная (0, 1);

— в каждой строке матрицы Ml ровно 2 единицы, они указывают инцидентные вершины; в свою очередь, строки указывают ребра, инцидентные соответствующим вершинам.

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

Графы эквивалентны, если они, конечно, имеют одинаковый порядок и одинаковый характер связей — соответствующие вершины в обоих графах или связаны каким-то ребром или же не связаны вовсе.

Степень вершины графа — количество прилежащих ребер.

Если все вершины имеют одинаковую степень, граф — регулярный такой-то степени.

Теорема о сумме степеней всех вершин графа. В символической форме: ,т.е., сумма эта равна удвоенному количеству ребер.

Теорема о количестве вершин нечетной степени: количество таких вершин имеет значение четного числа.

Полный граф имеет максимально возможное количество ребер, обозначается К_n.

В двудольных графах допускаются связи только между вершинами разных долей.

Если в двудольном графе количество ребер максимально возможное, он — полный двудольный граф.

Маршрут в графе — это последовательность проходимых ребер и вершин.

Частный случай маршрута — путь, где повторение ребер не допускается. Маршруты и пути могут быть разомкнутые и замкнутые (циклы).

Длин а маршрут а (пути) — это количество проходимых ребер.

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

Дерево — это связный ациклический граф.

В корневом дереве одна из вершин специально выделяется и именуется корень. Остовное дерево — это остовный подграф, являющийся деревом.

Теорема о количестве маршрутов заданной длины: Количество маршрутов длины к из вершины w_i. в вершину w_j. определяется значением элемента i j к-й степени матрицы смежности, т.е. .

Теорема о количестве маршрутов доказывается по индукции (полная математическая индукция). На основе степеней матрицы смежности строится матриц а связности MSW. Это квадратная, порядка n, бинарная матрица, симметричная относительно главной диагонали.

Теорема о связности графа: Для связности графа, т.е. для взаимной достижимости любых его двух вершин, необходимо и достаточно, чтобы матрица связности MSW была полностью единичной.

Если граф несвязный, он распадается на компоненты связности.В случае, если компоненты связности — деревья, получается лес. Если к тому же это остовный подграф, то— остовный лес. Отдельные свойства связных графов — их эйлеровость и гамильтоновость («-ость» считаем допустимым элементом словообразования).

Граф эйлеров, если в нем существует замкнутый маршрут, проходящий через каждое ребро ровно 1 раз (т.е. фактически — это замкнутый путь). Говорят еще: эйлерова цепь, эйлеров цикл. Если все ребра проходятся по 1 разу, но путь-маршрут не замкнут, граф — полуэйлеров. Все прочие графы — неэйлеровы.

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

Планарные графы

Планарный граф может быть изображен на плоскости без пересечения ребер. Такое изображение — карта графа. Карта связная, если планарный граф — связный.

Область карты графа — часть плоскости, ограниченная контуром из ребер. Степень области — количество ребер, составляющих границу области.

Теорема о сумме степеней всех областей планарного графа (может быть, даже и несвязного): , т.е. сумма эта равна удвоенному количеству ребер.

Теорем а Эйлер а для связных планарных графов: |W|—|L|+|R| = 2 т.е. количество вершин минус количество ребер плюс количество областей есть величина постоянная (константа Эйлера Е), имеющая значение 2

Теорема Эйлера справедлива и в отношении правильных выпуклых многогранников: |W|—|L|+|G| =E =2 здесь G — множество граней.

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

Теорема Куратовского утверждает: граф планарный тогда и только тогда, когда в процессе выполнения операций элементарного стягивания он не содержит подграфов вида К₅ и К_3,3.

ми, разделяющими смежные области. Двойственный граф на рис.

Ориентированные графы (орграфы)

Можно отметить два существенных отличия орграфов от обычных графов:

— ориентация ребер, которые становятся дугами (дуга — «ребро со стрелкой»);

— наличие петель.

Как и обычные графы, орграфы однозначно описываются их матрицами смежности.

Связность орграфов бывает троякая:

— слабая;

— односторонняя:

— сильная.

Сильная связность означает взаимную достижимость любой пары вершин «в обе стороны», т. е. с учетом ориентации дуг и в прямом, и в обратном направлении.

Одностороння я связность соответствует взаимной достижимости, по крайней мере, в одну сторону для любой пары вершин. При этом нет сильной связности.

Слабая связность определяется как связность только на уровне неориентированного графа, получающегося из орграфа путем исключения петель и стрелок (дуги превращаются в ребра).

Задачи на графах

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

Все такие задачи можно условно разделить на две группы:

— маршруты, деревья и т.п.;

— задачи с мерой.

В первой группе:

— отыскание пути (маршрута) в лабиринте;

— проверка графа на эйлеровость;

— построение остовного дерева для связного графа;

— ориентация графа;

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