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

[2 — 4]. Пусть осуществляется производство некоторого товара в пунктах Л], А1, A2_t,..., А_т. Объем производства товара в каждом пункте равен соответственно а 1_ь а2,..., αί,..., аm. Товар необходимо доставить в магазины или потребителям, находящимся в других на­селенных пунктах: B1, В₂,..., Bj,..., В_п. Известна потребность каж­дого потребителя в товаре: b_x, b₂,..., bj,..., b_n. Задана также стои­мость Сij транспортировки товара из каждого пункта производства Aί в каждый магазин Bj. Требуется составить план завоза товара в магазины, обеспечивающий удовлетворение их спроса при мини­мальных транспортных издержках.

Пусть Xjj — объем товара, перевезенного из пункта производства с индексом i в магазин с индексом j. Тогда целевая функция С транс­портной задачи записывается в виде

m n

C = ∑ ∑ C ίj X ίj → min

ί= 1 j= 1

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

m

∑ X ίj ≤ b j

n

и в каждом пункте Aί будет выпущено количество товара, не превы­шающее возможный объем производства:

m

∑ X ίj ≤ α ί

j= 1

Целевая функция С обеспечивает минимизацию затрат на транс­портировку товара для всех магазинов в целом.

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

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

Задача о пользе услуг. Построим оптимизационную модель, у ко­торой некоторые переменные могут принимать только целые значе­ния. Она называется целочисленной моделью линейного програм­мирования. Допустим, перед человеком стоит вопрос, какими вида­ми бытовых услуг — у1, у2,..., у„ — ему следует воспользоваться, чтобы максимально облегчить свой быт (сэкономить время). Пред­полагается, что сумма денег, которой он располагает, равна d. После некоторого раздумья человек составил список:

услуга У1 стоит d1 рублей и экономит t 1 часов,

 

» у2» d 2»»» t 2»,

-----------------------------------

» уj» d j»»» t j»,

-----------------------------------

» у n» d n»»» t n».

 

Таким образом, каждая услуга экономит определенное время, которое может быть полезно использовано. Спрашивается, какими услугами следует воспользоваться?

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

Целевая функция модели выглядит так:

n

Т = max ∑ t j Xj.

J j=1

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

n

∑ dj x j ≤ D

J =1

(нельзя истратить денег на услуги больше имеющейся суммы); все Xj — целые.

 

 

Второе условие — условие целочисленноcти — отличает эту за­дачу от обычных задач линейного программирования.

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

 

Игровые модели

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

Случаи, когда для объекта моделирования характерно наличие противодействующих сил или неопределенности параметров, свойств или поведения, рассматриваются теорией игр [15, 23]. Теория игр — теория математических моделей принятия оптимальных ре­шений в условиях конфликта или неопределенности. Под конфлик­том следует понимать любое разногласие, возникающее вследствие несовпадения интересов.

В теории игр важное значение имеет понятие неопределенности. Рассмотрим его на примерах. При моделировании спроса на какой-либо товар могут быть известны только либо нижний и верхний пределы колебания спроса, либо статистическое распределение воз­можных значений спроса. Тогда в первом случае имеет место гак называемая стратегическая неопределенность, когда неизвестен даже закон распределений событий (значений спроса), а во вто­ром — статистическая неопределенность, соответствующая случаю, при котором нельзя точно назвать значение спроса, хотя его закон распределения известен. Неопределенности такого типа могут возникнуть в результате действии конкурента, удовлетворяющих какую-то часть спроса, или вследствие «игры природы» (изменения климатических, социальных и других условий). В любой игре име­ются следующие элементы: множество всех игроков I ={1,2,...,n}, где ί Є I — произвольный игрок. Всякий игрок i имеет в своем рас­поряжении множество стратегий поведения, или возможных дейст­вий, S ί.

Процесс игры заключается в выборе каждым игроком одной оп­ределенной стратегии S ί Є S ί, обеспечивающей, например, игроку ί максимальный выигрыш Hί(Sj). Функция Hί, называется функцией выигрыша игрока i.

Таким образом, налицо множество стратегий игроков (S1, S₂,..., S_n) - S_/r называемое ситуацией, в которой каждый игрок или их определенная группа (коалиция) имеет какой-либо выигрыш (про­игрыш). Множество всех ситуаций

 

S = S_] xS₂x... xS_n.

 

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

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

Рассмотрим пример из теории игр, поясняющий сказанное выше.

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

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

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

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

 

Спрос (на число рабочих мест)
Вероятность Рj:	0,01	0.09	0,2	0,3	0.3	0,1

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

Статья 1. Ежегодные расходы, не зависящие от числа рабочих мест предприятия:

• стоимость строительства и оборудования — 100 000 руб.;

• норма амортизации — 10%, затраты на амортизацию здания и
оборудования — 10 000 руб.;

• затраты на ремонт и поддержание помещения в рабочем состоянии – 14 000 руб.

• зарплата сторожа и уборщиц — 1500 руб.
Итого по статье 1 — 25 500 руб.

Статья 2. Ежегодные затраты, зависящие от числа рабочих мест (табл. 1.2.1).

Таблица 1.2.1

