Системный анализ структуры и функционирования гостиницы "Русский дворик"

                                           

Рис.1.Структура производственного отдела Белгородского филиала АПХ «Мираторг» (a1,a2,…a16-элементы системы; L1,L2,…L15-связи между элементами)

Изобразим данную структуру с помощью графа. Рис.2 Граф-это математическая модель структуры. Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. В нашем случае граф является ориентированным, так как все его дуги имеют направление.

Рис.2. Граф, построенный на основе данных о структуре производственного отдела АПХ «Мираторг» (a1,a2,…a16-элементы системы (вершины орграфа); L1,L2,…L15-связи между элементами) 

Матрица смежности вершин орграфа А - это квадратная матрица размером NxN (N - количество вершин в графе), заполненная единицами и нулями по следующему правилу:

-[aij]:aij=1,если есть дуга, ведущая из vi в vj;

-aij=0 в противном случае.

Построим матрицу смежности вершин нашего орграфа. Табл.2

 

 

 

 

 

 

 

 

 

 

 

Таблица 2

Матрица смежности вершин

 

	а1	а2	а3	а4	а5	а6	а7	а8	а9	а10	а11	а12	а13	а14	а15	а16	P
а1	0	1L1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
а2	0	0	1L2	0	0	0	0	0	0	0	0	0	0	0	0	0	1
а3	0	0	0	1L3	1L4	1L5	1L6	0	0	0	0	0	0	0	0	0	4
а4	0	0	0	0	0	0	0	1L7	1L8	1L9	0	0	0	0	0	0	3
а5	0	0	0	0	0	0	0	0	0	0	0	0	0	1L10	0	0	1
а6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1L11	0	1
а7	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1L12	1
а8	0	0	0	0	0	0	0	0	0	0	1L13	0	0	0	0	0	1
а9	0	0	0	0	0	0	0	0	0	0	0	1L14	0	0	0	0	1
а10	0	0	0	0	0	0	0	0	0	0	0	0	1L15	0	0	0	1
а11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

 

         Pа1=1; Pа2=2; Pа3=5; Pа4=4; Pа5=2; Pа6=2; Pа7=2; Pа8=2; Pа9=2; Pа10=2;       Pа11=1; Pа12=1; Pа13=1; Pа14=1; Pа15=1; Pа16=1. Таким образом, а3- вершина с максимальной степенью. Изолированных вершин нет.

