Assignment problem
The assignment problem is a fundamental combinatorial
optimization problem. In its most general form, the problem is as follows:
The problem instance has a number of agents and a number
of tasks. Any agent can be assigned to perform any task, incurring
some cost that may vary depending on the agent-task assignment.
It is required to perform as many tasks as possible by assigning at
most one agent to each task and at most one task to each agent,
in such a way that the total cost of the assignment is minimized.
Mathematical formulation of problem
computational procedure is for obtaining a polynomial representation
from state equations. ... Applying the basic procedure recursively leads
to a computational algorithm for determining the desired
representation.
assignment problem can be solved either by using the techniques of
Linear Programming or by the transportation method yet
the assignment method called Hungarian method of assignment
problem is much faster and efficient.
Variation in assignment problem
Any assignment problem is said to be unbalanced if the cost matrix is
not a square matrix, i.e. the no of rows and the no of columns are not
equal. To make it balanced we add a dummy row or dummy column with
all the entries is zero.
Tests of significance
it is important to know if the result of an experiment is significant enough
or not. In order to measure the significance, there are some predefined
tests which could be applied. These tests are called the tests of
significance or simply the significance tests.
In the process of testing for statistical significance, there are the
following steps:
1. Stating a Hypothesis for Research
2. Stating a Null Hypothesis
3. Selecting a Probability of Error Level
4. Selecting and Computing a Statistical Significance Test
5. Interpreting the results
There are basically two types of errors:
Type I
Type II
Type I Error
The type I error occurs when the researcher finds out that the
relationship assumed through research hypothesis does exist; but in
reality, there is evidence that it does not exist. In this type of error, the
researcher is supposed to reject the research hypothesis and accept the
null hypothesis, but its opposite happens. The probability that
researchers commit Type I error is denoted by alpha (α).
Type II Error
The type II error is just opposite the type I error. It occurs when it is
assumed that a relationship does not exist, but in reality it does. In this
type of error, the researcher is supposed to accept the research
hypothesis and reject the null hypothesis, but he does not and the
opposite happens. The probability that a type II error is committed is
represented by beta (β).
statistical Hypothesis
a statement about the value of a population parameter, in case of
two hypotheses, the statement assumed to be true is called the null
hypothesis (notation H0) and the contradictory statement is called
the alternative hypothesis (notation Ha).
The significance level, also denoted as alpha or α, is the
probability of rejecting the null hypothesis when it is true. For example,
a significance level of 0.05 indicates a 5% risk of concluding that a
difference exists when there is no actual difference.
The critical region is the region of values that corresponds to the
rejection of the null hypothesis at some chosen probability level.
A test of a statistical hypothesis, where the region of rejection is on
only one side of the sampling distribution, is called a one-tailed
test. two-tailed test is a method in which the critical area of a
distribution is two-sided and tests whether a sample is greater than or
less than a certain range of values. It is used in null-
hypothesis testing and testing for statistical significance.
we have to maximise the linear function Z subject to certain conditions
determined by a set of linear inequalities with variables as non-negative. There
are also some other problems where we have to minimise a linear function
subject to certain conditions determined by a set of linear inequalities with
variables as non-negative. Such problems are called Linear Programming
Problems.
FORMULATION OF THE LINEAR PROGRAMMING MODEL
Three components are: 1. The decision variable 2. The environment
(uncontrollable) parameters 3. The result (dependent) variable.
General Linear Programming Problem •
Maximize (minimize) a linear objective function z = c1x1 + c2x2 + · · ·
+ cnxn with decision variables x1, x2, . . . , xn.
• Subject to sign restrictions on each variable: xi ≥ 0, or xi
unrestricted (urs), and linear inequality or equality constraints a1,1x1
+ a1,2x2 + · · · + a1,nxn ≤ or ≥ or = b1 a2,1x1 + a2,2x2 + · · · + a2,nxn ≤
or ≥ or = b2 · · · am,1x1 + am,2x2 + · · · + am,nxn ≤ or ≥ or = bm.
SOLVING LPP GRAPHICALLY
A linear programming problem involves constraints that contain
inequalities. An
inequality is denoted with familiar symbols, <, >, ≤≤, and ≥≥. Due to
difficulties with strict inequalities (< and >), we will only focus
on≤≤ and≥≥.
In order to have a linear programming problem, we must have:
Inequality constraints
An objective function, that is, a function whose value we either
want to be as large as possible (want to maximize it) or as small as
possible (want to minimize it).
Transportation problem
is a special kind of Linear Programming Problem (LPP) in which goods
are transported from a set of sources to a set of destinations subject to
the supply and demand of the sources and destination respectively such
that the total cost of transportation is minimized.
The Transportation Method of linear programming is applied to the
problems related to the study of the efficient transportation routes i.e.
how efficiently the product from different sources of production is
transported to the different destinations, such as the
total transportation cost is minimum
standard model for linear programming (LP) problems is
defined as minimization of a cost function subject to equality
constraints and nonnegative design variables. ... The concept
of basic solutions of a rectangular system of linear equations
Ax = b is explained and basic and nonbasic variables are
defined.
