Решение задач линейного программирования
Графоаналитическое решение основной задачи линейного программирования. Решение задачи о коммивояжере методом ветвей и границ. Оптимизация дискретных управлений дискретным методом динамического программирования. Синтез непрерывных оптимальных уравнений.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 17.10.2017 |
| Размер файла | 498,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Исходные данные
Задание №1. Графоаналитическое решение ОЗЛП
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана
Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
Исходные данные
К заданию №1.
|
№ |
C1 |
C2 |
B1 |
B2 |
B3 |
B4 |
A11 |
A12 |
A21 |
A22 |
A31 |
A32 |
A41 |
A42 |
|
|
220 |
3 |
4 |
1 |
4 |
0,5 |
0,5 |
1 |
-1,5 |
-2 |
6 |
1 |
-2 |
-2 |
2 |
К заданию №2.
|
1 |
2 |
3 |
4 |
5 |
6 |
|||
|
С = |
1 |
? |
3 |
4 |
5 |
1 |
6 |
|
|
2 |
1 |
? |
5 |
1 |
3 |
2 |
||
|
3 |
4 |
2 |
? |
3 |
6 |
1 |
||
|
4 |
3 |
4 |
1 |
? |
5 |
7 |
||
|
5 |
5 |
1 |
6 |
2 |
? |
3 |
||
|
6 |
1 |
6 |
3 |
1 |
4 |
? |
К заданию №3.
|
№ |
A |
B |
б |
в |
г |
|
|
120 |
1 |
0,25 |
1 |
0,75 |
4 |
К заданию №4.
|
№ |
A |
B |
б2 |
|
|
120 |
0,3 |
0,6 |
3/4 |
К заданию №5.
|
№ |
k |
г |
|
|
120 |
40 |
20 |
Задание №1. Графоаналитическое решение ОЗЛП
1. Математическая постановка ОЗЛП:
ц=3x1+4x2>max, (0)
x1-1,5x2?1, (1)
-2x1+6x2?4, (2)
x1-2x2?0,5, (3)
-2x1+2x2?0,5, (4)
x1?0, (5)
x2?0, (6)
EF: x1-1,5x2=1, (1')
DF: -2x1+6x2=4, (2')
CE: x1-2x2=0,5, (3')
BD: -2x1+2x2=0,5, (4')
AC: x1=0, (5')
AB: x2=0, (6')
2. Записываем уравнение граничных линий допустимого многоугольника (1') - (6').
На плоскости (x1, x2) строим граничные линии.
3. Строим линию, пересекающую область ц.
, (7)
, (8)
4. Находим градиент целевой функции:
, (9)
, (10)
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи ц=3x1+4x2>max. Построим прямую, отвечающую значению функции ц=0: F=3x1+4x2=0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0;0), конец - точка (3;4). Будем двигать эту прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией. линейный программирование дискретный уравнение
Из рисунка видно, что оптимальная точка F* равная , находится на пересечении линий DF и EF и ее координаты определяются путем решения одноименных уравнений (1') и (2').
, , (11)
, (12)
Ответ: , ;
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
|
1 |
2 |
3 |
4 |
5 |
6 |
|||
|
С = |
1 |
? |
3 |
4 |
5 |
1 |
6 |
|
|
2 |
1 |
? |
5 |
1 |
3 |
2 |
||
|
3 |
4 |
2 |
? |
3 |
6 |
1 |
||
|
4 |
3 |
4 |
1 |
? |
5 |
7 |
||
|
5 |
5 |
1 |
6 |
2 |
? |
3 |
||
|
6 |
1 |
6 |
3 |
1 |
4 |
? |
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам:
hн= min(i) hнi
|
1 |
2 |
3 |
4 |
5 |
6 |
hн |
|||
|
С' = |
1 |
? |
3 |
4 |
5 |
1 |
6 |
1 |
|
|
2 |
1 |
? |
5 |
1 |
3 |
2 |
1 |
||
|
3 |
4 |
2 |
? |
3 |
6 |
1 |
1 |
||
|
4 |
3 |
4 |
1 |
? |
5 |
7 |
1 |
||
|
5 |
5 |
1 |
6 |
2 |
? |
3 |
1 |
||
|
6 |
1 |
6 |
3 |
1 |
4 |
? |
1 |
Произведем приведение матрицы C по столбцам: gi = min(х) gнi
|
1 |
2 |
3 |
4 |
5 |
6 |
|||
|
С' = |
1 |
? |
2 |
3 |
4 |
0 |
5 |
|
|
2 |
0 |
? |
4 |
0 |
2 |
1 |
||
|
3 |
3 |
1 |
? |
2 |
5 |
0 |
||
|
4 |
2 |
3 |
0 |
? |
4 |
6 |
||
|
5 |
4 |
0 |
5 |
1 |
? |
2 |
||
|
6 |
0 |
5 |
2 |
0 |
3 |
? |
||
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
В итоге получаем полностью приведенную (редуцированную) матрицу:
|
1 |
2 |
3 |
4 |
5 |
6 |
hн |
|||
|
С0 = |
1 |
? |
2 |
3 |
4 |
0 |
5 |
1 |
|
|
2 |
0 |
? |
4 |
0 |
2 |
1 |
1 |
||
|
3 |
3 |
1 |
? |
2 |
5 |
0 |
1 |
||
|
4 |
2 |
3 |
0 |
? |
4 |
6 |
1 |
||
|
5 |
4 |
0 |
5 |
1 |
? |
2 |
1 |
||
|
6 |
0 |
5 |
2 |
0 |
3 |
? |
1 |
||
|
gi |
0 |
0 |
0 |
0 |
0 |
0 |
Величины hн и gi называются константами приведения.
Нижняя граница цикла: d0=6 ().
Шаг №1.
Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества () и (), т.е. , где
В приведенной матрице исследуем все нулевые переходы.
|
1 |
2 |
3 |
4 |
5 |
6 |
бн |
|||
|
C0 = |
1 |
? |
2 |
3 |
4 |
0(4) |
5 |
2 |
|
|
2 |
0(0) |
? |
4 |
0(0) |
2 |
1 |
0 |
||
|
3 |
3 |
1 |
? |
2 |
5 |
0(2) |
1 |
||
|
4 |
2 |
3 |
0(4) |
? |
4 |
6 |
2 |
||
|
5 |
4 |
0(2) |
5 |
1 |
? |
2 |
1 |
||
|
6 |
0(0) |
5 |
2 |
0(0) |
3 |
? |
0 |
||
|
вi |
0 |
1 |
2 |
0 |
2 |
1 |
Наибольшая сумма констант приведения равна
х15= б1 + в5 =2+2=4,
следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
1 |
2 |
3 |
4 |
6 |
hн |
|||
|
2 |
0 |
? |
4 |
0 |
1 |
0 |
||
|
3 |
3 |
1 |
? |
2 |
0 |
0 |
||
|
C1= |
4 |
2 |
3 |
0 |
? |
6 |
0 |
|
|
5 |
? |
0 |
5 |
1 |
2 |
0 |
||
|
6 |
0 |
5 |
2 |
0 |
? |
0 |
||
|
gi |
0 |
0 |
0 |
0 |
0 |
d1=0
Шаг №2.
Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
1 |
2 |
3 |
4 |
6 |
бн |
|||
|
2 |
0(0) |
? |
4 |
0(0) |
1 |
0 |
||
|
3 |
3 |
1 |
? |
2 |
0(2) |
1 |
||
|
C1= |
4 |
2 |
3 |
0(4) |
? |
6 |
2 |
|
|
5 |
? |
0(2) |
5 |
1 |
2 |
1 |
||
|
6 |
0(0) |
5 |
2 |
0(0) |
? |
0 |
||
|
вi |
0 |
1 |
2 |
0 |
1 |
Наибольшая сумма констант приведения равна
х43=2+2=4, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
1 |
2 |
4 |
6 |
hн |
|||
|
C2 = |
2 |
0 |
? |
0 |
1 |
0 |
|
|
3 |
3 |
1 |
? |
0 |
0 |
||
|
5 |
? |
0 |
1 |
2 |
0 |
||
|
6 |
0 |
5 |
0 |
? |
0 |
||
|
gi |
0 |
0 |
0 |
0 |
d2=0
Шаг №3.
Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
1 |
2 |
5 |
6 |
бн |
|||
|
C2 = |
2 |
0(0) |
? |
0(0) |
1 |
0 |
|
|
3 |
3 |
1 |
? |
0(2) |
1 |
||
|
5 |
? |
0(2) |
1 |
2 |
1 |
||
|
6 |
0(0) |
5 |
0(0) |
? |
0 |
||
|
вi |
0 |
1 |
0 |
1 |
Наибольшая сумма констант приведения равна
х36=1+1=2, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
1 |
2 |
4 |
hн |
|||
|
2 |
0 |
? |
0 |
0 |
||
|
C3 = |
5 |
? |
0 |
1 |
0 |
|
|
6 |
0 |
5 |
0 |
0 |
||
|
gi |
0 |
0 |
0 |
d3=0
Шаг №4.
Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
|
1 |
2 |
4 |
бн |
|||
|
2 |
0(0) |
? |
0(1) |
2 |
||
|
C3 = |
5 |
? |
0(6) |
1 |
1 |
|
|
6 |
0(5) |
5 |
? |
5 |
||
|
вi |
0 |
5 |
1 |
Наибольшая сумма констант приведения равна
х52=1+5=6, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
1 |
4 |
hн |
|||
|
C4 = |
2 |
0 |
0 |
0 |
|
|
6 |
0 |
? |
0 |
||
|
gi |
0 |
0 |
d4=0
В соответствии с этой матрицей включаем в маршрут и .
Ответ: l* =C15+C52+C24+C43+C36+C61=1+1+1+1+1+1=6.
Дерево решения имеет следующий вид:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задание №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=-0,6, p2=0,6
5. Т.к. x>?, то
Учитывая, что x0=C1
Найдем оптимальную программу управления:
Размещено на http://www.allbest.ru/
6. Найдем оптимальный регулятор (оптимальный закон управления):
7. Закон управления можно получить и другим способом:
8.
9. Структурная схема:
Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
Найти: .
1. Преобразуем эту задачу в вариационную задачу на безусловный экстремум:
2.
3.
+
4.
5.
6. Составим оптимальную синтезированную систему управления:
7. Структурная схема:
Размещено на Allbest.ru
...Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Оптимизация движения автобетоносмесителей на строительную площадку с минимализацией времени и средств при строительстве. Расчет технических характеристик здания и определения минимального комплекта машин. Применение методов линейного программирования.
курсовая работа [10,9 M], добавлен 06.03.2015Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
контрольная работа [1023,6 K], добавлен 27.05.2013
