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

ВВЕДЕНИЕ

 

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

 

Задача ЛП в стандартной форме имеет следующий вид:

 

W = с_1*х_{1 +} с_2*х_{2 + … +} с_n*х_n → min (max)

 

где х₁, х₂ и х_п - переменные величины;

с₁, с₂ и с_п - коэффициенты.

 

Условия функционирования объекта (ограничения) в задачах линейного программирования должны относиться к одному из следующих типов:

d_1*х_{1 +} d_2*х_{2 + … +} d_n*х_{n =} d₀

е_1*х_{1 +} е_2*х_{2 + … +} е_n*х_{n ≥} е_o

f_1* х_{1 +} f_2* х_{2 + … +} f_n* х_{n ≤} f₀

 

где d_п, е_п, - коэффициенты;

d_o, е_o, f_o - постоянные величины.

 

В предлагаемых методических указаниях решение задач начинается с составления математической модели процесса, описанного в задаче, и анализа модели с целью выбора наиболее эффективного способа оптимизации. Для решения оптимальных задач использован пакет программ статического программирования "Statgraphic".

 

Процесс динамического программирования проводится от конца к началу. Первым планируется последний этап. При этом предполагаются различные варианты завершения предыдущего этапа, и для всех этих вариантов находят такое решение, при котором эффект на последнем этапе будет наибольшим. Такое решение будет условно оптимальным. Аналогично находятся услoвно оптимальное решение на последующих этапах.

 

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

 

 

ОПТИМИЗАЦИЯ ДОРОЖНОЙ СЕТИ

 

Исходные данные

 

Необходимо найти кратчайшее расстояние между двумя пунктами А и K, для перевозки грузов с минимальными затратами. Между этими пунктами находится 10 пунктов: 3 внутри, 5 внизу, 2 наверху.

 

 

Решение с использованием ПК

В соответствующие графы вводят начало, конец и длину участков.

 

В столбец «Вход»(H2) вводят формулу: =СУММЕСЛИ($C$2:$C$20;G2;$A$2:$A$20) и копируют на весь столбец.

В столбец «Выход»(I2): =СУММЕСЛИ($B$2:$B$20;G2;$A$2:$A$20)

В клетку B21 вводят формулу: =СУММПРОИЗВ(A2:A20;D2:D20)

 

 

 

 

Далее воспользуемся функцией «Поиск Решения»

 

Целевая функция: B21 -> min.

Изменяемые ячейки: A2-A20

Ограничения: Столбец J K; $J$2:$J$13 $K$2:$K$13.

 

Выводы

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

Исходные данные

 

Предприятие выпускает три вида продукции: П₁, П₂, П₃, при изготовлении которой используется оборудование трех типов О₁, О₂, О₃. Нормы времени работы каждого типа оборудования при изготовлении продукции П1, П2, Пз приведены в таблице 1.

 

Таблица 1

 

 

Вид продукции	Тип оборудования
О1	О2	О3
П1	0,22	0,17	0,25
П2	0,21	0,15	0,20
П3	0,31	0,12	0,15

 

В соответствие с производственным заданием продукции П₁ должно быть произведено не менее n₁=151 ед., П₂ - не менее n₂=201 ед., П₃ - не менее n₃=401 ед. За изготовление единицы продукции П₁, П₂, П₃ предприятие получает прибыль соответственно k₁=9, k₂=8, k₃=10 тыс. руб. Ресурс рабочего времени оборудования О₁ , О₂ , О₃ соответственно t₁=251, t₂=301, t₃=321.

 

Требуется определить объем выпуска продукции каждого вида, при котором план по каждому виду продукции выполнен, ресурсы времени по всем типам оборудования не превышены, а прибыль от реализации продукции, максимальна.

ОПТИМИЗАЦИЯ ПЕРЕВОЗОК

 

Исходные данные

Имеется 3 пункта, производящих некоторую продукцию. Затраты на производство единицы продукции в i -ом пункте равна ai, а максимально возможный объем её выпуска составляет bi единиц в год, i = 1,2,3. Изготовляемая продукция должна быть распределена между потребителями. Доставка единицы продукции от i -го пункта производства к j -му потребителю обходится в cij руб., j = 1,2..n. Потребитель в продукции для i -го потребителя составляет dj единиц в год. Требуется составить схему перевозок так, чтобы годовые затраты на производство и перевозку были минимальны.

 

с₁₁ = 4, с₁₂ =10, с₁₃ =8,

с₂₁ = 5, с₂₂ =4, с₂₃ =4,

с₃₁ = 5, с₃₂ =10, с₃₃ =7,

а₁ = 11, а₂ = 11, а₃ = 3,

 

Исходные данные

В состав объединения входят 4 предприятия. Сумма инвестиций для этих предприятий составляет 50 тыс. руб. Необходимо распределить их между предприятиями так, чтобы прибыль была максимальна. Кратность инвестиций равна 10.

 

Таблица 9

 

И	П1	П2	П3	П4

Цель задачи: Чтобы суммарная прибыль была максимальной.

 

 

Оптимизация инвестиций

 

Введем следующие обозначения:

Хi – остаточные средства на начало i – го этапа;

