Математическое моделирование

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

по дисциплине Исследование операций и методы оптимизации

студентами, обучающимися по направлению

230700.62 Прикладная информатика

Дата ввода – 24 сентября 2011г., протокол № 1

Дата изменения – 03 сентября 2014г., протокол № 1

Уфа- 2014г.

Г 12

Галиаскаров Ф.М. Исследование операций и методы оптимизации Методическое пособие – Уфа УИ РЭУ, 2014 – 50 с.

Методическое пособие разработано в соответствии с Государственным стандартом по направлению 230700.62 Прикладная информатика

Ответственный редактор: д.э.н., профессор Г.Г. Муфтиев

Ответственный за выпуск: д.т.н., профессор, заведующий кафедрой

информационных технологий Ф.М. Галиаскаров

Рецензенты: д.э.н., профессор кафедры общеобразовательных

и профессиональных дисциплин

Уфимского филиала Самарской

государственной академии путей сообщения А.Ф. Зимин;

д.э.н., профессор, заведующий кафедрой

бухгалтерского учета, финансов и банковского

дела УИ(ф) РЭУ Р.Н. Шайбаков

@ Галиаскаров Ф.М., 2014

@ Уфимский институт (филиал) ГГТЭУ, 2012

ПРЕДИСЛОВИЕ

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

Переход к новой модели образования по подготовке бакалавров и магистров предполагает, что экономист с университетским образованием должен уметь вести комплексный анализ экономических явлений, заниматься не только практической деятельностью, но и участвовать в научно-исследовательской работе. В учебных программах бакалавров и магистров в области экономики в университетах таких стран, как США, Германия, заложены довольно значительные объемы математики. Необходимым условием того, что наши бакалавры и магистры будут котироваться на уровне западных, является их высокая математическая культура.

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

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

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

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

- анализ существующей проблемы;

- математический анализ проблемы;

- применение результатов исследования на практике.

Математическое моделирование

Пример 1.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.

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

Обозначим через 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**) соответственно.

Пример 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.

Пример 1.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 - число разновидностей ценных бумаг. Целевая функция имеет смысл дисперсии фактической прибыли (рассеивание фактической прибыли от ожидаемой), первое ограничение есть условие на ожидаемую прибыль, а последнее - непревышение средств, выделенных на покупку ценных бумаг.

Пример 1.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.

Пример 1.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 -уровень запаса на конец периода-

Пример 1.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 заданные числа видов заявок и приборов.

Пример 1.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₂₃.

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

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

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

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

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

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

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

операции	непосредственно предшествующие операции	продолжительности операций
А	-	tA
В	-	tB
С	А	tC
D	А	tD
Е	B,D	tE
F	С,Е	-

Фиктивная операция 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

Пример 1.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)