Математическое моделирование. Общая структура

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

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

- Кто принимает решение?

- Каковы цели принятия решения для каждого ЛПР?

- В чем состоит принятие решения?

- Каковы возможности ЛПР (с точки зрения принятия решений)?

- При каких условиях происходит принятие решения?

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

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

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

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

ЛПР - планирующий орган (фирма);

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

принятие решения для ЛПР состоит в определении суточных объемов выпуска каждого из двух видов изделий;

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

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

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

- суточная норма b₁ эксплуатации станка 1;

- - суточная норма b₂эксплуатации станка 2;

- суточная норма b₃ эксплуатации станка 3;

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

- стоимость с₁ (продажи) единицы изделия вида 1;

- стоимостьc₂ (продажи) единицы изделия вида 2;

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

- объем суточного выпуска изделия вида 1;

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

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

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

В нашем примере обозначим:

x₁ - объем суточного выпуска изделия вида 1,

x₂ - объем суточного выпуска изделия вида 2.

Тогда доход от продажи x₁ и x₂ есть:

c₁ x₁ + c₂ x₂,

а время, необходимое для обработки x₁, x₂ единиц изделий на станке j, есть

a_ij x₁ + a_2j x₁ (j=l,2,3).

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

максимизировать c₁ x₁ + c₂ x₂,

выбирая x₁ и x₂ из условия

a₁₁ x₁ + a₂₁ x₂ £b₁,

a₁₂ x₁ + a₂₂ x₂ £b₁,

a₁₃ x₁ + a₂₃ x₂ £b₁,

x₁³0, x₂³0.

Условия неотрицательности переменных следует из смысла величин x₁и x₂ - это дополнение модели недостающими сведениями. Полученную задачу запишем более компактно:

max c₁ x₁ + c₂ x₂,

при ограничениях

a₁₁ x₁ + a₂₁ x₂ £b₁,

a₁₂ x₁ + a₂₂ x₂ £b₁,

a₁₃ x₁ + a₂₃ x₂ £b₁,

x₁³0, x₂³0.

Это есть задача математического программирования (см. определение во введении) с целевой функцией c₁ x₁ + c₂ x₂ и множеством допустимых решений X, которое описывается пятью неравенствами (на плоскости это есть многогранник, образованный пересечением пяти полуплоскостей).

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

Обозначим через N множество сторон, принимающих участие в данной конкретной задаче принятия решения:

N={1,2,...,n},

где каждый элемент i множества N называется лицом, принимающим решение (ЛПР), например, отдельная личность, фирма, плановый орган большого концерна, правительства и др. Каждый элемент iÎN характеризуется своими возможностями. Обозначим через Х_i множество всех его допустимых решений (стратегий, альтернатив). Предположим, что такие множества математически описаны для всех участников:

X₁, X₂,..., X_n.

После этого процесс принятия решения всеми ЛПР сводится к следующему формальному акту: каждое ЛПР выбирает конкретный элемент x₁ÎX₁, x₂ÎX₂,…, x_nÎX_n из своего допустимого множества решений. В результате получается набор х = (x₁,...,x_n) выбранных решений, который мы называем ситуацией.

Формализация целей принятия решения осуществляется по следующей схеме. Тем или иным способом строятся аналитические законы (функции) f₁,....,f_n, ставящие в соответствие каждой ситуации x набор из n чисел

f₁(x), f₂(x),...,f_n(x).

Функция f_i(x) == f_i(x₁,...,x_n) называется критерием качества i-го ЛПР. Число f_i(x) является количественной оценкой ситуации x для i-гo ЛПР с точки зрения преследуемой им цели. Поэтому в модели цель i-ro участника формализуется так: выбрать такое свое решение x_iÎX_i, чтобы добиться возможно большего значения функции f_i. Однако достижение этой цели полностью от него не зависит в виду наличия других сторон, влияющих на общую ситуацию x с целью достижения своих собственных целей. Этот факт пересечения интересов (конфликтность) отражается в том, что функция f_i помимо x_i зависит и от остальных переменных x_j (i¹j). Поэтому в моделях принятия решения со многими участниками применяются более сложные принципы оптимального поведения, чем прямая максимизация или минимизация критерия качества.

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

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

<N;X₁....,Xn;f₁....fn; Σ > (1)

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

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

