Оснащение арм сотрудников автотранспортного предприятия

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

Таблица 1

№ варианта	Последняя цифра шифра
	1	2	3	4	5	6	7	8	9	0
Подраз-деление	Бухгалте-рия		Диспетчер-ская		Произв.-технич.		Ремонтная зона		Планово-эконом.

Таблица 2

№ варианта	Предпоследняя цифра шифра
	1	2	3	4	5	6	7	8	9	0
Предельная сумма расхода (тыс. у.е.)	6.5	7	8	9	10	11	12	13	14	16
Число сотрудников	4	5	6	7	7	7	8	8	8	9

В работе должны быть представлены:

1. Схема локальной сети с указанием ее составных элементов с обоснованием выбора той или иной топологии.

1. Состав технических средств и их основные характеристики (табл.3).

2. Перечень программного обеспечения.

Таблица 3

Должность сотрудника	Кол-во	Технические характеристики	Стоимость одного экземпляра	Общая стоимость
…	…	…	…	…

Предоставленные средства должны быть израсходованы полностью.

Контрольная работа №2

Задача №1

Решение транспортной задачи в виде сетевой модели без ограничения пропускной способности сети

Рассматривается транспортная сеть с конечным числом коммуникаций. На рис. 1. представлена сеть с 11-ю вершинами (n = 11) и 17-ю дугами (m = 17). Расстояние между соседними вершинами Сij, соединенными дугами (прямоугольниками обозначены пункты отправления, а кружками — пункты доставки товаров) приведены в табл. 1. Размеры ресурсов Q_ri приведены в табл. 2, фондов (потребности) Q_ni в табл. 3. Необходимо распределить грузопотоки таким образом, чтобы минимизировать расстояния перевозок продукции.

1

10

6

Рис. 1. Транспортная сеть с конечным числом коммуникаций

Таблица 1

Расстояния между вершинами

Рассто-яния, км	Предпоследняя цифра шифра
	0	1	2	3	4	5	6	7	8	9
С1-2	90	100	110	120	130	140	150	160	170	180
С2-3	40	50	60	70	80	90	100	110	120	130
С3-4	80	90	100	110	120	130	140	150	160	170
С4-5	60	70	80	90	100	110	120	130	140	150
С5-6	50	60	70	80	90	100	110	120	130	140
С6-7	90	100	110	120	130	140	150	160	170	180
С7-8	70	80	90	100	110	120	130	140	150	160
С8-9	80	90	100	110	120	130	140	150	160	170
С1-9	60	70	80	90	100	110	120	130	140	150
С1-10	80	90	100	110	120	130	140	150	160	170
С3-10	110	120	130	140	150	160	170	180	190	200
С3-11	60	70	80	90	100	110	120	130	140	150
С5-11	70	80	90	100	110	120	130	140	150	160
С6-10	130	140	150	160	170	180	190	200	210	220
С7-10	110	120	130	140	150	160	170	180	190	200
С9-10	120	130	140	150	160	170	180	190	200	210
С10-11	80	90	100	110	120	130	140	150	160	170

Таблица 2

Размер ресурсов груза

Последняя цифра шифра	Количество груза, т
	Qr1	Qr6	Qr10
0	300	260	160
1	400	280	120
2	420	310	150
3	480	250	230
4	520	300	220
5	570	310	240
6	600	330	270
7	620	340	320
8	650	370	340
9	700	390	350

Таблица 3

Размер потребностей в грузе

Послед-няя цифра шифра	Количество груза, т
	Qn2	Qn3	Qn4	Qn5	Qn7	Qn8	Qn9	Qn11
0	130	160	90	40	90	80	90	40
1	140	170	100	50	100	90	100	50
2	150	180	110	60	110	100	110	60
3	160	190	120	70	120	110	120	70
4	170	200	130	80	130	120	130	80
5	180	210	140	90	140	130	140	90
6	190	220	150	100	150	140	150	100
7	200	230	160	110	160	150	160	110
8	210	240	170	120	170	160	170	120
9	220	250	180	130	180	170	180	130

Рассмотрим решение на примере. Рассматривается транспортная сеть с конечным числом коммуникаций. На рис. 2. представлена сеть с 11-ю вершинами (n = 11) и 17-ю дугами (m = 17). На каждой дуге поставлено число, характеризующее расстояние Сij между соседними вершинами, соединенными дугами (прямоугольниками обозначены пункты отправления, а кружками — пункты доставки товаров). В круглых скобках против каждой вершины отмечены размеры ресурсов со знаком плюс и фондов (потребности) со знаком минус. Необходимо распределить грузопотоки таким образом, чтобы минимизировать расстояния перевозок продукции.

Рис. 2. Транспортная сеть с конечным числом коммуникаций

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

Шаг 2. Присваиваем потенциалы вершинам. Например, вершине 1 — любой достаточно большой потенциал (допустим 100), чтобы впоследствии не иметь дело с отрицательными числами. Назначаем потенциалы остальным вершинам, придерживаясь следующего правила: при продвижении по дугам сети в направлении следования грузопотока к потенциалу предыдущей вершины прибавляем длину дуги, а при движении по дугам против потока эту длину из потенциала предыдущей вершины вычитаем. Правило объясняется тем, что движение по потоку происходит от станции отправления груза до станции его назначения, поэтому общее расстояние перевозок будет расти, а в обратном направлении, следовательно, будет уменьшаться (рис. 3).

Рис. 3; 4. Расчет транспортной сети

Шаг 3. Проверяем выполнение условия оптимальности для всех дуг сети, на которых нет грузопотоков, т. е. соблюдение выражения Vj-Ui ≤ Сij. В противном случае план перевозок не оптимален, ибо при переходе грузопотока на такие дуги общее расстояние перевозок уменьшится. В нашем примере грузопотоки отсутствуют на дугах: 8-9, 1-10, 3-11, 5-11, 7-10, 9-10. На дуге 8-9 Vj - Ui = 330 -150 = 180 > Сij = 70. Соответственно для дуг

1 — 10 имеем 110-100 = 10 < 75;

3—11 210-180 = 30 < 50;

5—11 230-180 = 50 < 60;

6—10 190-110=80< 120;

7—10 270- 110 = 160 > 100.

Таким образом, условие оптимальности нарушено на дугах 8 - 9 и 7 - 10.

Шаг 4. Выбираем дугу 8 - 9 с максимальным нарушением условия оптимальности и направляем по ней грузопоток от вершины с меньшим потенциалом до вершины с большим потенциалом (от 9-й к 8-й). Необходим замкнутый контур, состоящий из дуг с потоком и выбранной дуги с нарушением. Это можно сделать единственным способом — составить контур из дуг 9 - 8, 8 - 7, 7 - 6, 6 - 5, 5 - 4, 4 - 3, 3 - 2, 2 - 1, 1 - 9. Продвигаясь по контуру в направлении от меньшего потенциала к большему (в данном случае против часовой стрелки), находим дугу 8—7 со встречным потоком 75 ед. Прибавляя это число ко всем попутным грузопотокам и вычитая его из всех встречных, получаем улучшенный вариант перевозок (рис. 5).

Рис. 5. Расчет транспортной сети

Повторяем шаги 2 и 3. Нет необходимости заново подсчитывать все потенциалы вершин сети, достаточно исправить лишь потенциалы тех вершин, где изменилось направление грузопотоков. В нашем случае это вершина 8. Из рпс. видно, что при новом варианте распределения грузопотоков последние отсутствуют на дугах 7 - 8, 1 - 10, 3 - 11, 5 - 11, 6 - 10, 7 - 10, 9 - 10. Проверяем эти дуги на оптимальность из условия Vj - Ui < Сij.

Имеем соответственно на дугах:

7— 8 270-220 = 50 < 60;

1—10 110-100= 10<75;

3—11 210-180 = 30 < 50;

5—11 230-180 = 50 < 60;

6—10 190-110 = 80 < 100;

7—10 270-110 = 160 > 100;

9—10 150-110= 40<110.

Таким образом, условие оптимальности нарушено на дуге 7 - 10. Для получения оптимального варианта распределения грузопотоков повторяем шаг 4. Находим замкнутый контур, состоящий из дуг с потоками и дуги 7 - 10. Это контур, образованный из дуг 7—10, 10—3, 3—4, 4—5, 5—6, 6—7. Движение по нему следует осуществлять из вершины с меньшим потенциалом к вершине с большим потенциалом (т. е. от 10-й к 7-й), в данном случае против часовой стрелки. В этом контуре дуга с наименьшим встречным потоком — 6—7 с грузопотоком 25 ед. Это число прибавляем ко всем попутным и вычитаем из всех встречных потоков. В результате получаем новый вариант перевозок (рис.6).

Рис. 6. Расчет транспортной сети

Снова повторяем шаги 2 и 3. Теперь потенциал меняется лишь в вершине 7 и равен 210. Как видно из рис.6, в новом варианте без грузопотоков остались дуги 6—7, 7—8, 1—10, 3—11, 5—11, 6—10 и 9—10. В связи с тем, что изменился лишь потенциал вершины 7, достаточно проверить на оптимальность только дуги 6—7, 7—8. Для дуги 6 — 7 разность потенциалов Vj — Ui = 210 —190=20<Сij =80, а для дуги 7 – 8 - 220-210 = 10 < 60. Следовательно, получаем оптимальный вариант.

На рис. 7 изображена часть сети, по которой проходят грузопотоки. Она не содержит замкнутых контуров и называется деревом. Существует правило, по которому оптимальный план перевозок груза на сети без ограничения пропускной способности всегда образует дерево с числом связей (n —1), т.е. на единицу меньше вершин. Из этого правила следует исходить при составлении первоначального базисного плана, который также не должен содержать замкнутых контуров. Согласно этому же правилу на сети, имеющей форму дерева, для получения оптимального плана достаточного не допускать встречных перевозок.

Рис. 7. Расчет транспортной сети

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

Рис. 8. Расчет транспортной сети

При составлении базисного плана исходной задачи получаем два дерева: 7—1—6—5 и 2—3—4, которые соединены нулевым потоком по дуге 1 — 2, после чего имеем возможность определить потенциалы вершин. Вершине 1 присваиваем потенциал 100, вершине 2 соответственно 170, 3—90, 4—110, 7— 200, 6—150 и 5 — 190. Без потоков остались дуги 7—2, 7—5 и 5—4. Проверяем их на оптимальность: для дуги 7 — 2 200 -170 = 30 < 40; для дуги 7—5 200-190 =10< 50; для дуги 5—4 190-110=80<100.

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