Презентация Задачи и методы оптимального планирования онлайн

Содержание слайда: Тема: Задачи и методы оптимального планирования КТН, доцент Манкевич Александр Валерьевич

Содержание слайда: Учебные вопросы: Основные понятия Математическая постановка общей задачи линейного программирования (ОЗЛП) Транспортная задача Геометрический метод решения ОЗЛП Пример решения задачи линейного программирования (ЗЛП) Двойственные задачи линейного программирования

Содержание слайда: Первый учебный вопрос: Основные понятия

Содержание слайда: 1. Основные понятия 1.1 Сущность задач оптимального планирования Оптимальное планирование – комплекс методов который позволяет выбрать из многих возможных планов или программы наилучший с точки зрения заданного критерия оптимальности при определённых ограничениях. В экономическом анализе критерий оптимальности – показатель показывающий предельную меру экономического эффекта принимаемого решением (максимум прибыли, минимум трудозатрат, наименьшее время достижения цели и т.д.).

Содержание слайда: 1.1 Сущность задач оптимального планирования Основные задачи: Правильно и чётко формулировать цели экономической системы в целом и каждого его звена. Отбирать критерий оптимальности для всего комплекса задач планирования. Решать каждую задачу планирования в отдельности оптимально (находить единственно наилучшее решение с учётом избранных критериев оптимальности).

Содержание слайда: 1.2 Классификация задач оптимального планирования I. По характеру взаимосвязи между переменными: линейные; нелинейные. II. По характеру изменения переменных: непрерывный; дискретный. III. По характеру учёта факторов времени: статические; динамические.

Содержание слайда: 1.2 Классификация задач оптимального планирования (продолжение) IV. По наличию информации: полные определённости; неполные информации. V. По числу критериев оценки альтернатив: простые (однокритериальные); сложные (многокритериальные).

Содержание слайда: 1.3 Методы математического проектирования Дифференциальный; Линейный; Нелинейный; Динамический; Стохастический (вероятностный); Эвристический (интуиция, мнение экспертов) и т.д.

Содержание слайда: 1.4 Проблемы решаемые методами линейного программирования Оптимальное распределение мощностей различных машин, станков, механизмов; Оптимальное использование транспортных средств путём определения рациональных планов перевозок; Рациональное комплектование сырья и составление любых смесей и т.д.

Содержание слайда: Второй учебный вопрос: Математическая постановка общей задачи линейного программирования (ОЗЛП)

Содержание слайда: 2.1 Общие математические признаки общей задачи линейного программирования (ОЗЛП) Отыскание экстремума (min; max); Наличие большого числа переменных; Область существования переменных это линейные равенства и неравенства.

Содержание слайда: 2.2 Постановка общей задачи Найти значение переменных Х1, Х2, …, Хn, которые обращают в max или min функцию: (1) и удовлетворяет уравнениям или неравенствам № 1 – целевая функция; № 2 – ограничения; № 3 – условие неотрицательности; а, b, c – известные коэффициенты. Вид функций 1 и 2 определяют класс или вид математического программирования.

Содержание слайда: 2.3 Формы записи задачи линейного программирования Стандартная; Каноническая; Векторная; Матричная.

Содержание слайда: Третий учебный вопрос: Транспортная задача

Содержание слайда: 3.1 Транспортная задача В зависимости от выбранного критерия эффективности различают следующие задачи: по суммарному пробегу; по стоимости; по времени; комбинированные.

Содержание слайда: 3.1 Транспортная задача линейного проектирования (ТЗЛП) в общем виде Исходные данные: Скi - склады с запасом имущества в количестве аi ; Пj – потребители с потребностями в имуществе в количестве bj ; Сij – стоимость перевозки единицы имущества со склада потребителю; хij – количество единиц имущества доставленных со склада потребителю. Требуется найти такой план перевозок (хij), который бы удовлетворял ограничениям и суммарная стоимость перевозок была минимальной.

Содержание слайда: 3.1.1 Составляем логическую таблицу

Содержание слайда: 3.1.2 На основе таблицы составляем целевую функцию Целевая функция Ограничения по запасам на складах Ограничения по потребностям Условие неотрицательности

Содержание слайда: Четвёртый учебный вопрос: Геометрический метод решения ОЗЛП

Содержание слайда: 4.1 Основа метода Задачам линейного программирования можно дать наглядную геометрическую интерпретацию, которая позволяет наглядно увидеть ряд основных свойств задач линейного программирования, а также решить простейшие задачи. Основное условие: число переменных величин n на 2 больше чем число уравнений m (n = m + 2)

Содержание слайда: Геометрическая интерпретация ЗЛП Целевая функция Ограничения

