Файл: Теория систем лаб.pdf

Контрольные вопросы

1.Перечислите основные этапы метода анализа иерархий.

2.Опишите процесс попарного сравнения объекта по какому-либо признаку.

3.Опишите шкалу выбора приоритетов.

4.Перечислите основные свойства матрицы попарных сравнений.

5.Как происходит формирование вектора локальных приоритетов?

6.Опишите процесс свертки сводной матрицы локальных приори-

тетов.

7.На основании чего происходит выбор оптимального варианта в методе анализа иерархий?

8.Используются ли в методе анализа иерархий основные принципы синтеза сложных систем?

9.Можно ли отнести метод анализа иерархий к методам экспертных оценок?

10.Опишите процесс получения вектора глобальных приоритетов.

73

Лабораторная работа № 6 РЕШЕНИЕ ЗАДАЧ

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Краткие теоретические сведения

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

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

В основе вычислительных алгоритмов динамического программирования лежит следующий принцип оптимальности, сформулированный Р. Беллманом: каково бы ни было состояние системы S в результате (i-1) шагов, управление на i-м шаге должно выбираться так, чтобы оно по совокупности с управлениями на всех последующих шагах с (i+1)-го до N-го включительно доставляло экстремум целевой функции.

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

Контрольный пример

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

74

Таблица 6.1

Определить, как распорядиться имеющимся капиталом, чтобы прибыль была максимальна?

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

f1(x), f2(x), f3(х) – функции прибыли в зависимости от капитальных вложений, то есть столбцы 2–4 таблицы, F12(А) – оптимальное распределение, когда A единиц капитала вкладывается в первую и вторую торговые точки вместе, F123{А) – оптимальное распределение капитала величины A, вкладываемого во все точки вместе.

Например, для определения F12(2) надо найти f1(0)+f2(2)=0,41, f1(1)+f2(1)=0,53 f1(2)+f2(0)=0,45 и выбрать из них максимальную вели-

чину, то есть F12(2)=0,53.

Вообще F12(A)=max [f1(x)–f2(A-x)]. Вычисляем F12(0), F12(1), F12(2),

…, F12(9).

Распределение капитала между двумя торговыми точками (табл. 6.2).

Для А=4 возможны комбинации (4, 0), (3, 1), (2, 2), (1, 3), (0, 4), ко-

торые дают соответственно общую прибыль: 0,78; 0,90; 0,86; 0,83; 0,65.

75

Более подробно получение этих величин показано ниже:

Теперь, когда фактически есть зависимость F12 от величины вкладываемого в первые две точки капитала, можно искать F123(A)= =max [F12(x)+f3(A-x)] (табл. 6.3).

Более подробно получение этих величин при вложении капитала в три точки показано в табл. 6.4 для девяти единиц капитала.

76

Важно то, что полученные результаты были бы теми же, если бы использовались не F12 и F123, а, скажем, F31 и F312. Обратите внимание на то, что оптимальное решение для А=9 не единственное.

Индивидуальное задание

Вариант 1

Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства равны 5 условным единицам. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства, выделенные предприятию, приносят в конце года прибыль. Зависимость прибыли от объема вложения средств заданы в табл. 6.5.

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

Вариант 2

Производственное объединение выделяет четырем входящим в него предприятиям кредит в сумме 100 млн ден. ед. для расширения производства и увеличения выпуска продукции. По каждому предприятию

известен возможный прирост zi (ui ) (i 1,4) выпуска продукции (в денежном выражении) в зависимости от выделенной ему суммы ui . Для

упрощения вычислений выделяемые суммы кратны 20 млн ден. ед. и приведены в табл. 6.6.

77

При этом предполагаем, что прирост выпуска продукции на i-м предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения.

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

Вариант 3

Разработать оптимальную политику использования и замены оборудования не старше шести лет, если известны: стоимость продукции r(t), производимой с использованием этого оборудования, ежегодные эксплуатационные расходы v(t), остаточная стоимость s и стоимость p нового оборудования. Продолжительность планового периода принять равной 6 годам. Задачу решить при следующих числовых данных: t=4, s=2, p=10, значения r(t) и v(t) приведены в табл. 6.7.

Таблица 6.7

Известны также остаточная стоимость s, равная 4 и не зависящая от возраста оборудования, и цена p нового оборудования, равная 13 и не меняющаяся в плановом периоде.

Вариант 4

Планируется деятельность трех промышленных предприятий на очередной год. Начальные средства равны 9 условным единицам. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства, выделенные предприятию, приносят в конце года прибыль. Зависимость прибыли от объема вложения средств задана в табл. 6.8.

Таблица 6.8

78