Формулировка задачи математического программирования
Задачи математического программирования, как правило, содержат большое число переменных и ограничений и не всегда допускают умозрительный анализ. Здесь требуется тщательная формализация и включение в математическую модель всех сколько-нибудь существенных ограничений.
Прежде чем построить математическую модель задачи, необходимо четко разобраться с ситуацией, описанной в условии. Для этого необходимо с точки зрения заданной задачи, а не математики, ответить на следующие вопросы:
1) Что является искомыми величинами задачи?
2) Какова цель решения? Какой параметр задачи служит критерием эффективности (оптимальности) решения, например, прибыль, себестоимость, время и т.д. В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов?
3) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д.
После предварительной постановки задачи получают ее формальное решение для простейших случаев, на которых можно проанализировать корректность поставленной задачи. На основании такого анализа вводятся дополнительные параметры и ограничения, проверяется корректность отнесения задачи к тому или иному классу, корректность введения линейности.
Общая схема формализации на основании содержательного описания задачи:
1.Определение переменных задачи (основных параметров).
2. Определение управляющих переменных, характеризующих существо действий и их элементарных составляющих.
3. Формулировка критериев эффективности через параметры и управляющие переменные.
4. Определение ограничений (области допустимых решений) через переменные задачи.
Задача математического программирования содержит n переменных xi (i=1, 2,. . . , n), образующих n-мерный вектор переменных х.
На переменные накладываются ограничения — в форме равенств hi(x) = 0, i = 1, . . . , p или неравенств gi(x) ≥ 0, i = 1, . . . , q.
f(x) – целевая функция (в общем случае нелинейная) всех или некоторых переменных xi (i=1, 2,. . . , n).
Задача математического программирования формулируется следующим образом:
Минимизировать (или максимизировать) f(x) при условиях gi(x) ≥ 0, i = 1, . . . , q; hi(x) = 0, i = 1, . . . , p. Или кратко Min f(x)│ gi(x) ≥ 0, i = 1, . . . , q; hi(x) = 0, i = 1, . . . , p>.
6.2 Модели линейного программирования
Линейное программирование применяется при решении задач оптимального распределения ресурсов, управления и планирования производства; определения оптимального размещения оборудования; оптимального плана перевозок груза (транспортная задача) и т.д.
По оценкам американских экспертов около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.
Задачи линейного программирования относятся к категории оптимизационных. Они находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования.
Несмотря на различные области приложения, данные задачи имеют единую постановку: найти значения переменных x1, …, xn, доставляющие оптимум заданной линейной формы z=c1x1 + c2x2+… + cnxn при выполнении системы ограничений, представляющих собой также линейные формы.
В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны.
Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования.
Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.
При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели свойств пропорциональности, аддитивности.
Основные допущения при построении линейных моделей:
-. неотрицательность (не может быть отрицательного объема производства).
Пропорциональность — затраты ресурсов пропорциональны объему производства — вклад каждой переменной в целевой функционал и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной.
Например, если, продавая j-й товар в общем случае по фиксированной цене, фирма будет делать скидку при определенном уровне закупки до более низкого уровня цены, то будет отсутствовать прямая пропорциональность между доходом фирмы и количеством проданного товара. Т.е. в разных ситуациях одна единица j-го товара будет приносить разный доход.
Аддитивность означает, что целевой функционал и ограничения должны представлять собой сумму вкладов от различных переменных. Величина, соответствующая целому объему всегда равна сумме величин, соответствующих его частям при любом способе разбиения на части.
Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.
Решение практической задачи нельзя считать законченным, если найдено оптимальное решение. Некоторые параметры задачи (финансы, запасы сырья, производственные мощности и др.) можно регулировать, что, в свою очередь, может изменить найденное оптимальное решение. Эта информация получается в результате выполнения анализа чувствительности. Анализ чувствительности позволяет оценить влияние этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение можно улучшить за счет небольших изменений заданных параметров, то целесообразно реализовать эти изменения.
Лекция 1 Математическое программирование
Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.
Арифметические операции выполняет компьютер, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).
Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи – это отражение оригиналов в виде функций, уравнений, неравенств и др. математических объектов. Модель задачи математического программирования включает в себя:
- совокупность неизвестных величин х=(х1,х2. хn), их называют планом задачи.
- Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
- Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.
Ограниченными является не только материальные, финансовые и трудовые ресурсы, таковыми могут быть возможности технологического, технического и в целом научного потенциала, нередко потребности превышают возможности их удовлетворения. Совокупность ограничений, записанных в виде уравнений и неравенств, образует область допустимых решений (область экономических возможностей).
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
х i => 0 , Z(x*) = Z*(оптимальный план)
Классификация методов математического программирования.
В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:
1. Если целевая функция и функции системы ограничений, если они линейные относительно входящих неизвестных xi ,то такой раздел называется линейным. Методы и модели линейного программирования широко используются при оптимизации процессов во всех областях народного хозяйства. При разработке производственной программы предприятия, при определении наилучшего ассортимента выпускаемой продукции, задачах перспективного, текущего и оперативного планирования. Особенно широкое применение методов и моделей линейного программирования получили при решении экономии ресурсов производственно-транспортных и др. задач. Начало линейного программирования положил Канторович.
2. Если в задаче математического программирования целевая функция или одна из функций системы ограничений не линейна, то такой раздел называется нелинейным. Методы нелинейного программирования используются при расчете экономически-выгодных партий запуска деталей в производство при распределении ограниченных ресурсов, размеров запасов, размещения производительных сил.
3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.
Z( x )=∑ Zj (xj ) – аддитивный вид
Z( x )= П Z j(x j ) – мультипликативный
При таком представлении целевой функции процесс выработки решений имеет многошаговый характер, параметры целевой функции или системы ограничения изменяются во времени, также задачи решаются методами динамического программирования. Методами динамического программирования могут решаться задачи планирования, управления производства, поставками и запасами, в условиях изменения спроса, распределение ограниченных ресурсов, в частности, размещение капитальных вложений, замена оборудования. В перечисленных моделях математического программирования предполагается, что вся информация о протекаемых процессах заранее известна и достоверна. Также методы называются детерминированными. Или методы обоснования решений в условиях определенности.
Если параметры, входящие в функцию цели или ограничения задачи являются случайными, недостоверными или если приходится принимать решения в условиях риска неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а раздел называют стохастическим программированием. К нему относятся модели и методы выработки решений в условиях конфликтных ситуаций. В условиях неполной информации (экстремальной оценки), либо в условиях риска.
Позднее появились другие типы задач, учитывая специфику целевой функции и систему ограничений, в связи с чем возникли параметрическая.
К математическому программированию относятся методы экстремальных задач с бесконечным числом переменных.
Задачи математического программирования с одной целевой функцией решается методами скалярной оптимизации, однако в реальных задачах зачастую приходится учитывать несколько целевых функций. Также задачи относятся к векторной оптимизации. Задачи многокритериального подхода.