Матрица смежности дуг орграфа - это квадратная матрица m-ного порядка (m– число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы qij равны 1, если дуга ui непосредственно предшествует дуге uj и 0 в остальных случаях. Построим матрицу смежности дуг для нашего орграфа. Табл.3

 

 

 

 

 

 

 

 

 

Таблица 3

Матрица смежности дуг орграфа

 

	L1	L2	L3	L4	L5	L6	L7	L8	L9	L10	L11	L12	L13	L14	L15
L1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
L2	0	0	1	1	1	1	0	0	0	0	0	0	0	0	0
L3	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0
L4	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
L5	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
L6	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
L7	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
L8	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
L9	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
L10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
L11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
L12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
L13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
L14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
L15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

 

 

Матрица инциденций орграфа – прямоугольная матрица, размерности n×m, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы rij=1, если дуга ujисходит из i-той вершины. rij=-1, если дуга заходит в i-ую вершину и rij=0 в остальных случаях. Построим матрицу инцидентности для нашего орграфа. Табл.4

Таблица 4

Матрица инциденций

 

	l1	l2	l3	l4	l5	l6	l7	l8	l9	l10	l11	l12	l13	l14	l15
а1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
а2	1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0
а3	0	1	-1	-1	-1	-1	0	0	0	0	0	0	0	0	0
а4	0	0	1	0	0	0	-1	-1	-1	0	0	0	0	0	0
а5	0	0	0	1	0	0	0	0	0	-1	0	0	0	0	0
а6	0	0	0	0	1	0	0	0	0	0	-1	0	0	0	0
а7	0	0	0	0	0	1	0	0	0	0	0	-1	0	0	0
а8	0	0	0	0	0	0	1	0	0	0	0	0	-1	0	0
а9	0	0	0	0	0	0	0	1	0	0	0	0	0	-1	0
а10	0	0	0	0	0	0	0	0	1	0	0	0	0	0	-1
а11	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
а12	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0
а13	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
а14	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
а15	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
а16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

 

 Раздел III. Практическая часть. Решение конкретных задач линейного программирования.

3.1 Задача организации  рабочего времени

 В процессе функционирования любого предприятия очень важен и необходим процесс планирования, для того чтобы получить максимальную прибыль и минимизировать затраты. Например, производственный отдел Белгородского филиала АПХ «Мираторг» имеет несколько видов работ, которые необходимо выполнить в течении рабочего времени, общий фонд оплаты труда ограничен, материальные затраты, связанные с выполнением каждого вида работ, общий фонд материальных затрат тоже ограничены. Так же известна прибыль, получаемая при выполнении работы каждого вида в течении одного часа. И нужно найти такое распределение рабочего времени, чтобы суммарная прибыль была максимальной. Именно такого рода задачи решаются в теории линейного программирования.

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

Постановка задачи планирования в общем случае выглядит следующим образом:

• имеются некоторые плановые показатели: X, Y, ...;
• имеются некоторые ресурсы: R1, R2, ..., за счет которых эти плановые показатели могут быть достигнуты;
• имеется определенная стратегическая цель, зависящая от значений плановых показателей, на которую следует ориентировать планирование.

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

Задача оптимального планирования рабочего времени имеет следующую формулировку: Имеется nразличных видов работ А1, А2,…Аn, которые могут выполняться в течении рабочего времени Т. Оплата каждого вида работ составляет u1, u2…un в час. Общий фонд оплаты труда ограничен величиной U. Материальные затраты, связанные с выполнением каждого вида работ, составляют V1,V2,…Vn в час. Общий фонд материальных затрат ограничен величиной V. Прибыль получаемая при выполнении работы каждого вида в течении одно часа, составляет C1,C2,…Cn. Требуется найти такое распределение рабочего времени Т, чтобы суммарная прибыль была максимальной.

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

- целевая функция

(i=1,2,…k) - ограничение типа неравенств

   (i=k+1,…m) - ограничение типа неравенств

(j=1,2…s) условия не отрицательности переменных

Вектор X=(x1,x2…xn),удовлетворяющей ограничениям задачи линейного программирования называется планом(или допустимым решением)

План X*=(х1*,х2*…хn*), при котором целевая функция достигает своего максимального значения, называется оптимальным планом.

Теорема (о достижимости оптимального значения целевой функции в вершине многогранника решений)

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

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

Следствие. Оптимальный план(если он существует) может быть найден путем полного перебора вершин.

Таблица 5

Условие задачи

 

	u	v	C
A1	35	25	30
A2	30	45	25
T	125 час.
U	1000 у.е
V	1500 у.е

 

 

Решение:  

 

U1t1+U2 t2≤1000

V1 t1+V2 t2 ≤1500

t1 +t2 ≤125

C1t1+C2 t2→max

1. 35t1+30t2=1000

t1=0; t2=33,3

t2=0; t1=28,57

2. 25t1+45t2=1500

t1=0; t2=33,3

t2=0; t1=60

3. 30t1+25t2=0

t1=0; t2=0

t2=-6; t1=5

4. t1+t2=125

t1=0; t2=125

t2=0; t1=125

 

Рис.3. Графическое решение задачи планирования рабочего времени. Точка (28,571;0) является оптимальным планом.

 

Рис.4. Решение задачи организации рабочего времени в Excel

Результаты, полученные разными способами совпадают, значит решение верно. Следовательно, точка оптимально плана (28,571;0)

 

 

 

 

 

 

 

 

 

 

 

 

3.2 Задача о  назначении

 Производственный отдел Белгородского филиала АПХ «Мираторг» имеет огромный штат сотрудников различной классификации, которые занимают какую-то определенную должность и соответственно выполняют какую-то определенную работу. Но к примеру если директор производственного отдела решит расширить производство или развить другой вид продукции на базе предприятия появятся новые рабочие места и перед начальством будет стоять вопрос о назначении того или иного сотрудника на определенное рабочее место. Такого рода задачи рассматриваются в теории линейного программирования и относятся к типу целочисленных транспортных задач.