Демо (html) Моделирование систем

Смоделировать оптимальный план, если известна транспортная таблица

Все условия задачи отобразим в таблице (рисунок 1):

- пункты отправления и назначения,

- запасы, имеющиеся в пунктах отправления,

- заявки, поданные пунктами назначения,

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

Таблица 1

Рисунок 1. Транспортная таблица

В этой таблице пункты назначения обозначены - A1,…, Aj, …,An, a B1, …, Bi,…,Bm – это пункты отправления, т.е. m пунктов отправления и n пунктов назначения.

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

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного плана. Проведем нахождение опорного плана методом «северо-западного угла».

Для чего создадим таблицу, показанную на рисунке 2.

Рисунок 2. Таблица для определения опорного плана перевозок

Шаг 1. Если b1 < a1 , то из В1 вывозится полностью весь груз в А1, а недостающие (a1 - b1 ) единиц груза попытаемся довезти из следующего пункта отправки, т.е. В2. Если (a1 - b1 ) больше, чем имеющийся груз в В2, то переходим к Шагу 1( но уже рассматриваем пункт отправки В2 вместо В1) и т.д. После того как заявка А1 будет удовлетворена полностью, переходят к удовлетворению заявки следующего пункта назначения, т.е. А2. Причем эту заявку начинают удовлетворять грузом из первого по порядку пункта отправления с ненулевым грузом. Если (a1 - b1 ) < b2 , то переходим к шагу 2

Шаг 2. Если b1 > a1 , то из В1 вывозится a1 единиц груза в А1, и в В1 останется (b1 -a1) единиц груза. После этого заявка А1 будет удовлетворена полностью, а в В1 останется (b1 - a1) единиц груза. Этим остаточным грузом необходимо удовлетворить следующую заявку, т.е. заявку А2. Если этот остаточный груз в В1 меньше, чем заявка А2, то переходим к шагу 1, иначе переходим к шагу 2.

Шаг 3. Если b1 = a1, то груз из В1 полностью перевозится в пункт А1, удовлетворяя заявку А1. Затем начинают удовлетворять заявку А2 из пункта отправления В2 и выполняют либо шаг 1, либо шаг 2.

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

План

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

-Транспортная задача линейного программирования. Основные понятия

-Транспортная задача с неправильным балансом

-Алгоритм определения опорного плана транспортной задачи методом «северо-западного угла»

-Алгоритм нахождения оптимального плана методом наименьших затрат

-Алгоритм нахождения оптимального плана методом потенциалов

2.Моделирование решений транспортной задачи

-Моделирование опорного плана транспортной задачи методом «северо-западного угла»

-Моделирование оптимального плана транспортной задачи методом потенциалов

3.Контрольный пример

Цель: изучить на практическом примере процесс моделирования транспортной задачи линейного программирования.

Результат обучения:

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

Список рекомендуемой литературы:

• Бережная В., Бережной В.И. Математические методы моделирования экономических систем. 2-е изд., перераб. И доп. – М.: Финансы и статистика, 2006.
• Васильев Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. Изд-во КноРус, 2011.
• Поршнев С.В. Компьютерное моделирование физических процессов с использованием пакета MathCad. –М.:, 2004.
• Советов Б.Я., Яковлев С.А. Моделирование систем. Изд-во Высшая школа, 2009.

Используемые программы:

OpenOffice.org Calс

Табличный процессор OpenOffice.org Calс– программа, предназначенная для ввода и обработки данных.

Смоделировать оптимальный план для заданной транспортной таблицы

Смоделировать оптимальный план для заданной транспортной таблицы

Смоделировать оптимальный план для заданной транспортной таблицы

Смоделировать оптимальный план, если известна транспортная таблица

Выполнить расчет сетевого графика и ответить на вопросы

Выполнить расчет сетевого графика и ответить на вопросы

Выполнить расчет сетевого графика и ответить на вопросы

Выполнить расчет сетевого графика и ответить на вопросы

Выполнить расчет сетевого графика и ответить на вопросы

Для построения модели расчета сетевого графика заданного комплекса работ в OpenOffice.org Calс переименуем лист1 на <Сетевой график> и на этом листе, начиная с ячейки А1, заполним таблицу 1

Таблица 1.

Рисунок 3 . Таблица комплекса работ

Таблица 2

Рисунок 4. Упорядочение таблицы комплекса работ

Таблица 3

Рисунок 5. Упорядоченная таблица комплекса работ

Построим таблицу 4 для расчета параметров сетевого графика работ в диапазоне О2:АС12. Введем моделирующие формулы в ячейки таблицы 4, начиная с ячейки U3. Формулы приведены в таблице 5

Таблица 3

Таблица 4 Расчет сетевого графика работ

План

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

- Задача планирования комплекса работ. Основные понятия

- Упорядочение структурной таблицы

-Сетевой график комплекса работ

• Построение и расчет сетевого графика комплекса работ

- Временной сетевой график комплекса работ

- Алгоритм расчета сетевого графика

• Контрольный пример

Цель: изучить на практическом примере процесс моделирования задачи управления комплексом работ

Результат обучения:

получить навыки расчета сетевого графика

Список рекомендуемой литературы:

• Бережная В., Бережной В.И. Математические методы моделирования экономических систем. 2-е изд., перераб. И доп. – М.: Финансы и статистика, 2006.
• Васильев Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. Изд-во КноРус, 2011.
• Поршнев С.В. Компьютерное моделирование физических процессов с использованием пакета MathCad. –М.:, 2004.
• Советов Б.Я., Яковлев С.А. Моделирование систем. Изд-во Высшая школа, 2009.

Используемые программы:

OpenOffice.org Calс

Табличный процессор OpenOffice.org Calс– программа, предназначенная для ввода и обработки данных.

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

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

- действительная работа – трудовой процесс, требующий затрат времени и ресурсов;

- ожидание – процесс, не требующий затрат труда, но занимающий время;

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

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

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

Названия обычно записываются в «Перечне работ»

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

Можно установить следующие шесть основных правил построения сети:

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

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

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

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

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

- В сети не может быть тупиков, т.е. промежуточных событий, из которых не выходит ни одной работы и в которые не входит ни одна работа.

На рисунке показан сетевой график, где события обозначены А0, А1, А2, …, работы а1, а2, … .

Исходное событие А0 означает «начало работ» или «принятие решения о начале работ». Совместное выполнение работ а1 и а2 изображено дополнительным событием А1,2 в которое ведут пунктирные стрелки, не изображающие никаких работ, а означающие только логическую связь. Из события А1,2 исходит стрелка а4, изображающая работу а4, опирающуюся на работы а1 и а2 и в конце стрелки стоит событие А4, означающий выполнение работы а4.Завершающее событие А означает конец всего комплекса работ.

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

Таблица 5

Формулы для ввода в ячейки при построении модели расчета параметров сетевого графика работ

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

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

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

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

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

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

Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

- Задача оптимизации интерпретируется как n-шаговый процесс управления.

- Целевая функция равна сумме целевых функций каждого шага.

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

- Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk (отсутствие последействия).

- На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk- от конечного числа параметров.

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

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

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

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

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

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

первый раз — от конца к началу, в результате чего находятся решения на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса;

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

Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется результат, зависящий от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

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

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

План

• Теоретическая часть
  • Общая постановка задачи динамического программирования
  • Алгоритм решения задачи динамического программирования
  • Некоторые конкретные задачи динамического программирования
• Разработка модели определения оптимального маршрута
  • Постановка задачи
  • Ввод моделирующих формул
• Контрольный пример

Цель: изучить на практическом примере процесс построения модели решения задачи динамического программирования

Результат обучения:

получить навыки моделирования оптимальных решений

Список рекомендуемой литературы:

• Бережная В., Бережной В.И. Математические методы моделирования экономических систем. 2-е изд., перераб. И доп. – М.: Финансы и статистика, 2006.
• Васильев Л.Н., Деева Е.А. Моделирование микроэкономических процессов и систем. Изд-во КноРус, 2011.
• Поршнев С.В. Компьютерное моделирование физических процессов с использованием пакета MathCad. –М.:, 2004.
• Советов Б.Я., Яковлев С.А. Моделирование систем. Изд-во Высшая школа, 2009.

Используемые программы:

OpenOffice.org Calc

Табличный редактор OpenOffice.org Сalc – программа, предназначенная для ввода и обработки числовых данных.

При размещении расчетной таблицы (таблица 1), начиная с ячейки “B6”, формулы в желтых ячейках будут следующие:

Таблица 5

При размещении графической таблицы, начиная с ячейки “B19”, формулы будут соответствовать следующим: