Контрольная работа по "Моделирование"

Задание 1

Определение модели. Моделирование  как метод исследования систем. Этапы  моделирования.

 

Моде́ль (фр. modèle, от лат. modulus — «мера, аналог, образец») — это упрощенное представление  реального устройства и/или протекающих  в нем процессов, явлений.

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

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

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

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

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

На основе теоретического анализа процесса с использованием основных законов физики, химии и  других естественных или экономических  наук;

На основе данных активного или пассивного эксперимента.

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

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

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

Этапы моделирования

Этап 1. Постановка задачи.

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

- описать задачу,

- определить цели моделирования,

- проанализировать объект или процесс.

Описание задачи.

Задача формулируется  на обычном языке, и описание должно быть понятным. Главное здесь —  определить объект моделирования и  понять, что должен представлять собой результат.

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

Познание окружающего  мира.

Зачем человек  создает модели? Чтобы ответить на этот вопрос, надо заглянуть в далекое  прошлое. Несколько миллионов лет  назад, на заре человечества, первобытные  люди изучали окружающую природу, чтобы  научиться противостоять природным стихиям, пользоваться природными благами, просто выживать. Накопленные знания передавались из поколения в поколение устно, позже письменно, наконец с помощью предметных моделей. Так родилась, к примеру, модель земного шара — глобус, — позволяющая получить наглядное представление о форме нашей планеты, ее вращении вокруг собственной оси и расположении материков. Такие модели позволяют понять, как устроен конкретный объект, узнать его основные свойства, установить законы его развития и взаимодействия с окружающим миром моделей.

Создание объектов с заданными свойствами (задача типа «Как сделать, чтобы...»).

Накопив достаточно знаний, человек задал себе вопрос: «Нельзя ли создать объект с заданными  свойствами и возможностями, чтобы  противодействовать стихиям или ставить себе на службу природные явления?» Человек стал строить модели еще не существующих объектов. Так родились идеи создания ветряных мельниц, различных механизмов, даже обыкновенного зонтика. Многие из этих моделей стали в настоящее время реальностью. Это объекты, созданные руками человека.

Определение последствий  воздействия на объект и принятие правильного решения (задача типа «Что будет, если...»: что будет, если увеличить  плату за проезд в транспорте, или  что произойдет, если закопать ядерные отходы в такой-то местности?)

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

Эффективность управления объектом (или процессом).

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

Анализ объекта.

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

Этап 2. Разработка модели.

Информационная  модель.

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

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

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

Информационные  модели играют очень важную роль в  жизни человека.

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

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

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

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

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

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

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

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

Знаковая модель.

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

Компьютерная  модель

— это модель, реализованная средствами программной среды.

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

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

Основные функции  компьютера при моделировании систем:

исполнение  роли вспомогательного средства для  решения задач, решаемых и обычными вычислительными средствами, алгоритмами, технологиями;

исполнение  роли средства постановки и решения  новых задач, не решаемых традиционными средствами, алгоритмами, технологиями;

исполнение  роли средства конструирования компьютерных обучающих и моделирующих сред типа: «обучаемый — компьютер — обучающий», «обучающий — компьютер — обучаемый», «обучающий — компьютер — группа обучаемых», «группа обучаемых — компьютер — обучающий», «компьютер — обучаемый — компьютер»;

исполнение роли средства моделирования для получения  новых знаний;

«обучение» новых моделей (самообучение моделей).

Этап 3. Компьютерный эксперимент.

Компьютерное  моделирование — основа представления  знаний в ЭВМ. Компьютерное моделирование  для рождения новой информации использует любую информацию, которую можно  актуализировать с помощью ЭВМ. Прогресс моделирования связан с  разработкой систем компьютерного моделирования, а прогресс в информационной технологии — с актуализацией опыта моделирования на компьютере, с созданием банков моделей, методов и программных систем, позволяющих собирать новые модели из моделей банка.

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

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

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

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

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

Этап 4. Анализ результатов моделирования.

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

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

Как говорит  народная мудрость, на ошибках учатся.

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2

Двойственные  задачи в ЛП. Вторая теорема двойственности, т. е. условия о

дополняющей нежесткости, соответствие между переменными  прямой и

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

Определение: Две задачи линейного программирования называются взаимнодвойственными, если они обладают следующими свойствами:

1. В одной  задаче ищется максимум, а в  другой минимум целевой функции.

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

3. В каждой  задаче система ограничений задаётся  в виде неравенств, причём все они одного смысла, а именно: в задаче, в которой ищется максимум линейной формы, все неравенства вида "<=", а в задаче, в которой находится минимум линейной формы, противоположного смысла, т.е.">=".

4. Коэффициенты  при переменных систем ограничений описываются матрицами, транспонированными относительно друг друга.

5. Число неравенств  в системе ограничений одной  задачи совпадает с числом  переменных в другой задаче.

6. Условия не  отрицательности переменных сохраняются  в обеих задачах.

Отсюда вытекает правило составления задачи, двойственной к исходной.

Необходимо  привести неравенства системы ограничений  исходной задачи к одному виду.

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

Пример:

Вторая теорема  двойственности или теорема о  дополняющей нежесткости.

Для того чтобы  планы х* и у* пары двойственных задач  были оптимальными, необходимо и достаточно выполнение условий:

Из условий следует:

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

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

Соответствие  между переменными прямой и двойственной задач

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

Экономическая интерпретация дополнительных переменных двойственной задачи

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3

Решить транспортную задачу (200;150;150) i a_i - запас единиц груза i-го поставщика, B_j - потребность единиц груза j-го потребителя,

Решение.

Обозначим объем  продукции доставленный от поставщика A_i потребителю B_j через X_i,j . Суммарные потребности потребителей 90+100+70+130+110=500 равны суммарным запасам 200+150+150=500 продукции всех поставщиков. Имеем транспортную задачу закрытого типа. Опорный план находим методом северо-западного угла.

Записываем в левый нижний угол клетки А₁В₁ – 90 ед. продукции. Потребности полностью удовлетворены. Столбец В₁ вычеркиваем. У поставщика А₁ осталось 110 ед. продукции. Удовлетворим потребности 2-го потребителя B₂ за счет запаса поставщика А₁.

Записываем  в левый нижний угол клетки А₁В₂ – 100 ед. продукции. Потребности полностью удовлетворены. Столбец В₂ вычеркиваем. У поставщика А₁ осталось 10 ед. продукции. Записываем в левый нижний угол клетки А₁В₃ – 10 ед. продукции. Запасы полностью исчерпаны. Строку А₁ вычеркиваем.

Удовлетворяем потребителя B₃ за счет запаса поставщика А₂. Записываем 60 ед. в клетку А₂B₃. Потребности полностью удовлетворены. Столбец В₃ вычеркиваем. У поставщика А₂ осталось 90 ед. продукции. Записываем в левый нижний угол клетки А₂В₄ – 90 ед. продукции. Запасы полностью исчерпаны. Строку А₂ вычеркиваем.

Удовлетворяем потребителя B₄ за счет запаса поставщика А₄. Записываем 40 ед. в клетку А₃B₄. Потребности полностью удовлетворены. Столбец В₄ вычеркиваем. У поставщика А₃ осталось 110 ед. продукции. Записываем в левый нижний угол клетки А₃В₅ – 110 ед. продукции. Потребности полностью удовлетворены и запасы исчерпаны. Столбец В₅ и строку А₃ вычеркиваем.

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

Число занятых  клеток должно быть равно m+ n-1= 3+5-1= 7. В нашем случае число занятых клеток равно 7. Имеем невырожденный план.

Построенному  опорному решению отвечают затраты:

Проверим полученный опорный план на оптимальность. Находим потенциалы: U_i и V_j . Для каждой базисной переменной X_i,j потенциалы удовлетворяют условию U_i + V_j = c_i,j. Имеем систему

Теперь для  небазисных клеток найдем оценки  S _I,j=C_i,j-(U_i + V _j). Оценки запишем в левый нижний угол (красный цвет). Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-8) стоит в ячейке А₁В₅.

Вводим в  базис переменную  X₁₅ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(10,190;110) =10 : прибавляя 10 к значениям в клетках со знаком «+» и вычитая 10 из значений в клетках со знаком «-».

Теперь для  небазисных клеток найдем оценки S _I,j=C_i,j-(U_i + V_j).. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-9) стоит в ячейке А₂В₂. Вводим в базис переменную  X₂₂ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(100,80;100) =80 : прибавляя 80 к значениям в клетках со знаком «+» и вычитая 80 из значений в клетках со знаком «-».

Теперь для  небазисных клеток найдем оценки S _I,j=C_i,j-(U_i + V_j). Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка (-2) стоит в ячейке А₃В₂. Вводим в базис переменную X₃₂ и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+». Выбираем наименьшее значение из клеток со знаком «-» min(20,20) =20 : прибавляя 20 к значениям в клетках со знаком «+» и вычитая 20 из значений в клетках со знаком «-».

Так как среди  оценок нет отрицательных, то план оптимален.

Согласно плану  перевозок 1-ый поставщик отправляет 90 ед. продукции первому потребителю и 110 ед. продукции пятому потребителю.

2-ой поставщик отправляет 80 ед. продукции второму потребителю и 70 ед. продукции третьему потребителю.

3-ий поставщик  отправляет 20 ед. продукции второму  потребителю, 130 ед. продукции четвертому потребителю.

Суммарные затраты  при этом f _min =6520.

 

 

 

 

 

 

Список используемой литературы

1. http://www.pereplet.ru/obrazovanie/stsoros/655.html
2. http://www.structuralist.narod.ru/dictionary/mathprog.htm