Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Математическая модель оптимизационной задачи

Понятие оптимизационной математической модели

Дата добавления: 2014-11-28 ; просмотров: 3944 ; Нарушение авторских прав

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

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

Критерием оптимальности называется математическое выражение, позволяющее количественно оценить степень достижения поставленной цели при выборе того или иного решения

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

Во многих ситуациях принятия решений объективно присутствует несколько целей.

Задачи принятия решений, удовлетворяющих нескольким целям, называются многокритериальными задачами. Например, при выборе проектных решений по новому пассажирскому самолету требуется обеспечить максимальное число пассажиров (цель 1) при минимальном расходе топлива (цель 2).

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

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

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

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

Решением математической модели называется такой набор (совокупность) значений переменных, который удовлетворяет ее уравнениям связи.

Процесс построения оптимизационных математических моделей можно условно разбить на следующие основные этапы:

1) определение границ объекта оптимизации; 2) выбор управляемых переменных; 3) определение ограничений на управляемые переменные; 4) выбор критерия оптимизации; 5) формулировка математической задачи.

Рассмотрим пример на построение и решение оптимизационной задачи принятия решения.

Пример. Пусть требуется выбрать геометрические размеры цилиндрического бака объемом V из условия минимального расхода материала на его изготовление.

Для построения математической модели введем в рассмотрение вектор проектных решений Х = (r, h), где r, h –радиус и высота бака (Рис. 20).

Если предположить, что бак изготавливается сваркой из трех деталей, то расход материала при произвольном векторе решений Х будет равен площади поверхности бака:

(1)

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

Условие того, что бак должен иметь объем заданного значения V, представим в виде: V=pr 2 h. (2)

На компоненты вектора решений X необходимо наложить дополнительные условия: R > 0, h > 0. (3)

Выражения (1) – (3) описывают нелинейную однокритериальную модель формирования оптимальных решений, при n = 2, m = 1.

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

, (4)

где с – затраты времени на сварку единицы длины.

Выражения (1) – (4) описывают двухкритериальную нелинейную модель формирования оптимальных решений.

При построении математической модели в этой задаче были использованы известные геометрические закономерности.

Обобщенная оптимизационная модель запишется следующим образом:

где y – выходная характеристика (критерий оптимизации), которую требуется привести к экстремальному значению – максимуму или минимуму в зависимости от ее смысла; f(X) – целевая функция, т.е. функция, описывающая зависимость критерия оптимизации от значений параметров Х; – набор из n переменных процесса, которыми можно управлять при нахождении оптимального решения, эти параметры процесса называют в теории оптимизации переменными процесса, а Х – вектором состояния процесса ( – координаты вектора);

функции-ограничения параметров процесса; некоторые постоянные величины, выражающие количественные значения ограничений.

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

Решение оптимизационных задач управления методом линейного программирования

Ранее я описал, как принимать решения с учетом ограничивающих факторов. Цель таких решений – определить ассортимент продукции (производственный план), максимально увеличивающий прибыль компании. Решение заключалось в том, чтобы распределить ресурсы между продуктами согласно маржинальной прибыли, полученной на единицу ограниченных ресурсов, при соблюдении любых других ограничений, таких как максимальный или минимальный спрос на отдельные виды продукции. [1]

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

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

Скачать заметку в формате Word, рисунки в формате Excel

