Лабораторная работа 2. Задачи линейного программирование

Лабораторная работа 2. Задачи линейного программирование

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

при условии

Введем функцию

Преимущество применения метода динамического программирования для аддитивных функций (1) определяется тем, что вместо задачи минимизации функции многих переменных, что требует числа вычислений пропорционально кубу размерности задачи, решается n задач минимизации более простой функции одной переменной. Число вычислений в такой задаче растет линейно с ростом n. Недостаток состоит в том, что для решения задачи необходимо помнить все n функций Беллмана.

Табл. 2.1. Прибыль от вложений в каждый проект

20	5	4	6
40	8	10	9
60	12	15	14
80	17	18	18
100	20	21	17

		k=1		k =2		k =3
	20	0	6	0	6	20	6
	40	20	11	20,40	10	40	9
	60	0	16	40	16	60	14
	80	0,20	21	60	21	80	18
	100	20	26	40,60,80	24	80	18

Расчеты функции Беллмана для следующих шагов сведены во вспомогательную табл.2.3.

			k=2			k=1
20	0 20	20 0	0 4	6 0	6 4	0 5	6 0	6 5
40	0 20 40	40 20 0	0 4 10	9 6 0	9 10 10	0 5 8	10 6 0	10 11 12
60	0 20 40 60	60 40 20 0	0 4 10 15	14 9 6 0	14 13 16 15	0 5 8 12	16 10 6 0	16 15 14 12
80	0 20 40 60 80	80 60 40 20 0	0 4 10 15 18	18 14 9 6 0	18 18 19 21 18	0 5 8 12 17	21 16 10 6 0	21 21 18 18 17
100	0 20 40 60 80 100	100 80 60 40 20 0	0 4 10 15 18 21	18 18 14 9 6 0	18 22 24 24 24 21	0 5 8 12 17 20	24 21 16 10 6 0	24 26 24 22 23 20

Из данного примера видно, что метод динамического программирования позволяет находить глобальный минимум и решает задачу оптимизации для всех рассматриваемых начальных значений состояния объекта в рассматриваемом интервале, то есть в терминах задач управления решается задача синтеза. В следующем документе MATHCAD (док. Д.5) приведена программа, в которой реализован пример решения задачи распределения ресурса.

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

1. 
   Что такое задача линейного программирования?
   
2. 
   Как определяется множество допустимых решений в задаче ЛП?
   
3. 
   Где достигается минимум в задаче ЛП?
   
4. 
   Какая из сформулированных задач не является задачей ЛП?
   

Лабораторная работа 3. Задачи динамического программирования

Метод ветвей и границ

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

Определить оптимальные вложения ресурса в 100 ед. частями x_j по 10 ед. в п=с+3 проектов с функциями прибыли

Пусть M₀ – множество всех вариантов решения задачи перебора. Разобьем это множество на подмножества М_i так, чтобы эти подмножества охватывали все варианты, и чтобы каждый вариант входил только в одно подмножество, то есть чтобы выполнялись условия . Если продолжить такое разбиение для каждого из подмножеств, то в итоге построим дерево, корень которого содержит все варианты, а конечные ветви содержат единственный вариант. Если можно оценить снизу или сверху решения, содержащиеся в каждом подмножестве (определить функцию оценки или соответственно), то для сокращения перебора можно применить метод ветвей и границ.

Метод содержит три этапа – ветвление, оценку и отбрасывание вариантов.

Если удалось ввести функцию оценки, то после ветвления множества М₀ оцениваем решения во множествах М_i, и дальнейшее ветвление производится для наиболее перспективного множества с максимальной или минимальной оценкой в надежде, что именно там содержится оптимальное решение. Так продолжаем до тех пор, пока в множестве не окажется единственное решение (рис.4).

Рис. 4. Дерево вариантов комбинаторной задачи

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

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

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

3. По сравнению оценок. Пусть для двух множеств получены оценки и . Если выполняется неравенство , то во множестве М₁ нет лучших решений, чем во множестве М₂. Рассмотрим применение метода ветвей и границ для задачи коммивояжера на конкретном примере.

жүктеу/скачать 5,09 Mb.

Достарыңызбен бөлісу: