Usage | Course Paper

Page 1 of 14

Linear Optimization / Linear

Programming Notes

Introduction …………………………………………………………………………………………………………………… 1

LP Problems……………………………………………………………………………………………………………………. 2

Low-fat Cake Example ………………………………………………………………………………………………….. 5

Computer Solution Using R …………………………………………………………………………………………… 6

Graphical Solution ……………………………………………………………………………………………………….. 7

Duality in linear optimization………………………………………………………………………………………….. 11

Introduction

The purpose of linear optimization or linear programming is to maximize or minimize a given

numerical function dependent on a set of variables such to certain constraints. Linear

programming, or LP, involves optimizing (either maximizing or minimizing) a linear function by

satisfying a set of linear constraints. These constraints can be equalities or inequalities such as

less than, less than or equal to, etc. In 1947, George Dantzig developed the simplex method for

solving linear programming problems. World War II had ended in 1945 but there was still

considerable interest in the complex logistics of troop and resource movements. These were

some of the early problems that linear programming sought to address. The use of the word

programming was meant to mean planning rather than computer programming, although today

I think it is more ubiquitous.

There are a few “common” components of an LP problem. LP problems have a objective

function, i.e. the numerical function to be optimized. LP problems have decision variables that

relate to decisions that can be made in the context of the LP problem. Decision variables can

be controlled. LP problems have parameters, i.e. input data that cannot be controlled but

directly influence the solution of the problem. LP problems have constraints. These

constraints, or restrictions, impose conditions on the problem and its solution.

To minimize the following text I’ll drop the designation linear optimization and/or linear

programming and simply refer to our discussion as one on LP problems. Note that I’m only

including linear problems but that nonlinear optimization certainly exists and is very important.

Page 2 of 14

I also will not cover integer programming in this document. But that area of optimization also

comprises an important set of problems to consider.

LP Problems

Let’s consider a simple example that we can help us understand what LP problems are, look like

and that we can refer back to as we get deeper into the details of optimization. This example is

from Prof. Alexandra Seco’s lecture in Linear Programming at the Polytechnic Institute of Leiria

in Leiria, Portugal. You can search for Alexandra Seco and Linear Programming to obtain a copy

of Prof. Seco’s entire PowerPoint presentation. Let’s consider a nutritionist that is developing a

recipe for a low-fat cake.

The fat recipe is obtained through the use of butter and vegetable oil. The butter has 6

grams of unsaturated fat and 1 gram of saturated fat per soup spoon, while vegetable

oil contains 1 gram of unsaturated fat and 4 grams of saturated fat per soup spoon. The

recipe must contain at least 34 grams of unsaturated fat and 44 grams of saturated fat

and no more than 25 soup spoons fat will be used. Formulate the problem, given that

you want to minimize the calories recipe and knowing that the butter has 100 calories

per spoon, while the vegetable oil has 115 calories per spoon.

Prof. Alexandra Seco, 2016, Linear Programming

As we discussed in class we need to identify our decision variables. In this case we need to find

the number of spoons of butter and the number of spoons of vegetable oil to use in the recipe.

Let’s just designate these 𝑥1 and 𝑥2 respectively. And, we need to define our objective

function. What we want to do is to minimize the calories in our recipe given the number of

calories in butter and vegetable oil. So, our objective function is:

𝑀𝑖𝑛: 100𝑥1+115𝑥2

We can also create a table of the amount of saturated and unsaturated fat for butter and

vegetable oil as follows:

Butter

Vegetable oil

Unsaturated fat

6

1

Saturated fat

1

4

From our problem statement we can identify several constraints. For example there are

restrictions for saturated and unsaturated fat as follows:

Page 3 of 14

𝑈𝑛𝑠𝑎𝑡𝑢𝑟𝑎𝑡𝑒𝑑 𝑓𝑎𝑡: 6𝑥1+ 𝑥2 ≥34

𝑆𝑎𝑡𝑢𝑟𝑎𝑡𝑒𝑑 𝑓𝑎𝑡: 𝑥1+4𝑥2 ≥44

There is also a constraint associated with the maximum number of soup spoons or tablespoons

of fat as follows: 𝑥1+ 𝑥2 ≤25

And of course we have the normal nonnegativity constraints:

𝑥1 ≥0, 𝑥2≥0

Therefore, our overall LP problem is: 𝑀𝑖𝑛: 100𝑥1+115𝑥2

subject to (or s.t.): 6𝑥1+ 𝑥2 ≥34

𝑥1+4𝑥2 ≥44

𝑥1+ 𝑥2 ≤25

𝑥1 ≥0, 𝑥2≥0

Just as an aside I’d like to mention that any LP problem can be reduced to the canonical form

which is: 𝑀𝑖𝑛: 𝑧= 𝑐1𝑥1+ 𝑐2𝑥2+ ⋯+ 𝑐𝑛𝑥𝑛

s.t.: 𝑎11𝑥1+ 𝑎12𝑥2+ ⋯+ 𝑎1𝑛𝑥𝑛 ≥ 𝑏1

𝑎21𝑥1+ 𝑎22𝑥2+ ⋯+ 𝑎2𝑛𝑥𝑛 ≥ 𝑏2

⋮

𝑎𝑚1𝑥1+ 𝑎𝑚2𝑥2+ ⋯+ 𝑎𝑚𝑛𝑥𝑛 ≥ 𝑏𝑚

𝑥1,𝑥2,…,𝑥𝑛 ≥0

So, in the canonical form our LP problem has an objective function:

𝑀𝑖𝑛: 𝑧= 𝑐1𝑥1+ 𝑐2𝑥2+ ⋯+ 𝑐𝑛𝑥𝑛

with: decision variables 𝑥1,𝑥2,…,𝑥𝑛; coefficients of the objective function 𝑐1,𝑐2,…,𝑐𝑛;

technical coefficients 𝑎11,𝑎12,…,𝑎1𝑛, 𝑎21,𝑎22,…,𝑎2𝑛, 𝑎𝑚1,𝑎𝑚2,…,𝑎𝑚𝑛; independent terms

(constraint values) 𝑏1,𝑏2,…,𝑏𝑚; constraints ∑𝑎𝑖𝑗𝑥𝑗 ≥ 𝑏𝑖 (𝑖=1,2,…,𝑚)

𝑛

𝑗=1 ; as well as the

nonnegativity constraints 𝑥𝑗 ≥0,(𝑗=1,2,…,𝑛). It should be obvious that all this will lead us

to developing a system of linear equations upon which we can work some matrix magic. But

before we move on let’s just look at a couple different forms LP problems can be presented in.

In Cartesian form:

𝑀𝑖𝑛: 𝒛= ∑ 𝑐𝑗𝑥𝑗

𝑛

𝑗=1

s.t.: ∑𝑎𝑖𝑗𝑥𝑗 ≥ 𝑏𝑖 (𝑖=1,2,…,𝑚)

𝑛

𝑗=1

𝑥𝑗 ≥0,(𝑗=1,2,…,𝑛)

In Matrix form: 𝑀𝑖𝑛:𝒛= 𝒄𝑇𝒙

s.t.: 𝐴𝒙 ≥𝒃

𝒙 ≥𝟎

in which:

𝒄= [𝑐1

𝑐2

⋮

𝑥2

⋮

𝑏2

⋮

0⋮0],𝑎𝑛𝑑