Линейное программирование предусматривает построение математической модели рассматриваемой задачи. После чего решение может быть найдено графически (рассмотрено ниже), с использованием Excel (будет рассмотрено отдельно) или специализированных компьютерных программ. [2]

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

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

Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (рис. 1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Рис. 1. Использование и предоставление ресурсов

Николай хочет построить модель с тем, чтобы определить количество единиц продуктов А и В, которые он доложен производить в следующем месяце для максимизации маржинальной прибыли.

Линейная модель может быть построена в четыре этапа.

Этап 1. Определение переменных

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z = суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных (обозначим их х1, х2, х3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

х1 = количество единиц продукта А, произведенных в следующем месяце.

х2 = количество единиц продукта В, произведенных в следующем месяце.

Очень важно четко определить все переменные величины; особое внимание уделите единицам измерения и периоду времени, к которому относятся переменные.

Читать еще:  Методы оптимизации проектных решений

Этап. 2. Построение целевой функции

Целевая функция – это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х1, х2… в виде линейного уравнения.

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х1 единиц продукта А, маржинальная прибыль составит 2500 * х1. Аналогично маржинальная прибыль от изготовления х2 единиц продукта В составит 3500 * х2. Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х1 единиц продукта А и х2 единиц продукта В, то есть, целевая переменная Z составит:

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Максимизировать Z = 2500 * х1 + 3500 *х2

Этап. 3. Определение ограничений

Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х1 их2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х1, единиц, то будет потрачено З * х1, часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х2 продуктов, то потребуется 10 * х2 часов. Таким образом, общий объем машинного времени, необходимого для производства х1 единиц продукта А и х2 единиц продукта В, составляет 3 * х1 + 10 * х2. Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х1 ≥ 0 и х2 ≥ 0. В нашем примере второе условия является избыточным, так как выше было определено, что х2 не может быть меньше 12.

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

Максимизировать: Z = 2500 * х1 + 3500 *х2

При условии, что: 3 * х1 + 10 * х2 ≤ 330

Рассмотрим графический метод решения задачи линейного программирования.

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

Оси на графике представляют собой две искомые переменные (рис. 2). Не имеет значения, какую переменную отложить вдоль, какой оси. Важно выбрать масштаб, который в конечном итоге позволит построить наглядную диаграмму. Поскольку обе переменные должны быть неотрицательными, рисуется только I-й квадрант.

Рис. 2. Оси графика линейного программирования

Рассмотрим, например, первое ограничение: 3 * х1 + 10 * х2 ≤ 330. Это неравенство описывает область, лежащую ниже прямой: 3 * х1 + 10 * х2 = 330. Эта прямая пересекает ось х1 при значении х2 = 0, то есть уравнение выглядит так: 3 * х1 + 10 * 0 = 330, а его решение: х1 = 330 / 3 = 110

Аналогично вычисляем точки пересечения с осями х1 и х2 для всех условий-ограничений:

Оптимизационные модели

Автор: Андрей Нестеров ✔ 25.12.2016

Нестеров А.К. Оптимизационные модели // Энциклопедия Нестеровых

Рассмотрим задачи, элементы оптимизационных моделей и этапы их построения.

Понятие оптимизационных моделей

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

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

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

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

Задачи построения оптимизационных моделей

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

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

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

В оптимизационных моделях объектом моделирования может выступать:

  • склад предприятия,
  • выпуск новой продукции,
  • транспортировка готовой продукции и т.п.

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

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

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

Таким образом, следует сделать вывод:

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

Элементы оптимизационной модели

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

Элементы оптимизационной модели

Описание элементов оптимизационной модели приведено в таблице.

НОУ «Математическое моделирование при решении многокритериальных задач на оптимизацию.»

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

АДМИНИСТРАЦИИ ГОРОДА НИЖНЕГО НОВГОРОДА

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

Научное общество учащихся

Математическое моделирование при решении многокритериальных задач на оптимизацию.

Выполнил: Огарков Александр

ученик 9 «а» класса

Руководитель: Китаева М.В.

ГЛАВА I Теоретическая часть

1.1 Математическая модель объекта проектирования…………………. 5

Характеристика типовых задач математического

моделирования и подходов к их решению…………………………. 8

1.3 Компоненты принятия решений………………….…………………. 11

1.4 Теория решения многокритериальной задачи с помощью

Читать еще:  Оптимизация приложений android что это

метода оптимального выбора…………………….…..………. …. 13

Теория метода многокритериальной оптимизации по Парето…. 14

ГЛАВА II Практическая часть

Решение задач на МКО по методу оптимального выбора

Говорят, самое сложное –

это сделать правильный выбор .

На протяжении всей истории человечества люди при необходимости принимать решения прибегали к сложным ритуалам. Они устраивали торжественные церемонии, приносили в жертву животных, гадали по звёздам и следили за полётом птиц. Они полагались на народные приметы и старались следовать примитивным правилам, облегчающим им трудную задачу принятия решений.

Таким образом, необходимость принятия решений так же стара, как и само человечество. Несомненно, уже в доисторические времена первобытные люди, отправляясь, скажем, охотится на мамонта, должны были принимать те или иные решения: в каком месте устроить засаду? Как расставить охотников? Чем их вооружить?

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

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

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

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

— дать определение понятию «многокритериальная оптимизация» с точки зрения математического моделирования;

— рассмотреть два метода решения задач многокритериальной оптимизации (метод оптимизационного выбора и метод Парето).

— решить практические задачи, используя данные методы.

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

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

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

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

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

1.1 Математическая модель объекта проектирования.

1 . Определение основных понятий математического моделирования и характеристика этапов создания математической модели.

Под моделированием понимают процесс построения, изучения и применения моделей.

Модель – это материальный тип или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение даёт новые знания об объекте оригинале.

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

В математических методах широко применяются как аналитические, так и статистические модели.

Аналитические модели более грубы, учитывать меньшее число факторов, всегда требует каких-то допущений и упрощений.

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

Операции – всякое мероприятие, система действий, объединенных единым замыслом и направлением к достижению какой-либо цели. Операция является управляемым мероприятием, то есть от нас зависти, каким способом выбрать некоторые параметры, характеризующие ее организацию.

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

Решение — это всякий определенный набор зависящих от нас параметров.

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

Допустимые решения это решения, удовлетворяющие системе ограничений и требованию неотрицательности.

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

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

Целевая функция — функция переменных, от которых зависит достижение оптимального состояния системы.

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

Процесс математического моделирования можно подразделить на четыре этапа.

Первый этап – формулировка законов, связывающих основные объекты модели. Этот этап требует широкого знания фактов, относящихся к изучаемым явлениям, и глубокого проникновения в их взаимосвязи.

Второй этап – исследование математических задач, к которым приводят построенные математические модели.

Третий этап – выяснение того, удовлетворяет ли принятая гипотетическая модель критерию практики.

Четвертый этап – последующий анализ модели в связи с накоплением данных об изучаемых явлениях и модернизации модели.

2 . Основные этапы математического моделирования.

1) Построение модели. На этом этапе задается некоторый «нематематический» объект — явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.

2) Решение математической задачи, к которой приводит модель. На этом этапе большое внимание уделяется разработке алгоритмов и численных методов решения задачи , при помощи которых результат может быть найден с необходимой точностью.

