Моделирование задач линейного программирования в среде МС EXCEL

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

Порядок установки для Офиса 2003:

- выбрать режим " Сервис",

- выбрать " Настройки",

- установить " Поиск решений".

Порядок установки для Офиса 2007:

- войти в " Офис",

- войти в " Параметры EXCEL",

- выбрать " Надстройки",

- выбрать " Поиск решения",

- выбрать " Перейти",

- отметить галочкой " Поиск решения",

- нажать ОК,

- произвести перезагрузку,

- в " Данных" должен появиться режим " Поиск решения".

 

Модель задачи в среде EXCEL реализуется в виде таблиц. В качестве примера рассмотрим задачу выпуска продукции (приведенную в разделе 4.2. ). Необходимо определить план выпуска двух видов продукции для получения максимальной прибыли. Трудозатраты на производство продукции А – 20ч., продукции В – 10ч. Недельный лимит трудозатрат – 400 ч. Максимальный объем выпуска продукции А - 15 ед., продукции В - 30 ед. в неделю. Прибыль от реализации 1ед. продукции А – 50у.е.; В - 40у.е.

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

 

Таблица 6

Прод.	Надо выпустить	На ед. продукции	На всю продукцию
Трудозатраты	Прибыль	Трудозатраты	Прибыль
А	Х1			20х1	50х1
В	Х2			10х2	40х2
Всего				∑	∑

 

Целевая ячейка.

 

Числовые данные постановки заносятся в таблицу EXCEL. Ячейки х₁ и х₂ остаются свободными и указываются в экранной форме " Поиск решения" в качестве переменных. В остальные ячейки (выделены цветом) необходимо занести формулы, отображающие связи и отношения между числами модели.

Заполняем окна экранной формы:

· - " Установить целевую ячейку: " – вносим адрес целевой ячейки.

· - " Равной: " – устанавливаем максимальное значение целевой функции.

· - " Изменяя ячейки: " – указываем адреса переменных х₁ и х₂ .

· - " Ограничения: " – вносим ограничения модели.

· - " Выполнить".

Окно «Поиск решения» с занесенной информацией выглядит следующим образом (рис. 14).

Рис. 14 Экранная выдача режима " Поиск решения"

 

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

 

ТЕМА 5

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

5.1. Объекты имитационного моделирования.

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

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

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

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

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

Суть имитационного подхода раскрывается в самом названии. Мы имитируем процесс функционирования системы во времени.

Отличительной чертой любой имитационной модели является структурное сходство с самой системой.

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

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

Стохастичность - неизбежное свойство реальных сложных систем.

5.2. Оптимизация решения задач моделирования

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

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

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

 

5.3. Метод Монте-Карло

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

Например. Построим модель процесса стрельбы спортсмена по мишени. Пусть известно из опыта, что вероятность Р попадания его в цель составляет 0, 8. Тогда, используя датчик (или таблицу) случайных чисел на отрезке 0-1, выбираем случайное число R. Если выпадет число больше 0, 8, то спортсмен попал в мишень (состоялось событие А). Если меньше 0, 8, то произошел промах (состоялось событие Ā ).

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

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

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

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

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

При моделировании случайных процессов методом Монте-Карло сама случайность используется как аппарат исследования.

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

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

Приведем пример, когда метод Монте-Карло возможен, но не рационален. Пусть спортсмен производит несколько независимых выстрелов по мишени. Каждый выстрел попадает в мишень (событие А) с одинаковой вероятностью Р(А). Требуется найти вероятность хотя бы одного попадания.

Модель процесса попадания в мишень хотя бы одним выстрелом можно представить в аналитическом виде

Р=1 - (1-Р(А))ⁿ.

Рассмотрим частный случай, когда Р(А)=0, 5, а количество выстрелов равно 3. Тогда

Р=1- 0, 5³= 7/8.

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

А вот пример задачи, которую аналитически решать крайне сложно - задача о «случайном блуждании». Прохожий решил прогуляться, стоя на углу пересечения улиц. Пусть вероятность того, что, достигнув очередного перекрестка, он пойдет на север, юг, восток и запад, одинакова. Спрашивается, какова вероятность того, что пройдя 10 кварталов, прохожий окажется не далее 2 кварталов от места, где он начал прогулку?

Количество исходов на каждом перекрестке равно 4. Тогда общее количество исходов равно 4¹⁰. Эту задачу модно решить только имитацией – розыгрышем. Другими методами ее решить практически невозможно.

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

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

 

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

Поделиться:

Популярное:

1. I. ЦЕЛИ И ЗАДАЧИ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ
2. I.6. Педагогика как учебный предмет и задачи профессионального
3. III.10 Задачи на сцепление генов
4. III.2 Задачи на моногибридное скрещивание
5. III.8 Задачи на взаимодействие неаллельных генов
6. Q Задача об аренде оборудования: постановка задачи и методы решения
7. Административно-процессуальное право: предмет, метод и задачи. Источники административно-процессуального права. Система а-п права. Административно-процессуальные нормы в системе норм права.
8. Административное расследование: задачи, место и сроки проведения.
9. Асинхронные задачи интерфейса с устройствами ввода/вывода.
10. Билет № 28. Комбинаторные задачи. Виды и формулы для подсчёта числа возможных комбинаций.
11. Блок программирования, регуляции и контроля двигательной деятельности
12. В инициативной активности при постановке изобразительной задачи