Симплексный Метод Решения ЗЛП
Введение в исследование операций
Литература:
1) Ловянников Д.Г. Исследование операций
2) Минько Э.В. Методы прогнозирования и исследования операций
3) Классика – Вагнер Г. Основы исследования операций.
1885 – Фредерик Тейлор – оптимизация работы землекопов
1916 – Фредерик Ланчестер – «квадратичный закон», количественно связывающий достижение победы с двумя основными факторами: численным превосходством живой силы и эффективностью оружия.
1917 – датский математик А.К. Эрланг – задача минимизации потерь времени на установление телефонной связи (формулы Эрланга).
1939 – Леонид Канторович – оптимизация распила фанерного листа. Один из создателей математического программирования.
1939-1945 – планирование боевых действий.
1949 – Джордж Данциг – эффективный метод решения задач линейного программирования (ЗЛП) – симплекс-метод.
Задача принятия решения характеризуется наличием:
1) Цели (целей);
2) Альтернатив действий (различных способов достижения цели);
3) Ограничений (ограничивающих факторов, например, материальных, финансовых, социальных)
Формула (1)
Цель *в широком смысле* - идеальное представление желаемого состояния или результата деятельности.
Решение – конкретный результат ЗПР (например, производственный план, инвестиционная или инновационная стратегия и т.п.).
ЗПР направлена на отыскание наилучшего (оптимального) способа действий для достижения цели.
|
|
|
Операция – управляемое мероприятие, система действий, объединенных единым замыслом и направленное на достижение конкретной цели.
Операции присущи целевая направленность и повторяемость
Примеры операций:
-формирование портфеля заказов фирмы;
-разработка производственного плана.
Исследование операций (operation research) – научный метод выработки количественно обоснованных рекомендаций по принятию решений.
Основной метод ИО – математическое моделирование операций.
Модель (modellus) – этой материальный или знаковый образ исследуемого объекта или явления, более или менее точно отражающий его существенные свойства.
Математическая модель – знаковая модель на языке математических соотношений.
Моделирование – исследование объекта с помощью его модели.
Исход операции оценивается с помощью некоторых критериев качества (критериев эффективности или критериев оптимальности)
Критерий оптимальности – мат. Выражение, позволяющее количественно определить степень достижения цели операции.
Выделение системы из окружающей среды
Система – множество взаимосвязанных элементов, обособленное от среды и взаимодействующее с ней, как целое
|
|
|
Модель системы – формула (2)
Построение модели операции – формула (3)
Классификация операций
1) По числу целей
1.1 Одноцелевые или однокритериальные (4) – задача математического программирования
Если ЦФ линейна, т.е. (4.1), а ОДЗ – выпуклый многогранник R^n то это задача линейного программирования
1.2 Многоцелевые или многокритериальные (4.2)
2) Наличие / отсутствие зависимости критерия оптимальности и / или ограничений от времени
2.1 Статические (нет зависимости от времени)
2.2 Динамические (зависят от времени) (4.3)
3) Наличие случайных и неопределенных факторов, влияющих на исход операции. Этот признак назван «определенность-риск-неопределенность».
3.1 Детерминированные
3.2 Стохастические ЗПР (оперирование в условиях риска, причем вероятности известны).
3.3 ЗПР в условиях неопределенности (вызванной недостатком информации о системе)
Лекция 2
Задача линейного программирования (ЗЛП)
Математическое программирование – совокупность методов решения задач оптимизации вида (1)
Где А – вектор параметров задачи;
F – некоторый критерий качества (возможно, векторный).
Линейное программирование – это подраздел МП, связанный с отысканием экстремальных значений линейных функций, на неизвестные которых наложены линейные ограничения.
|
|
|
Стандартная задача линейного программирования (СЗЛП) (2)
Каноническая задача линейного программирования (КЗЛП) (3)
Основные вычислительные методы разработаны именно для КЗЛП.
Общая ЗЛП (ОЗЛП) (4)
Приведение ЗЛП от одной эквивалентной формы к другой
1. Переход «минимизация-максимизация» (5.1);
2. Переход от ограничений-неравенств к ограничениям-уравнениям (5.2).
3. Переход от переменных произвольного знака к неотрицательным переменным (5.3).
4. Переход от переменных, ограниченных снизу (сверху) к неотрицательным переменным (5.4)
5. Переход от уравнения к неравенствам (5.5)
Решение ЗЛП
Задача линейного программирования называется разрешимой, если она имеет хотя бы одно оптимальное решение и неразрешимой в противном случае.
Алгоритм графического решения ЗЛП
1. Построить ОДЗ на плоскости x0y
2. Построить градиент целевой функции F= c1x1+c2x2 (вектор нормали к прямой c1x1+c2x2=F)
3. Построить опорную прямую, перпендикулярную вектору нормали – линию уровня целевой функции.
4. Перемещая опорную прямую в направлении вектора нормали, определить «точку входа» и «точку выхода». В точке входа: F>min. В точке выхода: F>max
|
|
|
5. Определить координаты оптимальной точки (точки входа или точки выхода) и найти значение целевой функции в ней
Лекция 3
Симплексный Метод Решения ЗЛП
Основная идея метода
Для n переменных, областью допустимых ЗЛП является многомерный выпуклый многогранник – симплекс.
Оптимальное решение – как правило, вершина такого многогранника.
Симплекс метод заключается в последовательном целенаправленном обходе вершин симплекса.
Подготовительная процедура СМ
Для применения СМ задачу следует записать в каноническом виде
Алгоритм СМ (с естественным базисом)
Шаг 1: Получение начального решения (опорного плана).
Выбирают m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом +1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы.
Шаг 2: Выражение функции f только через свободные переменные.
Шаг 3: проверка решения на оптимальность.
Шаг 4: получение нового решения.
4.1 Выбор переменной, вводимой в базис.
4.2 Выбор переменной, выводимой из базиса.
4.3 Выполнение симплекс преобразования.
Переход на шаг 3.
Пример
Лекция 4
Метод искусственного базиса
Суть МИБ заключается в том, что в ограничения задачи искусственно вводят несколько новых переменных с таким расчетом, чтобы полученная новая система уже имела полный единичный базис, которому соответствует опорное решение новой системы ограничений.
Пусть требуется найти максимум ЦФ (1) при ограничениях (1)
Составим к исходной задаче расширенную задачу (М-задачу) (2)
Пример СМ с искусственным базисом (3)
Дата добавления: 2021-02-10; просмотров: 57; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!