- •Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.
- •Графический метод.
- •Каноническая задача. Базисный план. Формула приращений
- •Формула приращений целевой функции
- •Критерий оптимальности.
- •Достаточное условие неограниченности. Алгоритм обратной м-цы.
- •Итерация. Симплекс-метод (алгоритм).
- •Конечность. Геометрическая интерпретация.
- •Двухфазный симплекс-метод.
- •Выводы и следствия двухфазного симплекс-метода.
- •Приведение задач к канонической форме. Табличная реализация симплекс-метода.
- •Двойственная задача. Взаимодвойственность.
- •Соотношения двойственности 1,2.
- •Соотношения двойственности 3,4.
- •Соотношения двойственности 5,6. Следствия соотношения 6
- •Теоремы Фаркаша.
- •Двойственный симплекс-метод. Определения. Формула приращений.
- •Критерий оптимальности. Условие пустоты.
- •Итерация. Задача о диете.
- •Транспортная задача. Условие общего баланса. Условия дефицита и перепроизводства.
- •Особенности. Транспортная задача. Лемма 1. Следствия.
- •Лемма 2. Базисный план перевозок.
- •Базисный план. Метод минимального элемента.
- •Метод потенциалов транспортной задачи.
Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.
Задача следующая: имеется несколько вариантов поведения и надо из них выбрать в некотором смысле самый лучший, он называется оптимальным и является решением задачи.
Функция , заданная на множестве , называется целевой функцией, и задача оптимизации в самой общей форме имеет вид:
(1) Формула (1) означает, что среди всех планов требуется найти такой, который доставляет функции минимальное (либо максимальное) значение. Такой план обозначают и называют оптимальным планом, а число – оптимальным значением целевой функции задачи (1).
Определение 1. План называется оптимальным, если выполняется условие:
(2)
Предмет курса: теоретическое исследование (изучение) и практическое решение (разработка методов и алгоритмов) разнообразных экстремальных задач вида (1), то есть составление и реализация математической программы (программирование) нахождения оптимального плана или теория и практика решения экстремальных задач.
Определение 2. План называется - оптимальным, если для некоторого положительного (обычно малого) выполняется неравенство:
.
Оптимальный план обеспечивает малое отклонение по целевой функции от наилучшего (минимального) значения.
Определение. План называется локально-оптимальным, если существует , что выполняется неравенство:
,
где - это -окрестность плана в , , то есть план наилучший по крайней мере в своей окрестности радиуса .
ОБЩАЯ СХЕМА РЕШЕНИЕ ЗАДАЧ
Пусть существует некоторый объект поведения, который необходимо оптимизировать.
Этапы достижения цели исследования следующие:
Изучение и описательная постановка.
Он включает:
а) изучение структуры объекта, его составных частей;
б) установление связей и закономерностей его функционирования;
в) выяснение смысла качества, улучшение поведения объекта ;
г) сбор числовых данных, описывающих состояние связи и закономерности, качество поведения объекта;
Математическая формализация задачи.
Она включает:
а) введение неизвестных управляемых параметров для изменения поведения объекта - , которые однозначно описывают состояние объекта, и изменяя который можно добиваться целей;
б) запись в виде математических соотношений основных связей и закономерности. Обычно они имеют вид неравенств и равенств, связывающих переменные , и используют собранную в 1. информацию. Система этих соотношений и определяет (задаёт) множество;
в) запись целевой функции и операции оптимизации.
В результате второго этапа мы получаем задачу оптимизации (1).
Исследование задачи и построение метода.
Оно включает:
а) выяснение, к какому типу задач оптимизации относится наша, имеет ли разработанная теория и методы решения;
б) если теория разработана и имеются методы, то изучаем теории и выбор наиболее подходящего метода;
в) если теории и методов (подходящих) нет, то исследование задачи (дополнительное) и на этой основе разработка методов.
Численное решение.
Оно включает:
а) составление на основе метода алгоритма;
б) написание и отладка по алгоритму программы на ЭВМ;
в) получение оптимального плана и оптимального значения целевой функции.
5. Анализ решения и уточнение модели и процесса оптимизации, (сравниваем полученное решение с реальным поведением объекта; если есть возможность, то проводим эксперименты; если удовлетворяет, то процесс оптимизации заканчивается, если нет, то уточняем этот процесс на этапах 1-4. при оптимизации возможны ошибки сбора информации, моделирования, исследования, вычисления).
ПРОИЗВОДСТВЕННАЯ ЗАДАЧА Имеется некоторое предприятие, выпускающее продукцию из некоторых ресурсов. Требуется разработать производственный план, который обеспечивает ему наибольшую прибыль. Для этого:
1. Выясняем количество видов изделий, которое может выпускать предприятие; выясняем количество видов ресурсов (материалы, сырье), а также числа - объём того ресурса на период планирования . Определим числа - расход того ресурса на производство единицы той продукции: , . Выясняем числа - прибыль, которую получит предприятие от реализации единицы той продукции, .
2. Вводим неизвестные: пусть - количество той продукции, которую должно выпускать предприятие по плану . Формализация задачи. Целевая функция - суммарная прибыль предприятия имеет вид:
z = z(x) = c x + c x + … +c x max (3)
Предприятие не может использовать ресурсов больше имеющихся запасов. Отсюда ограничения по каждому расходу ресурсов:
(4)
Количество выпускаемой продукции не может быть отрицательным ( ую продукцию либо выпускают в количестве , либо нет ). Поэтому нужно на неизвестные наложить физические ограничения: (5)
Замечание. Среди ограничений (4) могут быть и равенства, если некоторый ресурс нужно использовать полностью (нельзя оставлять на хранение).
Определение. Ограничения типа (4) называются основными, а ограничения (5) прямыми.
(3), (4), (5)- математическая модель производственной задачи.
Математическая модель производственной задачи (3),(4),(5) относится к задачам линейного программирования, так как и в целевой функции (3) и в ограничениях (4),(5) неизвестные входят линейно. Линейное программирование хорошо изученный раздел оптимизации, разработанный метод их решения – симплекс - метод.
В библиотеке программ ЭВМ может содержаться программа, реализующая алгоритм симплекс – метода. Вводя в неё параметры задачи , то на выходе программы получаем - оптимальный план. Максимальная прибыль .
Модель (3),(4),(5) и полученный оптимальный план задачи могут нас и не удовлетворять, так как не учтены некоторые стороны производственного процесса (например, наличие брака продукции, изменение цен на рынке, изменение технологии и так далее). В этом случае следует построить более точную модель и получить задачу нелинейного программирования.
Производственную задачу удобно записывать используя векторно – матричные обозначения и операции.
Пусть = R , = R , , где
неизвестный вектор, вектор объёмов ресурсов, вектор прибыли.
A = -матрица расхода ресурса на единицу продукта.
Все векторы будут считаться столбцами, а для получения вектора строк будем использовать оператор транспонирования, тогда задачи (3) ,(4), (5) можно записать компактно:
= (6)