Ui – кол-во средств, которые решено выделить i – предприятию;

Пi – прибыль, получаемая этим предприятием.

 

Таблица 10

 

Хi	i = 4	i = 3	i = 2
U4	П4	U3	П’у3	U2	П’у2

Первые три колонки мы уже можем заполнить. Для заполнения других столбцов необходимо сделать промежуточные расчеты. Результаты приведены в таблице 11.

 

Таблица 11

	i = 3	i = 2	i = 1
	Ui	Ui+1	П3	П4	Пу3	П2	Пу3	Пу2	П1	Пу2	Пу1
								4
				4
				5			7
				8
							10
							13
				12
								16			16
				16

 

Для каждого уровня инвестиций находим максимальные значения прибыли и их записываем в таблицу 10.

Находим инвестиции:

U1 = 50 тыс. руб., прибыль составляет 16 единиц;

50 – 50 = 0 - остаток

 

При распределении инвестиций наиболее оптимальная прибыль, которую получат все 4 предприятия составит 16 единицы.

 

 

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Моделирование и оптимизация лесопромышленных процессов. Методические указания по выполнению расчетно-графических работ для студентов. Петрозаводск 1999 г.

2. Принятие оптимальных решений. Теория и применение в лесном комплексе.

В.Н. Андреев, Ю. Ю. Герасимов.

 

ВВЕДЕНИЕ

 

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

 

Задача ЛП в стандартной форме имеет следующий вид:

 

W = с_1*х_{1 +} с_2*х_{2 + … +} с_n*х_n → min (max)

 

где х₁, х₂ и х_п - переменные величины;

с₁, с₂ и с_п - коэффициенты.

 

Условия функционирования объекта (ограничения) в задачах линейного программирования должны относиться к одному из следующих типов:

d_1*х_{1 +} d_2*х_{2 + … +} d_n*х_{n =} d₀

е_1*х_{1 +} е_2*х_{2 + … +} е_n*х_{n ≥} е_o

f_1* х_{1 +} f_2* х_{2 + … +} f_n* х_{n ≤} f₀

 

где d_п, е_п, - коэффициенты;

d_o, е_o, f_o - постоянные величины.

 

В предлагаемых методических указаниях решение задач начинается с составления математической модели процесса, описанного в задаче, и анализа модели с целью выбора наиболее эффективного способа оптимизации. Для решения оптимальных задач использован пакет программ статического программирования "Statgraphic".

 

Процесс динамического программирования проводится от конца к началу. Первым планируется последний этап. При этом предполагаются различные варианты завершения предыдущего этапа, и для всех этих вариантов находят такое решение, при котором эффект на последнем этапе будет наибольшим. Такое решение будет условно оптимальным. Аналогично находятся услoвно оптимальное решение на последующих этапах.

 

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

 

 

ОПТИМИЗАЦИЯ ДОРОЖНОЙ СЕТИ

 

Исходные данные

 

Необходимо найти кратчайшее расстояние между двумя пунктами А и K, для перевозки грузов с минимальными затратами. Между этими пунктами находится 10 пунктов: 3 внутри, 5 внизу, 2 наверху.

 

 

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

 

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

 

Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении оптимума целевой функции при ограничении общего вида на варьируемые параметры.

 

Характерным для динамического программирования является то, что переменные рассматриваются не вместе, а последовательно – одна за другой. При этом вычислительная схема строится таким образом, чтобы вместо одной задачи с n переменными решалась серия задач с небольшим числом, а чаще всего с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два этапа:

· от последнего шага к первому;

· от первого шага к последнему или же, наоборот, в зависимости от исходных данных.

 

На первом этапе ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом: нельзя получить оптимальное значение целевой функции i -шагового процесса, если для любого ui, выбранного на шаге I, значение целевой функции для оставшихся i-1 шагов не является оптимальным.

 

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

 

Процесс поиска начинается с последовательно пройденных этапов.

1 этап - Попадание в точку K одним способом - J, L, I.

2 этап – 3-мя способами – G, E, C.

3 этап – 4-мя способами – B, H.

4 этап – 10-тью способами – F, D.

5 этап – 15-тью способами – А.

Далее ищем оптимальные варианты.

 

Для данной дорожной сети найдено кратчайшее расстояние между двумя пунктами А и K (A – C – E – G – L – K) = 91.8 ед. Необходимо отметить, что оптимизация дорожной сети в «ручную» при большом объёме данных является долгим и трудоёмким процессом.

 

 

Решение с использованием ПК

В соответствующие графы вводят начало, конец и длину участков.

 

В столбец «Вход»(H2) вводят формулу: =СУММЕСЛИ($C$2:$C$20;G2;$A$2:$A$20) и копируют на весь столбец.

В столбец «Выход»(I2): =СУММЕСЛИ($B$2:$B$20;G2;$A$2:$A$20)

В клетку B21 вводят формулу: =СУММПРОИЗВ(A2:A20;D2:D20)

 

 

 

 

Далее воспользуемся функцией «Поиск Решения»

 

Целевая функция: B21 -> min.

Изменяемые ячейки: A2-A20

Ограничения: Столбец J K; $J$2:$J$13 $K$2:$K$13.

 

Выводы

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