Day 1

Linear programming is concerned with the optimization (minimization or maximization) of a linear function while satisfying a set of linear equality and/or inequality constraints or restrictions

Definition

standard from

It is easy easy to convert constraints from one to form to another

Infeasible problem

Unbounded problem

Linear Programming Modeling

The modeling of a linear programming problem evolves through several stages. Here we are going to study the transportation problem which is a famous one.

Day 2

The simplex method

We presend simplex method as it applies to linear programming problems in standard from.

Example

Convert constraints to equalities by using slack variables

Constraint 1:

Constraint 2:
..
Constarint 3:
...

Initial dictionary:

We need an initial feasible solution

Independent variables (nonbasic variables):
x_1 = 0, x_2 = 0, x_3 = 0

dependent variables (basic variables):
w_1 = 5, w_2 = 11, w_3 = 8

Objective function value is

Question 1: Can the current feasible solution be improved?
Yes, If we increase x1, x2, or x3 the value of the objective funciton increases because the coefficients or x1, x2, or x3 in the objective function are positive

Question 2: Which variable should be chosen to increase?
x1, because it has the largest coefficient in the objective function. (This variable is called entering variable)

Question 3: How much can we increase the entering variable?
By increasing x1 the values of w1, w2, andw3 are changing. We must make sure that they remain non-negative

Since all w1, w2, and w3 should remain non-negative, x1 cannot be larger than the smallest of the bounds. Which means that x1 can be...

The feasible solution is:
x1 = 2.5 x2=0 x3 =0
w1 = 0 w2 =1 we = 1/2

pivoting
Row operations (pivoting) to get the new dictionary

Constraint 1:

Constraint 2:
...
Constraint 2:
...
Objective function:
...

Question 1: Can the current feasible solution be improved?

Question 2: Which variable should be chosen to increase?
Increasing w1 and s2 decreases the value of the objective function because their coefficients int he objective function are negative. The only independent (non basic) variable that we can increase to improve is x3(entering variable).

Question 3: How much can we increase the entering variable?
All the independent variables must remain non-negative. According to the second constraint, changing x3 doest not affect w2. Therefore, only constraints 2 and 3 impose bounds.

The feasible solution is:

Question: Can the current feasible solution be improved?
-> No, All the variables in the objective function have negative coefficients. By increasing them, the value of the objective function decreases.

The Simplex method

Consider the general linear programming problem in standard from:

within each iteration some variables are basic (B)
some variables are non-basic(N)

dictionary

Question 1: Can this solution be improved?

Question 2: Which variable should be chosen to increase?

Question 3: How much can we increase the entering variable x_k?

Day 3

In the previous section we considered problems for which the right-hand sides were all non-negative. This insuerd that the initial dictionary was feasible.

What if not all the right-hand sides are non-negative? How can we find an initial feasible solution? We need to find a feasible solution to start the simplex method. We handle this difficulty by introducing an auxiliary problem (Phase I)

Algorithm

Example:

Initial dictionary (Not feasible)

How can we find a feasible solution to start the simplex method? We should write the auxiliary problem and find its optimal solution. If the optimal value is zero, the optimal solution of the auxiliary problem is a feasible solution of the original problem.

We use simplex method and find the optimal solution of the auxiliary problem

FYI
Auxiliary problem

phaseI : THe process of solving the auxiliary problem to find an initial feasible solution is phase I
phase II : the process of going from a feasible solution to an optimal solution is called phase II.

Optimal solution of auxiliary problem: x_0 = 0, x_1 = 1.33, x_2 = 0.33, w_1 = 0, w_2 =0, w_3 = 0

Feasible solution of the original problem: x1 = 1.33, x2 = 0.33, w1 = 0, w2 = 0, w3 = 0. Now we can use simplex method to solve the original problem (Phase II)

Unboundedness

In this section, we discuss how to detect when the objective function value is unbounded. Let us now take a closer look at the leaving variable computation.

We choose the smallest bound for xk.

Example:

Geometry

용어 정리

entering variable: The variable that goes from nonbasic to basic is called the entering variable.

leaving variable: The variable that goes from basic to non basic is called the leaving variable. The rule just given for selecting a leaving variable describes exactly the process by which we use the rule in practice. That is, we look only at those variables for which ¯aik is positive and among those we select one with the smallest value of the ratio¯bi/¯aik.

pivot: Once the leaving-basic and entering-nonbasic variables have been selected, the move from the current dictionary to the new dictionary involves appropriate row opeartions to achieve the interchange. This step from one dictionary to the next is called a pivot.

phase I: The process of solving the auxiliary problem to find an initial feasible solution is often referred to as Phase I

phase II: The process of going from a feasible solution to an optimal solution is called Phase II.