introduction

Question 1

linear programming problem

Answer 1

minimising or maximising a linear function subject to linear constraints

Question 2

How to develop an LP model

Answer 2

1. decide the decision variables
2. determine the objective function
3. what are the explicit constraints
4. what are the implicit constraints

Question 3

Decision variables

Answer 3

x₁,x₂,…,xₙ

Question 4

Objective function

Answer 4

c₁x₁ + c₂x₂ + … +cₙxₙ

Question 5

cost coefficiants

Answer 5

c₁,c₂,…,cₙ

Question 6

constraints

Answer 6

a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ {≤,≥,=} b₁

…

Question 7

components of an LP problem in matrix form

Answer 7

decision vector, x (column vector of decision variables)
constraint matrix, A (matrix with rows for each constraint)
cost vector, c (column vector with all cost coeficiants)
RHS vector, b (with all RHS of all the constraints)
matrix with all the symbols from the constrains, D

Question 8

LP in matrix form

Answer 8

min/max (cᵀx) subject to AxDb plus any implicit constraints

Question 9

feasible points

Answer 9

are the points x that satisfy all the constraints

Question 10

feasible region

Answer 10

the set of all feasible points

Question 11

standard form

Answer 11

min cᵀx s.t. Ax = b x≥0

Question 12

canonical form

Answer 12

min cᵀx s.t. Ax ≥ b x≥0

Question 13

how to get into standard form (or canonical form)

Answer 13

1. multiply objective func by -1 to be into minimise
2. add slack variables to get into an equality. if ≥ then -s if ≤ then +s
3. to convert a fre variable replace it with two non-negative variables
4. separate upper and lower bounds into individual restrictions then correct via step 2.