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