Linear Programming

Question 1

What is the purpose of Linear programming?

Answer 1

Efficient use of resources

Question 2

What are the characteristics of Linear programming?

Answer 2

• LP uses mathmatical models to describe the problem of concern.
• All the functions are linear
• Programming=Planning

Question 3

When can the graphical method be used to solve LP?

Answer 3

It can be used when the problem has two (also three but very hard) decision variables.

Question 4

What are the 5 variables usually used in LP and what to they mean?

Answer 4

Z value of overall measure of performance
x_j Level of activity j
c_j increase in Z that would result from each unit in level of activity j
b_i amount if resouce i that is avaliable for allocation to activities
a_ij amount of reasource i consumed by each unit of activity j

Question 5

What is the objective function?

Answer 5

The function that is to be optimized (Maximized or minmized) Z=c_1x_1+…c_nx_n

Question 6

What are the restrictions called?

Answer 6

Constraints

Question 7

What are the functional contraints?

Answer 7

The first m constraints ( Those with a function of all variables in the left hand side.

Question 8

What are the non negativity constraints

Answer 8

x_j>=0

Question 9

What is a CPF?

Answer 9

A corner-point feasible solutio. Lies on the corner of the feasible region. The best CPF must be an optimal solution.

Question 10

What is Proportionality assumption?

Answer 10

The contribution of each activity to teh value od the objective function Z is proportional to the level of activity x_j as represented by by the X_jC_j term in the objective function. Can also be in the constraint represented by a_ijx_j.

Question 11

Additivity assumption?

Answer 11

Every function in a linear programming model is the sum of the individual contributions of the represpective activities

Question 12

Divisibility assumption?

Answer 12

Decision variables are allowed to have any value including non integer values.

Question 13

Certainty assumption?

Answer 13

Value assigned to each parameter of a linear programming model is assumed to be a known constant.

Question 14

What is the simplex method?

Answer 14

A general procedure for solving linear programming problems. It is an algebraic procedure.

Question 15

What is the optimality test?

Answer 15

If a CPF solution has no adjacent CPF solutions that are better then it must be an optimal solution. It is used to determine if an optimal solution has been reached.

Question 16

How does one solve an problem using the simplex method?

Answer 16

Initialization: choose an initian CPF
Optimality test: compare to adjacent CPF.
If optimal- Stop
If not optimal- Move to a better adjacent CPF.

Question 17

What are the key solution concepts?

Answer 17

Solution concept 1: The simplex method focuses solely on CPF solutions. For any problem at least one optimal solution.
Concept 2: The simplex method is an iterative algorithm.
Concept 3: When ever possible the initialization is choosen to the origin.
Concept 4: It is much quicker to compute an adjacent CPF. Therefore, simplex method always chooses a solution next to it.
Consept 5: compares to the solutions adjacent and moves to the best one
Concept 6: If it is better than the adjacent CPF then it is the best.

Question 18

How do you set up the Simplex method?

Answer 18

Introduce a slack variable and set the inequality to an equality.

Question 19

What is an Augmented soulution?

Answer 19

A solution for the original variables ( the decision variables) That has been augmented by the corresponding values of the slack variables.

Question 20

What is a basic solution?

Answer 20

An augmented corner point solution.

Question 21

What in a basic feasible solution?

Answer 21

An augmented CPF solution.