Линейное программирование
Графоаналитическое решение задач линейного программирования. Метод ветвей и границ. Определение ребра ветвления. Оптимизация дискретных динамических объектов методом Р. Беллмана. Синтез непрерывного оптимального управления с помощью уравнения Эйлера.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 17.10.2017 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
Оглавление
Исходные данные
Задание №1. Графоаналитическое решение основной задачи линейного программирования (ОЗЛП)
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана
Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
Исходные данные
К заданию №1.
|
№ |
C1 |
C2 |
B1 |
B2 |
B3 |
B4 |
A11 |
A12 |
A21 |
A22 |
A31 |
A32 |
A41 |
A42 |
|
|
213 |
2,5 |
1,5 |
12 |
2 |
2 |
0,5 |
-1 |
8 |
4 |
-7 |
-2 |
2 |
2 |
-4 |
К заданию №2.
|
1 |
2 |
3 |
4 |
5 |
6 |
|||
|
С = |
1 |
? |
1 |
5 |
4 |
1 |
3 |
|
|
2 |
5 |
? |
1 |
6 |
7 |
2 |
||
|
3 |
6 |
2 |
? |
3 |
4 |
1 |
||
|
4 |
1 |
5 |
4 |
? |
6 |
7 |
||
|
5 |
3 |
6 |
1 |
1 |
? |
4 |
||
|
6 |
7 |
3 |
6 |
5 |
1 |
? |
К заданию №3.
|
№ |
A |
B |
б |
в |
г |
|
|
113 |
1,1 |
0,6 |
1,8 |
1,2 |
4 |
К заданию №4.
|
№ |
A |
B |
б2 |
|
|
113 |
0,6 |
0,3 |
12 |
К заданию №5.
|
№ |
k |
г |
|
|
113 |
26 |
13 |
Задание №1. Графоаналитическое решение основной задачи линейного программирования (ОЗЛП)
1. Математическая постановка ОЗЛП:
ц=2,5x1+1,5x2>max, (0)
-x1+8x2?12, (1)
4x1-7x2?2, (2)
-2x1+2x2?2, (3)
2x1-4x2?0,5, (4)
x1?0, (5)
x2?0, (6)
DF: -x1+8x2=12, (1')
EF: 4x1-7x2=2, (2')
BD: -2x1+2x2=2, (3')
CE: 2x1-4x2=0,5, (4')
AC: x1=0, (5')
AB: x2=0, (6')
2. Записываем уравнение граничных линий допустимого многоугольника (1') - (6').
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение -x1+8x2 = 12 по двум точкам. Для нахождения первой точки приравниваем x1 = 0.
Находим x2 = 1.5. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -12. Соединяем точку (0;1.5) с (-12;0) прямой линией.
Построим уравнение 4x1-7x2 = 2 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -0.29. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 0.5. Соединяем точку (0;-0.29) с (0.5;0) прямой линией.
Построим уравнение -2x1+2x2 = 2 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -1. Соединяем точку (0;1) с (-1;0) прямой линией.
Построим уравнение 2x1-4x2 = 0.5 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -0.13. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 0.25. Соединяем точку (0;-0.13) с (0.25;0) прямой линией.
3. Строим линию, пересекающую область ц.
, (7)
, (8)
4. Находим градиент целевой функции:
, (9)
, (10)
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи ц=2,5x1+1,5x2>max. Построим прямую, отвечающую значению функции ц=0: F=2,5x1+1,5x2=0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (2.5; 1.5). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Из рисунка видно, что оптимальная точка F* равная , Прямая F(x) = const пересекает область в точке F. Так как точка F получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
-x1+8x2?12, (1)
4x1-7x2?2, (2)
Решив систему уравнений, получим: x1 = 4, x2 = 2, откуда найдем максимальное значение целевой функции:
, , (11)
, (12)
Ответ: , ;
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам:
hн= min(i) hнi
Произведем приведение матрицы C по столбцам:
gi = min(х) gнi
В итоге получаем полностью приведенную (редуцированную) матрицу:
Величины hн и gi называются константами приведения.
Нижняя граница цикла: d0=1+1+1+1+1+1+0+0+0+0+0+0 = 6
().
Шаг №1. Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества () и (), т.е. , где
В приведенной матрице исследуем все нулевые переходы.
Наибольшая сумма констант приведения равна
х41= б4 + в1 =3+2=5,
следовательно, множество разбивается на два подмножества и .
Оценка длины цикла:
.
Исключение ребра (4,1) проводим путем замены элемента х41 = 0 на ?, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (), в результате получим редуцированную матрицу.
Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца, в которой элемент х14 заменяем на ?, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
Шаг №2. Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
Наибольшая сумма констант приведения равна
х36=1+1=2, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве: В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
Шаг №3. Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
Наибольшая сумма констант приведения равна
х23=5+0=5, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве: В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
Шаг №4. Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества . программирование беллман уравнение
В приведенной матрице исследуем все нулевые переходы.
Наибольшая сумма констант приведения равна
х54=5+4=9, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве: В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
В соответствии с этой матрицей включаем в маршрут и .
Ответ: l* =C41+C36+C23+C54+C12+C65=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид:
Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана
Дано: (1)k=0,1,2,3
(2)
, (3)n=4
U - н.у. (неограниченное управление), (4)
, (5)
Найти: (6).
Решение: 1.
Минимизируем
Вычислим S3 от x3:
2.
Минимизируем
Вычислим S2 от U2:
3.
Минимизируем
Вычислим S1 от U2:
4.
Минимизируем
Вычислим S0 от U0:
Рассчитаем оптимальный процесс:
Рассчитаем оптимальное программное управление:
Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
Дано:
Найти: .
1. Выразим входное управляющее воздействие
Приведем задачу к варианту задачи на безусловный экстремум:
2.
3. Решим задачу с помощью уравнения Эйлера:
4. Решим ДУ Эйлера методом характеристического уравнения
p1=-3,65,p2=3,65
5. Т.к. x>?, то
Учитывая, что x0=C1
Размещено на http://allbest.ru
Найдем оптимальную программу управления:
Размещено на http://allbest.ru
6. Найдем оптимальный регулятор (оптимальный закон управления):
7. Закон управления можно получить и другим способом:
8.
9. Структурная схема:
Размещено на http://allbest.ru
Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
Найти: .
1. Преобразуем эту задачу в вариационную задачу на безусловный экстремум:
2.
3.
+
4.
5.
6. Составим оптимальную синтезированную систему управления:
7. Структурная схема:
Размещено на http://allbest.ru
Размещено на Allbest.ru
...Подобные документы
Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
лабораторная работа [42,8 K], добавлен 11.03.2011Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
контрольная работа [362,3 K], добавлен 03.11.2011Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Теоретические основы вариационного исчисления и область применения метода. Практическое решение задач оптимизации методом вариационного исчисления. Нахождение экстремума функционала и частных производных. Составление дифференциального уравнения Эйлера.
лабораторная работа [99,5 K], добавлен 16.12.2014Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Решение задачи линейного программирования симплекс-методом. Нахождение оптимального плана по критерию максимума прибыли. Транспорт - определение плана перевозок грузов на предприятие, которое обеспечивает минимальные совокупные транспортные издержки.
контрольная работа [2,0 M], добавлен 11.05.2008Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Целевая функция. Многоугольник решений. Решение задачи графическим методом. Линейное программирование. Составление симплекс–таблиц. Система ограничений. Система уравнений. Метод потенциалов. Опорное решение методом наименьших затрат. Матрица оценок.
контрольная работа [487,6 K], добавлен 29.09.2008Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008История развития и функции линейного программирования. Исследование условий типовых задач и возможностей табличного процессора. Решение задач о рационе питания, плане производства, раскрое материалов и рациональной перевозке груза в среде MS Excel.
курсовая работа [3,3 M], добавлен 28.04.2014