1. Множество ЛПР (N).

2. Критерии качества (f₁,...,fn).

3. Множества допустимых решений (X₁,...,Xn).

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

Конкретизируя эти элементы, их характеристики и свойства, мы получаем тот или иной конкретный класс задач (класс моделей) принятия решения. Так, если N состоит только из одного элемента (n=1), а все условия и предпосылки исходной реальной задачи можно описать в виде множества допустимых решений этого единственного ЛПР, то из (1) получаем структуру задач оптимизации (экстремальных задач):

<Х,f> (2)

В схеме (2) ЛПР может рассматриваться как планирующий орган, множество допустимых решении Х задается при помощи ограничений на возможности ЛПР, а критерий качества f называется целевой функцией. Задача оптимизации ставится так:

max f(x) (f(x)→max) (3)

^{xÎX xÎX}

min f(x) (f(x)→min) (4)

^{xÎX xÎX}

Это различная форма записи одной и той же задачи: (3) - задача на максимум, в которой требуется найти точку максимума x* функции f на множестве X; (4) -задача на минимум, в которой требуется найти точку минимума x** функции f на множестве X. Решениями (оптимальными) этих задач называются пары x*,f(x*) и x**, f(x**) соответственно.

§ 3. Этапы математического моделирования.

Примеры.

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

1. Изучение условия задачи (предметной области).

2. Определение важнейших факторов (см. §2).

3. Выделение известных и неизвестных параметров.

4. Выявление управляемых и неуправляемых параметров.

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

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

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

В приведенных ниже примерах составления моделей проследите эти этапы, которые мы выполним без комментариев (см. по этому поводу Пример 1.).

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

Обозначим: i - номер (название) блока, i = 1,....n; j - номер (название) фирмы-поставщика, j= 1,...,n; с_ij - стоимость выполнения i-ro блока j-ой фирмой (заданное число). Кроме того, введем для каждого i и j число.

Целевая функция, имеющая смысл общих затрат на покупку комплек­тующих блоков, запишется так

Ограничения задачи (на переменные х_ij) имеют следующий смысл:

1) каждый i-й блок должен быть выполнен (каким-либо поставщиком);

2) каждая фирма-поставщик j должна выполнить один (какой-либо) блок.

Математически эти условия запишутся соответственно:

x_i1+x_i2 +…+ x_in = 1,

x_ij+x_2j +…+ x_nj = 1.

Таким образом, приходим к следующей оптимизационнойзадаче (модели):

при ограничениях

x_ij = 0 или 1 для всех i,j.

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

Прибыль к концу планового периода на каждый доллар, вложенный в бумагу j-го вида, характеризуется двумя показателями: аj - фактическая прибыль (случайное число), aj - ожидаемая прибыль. Требуется, чтобы ожидаемая прибыль на доллар инвестиций была для всего набора ценных бумаг не ниже заданной величины b.

Для получения модели примем все средства, выделенные на покупку ценных бумаг, равными единице и обозначим через x_j - долю от всех средств, выделяемую для приобретения ценных бумаг вида j.

Риск учитывается при помощи ковариации (см. теорию вероятностей)

s_ij = М (а_i, - a_i) (а_j - a_j)

прибыли для ценных бумаг вида i и вида j.

Математическая модель имеет вид:

при ограничениях

x_j ³ 0, j=1,…,n

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

Пример 4 (Задача о рекламе). Фирма планирует проведение радиорекламной кампании по сбыту автомобилей в одном из регионов, где расположено s радиостанций, в течение двух недель. Фирма оценила предварительно, что если радиостанции j выделить у_j долларов, то чистый доход от увеличения сбыта равен R_j(y_j) (R_j - функция реализации дохода от объема финансирования рекламы). На рекламу выделена общая сумма, равная N долларам. Число рекламных объявлений в день не должно превышать M. Если фирма выделила j-й радиостанции у_j долларов, то число рекламных объявлений будет K_j(y_j) (K_j - функция, которая каждой выделенной сумме ставит в соответствие количество рекламных объявлений в день, считается известной). Как нужно финансировать s радиостанций, чтобы получить суммарную максимальную прибыль от реакции сбыта на рекламу?

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

при ограничениях

y_j ³ 0, j = 1,…,s.

