Linear Programming - Model Formulation & Graphical Method

General Linear Programming Problem

Consider the following

Optimize (maximize or minimize)
z = c₁x₁ + c₂x₂ + c₃x₃ + .........+ c_nx_n

subject to

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n ( £, =, ³ ) b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n ( £, =, ³ ) b₂
...................................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n ( £, =, ³ ) b_m
x₁, x₂,....., x_n ³ 0

"Mathematical structures are among the most beautiful discoveries made by the human mind" - Douglas Hofstadter

A word of guidance

If you have never taken a statistics course, then you will probably find the following å notation strange, and perhaps even puzzling. To properly understand the text, read the text atleast twice.

In å notation, it is written as

Optimize (maximize or minimize) z = c_jx_j

subject to
a_ijx_j ( £, =, ³ ) b_i; i = 1, 2, ....., m (constraints)

x_j ³ 0; j = 1, 2, ....., n (non-negative restrictions)

The å summation symbol considerably reduces the amount of writing lengthy expressions.

Where all c_j's, a_ij's, b_i's are constants and x_j's are decision variables. The expression ( £, =, ³ ) means that each constraint may take only one of the three possible forms:

• less than or equal to (£)
• equal to (=)
• greater than or equal to (³)

The expression x_j ³ 0 means that the x_j's must be non-negative.