3) Интерпретация полученных следствий из математической модели. Следствия, выведенные из модели на языке математики, интерпретируются на языке, принятом в данной области.

4) Проверка адекватности модели. На этом этапе выясняется, согласуются ли результаты эксперимента с теоретическими следствиями из модели в пределах определенной точности.

5) Модификация модели. На этом этапе происходит либо усложнение модели, чтобы она была более адекватной действительности, либо ее упрощение ради достижения практически приемлемого решения.

3 . Классификация моделей

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

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

1. 2 Характеристика типовых задач математического моделирования и подходов к их решению.

Задачи моделирования делятся на две категории: прямые и обратные .

Прямые задачи отвечают на вопрос, что будет, если при заданных условиях мы выберем какое-то решение из множества допустимых решений. В частности, чему будет равен, при выбранном решении критерий эффективности.

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

Читать еще:  Решение задач оптимизации в mathcad

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

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

Их можно разделить на:

принятие решений в условиях определенности — исходные данные — детерминированные ; принятие решений в условиях неопределенности — исходные данные — случайные величины .

Типовые задачи оптимизации и их экономико-математические модели

Постановка задач оптимизации

В общем виде задача оптимизации, или задача определения экстремума, ставится следующим образом.

функция f(X), определенная на множестве RN ;

Найти точку Y = (y1, y2. yN) D, в которой функция f (X) достигает экстремального (минимального или максимального) значения, т.е. f(X) = extr f(X) и Y D.

Функция f(X) называется целевой функцией, переменные X — управляемыми переменными, D — допустимым множеством и любой набор значений Y управляемых переменных, принадлежащий D (Y D), — допустимым решением задачи оптимизации [3].