Пример 5 (Задача управления производством). Фирма должна разработать календарную программу выпуска некоторого вида изделий на плановый период, состоящий из Т отрезков (недель, месяцев, кварталов, лет). Предполагается, что для каждого из этих отрезков имеется точный прогноз спроса на выпускаемую продукцию. Время изготовления партии изделий настолько мало, что им можно пренебречь. Для разных отрезков спрос неодинаков; кроме того, на экономические показатели производства влияют размеры изготовляемых партий. Хранение возникающих при этом запасов (превышение выпуска над спросом на некоторых отрезках) связано с определенными затратами.

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

Обозначим:

x_t - выпуск продукции в течение некоторого отрезка t;

y_t - уровень запасов на конец отрезка t;

D_t - спрос на продукцию для отрезка t;

Затраты на отрезке t (обозначим их С_t) зависят от выпуска x_t и уровня запасов y_t, т.е. являются функцией от этих неизвестных величин: c_t = c_t (x_t, y_t).

Требование удовлетворения спроса в пределах каждого временного отрезка означает, что уровень запасов на конец отрезка t (т.е. yt) должен равняться сумме - уровня запасов и начало отрезка t (т.е. yt-1) и выпуска продукция на отрезке t (т.е. xt) минус спрос на отрезке t (т.е. Dt).

Отсюда получаем следующую модель:

при ограничениях

уt-1 + xt - yt = Dt, t==1,2,…T;

yT = 0, xt, yt ³ 0 для всех t.

Здесь y₀ - заданный уровень запасов на начало планового периода, а y_T -уровень запаса на конец периода. -

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

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

Для составления модели сначала введем обозначения свободных величин:

N_j - количество приборов j-го типа,

d_i^t - число заявокi-го типа в момент времени t.

μ_ij - эффективность j-го прибора при обслуживании заявки i-го вида. Обозначим искомую величину:

x_ij- число приборов j-го вида, отведенных для обслуживания заявок i-го типа.

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

при ограничениях

x_ij - целые неотрицательные числа для всехi, j, здесь m и n заданные числа видов заявок и приборов.

Пример 7 (Выбор оптимального вида посевной культуры). Фермер может посеять одну из трех культур: A₁, А₂ или А₃. Урожаи этих культур во многом зависят от погоды. Требуется установить, какую из этих культур сеять, чтобы обеспечить наибольший доход, если известны цена а_i одного центнера культуры A_i, i = 1,2,3, и средняя урожайность каждой культуры в зависимости от погоды (будет ли лето засушливым нормальным или дождливым). Достоверный прогноз погоды отсутствует.

Обозначим через h_ij - урожайность i-й культуры при погодных условиях j (здесь j=1 - обозначение засушливого лета, j=2 - нормального лета, j=3 – дождливого лета). Числа h_ij, как и числа a_i, заданы (известны). Реально может иметь место только одна из ситуаций (i,j), i = l, 2, 3; j = l, 2, 3. Причем (i,j) означает, что посеяна культура A_j, а погода находится в состоянии j. Всего таких ситуаций девять. JIПР (фермер) может выбрать только вид культуры, состояние погоды от него не зависит.

Если фермер засеял культуру A₁, то он может получить (в зависимости от состояния погоды) один из следующих доходов:

a₁h₁₁, a₁h₁₂, a₁h₁₃

соответственно для культуры A₂:

a₂h₂₁, a₂h₂₂, a₂h₂₃

и для культуры А₃:

a₃h₃₁, a₃h₃₂, a₃h₃₃

Напишем все эти исходы в одну таблицу (матрицу):

Эта матрица и есть математическая модель исходной задачи. В ней действие фермера сводится к выбору одной из строк матрицы (одной из трех стратегий). Его доход зависит от "выбора" природой одного из своих состояний (одного из трех столбцов матрицы). Например, если фермер посеял культуру A₂, а лето получилось дождливым, то доход фермера равен a₂h₂₃.

Пример 8 (Выбор ассортимента товаров). На базе торговой организации имеется n типов одного из товаров ассортиментного минимума. В магазин должен быть завезен только один из типов данного товара. Требуется выбрать тот тип товара, который целесообразно завести в магазин. Если товар типа j будет пользоваться спросом, то магазин от его реализации получит прибыль p_j, если же он не будет пользоваться спросом - убыток q_j.

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