Содержание слайда: Алгоритм решения задачи графическим методом: Построить на координатной плоскости область соответствующую ограничениям, которые представлены прямыми линиями. Определить положительную или отрицательную полуплоскость ограничений в зависимости от вида неравенства с помощью вектора прямых, который направлен только в положительную полуплоскость. Выделить область допустимых решений (ОДР) и её вершины Построить целевую функцию F.

Содержание слайда: Алгоритм решения задачи графическим методом (продолжение): 5. Определить направление возрастания или убывания целевой функции в зависимости от её вида (min; max) с помощью вектора С (направленного в положительную полуплоскость). 6. Найти координаты точки max или min в вершине ОДР с помощью целевой функции F. Примечание: Решение может быть: единственным; множественным; отсутствует.

Содержание слайда: Виды решений ЗЛП

Содержание слайда: Виды решений ЗЛП

Содержание слайда: Пятый учебный вопрос: Пример решения ЗЛП

Содержание слайда: Решение задачи Целевая функция F = 2х1 + х2 → max Ограничения Решить задачу геометрическим методом

Содержание слайда: Решение задачи I Этап: II Этап: Определить направление векторов. III Этап: Выделить ОДР и её вершины – ОАВСД IV Этап:

Содержание слайда: Решение задачи V Этап: Определить направление вектора. 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

Содержание слайда: Решение задачи

Содержание слайда: Решение задачи P.S. Если взять целевую функцию F = х1 + 2х2 → max при тех же ограничениях, тогда F будет параллельна прямой ВС, следовательно, задача линейного проектирования будет иметь альтернативный оптимум (будет иметь множество значений на отрезке ВС).

Содержание слайда: Шестой учебный вопрос: Двойственные задачи линейного программирования

Содержание слайда: 6.1 Основные понятия Двойственность в линейном программировании это принцип, который заключается в том, чтобы для каждой задачи ЛП путём замены отдельных её элементов на двойственные можно сформулировать двойственную задачу. Связь между прямой и двойственной задачами устанавливается двумя теоремами: теоремой (признаком) двойственности; теоремой (признаком) оптимальности.

Содержание слайда: 6.1 Основные понятия (продолжение)

Содержание слайда: 6.2 Экономические свойства оценок В экономической литературе цены ресурсов y1, y2, …, ym носят следующие названия – учётные, неявные, теневые. Внешние цены с1, с2, …, сn на продукции известны как правило до начала производства.

Содержание слайда: 6.2 Экономические свойства оценок Алгоритм составления двойственной задачи I. Привести все неравенства системы ограничений прямой задачи к одному смыслу: Если в прямой задаче ищут максимум линейной функции, то все неравенства системы необходимо привести к виду меньше (≤). Если в прямой задаче ищут минимум линейной функции, то все неравенства системы необходимо привести к виду больше (≥). С этой целью неравенства, где данное требование не выполняется, надо умножить на «‒ 1».

Содержание слайда: Алгоритм составления двойственной задачи (продолжение) II. Составить расширенную матрицу коэффициентов прямой задачи

Содержание слайда: III. Составить расширенную матрицу двойственной задачи, транспонированную (замена строк столбцами с сохранением порядка) к прямой

Содержание слайда: Алгоритм составления двойственной задачи (продолжение) IV. Сформировать двойственную задачу. Fпр → Fдв , хj → yi; число переменных в двойственной задаче равно числу ограничений под № 2 в прямой задаче; число ограничений в системе (5) двойственной задачи равно числу переменных прямой задачи; коэффициенты при неизвестных целевой функции (4) двойственной задачи являются свободными членами в системе (2) прямой задачи; правые части ограничения в (5) двойственной задаче это коэффициенты при неизвестных в целевой функции(1); Если в прямой задаче ограничения имеют знак ≥, то в двойственной задаче ‒ ≤, и наоборот.

Содержание слайда: Пример Составить задачу двойственную следующей Целевая функция F = - х1 + х2 → max Ограничения

Содержание слайда: Пример. Решение I. Приведём все неравенства системы ограничений к виду ≤, так как ЦФ → max. С этой целью обе части неравенств с (1) по (4) умножим на «‒ 1» и получим

Содержание слайда: Пример. Решение (продолжение) II. Составим расширенную матрицу коэффициентов прямой задачи

Содержание слайда: Пример. Решение (продолжение) III. Составим расширенную матрицу двойственной задачи транспонированную к прямой

Содержание слайда: Пример. Решение (продолжение) IV. Сформируем двойственную задачу Целевая функция FДВ = ̶ у1 + 24 у2 + 3у3 ̶ 5у4 → min Ограничения

Содержание слайда: