Построение экономико-математической модели

Классификация многокритериальных задач

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

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

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

Классификация задач исследования операций

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

2. Динамическая задача.В процессе принятия решения параметры задачи изменяются во времени. Процедура принятия решения осуществляется поэтапно и может быть представлена в виде процесса, зависящего от времени, в том числе непрерывно. Пример -навигационная задача.

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

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

2,а). Стохастическая задача.Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.).

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

- искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями),

- «оптимизация в среднем» (вводится и оптимизируется некоторый статистический критерий).

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

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

Функция называется скалярной, если ее значением является некоторое число.

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

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

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

4. Задачи стохастического программирования. Это задачи линейного программирования с неизвестными числовыми параметрами, о которых имеются статистические данные.

5. Задачи дискретного программирования. Множество допустимых решений – дискретное множество.

6. Задачи целочисленного программирования. Множество допустимых решений – точки целочисленной решетки.

7. Задачи булева программирования. Множество допустимых решений - 0-1 матрицы.

В задачах ИСО, как правило, присутствует не один, а несколько признаков предпочтения (критериев). Такие задачи называются многокритериальными.

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

В случае противоречивых критериев, ИСО предлагает следующие подходы к отысканию подходящего решения.

1) Замена некоторых критериев ограничениями вида < или >. Например, минимизация стоимости f(x) → min, может быть заменена ограничением вида f(x) < A, где A -некоторая верхняя оценка стоимости, т.е. максимально допустимая стоимость.

2) Свертка критериев. Создается один глобальный скалярный критерий, целевая функция которого является некоторой функцией от исходных целевых функций. Наиболее употребимыми являются линейные свертки вида αf(x) + βg(x) (в случае двух критериев). Нетривиальной является задача отыскания адекватных значений коэффициентов α и β, отражающих относительную важность целевых функций f(x) и g( x).

3) Ранжирование критериев. Критерии ранжируются по степени важности.

4) Отыскание решений, лучших хотя бы по одному критерию.

Подходы 1) и 2) приводят к однокритериальной задаче. Подход 3) приводит к задаче с упорядоченными критериями. Подход 4) приводит к задаче с независимыми критериями. В задаче с упорядоченными критериями критерии упорядочиваются по важности и требуется найти оптимальное решение для наименее важного критерия на множестве решений, оптимальных для более важного критерия (см. рисунок). Самое большое множество – множество всех допустимых решений, в него вложено множество решений, оптимальных по самому важному критерию, далее вложено множество оптимальных решений по второму по важности критерию, и т.д.

В задаче с независимыми критериями требуется найти множество недоминируемых (эффективных) решений.

Недоминируемое решение лучше любого другого допустимого решения хотя бы по одному критерию либо не хуже по всем критериям.

Множество недоминируемых решений также называется множеством Парето.

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

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

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

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

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

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

Оптимизационную задачу можно сформулировать в общем виде:

Найти переменные , , …, удовлетворяющие системе неравенств (уравнений)

и обращающие в максимум (или минимум) целевую функцию

,

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

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

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

1. изучение условия задачи,

2. определение важнейших факторов,

3. выделение известных и неизвестных факторов,

4. выявление постоянных и зависимых факторов,

5. дополнение условия задачи недостающими сведениями,

6. введение системы обозначений,

7. составление математической модели (математическое описание важнейших факторов, соотношений и связей между параметрами).

Пример 1. Планирование суточного выпуска продукции – задача об использовании ресурсов

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

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

Решение:

На основании сведений, указанных в условии задачи, имеем:

- оперирующая сторона – фирма,

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

- зависимые факторы: принятие решения состоит в определении суточных объемов выпуска каждого из двух видов изделий,

- ограничения: возможности ограничены временными ресурсами эксплуатации станков трех видов.

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

В нашем примере известными являются следующие параметры:

- суточная норма эксплуатации станка j, j=1,2,3,

- время обработки единицы изделия вида i (i=1,2) на станке типа j, (j=1,2,3),

- стоимость продажи единицы продукции вида i (i=1,2).

Все эти параметры являются постоянными.

Неизвестными (искомыми) являются величины:

- объем суточного выпуска изделия вида i (i=1,2).

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

Тогда доход F от продажи составит от реализации изделия вида 1 и от реализации изделия вида 2, то есть

.

Время, необходимое для обработки единиц изделий на станке j, равняется величине

,

Теперь первоначальную задачу можно сформулировать математически:

. (4.1)

(4.2)

Экономико-математическая модель данной задачи формулируется в следующем виде: Найти план выпуска изделий, удовлетворяющий системе (4.2), при котором функция (4.1) принимает максимальное значение.

Рассмотрим примеры экономико-математических моделей некоторых известных задач.

Пример 2. Задача составления рациона (задача о диете, задача о смесях).

Имеется два вида крома I и II, содержащие питательные вещества (витамины) S₁ , S₂ , S₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в следующей таблице.

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных веществ в 1 кг корма
I	II
S1
S2
S3

Стоимость 1 кг корма I и II соответственно равна 4 и 6 рублей.

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

Экономико-математическая модель задачи имеет вид:

Составить дневной рацион Х=(х₁,х₂), удовлетворяющий следующей системе:

и условию

х₁ ³ 0, х₂ ³ 0,

при котором функция F

F=4х₁ +6х₂

принимает минимальное значение.

Пример 3. Задача об использовании мощностей (задача о загрузке)

Предприятию задан план производства продукции: требуется за время T выпустить n₁, n₂,…, n_k единиц продукции P₁, P₂,…, P_k. Продукция производится на станках S₁, S₂,…, S_k. Для каждого станка известны производительность a_ij (то есть число единиц продукции P_j, которое можно произвести на станке S_i) и затраты b_ij на изготовление продукции P_j на станке S_i в единицу времени.

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

Обозначим x_ij – время, в течение которого на станке S_i будут изготовлять продукцию P_j .

Экономико-математическая модель задачи имеет вид:

Найти такое решение Х=(x₁₁,x₁₂,…,x_mk), удовлетворяющее следующим системам:

и условию

x_ij³0, i=1,2,…,m; j=1,2,…,k

при котором функция F

F = b₁₁x₁₁ + b₁₂x₁₂ + …+ b_mkx_mk

принимает минимальное значение.

Пример 4. Задача о раскрое материалов.

На раскрой поступает материал одного образца в количестве а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональным числам b₁, b₂, b_l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i-того способа (i=1,2,…,n) дает a_ik единиц k-того изделия (k=1,2,…,l).

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Обозначим x_i – число единиц материала, раскраиваемых i-тым способом, и х – число изготавливаемых комплектов изделий.

Экономико математическая модель задачи имеет вид:

Найти такое решение Х=(x₁₁,x₁₂,…,x_nm), удовлетворяющее следующей системе:

и условию x_ij ³ 0,

при котором функция F = x принимает максимальное значение.

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