Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Основная задача линейного программирования

Основная задача линейного программирования

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 16.10.2017
Размер файла 195,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

  • Задание №1. Графоаналитическое решение ОЗЛП
  • Задание № 2. Задача о коммивояжере. Метод ветвей и границ
  • Задание №3. Оптимизация дискретных управлений дискретными динамическими объектами методом динамического программирования Р. Беллмана
  • Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера
  • Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона
  • Задание №1. Графоаналитическое решение ОЗЛП
  • 1. Математическая постановка ОЗЛП:
  • ц=5x1+x2>max, (0)
  • 2x1-2x2?4, (1)
  • 2x1+6x2?4, (2)
  • x1?0, (3)
  • x2?0, (4)
  • BD: 2x1-2x2=4, (1')
  • CD: 2x1+6x2=4, (2')
  • AC: x1=0, (3')
  • AB: x2=0, (4')
  • 2. Записываем уравнение граничных линий допустимого многоугольника (1') - (4'). На плоскости (x1, x2) строим граничные линии.
  • 3. Строим линию, пересекающую область ц.
  • , (5)
  • Х1+Х2=2(6)
  • 4. Находим градиент целевой функции:
  • , (7)
  • , (8)
  • Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
  • Рис. 1
  • Обозначим границы области многоугольника решений.
  • Рис. 2
  • Рассмотрим целевую функцию задачи ц=5x1+x2>max. Построим прямую, отвечающую значению функции ц=0: F=5x1+x2=0. Будем двигать эту прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
  • Рис. 3
  • Из рисунка видно, что оптимальная точка D* равная , находится на пересечении линий BD и CD и ее координаты определяются путем решения одноименных уравнений (1') и (2').
  • , , (9)
  • , (10)
  • Ответ: ;

Задание № 2. Задача о коммивояжере. Метод ветвей и границ

Расстояния между пунктами заданы матрицей:

1

2

3

4

5

6

С =

1

?

2

4

5

3

1

2

1

?

1

2

7

6

3

6

5

?

1

4

3

4

1

7

6

?

5

1

5

6

5

2

3

?

4

6

1

3

5

6

1

?

Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).

Произведем приведение матрицы C по строкам:

hн= min(i) hнi

1

2

3

4

5

6

hн

С' =

1

?

4

1

3

2

1

1

2

2

?

4

1

5

6

1

3

7

1

?

4

6

5

1

4

4

6

7

?

1

3

1

5

3

2

1

6

?

1

2

6

0

5

3

2

4

?

1

Произведем приведение матрицы C по столбцам:

gi = min(х) gнi

В итоге получаем полностью приведенную (редуцированную) матрицу:

1

2

3

4

5

6

hн

С0 =

1

?

3

0

2

1

0

1

2

2

?

3

0

4

5

1

3

7

0

?

3

6

5

1

4

4

6

6

?

0

2

1

5

3

1

0

5

?

0

2

6

0

4

2

1

3

?

1

gi

0

1

0

0

0

0

Величины hн и gi называются константами приведения.

Нижняя граница цикла:

d0=8 ().

Шаг №1.

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

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна х34= б3 + в4 =2+1=3, следовательно, множество разбивается на два подмножества и .

Оценка длины цикла: .

В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

1

2

3

5

6

hн

1

?

0

3

2

0

0

2

0

?

0

6

5

0

C1=

4

0

5

?

4

0

0

5

4

2

0

?

2

0

6

0

1

4

0

?

0

gi

0

0

0

0

0

d1=0

Шаг №2.

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

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна х53=2+0=2, следовательно, множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

d2=0

Шаг №3.

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

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна х21=5+0=5, следовательно, множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

2

5

6

hн

1

?

2

0

0

C3 =

4

5

?

0

0

6

1

0

?

0

gi

1

0

0

d3=1

Шаг №4.

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

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна х46=4+0=4, следовательно, множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

2

5

hн

C4 =

1

?

2

2

6

0

0

0

gi

0

0

d4=2

В соответствии с этой матрицей включаем в маршрут и .

Ответ: l* =C34+C46+C62+C21+C15+C53=1+1+3+1+3+2=11.

Дерево решения имеет следующий вид:

Рис. 4

Задание №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:

Рассчитаем оптимальный процесс:

Рассчитаем оптимальное программное управление:

Рис. 5

Рис. 6

Задание №4. Синтез непрерывного оптимального управления с помощью уравнения Эйлера

Дано:

Найти: .

1. Выразим входное управляющее воздействие

Приведем задачу к варианту задачи на безусловный экстремум:

2.

3. Решим задачу с помощью уравнения Эйлера:

4. Решим ДУ Эйлера методом характеристического уравнения

p1=-1,p2=1

5. Т.к. x>?, то

Учитывая, что x0=C1

Рис. 7

Найдем оптимальную программу управления:

Рис. 8

6. Найдем оптимальный регулятор (оптимальный закон управления):

7. Закон управления можно получить и другим способом:

8.

Рис. 9 Структурная схема

Задание №5. Синтез непрерывных оптимальных уравнений с помощью уравнения Эйлера-Пуассона

Найти: .

1. Преобразуем эту задачу в вариационную задачу на безусловный экстремум:

2.

3.

+

4.

5.

6. Составим оптимальную синтезированную систему управления:

коммивояжер дискретный программирование эйлер

Рис. 10 Структурная схема

Размещено на Allbest.ru


Подобные документы

  • Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации

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

    курсовая работа [195,5 K], добавлен 08.11.2009

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

    Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Методика решения задач линейного программирования

    Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Обзор задач дискретного программирования

    Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Экстремальные комбинаторные задачи. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори.

    курсовая работа [211,3 K], добавлен 22.05.2013

  • Решение транспортной задачи линейного программирования в среде MS Excel

    Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Графический метод решения задачи линейного программирования

    Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.

    контрольная работа [2,0 M], добавлен 02.05.2012

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

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

    курсовая работа [663,9 K], добавлен 10.06.2014

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

    Методы решения задачи оптимального резервирования технической системы. Решение задачи методами неопределенных множителей Лагранжа и динамического программирования. Построение оптимальной схемы системы при нагруженном резервировании ее элементов.

    лабораторная работа [31,5 K], добавлен 10.06.2009

  • Решение задач линейного программирования различными методами

    Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.

    контрольная работа [199,8 K], добавлен 15.06.2009

  • Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ

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

    курсовая работа [38,9 K], добавлен 15.11.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены