UNIT-IV
Summarize the Simplex method. Or Write the procedure to initialize simplex which
determine if a linear program is feasible or not . Or Use simplex to solve the farmers
problem given below.
Simplex method procedure:
Step 0 [Initialization] Present a given LP problem in standard form and set up initial
tableau.
Step 1 [Optimality test] If all entries in the objective row are nonnegative then stop: the
tableau represents an optimal solution.
Step 2 [Find entering variable] Select the most negative entry in the objective row. Mark
its column to indicate the entering variable and the pivot column.
Step 3 [Find departing [leaving] variable] For each positive entry in the pivot column,
calculate the θ-ratio by dividing that row's entry in the rightmost column [solution] by its
entry in the pivot column. [If there are no positive entries in the pivot column then stop:
the problem is unbounded.] Find the row with the smallest θ-ratio, mark this row to
indicate the departing variable and the pivot row.
Step 4 [Form the next tableau] Divide all the entries in the pivot row by its entry in the
pivot column. Subtract from each of the other rows, including the objective row, the new
pivot row multiplied by the entry in the pivot column of the row in question. Replace the
label of the pivot row by the variable's name of the pivot column and go back to Step 1.
Standard form of LP problem
Must be a maximization problem
All constraints [except the nonnegativity constraints] must be in the form of linear
equations
All the variables must be required to be nonnegative
Thus, the general linear programming problem in standard form with m
constraints and n unknowns [n ≥ m] is
Maximize c1 x1 + ...+ cn xn
Subject to ai 1x1+ ...+ ain xn = bi , i = 1,...,m, x1 ≥ 0, ... , xn ≥ 0
Example
maximize 3x + 5y maximize 3x + 5y
+ 0u + 0v subject to x + y ≤ 4
subject to x + y + u = 4
x + 3y ≤ 6 to x + 3y + v = 6
x≥0, y≥0 x≥0, y≥0, u≥0, v≥0
Variables u and v, transforming inequality constraints into equality
constrains, are called slack Variables
State and Prove Maximum Flow Min cut Theorem. Or Explain Max-Flow Problem Or
How do you compute maximum flow for the following graph using ford-Fulkerson
method?
Maximum Flow Problem
Problem of maximizing the flow of a material through a transportation network [e.g.,
pipeline system, communications or transportation networks]
Formally represented by a connected weighted digraph with n vertices numbered from 1
to n with the following properties:
• Contains exactly one vertex with no entering edges, called the source [numbered 1]
• Contains exactly one vertex with no leaving edges, called the sink [numbered n]
• Has positive integer weight uij on each directed edge [i.j], called the edge capacity,
indicating the upper bound on the amount of the material that can be sent from i to j
through this edge.
A digraph satisfying these properties is called a flow network or simply a network
Flow value and Maximum Flow Problem
Since no material can be lost or added to by going through intermediate vertices of the
network, the total amount of the material leaving the source must end up at the sink:
Σ x1j = Σ xjn
j: [1,j] є E j: [j,n] є E
The value of the flow is defined as the total outflow from the source [= the total inflow
into the sink].
The maximum flow problem is to find a flow of the largest value [maximum flow] for a
given network.
Max-Flow Min-Cut Theorem
1. The value of maximum flow in a network is equal to the capacity of its minimum cut
2. The shortest augmenting path algorithm yields both a maximum flow and a minimum
cut:
• Maximum flow is the final flow produced by the algorithm
• Minimum cut is formed by all the edges from the labeled vertices to unlabeled
vertices on the last iteration of the algorithm.
• All the edges from the labeled to unlabeled vertices are full, i.e., their flow amounts
are equal to the edge capacities, while all the edges from the unlabeled to labeled
vertices, if any, have zero flow
amounts on them.
Flow augmenting path algorithm or Ford Fulkerson method to solve max-flow
problem
Thus, to find a flow-augmenting path for a flow x, we need to consider paths from
source to sink in the underlying undirected graph in which any two consecutive
vertices i, j are either
i. connected by a directed edge from i to j with some positive unused capacity rij =
uij − xij (so that we can increase the flow through that edge by up to rij units), or
ii. connected by a directed edge from j to i with some positive flow xji (so that we
can decrease the flow through that edge by up to xji units)
For example,
Edges of the first kind are called forward edges because their tail is listed before their
head in th vertex list 1→. . . i →j . . .→n defining the path; edges of the second kind
are called backward edges because their tail is listed after their head in the path list
1→. . . i ←j . . .→n. To illustrate, for the path 1→4→3←2→5→6 of the last
example, (1, 4), (4, 3), (2, 5), and (5, 6) are the forward edges, and (3, 2) is the
backward edge.
Write down the optimality condition and algorithmic implementation for finding M-
augumenting paths in bipartite graphs? Or Illustrate the workings of the maximum
matching algorithm on the following weighted trees.
A matching in a graph is a subset of its edges with the property that no two edges
share a vertex. A maximum matching—more precisely, a maximum cardinality
matching—is a matching with the largest number of edges.
Case 1 (the queue‘s front vertex w is in V ) If u is a free vertex adjacent to w, it is
used as the other endpoint of an augmenting path; so the labeling stops and
augmentation of the matching commences. The augmenting path in question is
obtained by moving backward along the vertex labels (see below) to alternately add
and delete its edges to and from the current matching. If u is not free and connected
to w by an edge not in M, label u with w unless it has been already labeled.
Case 2 (the front vertex w is in U) In this case, w must be matched and we label its
mate in V with w.
STUDENTSFOCUS.COM
ALGORITHM Maximum Bipartite Matching(G)
//Finds a maximum matching in a bipartite graph by a BFS-
like traversal //Input: A bipartite graph G = V, U, E
//Output: A maximum-cardinality matching M in the input
graph initialize set M of edges with some valid matching
(e.g., the empty set) initialize queue Q with all the free
vertices in V (in any order) while not Empty(Q) do
w←Front(Q); Dequeue(Q)
if w ∈ V
for every vertex u adjacent to w do
if u is free
//augment
M ←M 𝖴 (w, u)
v←w
while v is labeled do
u←vertex indicated by v‘s label; M ←M − (v, u)
v←vertex indicated by u‘s label; M ←M 𝖴 (v, u)
remove all vertex labels
reinitialize Q with all free vertices in V
break //exit the for loop
else //u is matched
if (w, u) ∈ M and u is unlabeled
label u with w
Enqueue(Q, u)
else //w ∈ U (and matched)
label the mate v of w with w
STUDENTSFOCUS.COM
Enqueue(Q, v)
return M //current matching is maximum
For Example,
STUDENTSFOCUS.COM
Briefly describe on the stable marriage problem. (or)Gale shaply algorithm.
Stable marriage algorithm
A marriage matching M is a set of n (m, w) pairs whose members are selected from
disjoint n-element sets Y and X in a one-one fashion, i.e., each man m from Y is
paired with exactly one woman w from X and vice versa
Consider an interesting version of bipartite matching called the stable marriage
problem.
Consider a set Y = {m1, m2, . . . , mn } of n men and a set X = {w1, w2, . . . , wn } of
n women. Each man has a preference list ordering the women as potential marriage
partners with no ties allowed. Similarly, each woman has a preference list of the men,
also with no ties.
Input: A set of n men and a set of n women along with rankings of the women by each
man and rankings of the men by each woman with no ties allowed in the rankings
Output: A stable marriage matching
Step 0 Start with all the men and women being free.
Step 1 While there are free men, arbitrarily select one of them and do the following:
Proposal The selected free man m proposes to w, the next woman on his preference list
(who is the highest-ranked woman who has not rejected him before).
Response If w is free, she accepts the proposal to be matched with m. If she is not free,
she compares m with her current mate. If she prefersm to him, she accepts m‘s
proposal, making her former mate free; otherwise, she simply rejects m‘s proposal,
leaving m free.
Step 2 Return the set of n matched pairs.
For Example,
STUDENTSFOCUS.COM
STUDENTSFOCUS.COM
