Общая модель математического программирования

Лекция 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 ) – мультипликативный

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

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

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

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

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

Источник

1 Общая задача математического

Модель общей задачи математического программирования состоит из целевой функции (1.1) и ряда ограничений (1.2-1.3):

(1.1)

(1.2)

, (1.3)

где – известные функции,

а – заданные коэффициенты.

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

Ограничения (1.2) называются технологическими; их правые части представляют собой фиксированные объемы имеющихся в распоряжении ресурсов.

Значения , удовлетворяющие ограничениям (1.2-1.3), называются допустимым планом.

Решение задачи математического программирования называется оптимальным планом. Это такой набор значений, при котором выполняются ограничения (1.2-1.3) и целевая функция (1.1) принимает максимальное значение.

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

.

Часто в задачах, возникающих на практике, система технологических ограничений (1.2), содержит, кроме неравенств со знаком «≤», равенства и неравенства «≥». Однако это не сказывается на общности постановки задачи (1.1-1.3), поскольку такие ограничения легко преобразуются в стандартный вид вычитанием из левых частей дополнительных неотрицательных переменных.

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

1.2 Математическая формулировка задач линейного

Если в задаче (1.1-1.3) функциилинейны, она относится к классу линейного программирования. Математическая модель линейного программирования имеет вид:

(1.4)

(1.5)

(1.6)

Коэффициенты и матрицазаданы.

Требуется определить оптимальные значения , т.е. такие, при которых целевая функция (1.4) максимальная и выполняются ограничения (1.5)-(1.6).

1.3 Примеры построения простейших моделей математического

Задача 1.1 На участке лесо-паркового массива города требуется выполнить четыре вида мероприятий. Для их проведения используются три вида материалов и денежные средства. Затраты ресурсов на 1 га проведения мероприятий и коэффициенты относительной полезности мероприятий приведены в таблице 1.1.

Таблица 1.1 – Удельные затраты ресурсов на проведение мероприятий

Источник