Руководствуясь формализацией задачи примера 7, обоснуйте, что искомая модель имеет вид:

Объясните задачу магазина на этой модели.

Пример 9. (Планирование оптимального срока окончания проекта). Компания должна реализовать проект строительства объекта, состоящий из nопераций (работ). Руководители комплекса оценили продолжительность выполнения каждой операции и установили последовательность операций, т.е. точно определили, какие операции обязательно должны быть закончены, чтобы могла начаться любая из операций, входящих в комплекс.

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

При составлении математической модели предположим (для простоты), что проект состоит из пяти операция А,В,С,Д,Е. По условию задачи известны последовательность операций и их продолжительность. Пусть эти данные для наших пяти операций таковы:

Фиктивная операция F, начинающаяся в момент завершения проекта, вводится для удобства (см. ниже). Второй столбик таблицы означает, что операцию С нельзя начать, прежде чем незакончена операция А и т.д.

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

y_CD - момент начала операций С и Д;

y_E - момент начала операции Е;

y_F - момент начала операции F.

Здесь, y_F на самом деле есть момент завершения всего комплекса. Моменты y_A и y_B - это моменты 0 начала операций, т.к. операции А и В не имеют предшествующих. Модель имеет вид:

min y_F

при ограничениях

y_CD ≥ t_A

y_E ≥ t_B

y_E ≥ t_D + y_CD

y_F ≥ t_C + y_CD

y_F ≥ t_E + y_E

§ 4. Разделы и классы задач исследования операций.

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

Начнем с характеристики среды (∑) принятия решения.

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

В зависимости от количества ЛПР в (1) различают задачи оптимизации (2) и игровые задачи (n ≥ 2, где n - число элементов во множестве N).

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

В зависимости от характера конфликта различают, антагонистические (примеры 7,8), неантагонистические (бескоалиционные) и кооперативные игры.

Если в задаче оптимизации все элементы линейны (целевая функция и ограничения), то получаем задачу линейного программирования (примеры 1,2), в противном случае - задачу нелинейного программирования (пример З и пример 4,если функции R_j, и K_j нелинейные). Если в задаче оптимизации присутствует фактор времени, то она называется задачей оптимального управления (пример 5). Иногда такие задачи называют задачами динамического программирования. Однако это неточное название, так как динамическое программирование - это название метода решения задач оптимального управления.

Часто у ЛПР имеется не одна, а несколько целей. Математическая модель

<X;f₁,…,f_n;Σ> (5)

такой задачи называется задачей многокритериальной (или векторной) оптимизации. В модели (5) ЛПР выбирает решение х Î Х так, чтобы получить как можно большие значения f₁(x),...,f_n(x) критериев.

Есть классы задач ИО, получивших свое название, исходя из их назначения: системы массового обслуживания (пример 6), задачи управления запасами (пример 3), задачи сетевого и календарного планирования (пример 9).

Перечисленные классы задач изучаются в разделах ИО с соответствующими названиями.

Для полноты восприятия ниже мы приведем те «классические» задачи ИО, которые, благодаря их типичности, встречаются во многих учебниках по математическому программированию. Некоторые из них относятся к начальному периоду возникновения теории оптимизации. Примеры служат для иллюстрации некоторых видов задач принятия решения и не претендуют на реалистичность в последней инстанции. Это «учебные задачи». Естественно, задачи и модели, представляющие непосредственный практический интерес, будут более подробными, глубокими и сложными. Учебные задачи - это первое приближение к реальным (практическим) задачам, их упрощенный аналог. Руководствуясь материалами предыдущих двух параграфов, читатель может самостоятельно получить математические модели этих задач в качестве упражнений.

Задача оптимального раскроя материала. Фирма изготовляет изделие, состоящее из р деталей (например комплект постельного белья). Причем в одно изделие эти детали входят в количествах k₁,…,k_r.С этой целью производится раскрой m партий материала. В i-й партии имеется b_i единиц материала. Каждую единицу материала можно раскроить на детали n способами. При раскрое единицы i-й партии j-м способом получается а_ijr деталей r-го вида.

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

Транспортная задача. Имеется n поставщиков и m потребителей одного и того же продукта. Известны выпуск продукции у каждого поставщика и потребности в ней каждого потребителя, затраты на перевозки продукции от поставщиков к потребителям.

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

