- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Задачи и методы оптимального планирования презентация
Содержание
- 1. Задачи и методы оптимального планирования
- 2. Учебные вопросы: Основные понятия Математическая постановка общей
- 3. Первый учебный вопрос: Основные понятия
- 4. 1. Основные понятия 1.1 Сущность задач оптимального
- 5. 1.1 Сущность задач оптимального планирования Основные задачи:
- 6. 1.2 Классификация задач оптимального планирования I. По
- 7. 1.2 Классификация задач оптимального планирования (продолжение) IV.
- 8. 1.3 Методы математического проектирования Дифференциальный; Линейный; Нелинейный;
- 9. 1.4 Проблемы решаемые методами линейного программирования Оптимальное
- 10. Второй учебный вопрос: Математическая постановка общей задачи линейного программирования (ОЗЛП)
- 11. 2.1 Общие математические признаки общей задачи линейного
- 12. 2.2 Постановка общей задачи Найти значение переменных
- 13. 2.3 Формы записи задачи линейного программирования Стандартная; Каноническая; Векторная; Матричная.
- 14. Третий учебный вопрос: Транспортная задача
- 15. 3.1 Транспортная задача В зависимости от выбранного
- 16. 3.1 Транспортная задача линейного проектирования (ТЗЛП) в
- 17. 3.1.1 Составляем логическую таблицу
- 18. 3.1.2 На основе таблицы составляем целевую функцию
- 19. Четвёртый учебный вопрос: Геометрический метод решения ОЗЛП
- 20. 4.1 Основа метода Задачам линейного программирования можно
- 21. Целевая функция Ограничения
- 22. Построить на координатной плоскости область соответствующую
- 23. 5. Определить направление возрастания или убывания целевой
- 24. ЗЛП имеет единственное решение Виды решений ЗЛП ЗЛП имеет альтернативный оптимум (линия АВ)
- 25. ЗЛП имеет минимум и не имеет максимума Виды решений ЗЛП ЗЛП не имеет решения
- 26. Пятый учебный вопрос: Пример решения ЗЛП
- 27. Целевая функция F = 2х1 +
- 28. I Этап: II
- 29. V Этап: Определить направление вектора. VI
- 30. Решение задачи C (3;2)
- 31. P.S. Если взять целевую функцию F =
- 32. Шестой учебный вопрос: Двойственные задачи линейного программирования
- 33. Двойственность в линейном программировании это принцип, который
- 34. 6.1 Основные понятия (продолжение)
- 35. В экономической литературе цены ресурсов y1, y2,
- 36. Алгоритм составления двойственной задачи I. Привести все
- 37. II. Составить расширенную матрицу коэффициентов прямой задачи Алгоритм составления двойственной задачи (продолжение)
- 38. III. Составить расширенную матрицу двойственной задачи, транспонированную
- 39. IV. Сформировать двойственную задачу. Fпр → Fдв
- 40. Составить задачу двойственную следующей Целевая функция
- 41. I. Приведём все неравенства системы ограничений к
- 42. II. Составим расширенную матрицу коэффициентов прямой задачи Пример. Решение (продолжение)
- 43. III. Составим расширенную матрицу двойственной задачи транспонированную к прямой Пример. Решение (продолжение)
- 44. IV. Сформируем двойственную задачу
- 45. Спасибо за внимание!
Учебные вопросы: Основные понятия Математическая постановка общей задачи линейного программирования (ОЗЛП) Транспортная задача Геометрический метод решения ОЗЛП Пример решения задачи линейного программирования (ЗЛП) Двойственные задачи линейного программирования
Слайд 2Учебные вопросы:
Основные понятия
Математическая постановка общей задачи линейного программирования (ОЗЛП)
Транспортная задача
Геометрический метод
решения ОЗЛП
Пример решения задачи линейного программирования (ЗЛП)
Двойственные задачи линейного программирования
Пример решения задачи линейного программирования (ЗЛП)
Двойственные задачи линейного программирования
Слайд 41. Основные понятия
1.1 Сущность задач оптимального планирования
Оптимальное планирование – комплекс методов
который позволяет выбрать из многих возможных планов или программы наилучший с точки зрения заданного критерия оптимальности при определённых ограничениях.
В экономическом анализе критерий оптимальности – показатель показывающий предельную меру экономического эффекта принимаемого решением (максимум прибыли, минимум трудозатрат, наименьшее время достижения цели и т.д.).
В экономическом анализе критерий оптимальности – показатель показывающий предельную меру экономического эффекта принимаемого решением (максимум прибыли, минимум трудозатрат, наименьшее время достижения цели и т.д.).
Слайд 51.1 Сущность задач оптимального планирования
Основные задачи:
Правильно и чётко формулировать цели экономической
системы в целом и каждого его звена.
Отбирать критерий оптимальности для всего комплекса задач планирования.
Решать каждую задачу планирования в отдельности оптимально (находить единственно наилучшее решение с учётом избранных критериев оптимальности).
Отбирать критерий оптимальности для всего комплекса задач планирования.
Решать каждую задачу планирования в отдельности оптимально (находить единственно наилучшее решение с учётом избранных критериев оптимальности).
Слайд 61.2 Классификация задач оптимального планирования
I. По характеру взаимосвязи между переменными:
линейные;
нелинейные.
II.
По характеру изменения переменных:
непрерывный;
дискретный.
III. По характеру учёта факторов времени:
статические;
динамические.
непрерывный;
дискретный.
III. По характеру учёта факторов времени:
статические;
динамические.
Слайд 71.2 Классификация задач оптимального планирования (продолжение)
IV. По наличию информации:
полные определённости;
неполные информации.
V.
По числу критериев оценки альтернатив:
простые (однокритериальные);
сложные (многокритериальные).
простые (однокритериальные);
сложные (многокритериальные).
Оптимальное планирование основано на решении задач математического программирования.
Слайд 81.3 Методы математического проектирования
Дифференциальный;
Линейный;
Нелинейный;
Динамический;
Стохастический (вероятностный);
Эвристический (интуиция, мнение экспертов) и т.д.
Слайд 91.4 Проблемы решаемые методами линейного программирования
Оптимальное распределение мощностей различных машин, станков,
механизмов;
Оптимальное использование транспортных средств путём определения рациональных планов перевозок;
Рациональное комплектование сырья и составление любых смесей и т.д.
Оптимальное использование транспортных средств путём определения рациональных планов перевозок;
Рациональное комплектование сырья и составление любых смесей и т.д.
Слайд 10Второй учебный вопрос:
Математическая постановка общей задачи линейного программирования (ОЗЛП)
Слайд 112.1 Общие математические признаки общей задачи линейного программирования (ОЗЛП)
Отыскание экстремума (min;
max);
Наличие большого числа переменных;
Область существования переменных это линейные равенства и неравенства.
Наличие большого числа переменных;
Область существования переменных это линейные равенства и неравенства.
Слайд 122.2 Постановка общей задачи
Найти значение переменных Х1, Х2, …, Хn, которые
обращают в max или min функцию:
(1)
и удовлетворяет уравнениям или неравенствам
№ 1 – целевая функция;
№ 2 – ограничения;
№ 3 – условие неотрицательности;
а, b, c – известные коэффициенты.
Вид функций 1 и 2 определяют класс или вид математического программирования.
(1)
и удовлетворяет уравнениям или неравенствам
№ 1 – целевая функция;
№ 2 – ограничения;
№ 3 – условие неотрицательности;
а, b, c – известные коэффициенты.
Вид функций 1 и 2 определяют класс или вид математического программирования.
Слайд 132.3 Формы записи задачи линейного программирования
Стандартная;
Каноническая;
Векторная;
Матричная.
Слайд 153.1 Транспортная задача
В зависимости от выбранного критерия эффективности различают следующие задачи:
по
суммарному пробегу;
по стоимости;
по времени;
комбинированные.
по стоимости;
по времени;
комбинированные.
Данная задача впервые в мире была поставлена и решена в 1939 году в России Канторовичем Л.В. Её решением было положено начало методу линейного проектирования.
Слайд 163.1 Транспортная задача линейного проектирования (ТЗЛП) в общем виде
Исходные данные:
Скi -
склады с запасом имущества в количестве аi ;
Пj – потребители с потребностями в имуществе в количестве bj ;
Сij – стоимость перевозки единицы имущества со склада потребителю;
хij – количество единиц имущества доставленных со склада потребителю.
Требуется найти такой план перевозок (хij), который бы удовлетворял ограничениям и суммарная стоимость перевозок была минимальной.
Пj – потребители с потребностями в имуществе в количестве bj ;
Сij – стоимость перевозки единицы имущества со склада потребителю;
хij – количество единиц имущества доставленных со склада потребителю.
Требуется найти такой план перевозок (хij), который бы удовлетворял ограничениям и суммарная стоимость перевозок была минимальной.
Слайд 183.1.2 На основе таблицы составляем целевую функцию
Целевая функция
Ограничения по запасам на
складах
Ограничения по потребностям
Условие неотрицательности
Ограничения по потребностям
Условие неотрицательности
Слайд 204.1 Основа метода
Задачам линейного программирования можно дать наглядную геометрическую интерпретацию, которая
позволяет наглядно увидеть ряд основных свойств задач линейного программирования, а также решить простейшие задачи.
Основное условие:
число переменных величин n на 2 больше чем число уравнений m (n = m + 2)
Основное условие:
число переменных величин n на 2 больше чем число уравнений m (n = m + 2)
Слайд 21Целевая функция
Ограничения
* Плоскость делится прямой на 2 полуплоскости:
Геометрическая интерпретация ЗЛП
Слайд 22 Построить на координатной плоскости область соответствующую ограничениям, которые представлены прямыми
линиями.
Определить положительную или отрицательную полуплоскость ограничений в зависимости от вида неравенства с помощью вектора прямых, который направлен только в положительную полуплоскость.
Выделить область допустимых решений (ОДР) и её вершины
Построить целевую функцию F.
Определить положительную или отрицательную полуплоскость ограничений в зависимости от вида неравенства с помощью вектора прямых, который направлен только в положительную полуплоскость.
Выделить область допустимых решений (ОДР) и её вершины
Построить целевую функцию F.
Алгоритм решения задачи графическим методом:
Слайд 235. Определить направление возрастания или убывания целевой функции в зависимости от
её вида (min; max) с помощью вектора С (направленного в положительную полуплоскость).
6. Найти координаты точки max или min в вершине ОДР с помощью целевой функции F.
Примечание: Решение может быть:
единственным;
множественным;
отсутствует.
6. Найти координаты точки max или min в вершине ОДР с помощью целевой функции F.
Примечание: Решение может быть:
единственным;
множественным;
отсутствует.
Алгоритм решения задачи графическим методом (продолжение):
Слайд 27Целевая функция F = 2х1 + х2 → max
Ограничения
Решить задачу
геометрическим методом
Решение задачи
Слайд 28I Этап:
II Этап: Определить направление векторов.
III Этап: Выделить ОДР и её
вершины – ОАВСД
IV Этап:
IV Этап:
Решение задачи
Слайд 29V Этап: Определить направление вектора.
VI Этап: Перебираем все точки для F
= 2х1 + х2
точка О ̶ F = 2*0 + 0 = 0
точка А ̶ F = 2*0 + 2 = 2
точка В ̶ F = 2*1 + 3 = 5
точка С ̶ F = 2*3 + 2 = 8
точка Д ̶ F = 2*1,5 + 0 = 3
Ответ: точка С с координатами (3;2) является оптимальной, так как в ней F = 2х1 + х2 → max
точка О ̶ F = 2*0 + 0 = 0
точка А ̶ F = 2*0 + 2 = 2
точка В ̶ F = 2*1 + 3 = 5
точка С ̶ F = 2*3 + 2 = 8
точка Д ̶ F = 2*1,5 + 0 = 3
Ответ: точка С с координатами (3;2) является оптимальной, так как в ней F = 2х1 + х2 → max
Решение задачи
Слайд 31P.S. Если взять целевую функцию F = х1 + 2х2 →
max при тех же ограничениях, тогда F будет параллельна прямой ВС, следовательно, задача линейного проектирования будет иметь альтернативный оптимум (будет иметь множество значений на отрезке ВС).
Решение задачи
Слайд 33Двойственность в линейном программировании это принцип, который заключается в том, чтобы
для каждой задачи ЛП путём замены отдельных её элементов на двойственные можно сформулировать двойственную задачу.
Связь между прямой и двойственной задачами устанавливается двумя теоремами:
теоремой (признаком) двойственности;
теоремой (признаком) оптимальности.
Связь между прямой и двойственной задачами устанавливается двумя теоремами:
теоремой (признаком) двойственности;
теоремой (признаком) оптимальности.
6.1 Основные понятия
Слайд 35В экономической литературе цены ресурсов y1, y2, …, ym носят следующие
названия – учётные, неявные, теневые.
Внешние цены с1, с2, …, сn на продукции известны как правило до начала производства.
Внешние цены с1, с2, …, сn на продукции известны как правило до начала производства.
6.2 Экономические свойства оценок
Слайд 36Алгоритм составления двойственной задачи
I. Привести все неравенства системы ограничений прямой задачи
к одному смыслу:
Если в прямой задаче ищут максимум линейной функции, то все неравенства системы необходимо привести к виду меньше (≤).
Если в прямой задаче ищут минимум линейной функции, то все неравенства системы необходимо привести к виду больше (≥).
С этой целью неравенства, где данное требование не выполняется, надо умножить на «‒ 1».
Если в прямой задаче ищут максимум линейной функции, то все неравенства системы необходимо привести к виду меньше (≤).
Если в прямой задаче ищут минимум линейной функции, то все неравенства системы необходимо привести к виду больше (≥).
С этой целью неравенства, где данное требование не выполняется, надо умножить на «‒ 1».
6.2 Экономические свойства оценок
Слайд 37II. Составить расширенную матрицу коэффициентов прямой задачи
Алгоритм составления двойственной задачи (продолжение)
Слайд 38III. Составить расширенную матрицу двойственной задачи, транспонированную (замена строк столбцами с
сохранением порядка) к прямой
Алгоритм составления двойственной задачи (продолжение)
Слайд 39IV. Сформировать двойственную задачу.
Fпр → Fдв , хj → yi;
число переменных
в двойственной задаче равно числу ограничений под № 2 в прямой задаче;
число ограничений в системе (5) двойственной задачи равно числу переменных прямой задачи;
коэффициенты при неизвестных целевой функции (4) двойственной задачи являются свободными членами в системе (2) прямой задачи;
правые части ограничения в (5) двойственной задаче это коэффициенты при неизвестных в целевой функции(1);
Если в прямой задаче ограничения имеют знак ≥, то в двойственной задаче ‒ ≤, и наоборот.
число ограничений в системе (5) двойственной задачи равно числу переменных прямой задачи;
коэффициенты при неизвестных целевой функции (4) двойственной задачи являются свободными членами в системе (2) прямой задачи;
правые части ограничения в (5) двойственной задаче это коэффициенты при неизвестных в целевой функции(1);
Если в прямой задаче ограничения имеют знак ≥, то в двойственной задаче ‒ ≤, и наоборот.
Алгоритм составления двойственной задачи (продолжение)
Слайд 41I. Приведём все неравенства системы ограничений к виду ≤, так как
ЦФ → max. С этой целью обе части неравенств с (1) по (4) умножим на «‒ 1» и получим
Пример. Решение
Слайд 43III. Составим расширенную матрицу двойственной задачи транспонированную к прямой
Пример. Решение (продолжение)
Слайд 44IV. Сформируем двойственную задачу
Целевая функция FДВ = ̶ у1 +
24 у2 + 3у3 ̶ 5у4 → min
Ограничения
Ограничения
Пример. Решение (продолжение)
