Лекции_1 / Лекция 10. Сетевые задачи. Задачи о распределении капитала

Лекция 10. Сетевые задачи. Задача о распределении капитала.

Общая схема применения метода ДП.

Предположим, что все требования, предъявляемые к задаче ме­тодом ДП, выполнены. Построение модели ДП и применение метода ДП для решения сводится к следующим моментам:

1. Выбирают способ деления процесса управления на шаги.

2. Определяют параметры состояния и переменные управле­ния на каждом шаге.

3. Записывают уравнения состояний.

4. Вводят целевые функции k -го шага и суммарную целевую функцию.

5. Вводят в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k-м шаге: .

6. Записывают основные для вычислительной схемы ДП урав­нения Беллмана..

7. Решают последовательно уравнения Беллмана (условная оп­тимизация) и получают две последовательности функций.

8. После выполнения условной оптимизации получают опти­мальное решение для конкретного начального состояния и оптимальное управление.

Некоторые задачи, решаемые методом ДП:

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

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

Р ешение:

1. Ведем обозначения:

– номер этапа.

– пункт, из которого осуществляются перевозки.

– пункт, в который доставляется груз (от 2 до 14).

– стоимость перевозки единицы груза из пункта в пункт .

– минимальные затраты на перевозку груза из пункта в конечный пункт, если до него осталось этапов.

2. Весь процесс доставки груза из 1 в 14 разбиваем на этапы:

На 1-ом этапе транспорт с грузом из пункта 1 перемещается в пункты 2, 3, 4.

На 2-ом этапе из 2, 3, 4 можно попасть в 5, 6, 7, 8.

На 3-ем этапе из 5, 6, 7, 8 можно попасть в 9, 10, 11.

На 4-ом этапе из 9, 10, 11 можно попасть в 12, 13.

На 5-ом этапе из 12, 13 попадаем в пункт 14.

3. Задача решается, начиная с пункта 14, т. е. с последнего этапа.

4. Запишем функциональное уравнение для последнего этапа.

N=1

В пункт 14 груз может быть доставлен из пункта 12 или из пункта 13, поэтому вычисляем:

Маршрут 12, 14.

N=2

В пункты 12 и 13 груз может быть доставлен из пункта 9, 10 или 11, поэтому вычисляем отдельно затраты на перевозку ед. груза для пункта 9, 10, 11.

Для пункта 9:

Маршрут из пункта 9: 9, 13, 14 – 13 единиц.

Для пункта 10:

Маршрут из пункта 10: 10, 12, 14 – 14 единиц.

Для пункта 11:

Маршрут из пункта 11: 11, 12, 14 – 10 единиц.

N=3

В пункты 9, 10 и 11 груз может быть доставлен из пункта 5, 6, 7 или 8, поэтому вычисляем отдельно затраты на перевозку ед. груза для пункта 5, 6, 7 и 8.

Для пункта 5:

Маршрут из пункта 5: 5, 11, 12, 14 – 14 единиц.

Для пункта 6:

Маршрут из пункта 6: 6, 11, 12, 14 – 16 единиц.

Для пункта 7:

Маршрут из пункта 7: 7, 11, 12, 14 – 15 единиц.

Для пункта 8:

Маршрут из пункта 8: 8, 11, 12, 14 – 19 единиц.

N=4

В пункты 5, 6, 7 и 8 груз может быть доставлен из пункта 2, 3 или 4, поэтому вычисляем отдельно затраты на перевозку ед. груза для пункта 2, 3 и 4.

Для пункта 2:

Маршрут из пункта 2: 2, 5, 11, 12, 14 – 22 единицы.

Для пункта 3:

Маршрут из пункта 3: 3, 5, 11, 12, 14 – 21 единица.

Для пункта 4:

Маршрут из пункта 4: 4, 5, 11, 12, 14 – 16 единиц.

N=5

В пункты 2, 3 и 4 груз может быть доставлен из пункта 1.

Оптимальный маршрут 1, 4, 5, 11, 12, 14 с наименьшими затратами 24 единицы.

2. Пусть имеется груз, состоящий из неделимых предметов различных типов, который нужно погрузить в самолет грузо­подъемностью Р. Стоимость и вес каждого предмета -го типа известны и составляют соответственно и единиц (). Требуется определить, сколько предметов каждого типа надо загрузить в самолет, чтобы суммарная стоимость груза была наибольшей, а вес не превышал грузоподъемности само­лета. Математически задача записывается следующим образом: найти такие целые неотрицательные значения , которые бы максимизировали функцию при ограничении , где – количество груза -го типа, позволяющее достичь .

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

3. Для увеличения объемов выпуска пользующейся повы­шенным спросом продукции, изготовляемой предприятиями, выделены капиталовложения в объеме S тыс. руб. Использование -м предприятием тыс. руб. из указанных средств обеспечивает прирост выпуска продукции, определяемый значением нелиней­ной функции . Найти распределение капиталовложений между предприятиями, обеспечивающее максимальное увеличение выпуска продук­ции.

Решение. Математическая постановка задачи состоит в определении наибольшего значения функции

, при условиях , .

Сформулированная задача является задачей нелинейного программирования. Решение задачи можно найти с помощью динамического программирования. Для этого исходную задачу нужно рассмотреть как многоэтапную или мно­гошаговую. Вместо того чтобы рассматривать допустимые вари­анты распределения капиталовложений между п предприятиями и оценивать их эффективность, будем исследовать эффективность вложения средств на одном предприятии, на двух предприятиях и т. д., наконец, на п предприятиях. Таким образом, полу­чим п этапов, на каждом из которых состояние системы (в каче­стве которой выступают предприятия) описывается объемом средств, подлежащих освоению предприятиями. Реше­ния об объемах капиталовложений, выделяемых -му предприя­тию, и являются управлениями. Задача состоит в выборе таких управлений, при которых функция (1) принимает наиболь­шее значение.