🗊Презентация Общие теоретические вопросы. Оптимизация – общая постановка задачи. Целевая функция, система ограничений

Общие теоретические вопросы Оптимизация – общая постановка задачи. Целевая функция, система ограничений

Понятие оптимизации Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например: - количество продукции - расход сырья" -количество продукции - качество продукции"

Выбор компромиссного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи. При постановке задачи оптимизации необходимо: Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта. Объект должен обладать определенными степенями свободы - управляющими воздействиями. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий. Учет ограничений.

Модель задачи математического программирования включает: совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.); целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант - из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.

Стандартная математическая задача оптимизации формулируется таким образом: Среди элементов x, образующих множество Χ, найти такой элемент х*, который доставляет минимальное значение f(х*) заданной функции f(х). Для того чтобы корректно поставить задачу оптимизации необходимо задать: Допустимое множество — множество ; Целевую функцию — отображение ; Критерий поиска (max или min).

Общие теоретические вопросы Задача линейного программирования. Постановка задачи

Линейное программирование Линейное программирование — раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные.

Постановка задачи Общей задачей линейного программирования называют задачу (1) при ограничениях (2) (3) (4) (5) – произвольные, (6) где - заданные действительные числа; (1) – целевая функция; (2) – (6) –ограничения;  - план задачи.

Общие теоретические вопросы Графическое решение задачи линейного программирования. Пример

Пусть дана задача (1) (2) (3)

Геометрическая интерпретация элементов задачи Каждое из ограничений (2), (3) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (1) — (3) есть выпуклое множество.

Геометрическая интерпретация целевой функции Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник .

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (1)  параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (1)  параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения). Найдём частные производные целевой функции по и : (4) (5) Частная производная (4) (так же как и (5)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно,  и — скорости возрастания соответственно вдоль осей и . Вектор  называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор перпендикулярен к прямым  семейства  .

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

Пример Решить геометрическим методом ЗЛП: (2) (3)

Построим множество планов задачи, для этого построим прямые на плоскости : и отметим направления полуплоскостей, которые обозначают неравенства. Строим линии уровня и вектор-градиент целевой функции. Целевая функция убывает против направления вектора – градиента, следовательно, минимум целевая функция достигает в точке пересечения прямых .

Найдем ее координаты: тогда искомый оптимальный план задачи =(5;1), .

Решение прикладных задач Задача 1

Дано словесное описание задачи. Привести ее табличное и математическое описание: целевая функция, система ограничений. Завод выпускает два вида строительных материалов: жидкое стекло и пенопласт. Трудозатраты на производство 1 т. стекла – 20 ч., пенопласта – 10ч. На заводе работает 10 рабочих по 40 часов в неделю. Оборудование позволяет производить не более 15 т. стекла и 30 т. пенопласта в неделю. Прибыль от реализации 1 т. стекла – 50 руб., 1 т. пенопласта – 40 руб. Сколько материалов каждого вида необходимо произвести для того, чтобы получить максимальную прибыль.

Табличное описание задачи

Математическое описание задачи Пусть – план выпуска завода строительных материалов в неделю, где т – количество жидкого стекла, т – количество пенопласта, тогда – целевая функция прибыли - неравенства ограничения .

Решение прикладных задач Задача 2

Дано словесное описание задачи. Привести ее табличное и математическое описание: целевая функция, система ограничений. Предприятие располагает ресурсами сырья и рабочей силы, необходимыми для производства двух видов продукции. Запас сырья составляет 120 т. , трудозатрат – 400 часов. На единицу первого продукта необходимо затратить 3 т. сырья, на единицу второго – 5 т. На единицу первого продукта тратится 14 ч.. второго – 12 ч. Прибыль от реализации единицы первого продукта равна 30тыс./т., второго продукта – 35 тыс./т. Чему равна максимальная прибыль.

Табличное описание задачи

Математическое описание задачи Пусть – план выпуска предприятием двух видов продукции, где т – количество I вида продукции, т – количество II вида продукции, тогда – целевая функция прибыли - неравенства ограничения .

Решение прикладных задач Задача 3

Дано словесное описание задачи. Привести ее табличное и математическое описание: целевая функция, система ограничений. На предприятии имеется три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков равно 100, 250, 180 ч. соответственно. Время выполнения каждой операции составляет 100, 120, 70, 110, 130 ч. соответственно. Производительность каждой группы станков задается матрицей А = . Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей.

Табличное описание задачи

Математическое описание задачи Обозначим через количество часов работы группы станков i-го вида, выделенное на j-ю операцию, математическая модель задачи имеет следующий вид: