ТЕМА: Транспортная задача.

Цель работы: Изучить метод потенциалов.

Методическая указания

Пример 2. Фирма обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: “Морской”, “Солнечный”, “Слава” и “Уютный”, в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице 1.

Таблица 1

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

I. Математическая модель задачи.

1) Переменные задачи. Обозначим количество туристов, которые будут перевозиться из пункта i в отель j как X_ij (i=1,2,3; j=1,2,3,4). Это переменные задачи, значения которых должны быть определены в процессе решения. Например, X₂₃ - это число туристов, которое должно быть перевезено из аэропорта (пункт 2) в отель “Слава” (пункт 3). В задаче содержится 3*4=12 переменных.

2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные и целые числа, т.е.

X_ij 0, (1)

X_ij - целые числа, (2)

где i=1, 2, 3; j=1, 2, 3, 4.

Кроме этого, должны быть удовлетворяться следующие условия. Число туристов, вывозимых с железнодорожного вокзала (пункт 1) равно 15, поэтому:

X₁₁ + X₁₂ + X₁₃ + X₁₄ = = 15 (3)

Аналогично для аэропорта (пункт 2):

X₂₁ + X₂₂ + X₂₃ + X₂₄ = = 25 (4)

И для морского вокзала (пункт 3):

X₃₁ + X₃₂ + X₃₃ + X₃₄ = = 5 (5)

По условию задачи в отеле “Морской” (пункт 1) забронировано 5 мест, поэтому:

X₁₁ + X₂₁ + X₃₁ = = 5 (6)

Аналогично, для отеля “Солнечный” (пункт 2):

X₁₂ + X₂₂ + X₃₂ = = 15 (7)

Для отеля “Слава” (пункт 3):

X₁₃ + X₂₃ + X₃₃ = = 15 (8)

Для отеля “Уютный" (пункт 4):

X₁₄ + X₂₄ + X₃₄ = = 10 (9)

Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи (X_ij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j (C_ij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи (в данном примере - это число туристов в исходных пунктах и число мест в пунктах назначения - отелях).

Для примера 2 таблица имеет вид (таблица 2):

Таблица 2

Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.

Для нашего примера предположим, что в аэропорт прибыло не пять, а десять туристов. Сумма чисел в последнем столбце будет равна: 15 + 25 + 10 + 50. Чтобы сбалансировать задачу вводим пятый столбец (фиктивный отель) с пятью местами. Таблица в этом случае будет иметь вид (таблица 3):

Таблица 3

3) Целевая функция. Транспортные расходы на перевозку туристов в отели вычисляются по формуле:

Z = C_ijX_ij = 10X₁₁ + 0X₁₂ + 20X₁₃ +. +18X₃₄ (10)

Окончательно транспортная задача имеет вид (таблица 2). Нужно найти такие значения переменных X_ij (i=1,2,3; j=1,2,3,4) при которых целевая функция, определяемая формулой (10), будет иметь минимальное значение и будут выполнены ограничения (1) ё (9):

X_ij 0, где X_ij - целые числа (i=1,2,3; j=1,2,3,4)

?;

?;

?;

Как и в рассмотренной выше задаче распределения ресурсов (пример 1) транспортная задача является задачей линейного программирования и может быть решена симплекс-методом. В виду специфики транспортной задачи для нее был разработан специальный метод решения - метод потенциалов (см. Л1).

II. Решение транспортной задачи в процедуре EXCEL “Поиск решения”

1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL (рис.17).

В ячейках B3: E5 введены стоимости перевозок (табл.1).

В ячейках F3: F5 находится число прибывающих туристов. А в ячейках B6: E6 находится число мест в отелях. Ячейки B8: E10 - рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи X_ij.

В ячейках F8: F10 нужно записать формулы для вычисления левых частей ограничений (3) ё (5):

в F8 должна быть сумма ячеек B8: E8;

в F9 должна быть сумма ячеек B9: E9;

в F10 должна быть сумма ячеек B10: E10.

Формулы для вычисления левых частей ограничений (6) ? (9) введем в ячейки B11: E11:

в B11 должна быть сумма ячеек B8: B10;

в C11 должна быть сумма ячеек C8: C10;

в D11 должна быть сумма ячеек D8: D10;

в E11 должна быть сумма ячеек E8: E10;

Целевую функцию поместим в ячейку G3:

G3: СУММПРОИЗВ (B3: E5; B8: E10).

Таблица исходных данных имеет вид (Рис.17):

Рис.17

2) Заполнение окна процедуры "Поиск решения".

целевая функция: G3;

значение целевой функции: min;

изменяемые ячейки: B8: E10;

ограничения задачи:

F8: F10 = F3: F5 (формулы (3) ё (5))

B11: E11 = B6: E6 (формулы (6) ё (9))

B8: E10 0 (1) и B8: E10 - целые числа (2)

В окне "Параметры" установить "Линейная модель", что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис.18:

Рис.18

Выполнив процедуру "Поиск решения" получим следующие результаты (рис. 19):

Рис. 19

Таким образом с железнодорожного вокзала (исходный пункт 1) следует 10 туристов отвезти в отель "Уютный" (пункт 4) и 5 туристов в отель "Солнечный" (пункт назначения 2); из аэропорта (исходный пункт 2) 10 туристов отвезти в отель "Солнечный" (пункт назначения 2) и 15 туристов в отель "Слава" (пункт назначения 3); туристов прибывающих на морской вокзал (исходный пункт 3) нужно отправить в отель "Морской" (пункт назначения 1). Все эти результаты видны в конечной таблице (рис. 19) При этом суммарная стоимость транспортных расходов составит 315 рублей (ячейка G3).

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

