UID: 20191017
Jun Min Ki
I keep the promise between Professor Lee and I
HW8
HW7
Lambda=7
빠른 서버(fast sever): 처리속도 mu=5, 고장속도 gamma=2, 수리속도
nu=7
느린 서버(slow sever): 처리속도 mu=4, 고장속도gamma=1수리속도 nu=10
Pux = 빠른서버만 정상
Pdx = 느린서버만 정상
Pud = 둘다 정상
Pxx = 둘다 고장
% s.t
35*P0=4*P2+5*P3+4*P4+5*P5
24*P1=7*P0+2*P2+P5
18*P2=7*P0+2*P3+4*P7
14*P3=7*P0+7*P2+5*P8
12*P4=7*P0+10*P5+5*P8
22*P5=7*P0+P4+5*P9
24*P6=7*P1+2*P7+P9
18*P7=7*P2+2*P8+4*P11
20*P8=7*P3+7*P4+7*P7+10*P9+9*P12
23*P9=7*P5+10*P6+P8+5*P13
24*P10=7*P6+2*P11+P13
20*P11=7*P7+7*P10+2*P12+4*P15
19*P12=7*P8+7*P11+10*P13+9*P16
14*P13=7*P9+10*P10+P12+5*P17
17*P14=7*P10+2*P15+P17
13*P15=7*P11+7*P14+2*P16
12*P16=7*P12+7*P15+10*P17
16*P17=7*P13+10*P14+P16
%%
clc; clear all; close all;
a = [35 0 4 -5 -4 -5 0 0 0 0 0 0
0 0 0 0 0 0;
-7 24 -2 0 0 -1 0 0 0 0 0 0 0 0 0
0 0 0;
-7 0 18 -2 0 0 0 -4 0 0 0 0 0 0 0
0 0 0;
-7 0 -7 14 0 0 0 0 -5 0 0 0 0 0 0
0 0 0;
-7 0 0 0 12 -10 0 0 -5 0 0 0 0 0
0 0 0 0;
-7 0 0 0 -1 22 0 0 0 -5 0 0 0 0 0
0 0 0;
0 -7 0 0 0 0 24 -2 0 -1 0 0 0 0 0
0 0 0;
0 0 -7 0 0 0 0 0 18 -2 0 0 -4 0 0
0 0 0;
0 0 0 -7 -7 0 0 -7 20 -10 0 0 -9
0 0 0 0 0;
0 0 0 0 0 -7 -10 0 -1 23 0 0 0 5
0 0 0 0;
0 0 0 0 0 0 -7 0 0 0 24 -2 0 -1 0
0 0 0;
0 0 0 0 0 0 -7 0 0 -7 20 -2 0 0
-4 0 0 0;
0 0 0 0 0 0 0 0 -7 0 0 -7 19 -10
0 0 -9 0;
0 0 0 0 0 0 0 0 0 -7 -10 0 -1 14
0 0 0 -5;
0 0 0 0 0 0 0 0 0 0 -7 0 0 0 17
-2 0 -1;
0 0 0 0 0 0 0 0 0 0 0 -7 0 0 -7
13 -2 0;
0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 -7
12 -10;
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1];
b=[0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]';
p=inv(a)*b;
sum_p=sum(p)
WIP=[0 1
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4]*p
TH=7
wip_q=[0
1 0 0 0 0 2 1 0 1 3 2 1 2 4 3 2 3]*p
wip_s=WIP-wip_q
ct_q=wip_q/TH
ct_s=wip_s/TH
ct=ct_q+ct_s
HW6
Shipment : 3w, mfg : 1w, SS : 1.7w,
Component Shipment : 2w
|
Case
1 : component = inf |
||||||||
|
Demand |
120 |
250 |
200 |
300 |
350 |
250 |
200 |
250 |
|
SS |
390 |
410 |
545 |
525 |
390 |
375 |
250 |
0 |
|
Demand+SS |
510 |
660 |
745 |
825 |
740 |
625 |
450 |
250 |
|
BoH |
50 |
0 |
0 |
0 |
0 |
390 |
375 |
250 |
|
W/I |
60 |
100 |
80 |
90 |
740 |
235 |
75 |
0 |
|
EoH |
0 |
0 |
0 |
0 |
390 |
375 |
250 |
0 |
|
Shortage |
10 |
150 |
120 |
210 |
0 |
0 |
0 |
0 |
|
Shipment |
90 |
740 |
235 |
75 |
0 |
0 |
0 |
0 |
|
mfg |
740 |
235 |
75 |
0 |
0 |
0 |
0 |
0 |
|
Case
2 : component = 0 |
||||||||
|
Demand |
120 |
250 |
200 |
300 |
350 |
250 |
200 |
250 |
|
SS |
390 |
410 |
545 |
525 |
390 |
375 |
250 |
0 |
|
Demand+SS |
510 |
660 |
745 |
825 |
740 |
625 |
450 |
250 |
|
BoH |
50 |
0 |
0 |
0 |
0 |
0 |
0 |
250 |
|
W/I |
60 |
100 |
80 |
90 |
0 |
0 |
450 |
0 |
|
EoH |
0 |
0 |
0 |
0 |
0 |
0 |
250 |
0 |
|
Shortage |
10 |
150 |
120 |
210 |
350 |
250 |
0 |
0 |
|
Shipment |
90 |
0 |
0 |
450 |
0 |
0 |
0 |
0 |
|
mfg |
0 |
0 |
450 |
0 |
0 |
0 |
0 |
0 |
HW5
Shipment : 3w, mfg : 1w, Component Shipment
: 2w
|
Case
1 : component = inf |
||||||||
|
Demand |
120 |
250 |
200 |
300 |
350 |
250 |
200 |
250 |
|
BoH |
50 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
W/I |
60 |
100 |
80 |
90 |
350 |
250 |
200 |
250 |
|
EoH |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Shortage |
10 |
150 |
120 |
210 |
0 |
0 |
0 |
0 |
|
Shipment |
90 |
350 |
250 |
200 |
250 |
0 |
0 |
0 |
|
mfg |
350 |
250 |
200 |
250 |
0 |
0 |
0 |
0 |
|
Case
2 : component = 0 |
||||||||
|
Demand |
120 |
250 |
200 |
300 |
350 |
250 |
200 |
250 |
|
BoH |
50 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
W/I |
60 |
100 |
80 |
90 |
0 |
0 |
200 |
250 |
|
EoH |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Shortage |
10 |
150 |
120 |
210 |
350 |
250 |
0 |
0 |
|
Shipment |
90 |
0 |
0 |
200 |
250 |
0 |
0 |
0 |
|
mfg |
0 |
0 |
200 |
250 |
0 |
0 |
0 |
0 |
HW4
from collections import defaultdict,
deque
def bfs(graph, source, sink, parent):
visited = set()
queue = deque([source])
visited.add(source)
while queue:
u = queue.popleft()
for v, cap in graph[u].items():
if v not in visited and cap > 0:
queue.append(v)
visited.add(v)
parent[v] = u
if v == sink:
return True
return False
def ford_fulkerson(graph, source, sink):
parent = {}
max_flow = 0
while bfs(graph, source, sink,
parent):
path_flow = float('Inf')
s = sink
while(s != source):
path_flow = min(path_flow, graph[parent[s]][s])
s =
parent[s]
max_flow += path_flow
v = sink
while(v != source):
u =
parent[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parent[v]
return max_flow
def apply_capacity_limits(original_graph, sp_index, supply_limit):
modified_graph = defaultdict(dict)
for u in original_graph:
for v, caps in original_graph[u].items():
if u.startswith('SP'):
cap = min(caps[sp_index],
supply_limit)
else:
total_cap = caps[0]
sp_sum = sum(caps[1:])
if sp_sum > total_cap:
ratio = total_cap / sp_sum
cap = caps[sp_index]
* ratio
else:
cap = caps[sp_index]
modified_graph[u][v] = cap
if v not in modified_graph:
modified_graph[v]
= {}
if u not in modified_graph[v]:
modified_graph[v][u]
= 0
return modified_graph
start_points = {
'SP1': 1,
'SP2': 2,
'SP3': 3
}
supply_limits = {
'SP1': 25,
'SP2': 25,
'SP3': 35
}
graph = {
'SP1': {'N1': [10, 10, 0, 0], 'N2': [25, 15, 0, 0]},
'SP2': {'N1': [10, 0, 10, 0], 'N4': [25, 0, 15, 0]},
'SP3': {'N3': [20, 0, 0, 20], 'N5': [15, 0, 0, 15]},
'N1': {'N6': [15, 5, 10, 0], 'N9': [15, 5, 0, 10]},
'N2': {'N8': [20, 10, 0, 10], 'N9': [25, 15, 5, 5]},
'N3': {'N6': [20, 0, 0, 20], 'N11': [20, 10, 0, 10]},
'N4': {'N7': [20, 0, 10, 10], 'N10': [25, 0, 15, 10]},
'N5': {'N10': [20, 10, 10, 0], 'N11': [25, 15, 10, 0]},
'N6': {'N12': [25, 0, 0, 25], 'N13': [30, 30, 30, 30]},
'N7': {'N12': [20, 10, 5, 5], 'N14': [25, 10, 5, 10]},
'N8': {'N14': [20, 10, 5, 5]},
'N9': {'N13': [25, 15, 15, 5]},
'N10': {'EC': [30, 20, 5, 15]},
'N11': {'EC': [35, 15, 10, 10]},
'N12': {'N15': [20, 10, 5, 5]},
'N13': {'N15': [30, 15, 10, 15]},
'N14': {'EC': [45, 25, 10, 10]},
'N15': {'N14': [25, 15, 5, 15]}
}
for sp, index in start_points.items():
supply_limit = supply_limits[sp]
modified_graph = apply_capacity_limits(graph, index, supply_limit)
max_flow = ford_fulkerson(modified_graph, sp, 'EC')
print(f"최대 유량 ({sp}에서 EC까지): {max_flow}")
HW3
minimize:
30X₁ + 35X₂ + 110X₃ + 170X₄ +
55X₅ + 45X₆ + 100X₇
+ 80X₈ + 55X₉ + 50X₁₀ + 35X₁₁ + 55X₁₂ +
140X₁₃ + 143X₁₄ + 135X₁₅
+ 90X₁₆ + 24X₁₇ + 40X₁₈
+ 40X₁₉ + 70X₂₀ + 40X₂₁ +
30X₂₂ + 125X₂₃ + 120X₂₄ + 15X₂₅ + 25X₂₆
+ 100X₂₇ + 95X₂₈ + 140X₂₉
+ 110X₃₀ + 170X₃₁ +
280X₃₂ + 30X₃₃ + 90X₃₄ + 70X₃₅ + 25X₃₆ + 135X₃₇
+ 125X₃₈
subject
to:
X₁ = 1
X₂ + X₃ + X₄ + X₅
+ X₆ + X₇ + X₈ + X₉ + X₁₀ + X₁₁ + X₁₂ =
1
X₂₀ + X₁₉ + X₃₃ + X₃₄ =
1
X₂ - X₃₅
= 0
X₂ + X₃ - X₃₂ = 0
X₄ - X₃₁ = 0
X₅
- X₂₇ - X₃₀ = 0
X₆
- X₂₉ = 0
X₇
- X₂₆ - X₂₈ = 0
X₈
- X₂₅ = 0
X₉
+ X₈ - X₂₂ - X₂₄ - X₂₆ = 0
X₁₀ - X₃₇ - X₃₈
= 0
X₁₁ - X₁₄ = 0
X₁₂ - X₁₃ = 0
X₁₃ + X₁₄ + X₁₅ + X₁₆ + X₁₈
- X₁₉ = 0
X₁₅ - X₃₇ = 0
X₁₆ + X₁₇ - X₃₆
= 0
X₁₇ + X₂₁ -
X₁₈ - X₂₀ = 0
X₂₁ - X₃₀
= 0
X₂₃ - X₃₈
= 0
X₂₇ - X₃₄ =
0
X₃₃ - X₃₂ - X₃₁ - X₃₀
- X₂₉ - X₂₈ - X₂₄ - X₂₃ =
0
Code:
import
networkx as nx
graph
= {
"SP(진천)": {"진천터미널": 30},
"진천터미널": {
"죽산터미널": 35,
"안성터미널": 110,
"동서울터미널": 170,
"대전복합터미널": 55,
"청주북부터미널": 45,
"남청주터미널": 100,
"청주사창터미널": 80,
"청주고속버스터미널": 55,
"청주공항역": 35,
"신탄진터미널": 50,
"오근장역": 55
},
"죽산터미널": {"안성터미널": 70},
"안성터미널": {"구미종합버스터미널": 280},
"동서울터미널": {"구미종합버스터미널":
170},
"대전복합터미널": {
"구미종합버스터미널": 110,
"대전역": 25,
"김천터미널": 100
},
"대전역": {"김천구미역": 24, "구미역": 90},
"김천구미역": {"TP(금오공대)": 70, "구미역": 40},
"구미역": {"TP(금오공대)": 40},
"청주북부터미널": {"구미종합버스터미널": 140},
"남청주터미널": {"구미종합버스터미널":
95},
"청주사창터미널": {"청주고속버스터미널":
15},
"청주고속버스터미널": {"구미종합버스터미널": 120, "오송역": 30},
"오송역": {"김천구미역": 40},
"청주공항역": {"구미역": 143},
"신탄진터미널": {"여주터미널": 125,
"평택역": 135},
"여주터미널": {"구미종합버스터미널": 125},
"평택역": {"구미역": 135},
"오근장역": {"구미역": 140},
"구미종합버스터미널": {"TP(금오공대)": 30}
}
def
find_shortest_path(graph, start, end):
G = nx.DiGraph()
for node, edges in graph.items():
for neighbor, weight in edges.items():
G.add_edge(node, neighbor,
weight=weight)
shortest_path = nx.dijkstra_path(G, source=start,
target=end)
shortest_path_distance
= nx.dijkstra_path_length(G,
source=start_node, target=end_node)
return shortest_path,
shortest_path_distance
start_node = "SP(진천)"
end_node = "TP(금오공과대학교)"
(shortest_path,shortest_path_distance)
= find_shortest_path(graph, start_node,
end_node)
print(f"The shortest path from {start_node} to {end_node} is {shortest_path} with a total travel time of {shortest_path_distance} minutes.")
HW2
HW1
Q:
로봇 청소기가 배터리를 충전하기 위해 어떻게 충전단자로 이동하는가?
A:
로봇 청소기는 다양한 기술을 결합하여 충전소로의 복귀 경로를 결정합니다. SLAM(Simultaneous Localization and
Mapping) 기술을 통해
주변 환경을 인식하고 내부 지도를 생성하며, 자신의 정확한 위치를 파악합니다. 또한, 인프라 레드(IR)
또는 라디오 주파수(RF) 신호를 사용해 충전소의 방향을 감지하고, 충전소 근처에서는 이 신호를 따라 이동합니다. 일부 로봇 청소기에서는 빔 포밍(beam
forming) 기술을 활용해 충전소로부터 오는 신호의 방향을 더욱 정확히 탐지하여 충전소의 위치를 정밀하게 찾아갑니다.