Задача о назначениях на работу. Имеется n работ и n исполнителей. Стоимость выполнения работы i исполнителем j равна c_ij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты (ФЗП).

Задача о смесях (о рационе). Из m видов исходных материалов, каждый из которых состоит из n компонент, составить смесь, в которой содержание компонент должно быть не меньше b₁,...,b_n. Известны цены единицы материалов: c₁...c_m и удельный вес j-гo компонента в единице i- гo материала.

Составить смесь, в которой затраты должны быть минимальны.

Задача о рюкзаке. Имеется n предметов. Вес предмета i равен p₁, ценность c₁ (i=l,…,n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

Задача о коммивояжере. Имеется n городов и задано расстояние c_ij между ними (i,j=l....,n). Выезжая из одного (исходного) города, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в исходный город.

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

Задача о станках. На универсальном станке обрабатываются одинаковые партии из n деталей. Переход от обработки детали i к обработке детали j требует переналадки станка, которая занимает c_ij времени.

Требуется определить последовательность обработки деталей, при которой общее время переналадок станка при обработке партии деталей минимально.

Задача о распределении капиталовложений. Имеется n проектов, причем для каждого проекта i известны ожидаемый эффект γ_j от его реализации и необходимая величина капиталовложений g_j. Общий объем капиталовложений не может превышать заданной величины b.

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

Задача о размещении производства. Планируется выпуск m видов продукции, которые могли бы производиться на n предприятиях (n>m). Издержки производства и сбыта единицы продукции, плановый объем годового производства продукции и плановая стоимость единицы продукции каждого вида известны.

Требуется из n предприятий выбрать такие m, каждое из которых будет производить один вид продукции.

§ 5. Основные требования к математическим моделям и их свойства.

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

1) адекватность (соответствие модели своему оригиналу),

2) простота (незасоренность второстепенными факторами),

3) объективность (соответствие научных выводов реальным условиям),

4) чувствительность (способность модели реагировать изменению начальных параметров),

5) устойчивость (малому возмущению исходных параметров должно соответствовать малое изменение решения задачи (модели)).

6) универсальность (широта области применения).

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

- можно ли использовать известную модель для формализации данной задачи?

- если нет, то в какой мере требуется переработка (подгонка) соответствующей модели?

Идентификация модели и метода решения задачи показана на следующей схеме:

Пример 10 (Задача размещения предприятий). С целью расширения сферы деятельности фирма планирует открыть несколько новых филиалов. Пункт i представляет собой одно и возможных точек размещения нового филиала с мощностью S_i, а постоянные затраты связанные с его эксплуатацией, равны F_i ≥ 0 (независимо от фактического объема выпуска). Существует всего m возможных пунктов (i=1,2,…,m) размещения, но открывать филиалы во всех этих пунктах нерационально. Для каждого пункта i изготовления и пункта j сбыта известны:

c_ij ≥ 0 - совокупные производственные и транспортные затраты, F_ij ≥ 0 -некоторые постоянные затраты (Пусть F_ij не зависит от объема перевозок x_ij > 0, но при x_ij=0 F_ij также равна нулю).

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

Для построения математической моделиэтой задачи полезно ориентироваться на модель классической транспортной, задачи, сформулированной в §4 (исходя из схожести условий), которая имеет вид:

(суммарные транспортные расходы) (5)

при ограничениях

(предложение) (6)

(спрос) (7)

x_ij ≥ 0 (объем перевозок) (8)

В нашем примере введем обозначения:

U_ij = min (а_i,b_j).

Тогда вместо целевой функции(5) получаем суммарные расходы в виде:

(9)

Вместо ограничения (6) на мощности поставщиков вводим ограничения на пропускные способности маршрутов:

(10)

Ограничение (7) по спросу потребителей остается без изменения:

(11)

Построение модели еще не закончено. Нужно добиться того, чтобы условие x_ij>0 выполнялось только в случае, когда z_ij = 1. Это достигается с помощью линейных ограничений:

x_ij ≤ U_ij z_ij при любых i,j= 1,...,m (12)

Кроме того,

х_ij ≥ 0, i,j = 1,...,m (13)

Теперь мы сможем сказать, что модель (9)-(13) задачи примера 10 получена в результате модификация модели (5) - (8) классической транспортной задачи.

Поиск по сайту: