Исследование операций. Lab4. Сети

Задание:

Пример 6.2.1. (Замена оборудования) Фирма по прокату автомобилей планирует замену автомобильного парка на очередные пять лет. Автомобиль должен проработать не менее одного года, прежде чем фирма поставит вопрос о его замене. В таблице 6.1 приведены стоимости замены автомобилей (в тысячах долларов), зависящие от времени замены и числа лет в течение которых автомобиль находится в эксплуатации.

 

 

Эту задачу можно представить на сети в следующем виде. Каждому году ставится в соответствие определенный узел. «Длина» дуги, соединяющей два узла, равна соответствующей стоимости замены из табл.6.1.

 

таблица 6.1

  1 2 3 4 5
1   4,0 5,4 9,8 13,7
2     4,3 6,2 8,1
год    3       4,8 7,1
4         4,9

 

Сеть изображена на рис. 6.4. Задача сводится к нахождению кратчайшего «пути» между узлами 1 и 5.

Сеть для нахождения кратчайшего пути

Оптимальное решение дает путь 1 2 5 со стоимостью 4+8.1=12.1 тыс. долл. Это означает, что каждый автомобиль заменяется через два года, а через пять — списывается.

 

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

 

Решение:

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

Сеть2 для нахождения кратчайшего пути

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

 

Файл с данными «Data.m»:

Главный файл «lab4.m»:

Программа, реализующая алгоритм Дейкстры «MinimumWay»:

Программа вывода на экран «MWWriteDecision.m»:

В результате работы программы получим:

 

 

1-viy uzel — 1

2-viy uzel — 3

3-viy uzel — 5

Stoimost — 1.350000e+001

 

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

 

Вывод :

Мы изучили алгоритм Дейкстры, с помощью которого можно найти минимальный «путь».

Скачать ZIP-архив с исходными кодами

 


Поделиться:
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован.

*