Project Management & Optimization: CPM, PERT, Network Flow, & Integer Programming

Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT)

Activity Duration and Delays

If an activity's slack (MTIJ) equals zero, any delay in this activity will delay subsequent activities. However, activities can not delay the project if MTIJ is greater than zero.

Critical Path

The critical path is the longest path, which represents the minimum time necessary to complete the project. Activities on the critical path are called critical activities.

Activities with Uncertain Duration

When the duration of activities is not known with certainty, three estimates are used: optimistic (a_ij), realistic (m_ij), and pessimistic (b_ij). It is assumed that the duration of activities follows a beta distribution. Assuming t_ij are independent random variables, the total project time follows a normal distribution: T = Σt_ij (critical activities), V(T) = Σv_ij (critical activities).

Formulation of a PERT Problem

Minimize Z = Σ_i=1ⁿ T_i, where T_i = ET_i, T_j = ET_j, subject to T_j - T_i ≥ t_ij, T_ij ≥ 0.

Network Flow Problems

Node

A node is a point of intersection in the graph, identified with a number.

Arc

An arc is the union between two nodes, identified with two numbers. It is called oriented if it has a determined direction. If all arcs are oriented, the network is oriented.

Capacity of an Arc

The capacity of an arc (d) is the maximum flow that can pass through an oriented arc.

Connected Nodes

Two nodes are connected when they are linked by a non-oriented arc.

Chain, Path, and Arc

A chain is a set of successive arcs where each arc has a node in common with the previous one. A path is a chain with a direction. A cycle is a path that begins and ends at the same node.

Shortest Path Problem

The shortest path problem aims to determine the shortest route between an origin and a destination connected by a network with distances assigned to each arc. It is solved using Dijkstra's algorithm.

Maximum Spanning Tree Problem

The maximum spanning tree problem aims to connect all nodes in a network so that the total distance of the arcs connecting them is minimal. A spanning tree of a network with 'n' nodes is a set of 'n-1' arcs.

Maximum Flow Problem

The maximum flow problem aims to carry the maximum possible amount of flow through a network from a source to a destination. It consists of the following components: source, destination, arcs with limited capacity, and the objective of transporting the maximum possible flow.

Conditions for Feasible Flow

• The flow through an arc cannot be negative or exceed its capacity.
• The flow that enters a node must equal the flow that leaves it.

Logistics and the Traveling Salesman Problem (TSP)

Logistic Function

The logistic function aims to provide goods and services that are demanded in a timely manner and under appropriate conditions. Route design and fleet sizing are important in logistics.

Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) aims to design a route where the origin and destination match, passing through all required points so that the total distance is minimal.

Integer Programming (IP)

Features of an Integer Programming Model

• Linear objective function
• Linear constraints
• Non-negativity conditions
• Some variables must be integers

Why Simplex Cannot Be Applied to an IP

The simplex method cannot be applied to an IP because the feasible region is a set of discrete points, no longer a convex set.

Types of Integer Programming

• Pure: All variables must be integers.
• Mixed: Only some variables must be integers.
• Binary: Variables can only be 0 or 1.

Knapsack Problem

The knapsack problem aims to fill an entity with limited capacity using a series of objects with characteristics and a value called utility. The objective is to maximize the total utility. Binary variables are used.

Fixed Cost Problem

The fixed cost problem involves deciding which activities should be carried out, given that each activity has an associated fixed cost and a variable cost.

Method for Solving Integer Programming Problems

The branch and bound method is used to solve integer programming problems.

Relaxed Problem

A relaxed problem is a linear program derived from the original integer programming problem by dispensing with the condition that some variables must be integers. Its solution will always be better than or equal to the original problem's solution.