Содержание модели математического программирования

Предметы и задачи курса.

Математическое программирование курс, связанный с математическим моделированием.

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

Все эти этапы реализуются с помощью:

1. ЛПР (лицо принимающее решение)
2. Прикладной математик
3. Просто математик
4. Специалист компьютерных технологий

Все они вместе образуют группу принятия решений или группа исследования операций (старое название) и так же старое название – группа мозговой атаки. Все это вылилось из науки исследования операций, появилась в 40-ых годах, когда был высажен десант.

В настоящее время сформировалась группа математическая поддержка принятия решений (математическое программирование или методы оптимизации принятия решений – основа этой науки).

Основные задачи и модели, используемые в математическом программировании.

1. Задача распределения ресурсов. Пусть предприятие может выпустить 4-ре продукта измеряемых в следующих величинах: грамм, килограмм, центнер и тонна. Продукты продаются на рынке по ценам соответственно: 4 деньги за грамм, 5 денег за килограмм и 9 денег за центнер и 11 денег за тонну. Продукты изготавливаются из трех видов ресурсов запасы, которых соответственно: 15 метров, 120 литров и 100 часов. Нормы расходов каждого ресурса, на каждый продукт определяет следующей табличкой

Определить такой план выпуска продукции, чтобы суммарный доход был максимальный.

Ресурсы – технологии – деньги.

Модель этой задачи.

Обозначим выпуск продукции X1, X2, X3, X4. Это вещественные числа, т.е. любе доли грамм, килограмм, центнера и тонн.

Maxd = 4*X1 + 5*X2 + 9*X3 + 11*X4

По первому ресурсу ограничения 1р ~ 1*X1 + 1*X2 + 1*X3 + 1*X4 ≤ 15

По второму ресурсу ограничения 2р ~ 3*X1 + 2*X2 + 4*X3 + 5*X4 ≤ 120

По третьему ресурсу ограничения 3р ~ 10*X1 + 12*X2 + 13*X3 + 14*X4 ≤ 100

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

Функция d соответствующий критерий принятия решения называется функцией цели. Ограничения по ресурсам называется ограничением задач, а ограничение на знак переменных (x≥0) называется ограничение на тип искомых величин – переменных. В нашем случае не отрицательная, вещественная.

Это классическая задача на выпуск продукции. Выпуск продукции – это программа предприятия, т.е. мы «программируем» предприятие с помощью математики. Значит, мы имеем задачу математического программирования (ЗМП). Придумал и сформулировал историю этой науки Конторович, он был гений, где-то в 37 году, он решил транспортную задачу и потом решил нашу задачу (см. выше) и много других подобный. Купнонс – другой ученый. Нобелевская премия в 72 году была получена ими двумя.

Замечания к задаче распределение ресурсов:

1. Могут быть ограничения на выпуск продукции, например, выпускать второго продукта не меньше 2 кг (X2≥2)
2. Ограничение на комплектность. Пусть, продукты следует выпускать в комплекте, каждая из которых содержит 2 грамма первого, 3 кг второго, 1 центнер третьего, 1 тонну четвертого. Тогда необходимо записать следующее ; ; .
3. X по своему типу может быть не только вещественным, но и целым числом. Например, вы считаете количество станков, количество деталей, людей и т.д., т.е. продукты неделимые. Тогда в ограничения необходимо написать Х – целое. Тип Х может быть и дискретный, т.е. вы берете не любое число, а из набора чисел. Например, X1 = .
4. Задача на максимум ОБЯЗАТЕЛЬНО содержит ограничения типа меньше или равно или равно, если таких ограничений нет, то ответ тривиальный – бесконечность.
5. Функция цели может быть и на минимум (например, минимум затрат на производство продукции), но тогда должны быть обязательно ограничения вида больше или равно, либо равно, чтобы не получить тривиальный ответ – 0. Т.е. если вы решаете на минимум затрат (наименьшие затраты), то обязательно должно быть условие на выпуск продукции (выпустить не меньше).
6. Именно противоречия между функцией цели и ограничениями дает нам наилучшую или оптимальную точку.

Эта задача для Х – произвольная, является линейной задачей или ЗЛП (задачей линейного программирования). При этом функция цели линейная для Х, а ограничения линейные, не строгие неравенства или равенства. Это классическая задача называется задачей распределения ресурсов, позволяет определить выпуск продукции так, чтобы получить максимальную выгоду.

Источник

Лекция 1 Математическое программирование

Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.

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

Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).

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

1. совокупность неизвестных величин х=(х₁,х₂. х_n), их называют планом задачи.
2. Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
3. Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.

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

Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.

Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.

х _i => 0 , Z(x*) = Z*(оптимальный план)

Классификация методов математического программирования.

В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:

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

2. Если в задаче математического программирования целевая функция или одна из функций системы ограничений не линейна, то такой раздел называется нелинейным. Методы нелинейного программирования используются при расчете экономически-выгодных партий запуска деталей в производство при распределении ограниченных ресурсов, размеров запасов, размещения производительных сил.

3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.

Z( x )=∑ Z_j (x_j ) – аддитивный вид

Z( x )= П Z _j(x _j ) – мультипликативный

При таком представлении целевой функции процесс выработки решений имеет многошаговый характер, параметры целевой функции или системы ограничения изменяются во времени, также задачи решаются методами динамического программирования. Методами динамического программирования могут решаться задачи планирования, управления производства, поставками и запасами, в условиях изменения спроса, распределение ограниченных ресурсов, в частности, размещение капитальных вложений, замена оборудования. В перечисленных моделях математического программирования предполагается, что вся информация о протекаемых процессах заранее известна и достоверна. Также методы называются детерминированными. Или методы обоснования решений в условиях определенности.

Если параметры, входящие в функцию цели или ограничения задачи являются случайными, недостоверными или если приходится принимать решения в условиях риска неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а раздел называют стохастическим программированием. К нему относятся модели и методы выработки решений в условиях конфликтных ситуаций. В условиях неполной информации (экстремальной оценки), либо в условиях риска.

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

К математическому программированию относятся методы экстремальных задач с бесконечным числом переменных.

Задачи математического программирования с одной целевой функцией решается методами скалярной оптимизации, однако в реальных задачах зачастую приходится учитывать несколько целевых функций. Также задачи относятся к векторной оптимизации. Задачи многокритериального подхода.

Источник