Зависимость ежегодных затрат от числа рабочих мест, руб.

 

Статья затрат	Число рабочих мест
Оборотные средства Зарплата рабочих Прочие затраты	80 000 15 000 500	120 000 22 500 750	160 000 30 000 1 000	200 000 37 500 1 250
Итого	95 500	143 250	191 000	238 750

 

Статья 3. Ежегодные затраты, пропорциональные среднему числу фактически загруженных рабочих мест (табл. 1.2.2).

 

Таблица 1.2.2

Ежегодные затраты, зависящие от числа загруженных рабочих мест

 

Число загруженных рабочих мест R
Затраты на газ. воду, электроэнер­гию, канализацию, отопление, руб.		36 000	72 000	108 000	144 000	180 000

Найдем средний за год объем реализации услуг, предоставляе­мых предприятием, при определенном числе рабочих мест (табл. 1.2.3).

 

Таблица 1.2.3

 

Расчет объема	реализации услуг за год
Число загруженных рабочих мест (R)
Объем реализации услуг, руб.		219 000	438 000	657 000	876 000	1 095 000

 

В зависимости от затрат и предполагаемого объема реализации услуг определим прибыль (убыток) предприятия (табл. 1.2.4).

Таблица 1.2.4

Оценка прибыли Si, соответствующей различным стратегиям, руб./год

 

Номер стратегии

Число рабо­чих мест

R -

= 0

R

= 10

R

= 20

R =

= 30

R --

= 40

R =

-121

-168

-216

—33

-264

- 81

 

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

Представим функцию выигрыша H,{Sj) в виде

6 -3

Hί (Sί) = ∑ Sί Pj * 10

J = 1

 

где i — номер стратегии, i = 1; 4;

j — число рабочих мест на предприятии, кратное 10, J = 1; 6;

Sj,- — прибыль предприятия, соответствующая стратегии ί;

Р j — вероятность спроса на число рабочих мест j на предпри­ятии.

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

H1(S1) = 121-0,01 + 62-0,09 + 245-0,2 + 245-0,3 + 245-0,3 + + 245-0,1 =224,87;

H₂(S₂) = 168,75-0.01 + 14.25-0,09 + 197,250,2 + 380,25-0,3 + + 380,25-0,3 + 380,25-0,1 = 305,22;

H₃(S₃) = -216,50.01 - 33,5-0,09 + 149,50,2 + 332,50.3 + + 515,5-0,3 + 515,5-0,1 = 330,67;

H₄(S₄) = -264,250,01 - 81,250,09 + 101,750,2 + 284.750,3 + + 467,750,3 + 650,75-0,1 = 301,12.

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

 

Имитационные системы

 

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

Моделирование «больших систем» почти всегда связано либо с неопределенностью критериев, либо с наличием критериев, предъявляющих к решению противоречивые требования, а также с непо­стоянством критериев.

В этой связи развивается другое направление экономико-мате­матического моделирования «больших систем» — имитационное мо­делирование.

Имитационное моделирование представляет собой систему, со­стоящую из совокупностей следующих элементов:

• имитационных моделей, отображающих определенные черты,
  свойства или части «большой системы» и позволяющих отвечать на
  вопрос: что будет при данных условиях и принятом решении (пря­
  мая задача моделирования)?;
• экспертов и экспертных процедур, необходимых для анализа и
  оценки различных решений, исключения заведомо слабых решений,
  построения «сценариев» развития событий, выработки целей и кри­
  териев;
• «языков» ЭВМ, на основе которых осуществляется двухсторон­
  ний контакт экспертов с ЭВМ. Эксперт задает исходные данные,
  меняет структуру моделей, формулирует вопросы ЭВМ при помощи
  специальных языков моделирования.

Итак, в имитационной системе можно выделить три основных вида элементов.

Имитационные модели [4, 29] представляют собой довольно сложные программы для компьютера, описывающие поведение ком­понентов системы и взаимодействие между ними. Расчеты по этим программам при различных исходных данных позволяют имитиро­вать динамические процессы, происходящие в реальной системе.

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

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

Имитационные модели в некоторой степени напоминают физи­ческие модели, т.е. модели реальных объектов в миниатюре. Напри­мер, существует физическая модель Братской ГЭС, в которой вос­произведены все реальные условия ее работы в уменьшенном мас­штабе. Задавая различные скорости течения воды, меняя условия прохождения водного потока через колеса гидроагрегатов, донные и сливные отверстия, ученые измеряют различные параметры вод­ных потоков, оценивают устойчивость сооружений станций, степень размыва речного дна, берегов и дают заключения о наилучших ре­жимах работы ГЭС. Примерно так же происходит процесс имитационного моделирования. Разница заключается только в том, что вместо потоков воды используются потоки информации о движении воды, вместо показаний физических приборов — данные, получен­ные с помощью ЭВМ. Конечно, имитационный эксперимент менее нагляден, чем физический опыт, но его возможности гораздо шире, так как в имитационной модели фактически допустимы любые из­менения, каждый фактор можно варьировать по усмотрению иссле­дователя, ошибки, возникающие в модели или исходных данных, легче заметить.

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

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

