Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

	С1	С2	С3	С4	С5
L1	35	30	18	11	24
L2	32	33	21	10	21
L3	24	31	29	22	11
L4	9	16	28	35	26
L5	26	19	17	24	35

	C1	С2	С3	С4	С5
L1	26	14	1	1	13
L2	23	17	4	0	10
L3	15	15	12	12	0
L4	0	0	11	25	15
L5	17	3	0	14	24

	C1	C2	C3	C4	C5
L1	25	13	0	0	12	
L2	23	17	4	0	10	
L3	15	15	12	12	0
L4	0	0	11	25	15
L5	17	3	0	14	24	
				

.

1. .

2. Обведем , обведем квадратной рамкой элемент и вычеркнем ;

Обведем и вычеркнем ;

Обведем и вычеркнем .

1. Индекс квадратности .

2. Пометим , далее , далее . Прочеркнем и получим опорное множество.

3. Минимальный непрочеркнутый элемент .

7.

	С1	С2	С3	С4	С5
L1	22	10	0	0	9
L 2	20	14	4	0	7
L 3	15	15	15	15	0
L 4	0	0	14	28	15
L 5	14	0	0	14	21

Остальные элементы не изменяются .

1. Обведем ; обведем , вычеркнем .

Обведем , вычеркнем .

Обведем , вычеркнем .

Обведем .

И

=18+10+11+9+19=67.

ндекс квадратности  .

Аналогичный расчет позволяет определить максимальные потери, которые составляют 167 ед. Между наилучшим и наихудшим решением имеется разница 100 ед. и существует ещё 118 промежуточных решений.

Лабораторная работа № 6 (4 часа)

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

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

.

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

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

Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшем с точки зрения всего процесса в целом, а не "узких" интересов данного этапа.

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

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

Рассмотрим задачу о распределении дополнительных ресурсов между n функциональными подсистемами. Известны F(X, I) – эффективности i-той функциональной подсистемы, если ей выделено
x_i – ресурсов, на которые наложены ограничения:

(1)

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

Эта задача по своему характеру является комбинаторной. В самом деле, речь идет о том, чтобы перебрать все разбиения b_n ресурсов на n групп.

Можно было бы вычислить эффективность, соответствующую каждой комбинации:

(x₁, x₂,…x_n):

(1, 1,…) или (1010…)

(2, 1,…) или (11010…)

В этом случае пришлось бы просмотреть вариантов.

Но если возникнет необходимость знать оптимальное решение в случае, когда общий объем ресурсов не превышает b_n и составляет 0, 1, 2, … b_n, то число вариантов, которые надо было просмотреть, окажется в несколько раз больше:

.

Для решения такой задачи есть прямой смысл использовать метод динамического программирования.

Пусть для любого набора (x₁,.x₂, …x_n) существует аддитивный критерий:

Предположим, что ограничения, наложенные на аргументы x_i, такие, что существует верхняя (sup F_n) или нижняя (inf F_n) граница множества аддитивных критериев, т.е.

(2)

Определим набор (x₁,.x₂, …x_n) для соответствующих функций f₁(x₁), f₂(x₂) … F(X, I) такой, чтобы, удовлетворив ограничению (1), получить экстремальное значение (2).

Предположим, что из совокупности x_i выделена и зафиксирована величина x_n. Если в этой ситуации найти экстремальное значение:

то окажется, что значение аддитивного критерия F_n будет зависеть от выбранного значения x_n:

При любом значении x_n переменные x₁,.x₂, …x_n-1 должны удовлетворять неравенству:

Введя обозначения:

,

можно утверждать, что

(3)

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

Имея в виду, что – верхняя (нижняя) границы множества
F_n-1, нетрудно видеть, что задача отыскания полностью совпадает с исходной задачей,  различие лишь в числе переменных.

Характеристики

Список файлов книги