Понятно, что искомая точка Y, в которой f(X) достигает своего экстремума, должна принадлежать пересечению области определения O функции f(X) и допустимого множества D (Y O D). Если множества O и D совпадают со всем пространством RN (O = D = RN), то такая задача называется задачей на безусловный экстремум. Если хотя бы одно из множеств O или D является собственным подмножеством пространства RN (O RN , D RN) или множества O и D пересекаются (O D ), то такая задача называется задачей на условный экстремум, в противном случае (O D = ) точка экстремума Y не существует. Подчеркнем один частный случай: если множества O и D пересекаются в одной точке Y, то эта точка Y является единственным допустимым решением.

Методы линейного программирования.

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

В самом общем виде задача математически записывается так:

Где X = (Х1, Х2,…, Хn);

W — область допустимых значений переменных Х1, Х2,…, Хn;

f(X) — целевая функция [3].

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать X() W такое, что f(X()) f(X), при любом X W, или для случая минимизации — что f(X()) ? f(X), при любом X W.

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

Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

  • · задачи линейного программирования, если f(X) и W линейны;
  • · задачи целочисленного программирования, если ставится условие целочисленности переменных Х1, Х2,…, Хn;
  • · задачи нелинейного программирования, если форма f(X) носит нелинейный характер.

Задачи линейного программирования.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

f(X) = СjXj max(min);

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

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот [4].

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

  • 1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
  • 2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
  • 3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
  • 4) если некоторая переменная Хk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными::

Постановка задачи линейного программирования

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), но n потребителям этих ресурсов [3].

На автомобильном транспорте часто встречаются следующие задачи, относящиеся к транспортным:

  • · прикрепление потребителей ресурса к производителям;
  • · привязка пунктов отправления к пунктам назначения;
  • · взаимная привязка грузопотоков прямого и обратного направлений;
  • · задачи оптимальной загрузки промышленного оборудования;
  • · оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями.

Транспортным задачам присущи следующие особенности:

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

Транспортные задачи могут решаться симплекс-методом.

Симплекс-метод решения задач линейного программирования.

Симплекс-метод позволяет отказаться от метода перебора при решении задач линейной оптимизации, является основным численным методом решения задач линейного программирования и позволяет за меньшее число шагов, чем в методе перебора, получить решение [3].

Реализация алгоритма симплекс-метода.

  • 1. Записать задачу в канонической форме: заменить все ограничения-неравенства с положительной правой;
  • 2. Разделить переменные на базисные и свободные: перенести свободные переменные в правую часть ограничений-неравенств.
  • 3. Выразить базисные переменные через свободные: решить систему линейных уравнений (ограничений-неравенств) — относительно базисных переменных;
  • 4. Проверить неотрицательность базисных переменных: убедиться в неотрицательности свободных членов в выражениях для базисных переменных. Если это не так, вернуться к пункту 2, выбирая другой вариант разделения переменных на базисные и свободные.
  • 5. Выразить функцию цели через свободные переменные: базисные переменные, входящие в функцию, выразить через свободные переменные;
  • 6. Вычислить полученное базисное решение и функцию цели на нем: приравнять к 0 свободные переменные;
  • 7. проанализировать формулу функции цели: если все коэффициенты свободных переменных положительны (отрицательны), то найденное базисное решение будет минимально (максимально) и задача считается решенной;
  • 8. Определить включаемую в базис и исключаемую из базиса переменные: если не все коэффициенты при свободных переменных в функции цели положительны (отрицательны), то следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных не станет равной 0. Свободную переменную рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную рассматриваем как новую базисную переменную (исключаемую из базиса);
  • 9. Используя новое разделение переменных на базисное и свободное, вернуться к пункту 3 и повторять все этапы до тех пор, пока не будет найдено оптимальное решение [4].

В заключение отметим, что определение оптимального решения распадается на два этапа:

  • · нахождение какого-либо допустимого решения с положительным свободным членом;
  • · определение оптимального решения, дающего экстрему целевой функции.

Решить графическим методом типовую задачу оптимизации. Осуществить проверку правильности решения с помощью средств MS Excel (надстройки Поиск решения).

Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:

Ссылка на основную публикацию
Adblock
detector