Лекция 3:
Детерминированные линейные модели с непрерывными переменными
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Детерминированные линейные модели с непрерывными переменными презентация
Содержание
- 1. Детерминированные линейные модели с непрерывными переменными
- 2. Часть 1 Общая постановка задач и алгоритм их решения
- 3. Формальная постановка задачи
- 4. Линейное программирование Дж. Данциг. Целевая функция Симплекс
- 5. Основные постулаты линейного программирования Оптимальное решение всегда
- 6. Пример 1 Определить оптимальное решение задачи:
- 7. Выделение базисных переменных. Пусть в качестве базисных
- 8. Эквивалентная каноническая форма задачи (1) х1
- 9. Переход к новому базису Т.к.
- 10. Переход к новому базису Т.к. коэффициент при
- 11. Канонический вид системы с учетом нового базиса
- 12. Настройка пакета Simplexwin 3.1 –ввод числа переменных и ограничений
- 13. Ввод исходных данных в пакет Simplexwin 3.1
- 14. Вывод результатов пакетом Simplexwin 3.1
- 15. Достоинства и недостатки симплекс-метода 1. Достоинства: Гарантия
- 16. Самостоятельно Решить задачу симплекс-методом, добавив переменные: S=5x₁+8x₂+3x₃
- 17. Часть 2 Важный частный случай: задача с одним ограничением
- 18. Задача с одним видом ресурса Требуется определить
- 19. Алгоритм поиска решения задачи (1) Ганс Христиан
- 20. Достоинства и недостатки алгоритма 1. Достоинства: Гарантия
- 21. Пример 2 Решить самостоятельно, пользуясь приведенным выше
- 22. Задача с одним видом ресурса и ограничениями
- 23. Алгоритм поиска решения задачи (2) Начало, S=0.
- 24. Пример 3 Решить самостоятельно, пользуясь приведенным выше
- 25. Графическая интерпретация задач линейного программирования Аналитическая
- 26. Достоинства и недостатки алгоритма 1. Достоинства: Гарантия
- 27. Графическая интерпретация задач линейного программирования - область
- 28. Задачи ЛП на графах Задача о максимальном
- 29. Графическое представление задачи о максимальном потоке.
- 30. Задача о максимальной циркуляции на взвешенном орграфе
- 31. Формальная постановка задачи о максимальной циркуляции Здесь
- 32. Графовая иллюстрация 1 3 4 2
- 33. Решение задачи программой поиска максимальных циркуляций на планарных графах
- 34. Прямые и двойственные задачи Прямая задача
- 35. Двойственная задача
- 36. Графическое решение двойственной задачи
- 37. Решить самостоятельно графически Задача № 1
Часть 1 Общая постановка задач и алгоритм их решения
Слайд 5Основные постулаты линейного программирования
Оптимальное решение всегда принадлежит одной из вершин симплекса.
Локально
оптимальное решение задачи линейного программирования одновременно является и глобально оптимальным.
Слайд 6Пример 1
Определить оптимальное решение задачи:
где: хi – непрерывная неотрицательная переменная;
Решение
– симплекс методом.
Слайд 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 в целевую функцию, получим:
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)
х1 и х5 – базисные переменные.
Базисное решение:
х1=3; x5=5; x2=x3=x4=0.
Значение целевой функции = 28.
Значение целевой функции = 28.
Слайд 9Переход к новому базису
Т.к. коэффициент при х3 в целевой функции отрицателен,
то увеличение х3 вызовет уменьшение функционала цели.
Т.о. введению в базис подлежит х3. Теперь следует выбрать переменную, выводимую из базиса:
х1 = 3 – 2х3 из равенства (4)
х5 = 5- 3х3 из равенства (5)
Если :
Т.о. введению в базис подлежит х3. Теперь следует выбрать переменную, выводимую из базиса:
х1 = 3 – 2х3 из равенства (4)
х5 = 5- 3х3 из равенства (5)
Если :
то х5 станет <0, что недопустимо.
то х1 станет <0, что недопустимо.
из базиса выводится х1.
Новый базис имеет вид:
х3 = 1,5; x5 = 0,5; x1=x2=x4=0; f(x) = -8
Значение целевой функции уменьшилось с 28 до –8.
Новая система имеет вид:
где х3 и х5 – базисные переменные.
Слайд 10Переход к новому базису
Т.к. коэффициент при х2 в целевой функции отрицателен,
в базис вводится х2. Для того, чтобы определить, какая переменная выводится из базиса, проанализируем выражения, получаемые из 1-го и 2-го равенств:
Слайд 11Канонический вид системы с учетом нового базиса
Поскольку все коэффициенты небазисных переменных
положительны, полученное решение является глобально оптимальным:
Слайд 15Достоинства и недостатки симплекс-метода
1. Достоинства:
Гарантия глобально оптимального решения.
Высокое быстродействие независимо от
размерности.
Наличие большого числа программных реализаций.
2. Недостатки:
Решаются только линейные задачи с непрерывными неотрицательными переменными.
Наличие большого числа программных реализаций.
2. Недостатки:
Решаются только линейные задачи с непрерывными неотрицательными переменными.
Слайд 16Самостоятельно
Решить задачу симплекс-методом, добавив переменные:
S=5x₁+8x₂+3x₃ max;
2x₁+3x₂+4x₃ ≤ 12;
x₁≥0; x₂ ≥0; x₃ ≥0.
x₁≥0; x₂ ≥0; x₃ ≥0.
Слайд 18Задача с одним видом ресурса
Требуется определить вектор переменных Х, который бы
максимизировал финансовые поступления на предприятие:
(1)
где: хi – объем выпускаемой продукции i-го вида (непрерывная неотрицательная переменная); сi – стоимость единицы выпускаемой продукции i-го вида; b – величина имеющегося ресурса (например, человекочасы); аi, – затраты единственного вида ресурса, приходящиеся на единицу i-го вида продукции.
(1)
где: хi – объем выпускаемой продукции i-го вида (непрерывная неотрицательная переменная); сi – стоимость единицы выпускаемой продукции i-го вида; b – величина имеющегося ресурса (например, человекочасы); аi, – затраты единственного вида ресурса, приходящиеся на единицу i-го вида продукции.
Слайд 19Алгоритм поиска решения задачи (1)
Ганс Христиан Андерсен
Блок-схема алгоритма
Начало, S=0.
Ввод n, b, ci, ai, i=1,2,…n
Все наряд-заказы ранжируются таким образом, что:
j=1
Печать S и
Конец алгоритма
1
2
3
4
6
7
8
9
Слайд 20Достоинства и недостатки алгоритма
1. Достоинства:
Гарантия глобально оптимального решения.
Простота реализации.
Высокое быстродействие.
Низкие требования
к ресурсам компьютера.
2. Недостаток:
Узкий диапазон применения.
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.
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.
Ввод n, b, ci, ai, i=1,2,…n
Все
наряд-заказы ранжируются таким образом, что:
j=1
b=0
Нет
Конец алгоритма
Да
1
2
3
4
5
6
7
8
9
Слайд 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.
2x₁+3x₂+4x₃ ≤ 12;
4≥x₁≥0; 2≥x₂ ≥0; 3≥x₃ ≥0.
Ответ: x₁=3; x₂ =2; x₃=0; S=33.
Слайд 25Графическая интерпретация задач линейного программирования
Аналитическая Графическая
форма
интерпретация
-x1+x2=1
x1+x2=2
x1-2x2=1
Область допустимых решений ограничена.
Слайд 26Достоинства и недостатки алгоритма
1. Достоинства:
Гарантия глобально оптимального решения.
Простота реализации.
Высокое быстродействие.
Низкие требования
к ресурсам компьютера.
2. Недостаток:
Узкий диапазон применения.
2. Недостаток:
Узкий диапазон применения.
Слайд 27Графическая интерпретация задач линейного программирования - область допустимых решений не ограничена
Формальная
Графическая
постановка интерпретация
постановка интерпретация
Слайд 28Задачи ЛП на графах
Задача о максимальном потоке: На графе G(X,U), множество
вершин которого X, а множество дуг U, определить максимальный поток из вершины – источника в вершину – сток, если поток f (i,j) по дуге не может превысить пропускной способности дуги r(i,j).
Слайд 30Задача о максимальной циркуляции на взвешенном орграфе
Содержательная постановка задачи: на взвешенном
орграфе с бикомпонентами требуется распределить замкнутые потоки (циркуляции) в контурах таким образом, чтобы:
Их сумма в одной и той же дуге не превышала пропускной способности этой дуги.
Суммарный вес всех циркуляций должен быть максимальным.
Их сумма в одной и той же дуге не превышала пропускной способности этой дуги.
Суммарный вес всех циркуляций должен быть максимальным.
Слайд 31Формальная постановка задачи о максимальной циркуляции
Здесь s(аi ) - циркуляция в
i-о контуре; r(p,q) – пропускная способность дуги (p,q) множества U;
A(p,q) – подмножество контуров, которым принадлежит дуга (p,q).
A(p,q) – подмножество контуров, которым принадлежит дуга (p,q).