Экспертные процедуры используют коллективный опыт людей и предназначены для усреднения мнений и получения объективно! оценки какого-либо события или явления. Проведение экспертиз в большинстве случаев позволяет выработать определенные решения оценить относительную важность ряда событий или найти пропорции между показателями. Например, экспертам, занятым планированием в сфере обслуживания населения, может быть задан вопрос: «В каком отношении (пропорции) должны развиваться отрасли сферы обслуживания населения с точки зрения объемов реализации услуг?» При ответе на вопрос каждому эксперту предлагается проставить коэффициенты относительной важности, или баллы, каждой отраслевой группы обслуживания, например, в такой форме:

Сфера обслуживания	Баллы	Нормированные баллы
Торговля		0.33
Общественное питание		0.17
Бытовое обслуживание		0.18
Коммунальное хозяйство		0.21
Пассажирский транспорт		0.11

 

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

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

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

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

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

Общение человека-эксперта с компьютером при имитации «больших систем» требуется в двух случаях. В первом случае, когда имитационная модель не использует формальный математический аппарат и представляет собой в основном процесс экспертной оцен­ки совокупности содержательных событий или целей, для общения применяют типовые пакеты Excel, Word и т.п. Процесс общения экс перта с ЭВМ при подсчете средних баллов или коэффициентов, оце­нивающих те или иные события, цели, осуществляется согласно ме­тодике экспертного анализа. Здесь применение ЭВМ минимально. Во втором случае, когда имитационную модель используют для изу­чения функционирования какого-либо сложного объекта, например производственного предприятия, банка или рынка, путем машинной имитации информационных процессов при заданных условиях, мо­дель записывается на одном из специальных имитационных языков, например JPSS, Симскрипт, Симула, Динамо, MathCad plus и пр.

Важным преимуществом таких языков является наличие в них методов нахождения ошибок, значительно превосходящих соответ­ствующие возможности универсальных языков. Однако применение специальных имитационных языков налагает ограничения на форму вывода информации о поведении моделируемой системы. Исполь­зование универсального языка типа Фортран меньше всего ограни­чивает форму вывода данных. Наоборот, использование языка типа Симскрипт вынуждает приспосабливаться к требованиям, налагае­мым этим языком. Поэтому в сложных имитационных системах для общения экспертов с имитационной моделью используют различные языки. При описании процессов в имитируемой системе могут быть применены такие языки, как JPSS, Симскрипт, Симула, Динамо, а для описания различных «сервисных» и выводных процедур — уни­версальные языки Фортран, PL, Алгол, а также пакеты Excel, Word и т.п. Приведем пример имитационной системы.

Пример. Имитация работы парикмахерской по схеме, представ­ленной на рис. 1.2.1.

Входной поток клиентов (заявок) характеризуется следующим законом распределения моментов поступления заявок:

 

Часы работы парикмахерской

б

Число пришедших клиентов

И

Из таблицы видно, сколько клиентов (заявок) пришло в первый, второй и т.д. часы работы парикмахерской. Всего данная парикма­херская работает 12 ч. Предположим, что среднее время обслужива­ния заявки t_ср = 20 мин. Число мастеров (каналов обслуживания) равно восьми. Клиенты (заявки) обслуживаются по очереди без при­оритета. Требуется определить: среднее число клиентов в очереди в разные часы работы парикмахерской; среднее время ожидания кли­ентов в очереди; оптимальное число мастеров в каждый час работы при условии, что время ожидания в очереди не более 10 мин; среднее время простоя мастеров и т.д.

 

Рис. 1.2.1. Схема работы парикмахерской

Зал ожидания (клиенты сидят в очереди)

Решить эту задачу в аналитическом виде методами теории мас­сового обслуживания очень сложно, ее можно решить при помощи имитационной модели. Схема такой модели приведена на рис. 1.2.2. Модель построена из специальных блоков, называемых агрегатами. Каждый агрегат выполняет определенные функции. Так, агрегат Aq (очередь) предназначен для распределения клиентов (заявок), при­шедших в систему (парикмахерскую), между каналами обслужива­ния (мастерами) А1 — А8, а также для имитации очереди клиентов. Заявка из очереди попадает на первый освободившийся канал обслу­живания, где находится в течение времени обслуживания t_с = 20 мин.

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

Второй вход Aq принимает значение, равное единице, если осво­бождается какой-либо канал обслуживания (мастер). В противном случае второй вход равен нулю. Состояние агрегата Aq отображается в виде трех компонент: X, Y, Z (X — число заявок, находящихся в очереди; Y — номер канала, освободившегося первым; Z — сум­марное время нахождения всех заявок в очереди за определенный час работы системы). Состояние агрегата A0 зависит от входных сиг­налов: если пришла новая заявка или заявка из очереди поступила на обслуживание, меняются величина очереди, номера каналов Y и время /. Все возможные изменения состояния описываются и «за­кладываются» в модель. Выход агрегата А_о соответствует единице, если в данный момент заявка из очереди пошла на обслуживание, и нулю, если этого не происходит. Аналогично описываются и дру­гие агрегаты.

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

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

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

 

 

⇐ Предыдущая123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: