Метод имитационного моделирования


--[[Участник:Artix|Artix]] 22:39, 16 января 2011 (UTC)

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

В рамках имитационного моделирования применяются несколько инструментов, помогающих
 решать задачи. Это - множества, последовательности, графы, сети Петри, а также
 событийные модели. Вот пример последних мне и хотелось бы привести здесь. Задача
 состоит в том, что в пункте А находится 20 тонн груза и его нужно доставить в
 пункт Б. Есть три грузовика, которые за один заезд могут доставить 1 тонну груза.
 В ходе перевозки заданы временные задержки, которые определены не четко - задержка
 погрузки, задержка доставки груза, задержка разгрузки и задержка перегона пустого
 автомобиля в пункт А.

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

/*///////////////////////////////////////////////////////////////

 IMMITACIO, PHP, 2011-01-01
 
 Artix, master@7masterov.ru, icq:53666599, skype:artixmaster
 
 * Error in code? Nothing is perfect!
 * Free source for free Linux, use it for free!
 * Please, do not remove this comment!

///////////////////////////////////////////////////////////////*/

// Задача - перевезти 20 тонн груза из А в Б
// Сколько времени потребуется для перевозки?
// Одна машина перевозит 1 тонну груза
// Время загрузки - от 10 до 25 мин
// Время доставки - от 25 до 30 мин
// Время разгрузки - от 10 до 15 мин
// Время перегона без груза - от 10 до 15 мин

// Максимальное число итераций - страховка
define("MAX_LOOPS", 10000);


// Ресурс - некоторые убывающие или возрастающие данные
class Resource {

    public $data;

    function __construct($data) { $this->data = $data; }
}

// Событие = текущее состояние + процедура перехода в новое состояние
class Event {
    private $Name;
    private $finishTime;
    private $onFinish;
    private $data;
    
    function __construct($name, $time, $callback, $data = null) {
        // Наименование текущего состояния
        $this->Name = $name;
        // Время окончания состояния
        $this->finishTime = $time;
        // Процедура перехода в другое состояние
        $this->onFinish = $callback;
        // Вспомогательные данные текущего состояния
        $this->data = $data;
    }
    
    // Показ текущего состояния
    public function show() {
        echo sprintf("%4s : %s (%s)\n", $this->finishTime, $this->Name, $this->onFinish);
    }
    
    // Срабатывание события перехода при завершении текущего состояния
    public function runCallback($monitor) {
        $func = $this->onFinish;
        if ($func!='') $func($monitor,$this->data);
    }
    
    // Поправка монитора - установка глобального времени
    public function syncTime($globalTime) { $this->finishTime += $globalTime; }
    
    // Получение времени окончания события
    public function getTime() { return $this->finishTime; }
}



// Главный класс - монитор событий
class Monitor {
    
    private $GlobalTime;
    private $eventList;
    private $resourceList;
    private $stageChanged;
    
    // Начальная инициализация
    public function Initialize() {
        $this->GlobalTime = 0;
        $this->clearEvents();
        $this->clearResources();
        $this->stageChanged = true;
    }
   
    // Показ очереди событий
    private function showQueue() {
        if ($this->stageChanged) {
            echo sprintf("[GLOBAL_TIME = %s], [PLAN LIST]\n",$this->GlobalTime);
            foreach($this->eventList as $event) {
                $event->show();
            }
            echo "\n";
            $this->stageChanged = false;
        }
    }
   
    // Проверка на срабатывание и запуск событий в очереди
    private function runQueue() {
        foreach($this->eventList as $key => $event) {
            if ($event->getTime()==$this->GlobalTime) {
                unset($this->eventList[$key]);
                $event->runCallback($this);
            }
        }
    }
    
    // Добавление события в очередь
    public function addEvent(Event $e) {
        $this->stageChanged = true;
        $e->syncTime($this->GlobalTime);
        $this->eventList[] = $e;
    }
    
    // Очистка очереди событий
    public function clearEvents() {
        $this->eventList = array();
    }
    
    // Очистка реестра ресурсов
    public function clearResources() {
        $this->resourceList = array();
    }
    
    // Добавление ресурса в реестр
    public function addResource($name, $resource) {
        $this->resourceList[$name] = $resource;
    }
    
    // Получение ресурса
    public function getResource($name) {
        return $this->resourceList[$name];
    }
   
    // Запуск монитора на выполнение
    public function Run() {
        while(count($this->eventList) && $this->GlobalTime<MAX_LOOPS) {
            $this->runQueue();
            $this->showQueue();
            $this->GlobalTime++;
        }
        print_r($this->resourceList);
    } 
}


// Главная программа


// Вернулись за грузом, начинаем загружаться
function FinGoingBack($monitor,$data) {
    $resource = $monitor->getResource("transfer");
    $resource->data["transferCount"]++;

    $resource = $monitor->getResource("point A");
    if ($resource->data["volume"]>0) {
        $monitor->addEvent(new Event("Loading car $data with package ".$resource->data['volume'],rand(10,25),"FinLoad",$data));
        $resource->data["volume"]--;
    }
}

// Закончили разгрузку, возвращаемся за грузом
// Если, конечно, грузы еще есть
function FinUnload($monitor,$data) {
    $r = $monitor->getResource("point B");
    $r->data['volume']++;
    
    $resource = $monitor->getResource("point A");
    if ($resource->data['volume'])
        $monitor->addEvent(new Event("Car $data going back from B to A",rand(10,15),'FinGoingBack',$data));
}

// Закончили транспортирование, приступаем к разгрузке
function FinTransport($monitor,$data) {
    $resource = $monitor->getResource("transfer");
    $resource->data["transferCount"]++;
    $monitor->addEvent(new Event("Unloading car $data",rand(15,20),'FinUnload',$data));
}

// Закончили загрузку, транспортируем груз
function FinLoad($monitor,$data) {
    $resource = $monitor->getResource("point A");
    $monitor->addEvent(new Event("Transporting car $data from A to B",rand(25,30),'FinTransport',$data));
}

$m = new Monitor;
$m->Initialize();
// Добавляем ресурсы:
// В пункте А - 20 тонн груза
$m->addResource("point A", new Resource(array(
    "volume" => 20
)));
// В пункте Б - пусто
$m->addResource("point B", new Resource(array(
    "volume" => 0
)));
// Статистический ресурс - число перегонов между городами
$m->addResource("transfer", new Resource(array(
    "transferCount" => 0
)));
// Берем три груза
$resource = $m->getResource("point A");
$resource->data["volume"]-=3;
// И отправляем три грузовика
$m->addEvent(new Event("Loading car 1",rand(10,25),"FinLoad",1));
$m->addEvent(new Event("Loading car 2",rand(10,25),"FinLoad",2));
$m->addEvent(new Event("Loading car 3",rand(10,25),"FinLoad",3));
$m->Run();

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

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