Linear Optimization with Application

A mathematical optimization model consists of an objective function and a set of constraints in the
form of a system of equations or inequalities. Those who manage and control systems of men and
equipment face the continuing problem of improving (e.g., optimizing) system performance.

To identify methods for improvement of system operation, one must construct a synthetic
representation or model of the physical system, which could be used to describe the effect of a
variety of proposed solutions.

A model is a representation of the reality that captures "the essence" of reality, model captures
some aspect of the reality it attempts to represent.

The mathematical (i.e., analytical) model that describes the behaviour of the measure of
effectiveness is called the objective function. If the objective function is to describe the behaviour of
the measure of effectiveness, it must capture the relationship between that measure and those
variables that cause it to change. System variables can be categorized as decision variables and
parameters. A decision variable is a variable, that can be directly controlled by the decision-
maker. There are also some parameters whose values might be uncertain for the decision-maker.

Formulation of a meaningful objective function is usually a tedious and frustrating task. Attempts to
develop the objective function may fail. Failure could result because the analyst chose the wrong set
of variables for inclusion in the model.

Ultimate success is more often preceded by a string of failures and small successes. At each stage of
the development process the analyst must judge the adequacy and validity of the model.

Optimization-Modelling Process

Optimization modelling requires appropriate time. The general procedure that can be used in the
process cycle of modelling is to: (1) describe the problem, (2) prescribe a solution, and (3) control the
problem by assessing/updating the optimal solution continuously, while changing the parameters
and structure of the problem. Clearly, there are always feedback loops among these general steps.
 There are a variety of software packages to solve optimization problems. For example, LINDO or
your WinQSB solve linear program models and LINGO and What'sBest! solve nonlinear and linear
problems.

Feasible and Optimal Solutions: A solution value for decision variables, where all of the constraints
are satisfied, is called a feasible solution. Most solution algorithms proceed by first finding a feasible
solution, then seeking to improve upon it, and finally changing the decision variables to move from
one feasible solution to another feasible solution. This process is repeated until the objective
function has reached its maximum or minimum. This result is called an optimal solution.

There are well over 4000 solution algorithms for different kinds of optimization problems. The
widely used solution algorithms are those developed for the following mathematical programs:
convex programs, separable programs, quadratic programs and the geometric programs.

Linear Program

Linear programming deals with a class of optimization problems, where both the objective function
to be optimized and all the constraints, are linear in terms of the decision variables.

Any LP problem consists of an objective function and a set of constraints.

When you formulate a decision-making problem as a linear program, you must check the following
conditions:
 1. The objective function must be linear. That is, check if all variables have power of 1 and they
are added or subtracted (not divided or multiplied)
2. The objective must be either maximization or minimization of a linear function. The
objective must represent the goal of the decision-maker
3. The constraints must also be linear. Moreover, the constraint must be of the following forms
( £, ³, or =, that is, the LP-constraints are always closed).

The carpenter problem

Maximize 5X1 + 3X2

That is, the net incomes (say, in dollars, or tens of dollars) from selling X1 tables and X2 chairs.

The constraining factors which, usually come from outside, are the limitations on labors (this
limitation comes from his family) and raw material resources (this limitation comes from scheduled
delivery). Production times required for a table and a chair are measured at different times of day,
and estimated to be 2 hours and 1 hour, respectively. Total labor hours per week are only 40 hrs.
Raw materials required for a table and a chair are 1, and 2 units respectively. Total supply of raw
material is 50 units per week. Therefore, the LP formulation is:

Maximize 5 X1 + 3 X2

Subject to:
2 X1 + X2 £ 40 labor constraint
X1 + 2 X2 £ 50 material constraint
and both X1, X2 are non-negative.

The optimal solution, i.e., optimal strategy, is to make X1 = 10 tables, and X2 = 20 chairs. We
may program the carpenter's weekly activities to make 10 tables and 20 chairs. With this (optimal)
strategy, the net income is $110. This prescribed solution was a surprise for the carpenter since,
because of more net income of selling a table ($5), he used to make more tables than chairs!

Graphical Solution Method

If a linear program has a bounded optimal solution, then one of the corner points provides an
optimal solution