Лабораторная работа №4

ТЕМА: Создание концептуальной модели

Цель работы: Изучить понятие концептуальная модель, стартификация, детализация, локализация.

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

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

Рис.1. Отображение оригинала S_o и модели S_m в сознании исследователя

Первоначально концептуальная модель системы S_o возникает в сознании исследователя j (рис.1). Модель ориентируется на выявление определенных свойств системы в соответствии с целями моделирования. Для этого исследователь делает как бы мысленный срез системы в "плоскости" той метасистемы М, в качестве элемента которой представляет интерес система S_o, т.е. выполняет M-ориентацию. Затем исследователь выявляет основные признаки ориентированной модели и может добавить некоторые признаки и условия, которые облегчат исследование модели или позволят представить ее в виде некоторого среза моделирующей системы S_m. Концептуальная модель - это субстрат системы с позиций достижения целей моделирования.

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

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

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

Рис.2. Уровни модели

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

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

Уровни детализации иногда называются стратами, а процесс выделения уровней - стратификацией. Выбор страт зависит от целей моделирования и степени предварительного знания свойств элементов. Для одной и той же системы могут быть использованы различные страты. Обычно в модель включаются элементы одного уровня детализации - K-страта. Однако может представлять интерес построение модели из элементов разных страт. В том случае, когда общесистемные (функциональные) свойства отдельных элементов мало известны или вызывает затруднение их описание, можно для каждого такого элемента включить в модель его детализированное описание из нижестоящего (К - 1) - страта. Некоторые элементы и этого уровня можно расчленить, т.е. использовать их описание из следующего уровня - (К - 2) - страта.

При построении ориентированной и стратифицированной концептуальной модели необходимо руководствоваться следующим. В модель должны войти все те параметры системы S_ok и, в первую очередь, параметры {s_oj}, допускающие варьирование в процессе моделирования, которые обеспечивают определение интересующих исследователя характеристик Y_ok при конкретных внешних воздействиях {x_on} на заданном временном интервале Т функционирования системы. Остальные параметры должны быть, по возможности, исключены из модели.

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

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

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

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

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

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

Структуризация.

Управление.

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

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

Задание: Построить концептуальную модель следующих объектов:

1. Школа

2. Швейная фабрика

3. Университет

4. Детский сад

5. Лицей

6. Колледж

7. Больница

8. Банк

9. Поликлиника

Лабораторная работа №5

Тема: Задача Джонсона для двух станков.

Цель работы: Изучения составления расписания работы технологической линии.

Задание:

Найти оптимальное расписание для двух машин.

Составить блок - схему алгоритма Джонсона.

Составить программу на алгоритмическом языке паскаль.

Теоретическая часть

Имеется два станка и n деталей, каждая из которых должна пройти обработку с начала на первой, а затем на второй машине. Время операции j - й детали на первом станке обозначим через a_j, на втором - через b_j. Требуется дать расписания которое минимизирует общее время обработки всех деталей.

Алгоритм Джонсона для получения оптимального расписания. Идея его состоит в стремление максимально сократит простой второй машины полном исключении прерываний и искусственных простоев первой. Запиваем числа a_j и b_j в табл.1

Просматриваем продолжительности работ a_j и b_j, j=1,n и находим среди них наименьшую.

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

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

Вычеркиваем столбец соответствующий этой детали.

Процесс повторяется в отношении оставшихся деталей.

Если попадаются равные числа, то для определенности деталь с меньшим индексом располагается первой. В случае же равенства a_j и b_j парядок деталей устанавливается по первой машине.

Пример. Найти оптимальное расписание для двух машин. (Табл.2)

Рис 2

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

Подставим над столбцом 5 "птичку" или вычеркнем его.

В оставшейся матрице ищем минимальные элемент (6). Согласно пункту (6) алгоритма, деталь с меньшим индексом следует располагать первой.

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

Точно так же устанавливается порядок обработки остальных. На рис.2 представлен линейный график оптимального расписания (график Ганта).

Таким образом, время простоя (на графике заштрихованная часть) второй равно a₁₀=6 (единиц). Общее время прохождения всех работ:

a₁₀+ (b₁+b₂+…+b₁₀) =6+151=157 (единиц)

Содержания отчёта

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

Алгоритм расчёта. (блок - схема)

Листинг программы и результата вычислений

Контрольные вопросы.

Для каких случаев решена задача Джонсона

Описание задача Джонсона

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

Лабораторная работа №6

1. Налимов В.В. Теория эксперимента. М., Наука, 1971. - 207 с.

2. Налимов В.В., Голикова Т.И. Логические основания планирования эксперимента М.: Металлургия, 1981. - 151 с.

3. Федоров В.В. Теория оптимального эксперимента. М., Наука, 1971.

4. Лотов А.В. Введение в экономико-математическое моделирование. - М.: Наука, 1984. - 392 с.

5. Вознесенский В.А. Статистические методы планирования эксперимента в технико-экономических исследованиях. - М.: Финансы и статистика, 1981. - 263 с.

6. Тихонов А.И., Уфимцев М.В. Статистическая обработка результатов экспериментов. - М.: Моск. Ун-т, 1988. - 174 с.

Размещено на Allbest.ru