Понятие модели и их разновидности

Рассмотрим на плоскости х₁Ох₂ совместную систему линейных неравенств

a₁₁x₁ + a₂₂x₂   b₁

a₂₁x₁ + a₂₂x₂   b₂

. . . . . . . .

a_M1x₁ + a_M2x₂   b_M

 

x₁  0, x₂  0

Это все равно, что в  системе (1.2.2) - (1.2.3) положить N=2. Каждое неравенство этой  системы геометрически определяет полуплоскость с граничной прямой

a_i1x₁ + a_i2x₂ = b_i ,(i = 1, 2, ..., m). Условия неотрицательности определяют  полуплоскости соответственно  с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

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

Если в системе ограничений (1.2.2) - (1.2.3) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i  ,(i = 1, 2, ..., n), а условия неотрицательности – полупространства с граничными плоскостями соответственно х_j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.2.2) - (1.2.3) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a_i1x₁ + a_i2x₂ + a_iNx_N = b_i (i = 1, 2, ..., m), а условия неотрицательности – полупространства с граничными гиперплоскостями х_j 0 (j = 1, 2, ..., n).

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

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

 

 

1.3 Выбор метода реализации  модели

 

 

 транспортного цеха  — задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Это задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.

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

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

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

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

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

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

Алгоритм:

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

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

Если не все потребители  удовлетворены и не все поставщики израсходовали товары, возврат к  п. 1, в противном случае задача решена.

Метод потенциалов и метод  последовательного улучшения плана. Пусть  - некоторый опорный план задачи T. Обозначим через совокупность векторов , отвечающих основным коммуникациям плана . Наши рассуждения будут вестись в предположении невырожденности задачи T. Поэтому состоит из m+n-1 векторов и является базисом опорного плана .

На первом этапе метода потенциалов вычисляются предварительные  потенциалы

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

                                                   для .                                 (3.1)

(Здесь  - множество пар индексов векторов, составляющих базис плана .)

Переименуем векторы базиса и обозначим l-й вектор через

Учитывая, что все компоненты вектора  , кроме двух, равных единице, равны нулю, можно переписать систему (3.1) в эквивалентном виде

.

Здесь

;

- стоимость единичной  перевозки по коммуникации, соответствующей  вектору  .

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

,

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

Предположим, что при некоторых i,j

.

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

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

Согласно методу улучшения  плана после разложения вводимого  вектора (вектора  ) по векторам старого базиса разыскивается величина

                                                     .                                              (3.2)

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

Базисные компоненты нового плана определяются по формуле

                                                                                   (3.3)

Для транспортной задачи коэффициенты равны нулю или . При этом в том и только в том случае, если i-й вектор базиса соответствует коммуникации, которая занимает нечетную (четную) позицию в построенном маршруте. Поэтому формула (3.2) в случае транспортной задачи может быть заменена правилом: - минимальная нечетная перевозка маршрута, связывающего пункты и . Это правило и используется в методе потенциалов. Формула (3.3) применительно к транспортной задаче превращается в правило изменения плана перевозок, употребляемое в методе потенциалов: перевозки, запланированные по нечетным (четным) коммуникациям, уменьшаются (увеличиваются) на величину , перевозка между и полагается равной , остальные перевозки сохраняют свои значения.

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

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

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

1) постановка задачи;

2) поиск оптимального  решения;

3) внедрение.

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

 

 

 

2 Расчет модели

 

2.1 Постановка задания

 

 

Моделирование работы транспортного  цеха

Задание: Построить имитационную модель работы транспортного цеха.

Исходные данные:

Транспортный цех обслуживает  три филиала А, В и С. Грузовики перевозят изделия из А в В и из В в С, возвращаясь потом в А без груза. Погрузка изделий в филиале А занимает 20 мин, переезд из А в В длится 30 мин, разгрузка и загрузка в филиале В - по 20 мин, переезд в С - 30 мин, разгрузка в С - 20 мин и переезд в А - 20 мин. Если на момент загрузки в филиалах А и В изделия отсутствуют, грузовики уходят дальше по маршруту пустыми. Изделия в А выпускаются партиями по 1000 шт. через 20 ± 3 мин, в В - такими же партиями через 20 ± 5 мин. На линии эксплуатируется восемь грузовиков, каждый может перевозить по 1000 изделий. В начальный момент четыре грузовика находятся в А, четыре - в В.

Цели моделирования:

Определить частоту пустых перегонов грузовиков между филиалами А и В, В и С.

 

 

2. Построение концептуальной  модели

 

2.1 Анализ задачи

 

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

 

Рис. 1. Структурная схема  процесса функционирования.

Название объекта	Описание объекта
t =20+-3	Время поступления изделий  в филиал А
t=20+-5	Время поступления изделий  в филиал В
1	Переезд грузовиков из филиала А в филиал В
2	Переезд грузовиков из филиала В в филиал С
3	Переезд грузовиков из филиала С в филиал А.

 

Таким образом, входным потоком  будут изделия, выпускающиеся в  филиале А и филиале В, а выходным – пустые грузовики.

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

Предварительный расчет:

Предположим, что грузовики  в стационарном режиме (т.е. достаточно времени спустя от начала процесса) движутся без пустых перегонов. Тогда  один грузовик делает один круг за время, равное 160 минутам, т.к. 30 + 30 + 20 = 80 мин  уходит на переезды между пунктами, и 20 + 40 + 20 = 80 мин – на погрузку и  разгрузку в пунктах А, В и С. Итого время на один круг маршрута составляет 80 + 80 = 160 мин.

За 160 мин грузовик перевезет  тогда 2 партии изделий, одну партию –  в среднем за 80 мин. Следовательно, 8 грузовиков будут перевозить одну партию в среднем за 80/8 = 10 мин. Это  время равно среднему времени  между выпуском партий изделий: в  пункте А партии выпускаются в среднем через 20 мин, и так же в пункте В. Вместе два пункта выдают одно изделие в среднем через 10 мин.

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