Детерминированные линейные модели с непрерывными переменными

Нажмите для полного просмотра!

Детерминированные линейные модели с непрерывными переменными, слайд №2

Детерминированные линейные модели с непрерывными переменными, слайд №3

Детерминированные линейные модели с непрерывными переменными, слайд №4

Детерминированные линейные модели с непрерывными переменными, слайд №5

Детерминированные линейные модели с непрерывными переменными, слайд №6

Детерминированные линейные модели с непрерывными переменными, слайд №7

Детерминированные линейные модели с непрерывными переменными, слайд №8

Детерминированные линейные модели с непрерывными переменными, слайд №9

Детерминированные линейные модели с непрерывными переменными, слайд №10

Детерминированные линейные модели с непрерывными переменными, слайд №11

Детерминированные линейные модели с непрерывными переменными, слайд №12

Детерминированные линейные модели с непрерывными переменными, слайд №13

Детерминированные линейные модели с непрерывными переменными, слайд №14

Детерминированные линейные модели с непрерывными переменными, слайд №15

Детерминированные линейные модели с непрерывными переменными, слайд №16

Детерминированные линейные модели с непрерывными переменными, слайд №17

Детерминированные линейные модели с непрерывными переменными, слайд №18

Детерминированные линейные модели с непрерывными переменными, слайд №19

Детерминированные линейные модели с непрерывными переменными, слайд №20

Детерминированные линейные модели с непрерывными переменными, слайд №21

Детерминированные линейные модели с непрерывными переменными, слайд №22

Детерминированные линейные модели с непрерывными переменными, слайд №23

Детерминированные линейные модели с непрерывными переменными, слайд №24

Детерминированные линейные модели с непрерывными переменными, слайд №25

Детерминированные линейные модели с непрерывными переменными, слайд №26

Детерминированные линейные модели с непрерывными переменными, слайд №27

Детерминированные линейные модели с непрерывными переменными, слайд №28

Детерминированные линейные модели с непрерывными переменными, слайд №29

Детерминированные линейные модели с непрерывными переменными, слайд №30

Детерминированные линейные модели с непрерывными переменными, слайд №31

Детерминированные линейные модели с непрерывными переменными, слайд №32

Детерминированные линейные модели с непрерывными переменными, слайд №33

Детерминированные линейные модели с непрерывными переменными, слайд №34

Детерминированные линейные модели с непрерывными переменными, слайд №35

Детерминированные линейные модели с непрерывными переменными, слайд №36

Детерминированные линейные модели с непрерывными переменными, слайд №37

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Детерминированные линейные модели с непрерывными переменными. Доклад-сообщение содержит 37 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Моделирование систем Лекция 3: Детерминированные линейные модели с непрерывными переменными

Слайд 2

Описание слайда:

Часть 1 Общая постановка задач и алгоритм их решения

Слайд 3

Описание слайда:

Формальная постановка задачи

Слайд 4

Описание слайда:

Линейное программирование Дж. Данциг.

Слайд 5

Описание слайда:

Основные постулаты линейного программирования Оптимальное решение всегда принадлежит одной из вершин симплекса. Локально оптимальное решение задачи линейного программирования одновременно является и глобально оптимальным.

Слайд 6

Описание слайда:

Пример 1

Слайд 7

Описание слайда:

Выделение базисных переменных. Пусть в качестве базисных (не равных нулю) переменных выбраны х1 и х5: x1 = 8 + x2 – 5x3 + x4 – x5. Отсюда: 5х1 = 40 + 5х2 – 25х3 + 5х4 – 5х5 (2) Подставляя (2) в первое равенство системы (1), получим: 40 + 5х2 – 25х3 + 5х4 – 5х5 – 4х2 + 13х3 – 2х4 + х5 = 20. Отсюда следует: х2 – 12х3 + 3х4 – 4х5 + 20 = 0. Окончательное равенство, включающее х5, имеет вид: Подставляя (3) в выражение для х1, получим: После подстановки х1 и х5 в целевую функцию, получим:

Слайд 8

Описание слайда:

Эквивалентная каноническая форма задачи (1)

Слайд 9

Описание слайда:

Переход к новому базису

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

Настройка пакета Simplexwin 3.1 –ввод числа переменных и ограничений

Слайд 13

Описание слайда:

Ввод исходных данных в пакет Simplexwin 3.1

Слайд 14

Описание слайда:

Вывод результатов пакетом Simplexwin 3.1

Слайд 15

Описание слайда:

Достоинства и недостатки симплекс-метода 1. Достоинства: Гарантия глобально оптимального решения. Высокое быстродействие независимо от размерности. Наличие большого числа программных реализаций. 2. Недостатки: Решаются только линейные задачи с непрерывными неотрицательными переменными.

Слайд 16

Описание слайда:

Самостоятельно Решить задачу симплекс-методом, добавив переменные:

Слайд 17

Описание слайда:

Часть 2 Важный частный случай: задача с одним ограничением

Слайд 18

Описание слайда:

Задача с одним видом ресурса

Слайд 19

Описание слайда:

Алгоритм поиска решения задачи (1) Ганс Христиан Андерсен Блок-схема алгоритма

Слайд 20

Описание слайда:

Достоинства и недостатки алгоритма 1. Достоинства: Гарантия глобально оптимального решения. Простота реализации. Высокое быстродействие. Низкие требования к ресурсам компьютера. 2. Недостаток: Узкий диапазон применения.

Слайд 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.

Слайд 22

Описание слайда:

Задача с одним видом ресурса и ограничениями на выпуск каждого вида продукции Требуется определить вектор переменных Х, который бы максимизировал финансовые поступления на предприятие: где: хi – объем выпускаемой продукции i-го вида (непрерывная неотрицательная переменная); сi – стоимость единицы выпускаемой продукции i-го вида; b – величина имеющегося ресурса (например, человекочасы); аi, – затраты единственного вида ресурса, приходящиеся на единицу i-го вида продукции, di - верхняя граница выпуска i-го вида продукции.

Слайд 23

Описание слайда:

Алгоритм поиска решения задачи (2) Начало, S=0.

Слайд 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.

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

Слайд 27

Описание слайда:

Графическая интерпретация задач линейного программирования - область допустимых решений не ограничена Формальная Графическая постановка интерпретация

Слайд 28

Описание слайда:

Задачи ЛП на графах Задача о максимальном потоке: На графе G(X,U), множество вершин которого X, а множество дуг U, определить максимальный поток из вершины – источника в вершину – сток, если поток f (i,j) по дуге не может превысить пропускной способности дуги r(i,j).

Слайд 29

Описание слайда:

Графическое представление задачи о максимальном потоке.

Слайд 30

Описание слайда:

Задача о максимальной циркуляции на взвешенном орграфе Содержательная постановка задачи: на взвешенном орграфе с бикомпонентами требуется распределить замкнутые потоки (циркуляции) в контурах таким образом, чтобы: Их сумма в одной и той же дуге не превышала пропускной способности этой дуги. Суммарный вес всех циркуляций должен быть максимальным.