Assignment II: Network Models

Instructions:

$$ Submission Deadline: TBD

$$ Format: Submit your solutions in a single PDF document.

$$ Software Tools: You may use software tools such as MATLAB, LINGO, or any network

optimization software to solve the problems, but make sure to include your code and

detailed explanations.

$$ Collaboration: You may discuss the problems with classmates, but each student must

submit their own individual solutions.

Problem $1$: Shortest$-$Route Problem

Consider the following network with nodes and directed arcs with given distances:

From

To

Distance

A

B

$4$

A

C

$2$

B

C

$5$

B

D

$10$

C

D

$3$

D

E

$4$

C

E

$7$

$1.$ Graph Representation: Draw the network graph.

$2.$ Dijkstra$$s Algorithm: Use Dijkstra$$s Algorithm to find the shortest path from node A to

node E$.$ Show all steps clearly.

Problem $2$: Minimal Spanning Tree Problem

Given the following undirected graph with edge lengths:

Node $1$

Node $2$

Length

A

B

$1$

A

C

$3$

B

C

$3$

B

D

$6$

C

D

$4$

C

E

$2$

D

E

$5$

$1.$ Graph Representation: Draw the network graph.

$2.$ Kruskal$$s Algorithm: Apply Kruskal$$s Algorithm to find the minimal spanning tree.

Show each step and the resulting tree.

$3.$ Prim$$s Algorithm: Apply Prim$$s Algorithm starting from node A$.$ Show each step and

the resulting tree.

Problem $3$: Maximal Flow Problem

Consider a network with the following capacities:

From To Capacity

S A $16$

S B $13$

A B $10$

A C $12$

B D $14$

C B $9$

C T $20$

D C $7$

D T $4$

$1.$ Graph Representation: Draw the network graph.

$2.$ Ford$-$Fulkerson Method: Use the Ford$-$Fulkerson method to find the maximum flow

from source S to sink T$.$ Show each augmenting path and the resulting flow.

Problem $4$: Minimum Cost Flow Problem

Given the following network with costs and capacities:

From To Cost Capacity

S A $210$

S B $45$

A B $115$

A T $210$

B T $310$

$1.$ Graph Representation: Draw the network graph.

$2.$ Linear Programming Formulation: Formulate the minimum cost flow problem as a

linear programming problem.

$3.$ Solution Using Successive Shortest Path Algorithm: Solve the problem using the

successive shortest path algorithm. Show all steps and the final flow and cost.

Problem $5$: Real$-$World Application

Select a real$-$world problem that can be modeled as a network problem $($e$.$g$.,$ transportation

logistics$,$ communication networks$).$ Provide the following:

$1.$ Problem Description: Describe the real$-$world problem in detail.

$2.$ Network Representation: Construct the network graph for the problem.

$3.$ Solution Approach: Suggest an appropriate algorithm $($shortest path, minimal spanning

tree, maximal flow, or minimum cost flow$)$ and justify your choice.

$4.$ Implementation: Solve the problem using the chosen algorithm. Provide detailed steps

and the final solution.

Submission Checklist:

$$ Ensure all graphs are clearly drawn and labeled.

$$ Show all steps and calculations for each algorithm.

$$ Include any code used in the solution.

$$ Provide detailed explanations for each problem.

Good luck! If you have any questions, please reach out during office hours or via email.

This assignment covers various aspects of network models, reinforcing students' understanding

and application of algorithms to solve practical problems in operations research.