Презентация «Детерминированные линейные модели с непрерывными переменными»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 37 слайдов и доступен в формате ppt. Размер файла: 1.75 MB
Pic.1
Моделирование систем Лекция 3: Детерминированные линейные модели с непрерывными переменными
Pic.2
Часть 1 Общая постановка задач и алгоритм их решения
Pic.3
Формальная постановка задачи
Pic.4
Линейное программирование Дж. Данциг.
Pic.5
Основные постулаты линейного программирования Оптимальное решение всегда принадлежит одной из вершин симплекса. Локально оптимальное решение задачи линейного программирования одновременно является и …
Pic.6
Пример 1
Pic.7
Выделение базисных переменных. Пусть в качестве базисных (не равных нулю) переменных выбраны х1 и х5: x1 = 8 + x2 – 5x3 + x4 – x5. Отсюда: 5х1 = 40 + 5х2 – 25х3 + 5х4 – 5х5 (2) Подставляя (2) в …
Pic.8
Эквивалентная каноническая форма задачи (1)
Pic.9
Переход к новому базису
Pic.10
Переход к новому базису Т. к. коэффициент при х2 в целевой функции отрицателен, в базис вводится х2. Для того, чтобы определить, какая переменная выводится из базиса, проанализируем выражения, …
Pic.11
Канонический вид системы с учетом нового базиса Поскольку все коэффициенты небазисных переменных положительны, полученное решение является глобально оптимальным:
Pic.12
Настройка пакета Simplexwin 3. 1 –ввод числа переменных и ограничений
Pic.13
Ввод исходных данных в пакет Simplexwin 3. 1
Pic.14
Вывод результатов пакетом Simplexwin 3. 1
Pic.15
Достоинства и недостатки симплекс-метода 1. Достоинства: Гарантия глобально оптимального решения. Высокое быстродействие независимо от размерности. Наличие большого числа программных реализаций. 2. …
Pic.16
Самостоятельно Решить задачу симплекс-методом, добавив переменные:
Pic.17
Часть 2 Важный частный случай: задача с одним ограничением
Pic.18
Задача с одним видом ресурса
Pic.19
Алгоритм поиска решения задачи (1) Ганс Христиан Андерсен Блок-схема алгоритма
Pic.20
Достоинства и недостатки алгоритма 1. Достоинства: Гарантия глобально оптимального решения. Простота реализации. Высокое быстродействие. Низкие требования к ресурсам компьютера. 2. Недостаток: Узкий …
Pic.21
Пример 2 Решить самостоятельно, пользуясь приведенным выше алгоритмом и симплекс методом: S=5x₁+9x₂+3x₃ max; 2x₁+3x₂+4x₃ ≤ 12; x₁≥0; x₂ ≥0; x₃ ≥0. Ответ: x₁=0; x₂ =4; x₃ =0, Smax=36.
Pic.22
Задача с одним видом ресурса и ограничениями на выпуск каждого вида продукции Требуется определить вектор переменных Х, который бы максимизировал финансовые поступления на предприятие: где: хi – …
Pic.23
Алгоритм поиска решения задачи (2) Начало, S=0.
Pic.24
Пример 3 Решить самостоятельно, пользуясь приведенным выше алгоритмом и симплекс методом: S=5x₁+9x₂+3x₃ max; 2x₁+3x₂+4x₃ ≤ 12; 4≥x₁≥0; 2≥x₂ ≥0; 3≥x₃ ≥0. Ответ: x₁=3; x₂ =2; x₃=0; S=33.
Pic.25
Графическая интерпретация задач линейного программирования Аналитическая Графическая форма интерпретация
Pic.26
Достоинства и недостатки алгоритма 1. Достоинства: Гарантия глобально оптимального решения. Простота реализации. Высокое быстродействие. Низкие требования к ресурсам компьютера. 2. Недостаток: Узкий …
Pic.27
Графическая интерпретация задач линейного программирования - область допустимых решений не ограничена Формальная Графическая постановка интерпретация
Pic.28
Задачи ЛП на графах Задача о максимальном потоке: На графе G(X,U), множество вершин которого X, а множество дуг U, определить максимальный поток из вершины – источника в вершину – сток, если поток f …
Pic.29
Графическое представление задачи о максимальном потоке.
Pic.30
Задача о максимальной циркуляции на взвешенном орграфе Содержательная постановка задачи: на взвешенном орграфе с бикомпонентами требуется распределить замкнутые потоки (циркуляции) в контурах таким …
Pic.31
Формальная постановка задачи о максимальной циркуляции
Pic.32
Графовая иллюстрация
Pic.33
Решение задачи программой поиска максимальных циркуляций на планарных графах
Pic.34
Прямые и двойственные задачи Прямая задача
Pic.35
Двойственная задача
Pic.36
Графическое решение двойственной задачи
Pic.37
Решить самостоятельно графически Задача № 1 Задача № 2
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
