[GEMATMW] Module 5: Mathematics for Efficiency

Linear programming

Linear programming

a mathematical method that is used to determine the best possible outcome or solution from a given set of constraints, which are usually represented in the form linear inequalities

Decision Variables

the quantity that the decision maker controls

Objective Function

represents the goal of the problem

Constraints

limitations of resources or conditions we need to satisfy

Corner point principle

the objective function is optimized at one of the corner points

Feasible region

set of points that satisfies all constraints

Graph Theory

study of graphs, which are mathematical structures used to model pairwise relations of objects

Konigsberg

now known as Kaliningrad, in Russia; origin of graph theory

Leonhard Euler

inventor of graph theory

Undirected graph

consists of a set of vertices and a set of edges that which join two vertices

adjacent

if two vertices are joined by an edge

order

|V(G)|; number of vertices in a graph

size

|E(G)|; number of edges in a graph

Multiple edge

If there is more than one edge joining vertices

Loop

an edge from a vertex to itself

Multigraph

graph that contains multiple edges or loops

Simple graph

graph that does not contains multiple edges or loops

degree

number of edges that are incident to the vertex

neighborhood

set of all vertices that are adjacent to a specific vertex

walk

a sequence of vertices such that two consecutive vertices are joined by an edge

path

a walk with distinct vertices

cycle

a walk with distinct vertices and the same starting and ending vertex

Connected graph

graph where there is always a path from a vertex to all other vertices

Disconnected graph

graph where there are vertices unaccessible to other vertices

Weighted graph

all the edges of are assigned with numerical values

Directed graph

consists of a set of vertices and a set of arcs that are formed using ordered pairs of vertices

arc

edge from initial to terminal vertex

Djikstra’s Algorithm

a tool for determining a shortest path from a starting vertex to any destination vertex

state

distance value and status label

distance value

represents an estimate of its distance from vertex; may be updated every time Dijkstra’s algorithm is used

status labels

either permanent or temporary

Assignment problems

special kind of linear programming problems where the primary concern is determining optimal assignment or allocation of resources

Assignment problems

determines an efficient way of distributing goods or tasks in order to attain minimum cost or maximum profit

Assignment problems

a person cannot be assigned to two or more jobs; a job cannot be assigned to two or more people

Balanced assignment problem

number of people is equal to the number of task

Unbalanced assignment problem

number of people is not equal to the number of task

Opportunity cost table

the rows contain people and the columns contain the tasks

Optimality test

draw the least number of horizontal and vertical lines needed to cover all zeros

Hungarian Method

algorithm used for assignment problems