Linear Programming :A Math notes

4. Linear Programming

Convex Combination :

If x₁ and x₂ are two elements in a set (taken ) such that if a + b = 1 ('a' and 'b' are scalar ), then convex combination of x₁, x₂ ∈ S (artritrany elements) is given by (ax₁ + bx₂).

Also, we can write it as

            ax₁ + (1-a)x₂    [∵ a + b = 1]

Convex Region :

A region is said to be convex if the line-segment drawn between any two points of this region is completely existing within this region.

    A circle, a square, a rectangle, a rhombus, a trapezium etc are (all) convex regions. A quadrilateral is a convex region, but a pentagon cannot be always  a convex region.

Liner set : Affine set : Convex set

A set A is linear set (a vector subspace of X, where X is any set in the R) if (∝ x₁ + β x₂) ∈ A, where ∝, β ∈ R ; x₁, x₂ ∈ A

     A set A is affine set (a vector subspace of X, where X is any set in R) if [∝x₁ + (1 - ∝)x₂] ∈ A, where ∝ ∈ R; x₁ , x₂ ∈ A.

    A set A is convex set (a vector subspace of X, where X is any set in R) if [∝x₁ + (1 - ∝)x₂] ∈ A, where x₁, x₂ ∈ A; ∝ ∈ [0, 1]; here [0,1] is the closed interval, i.e. o ≤ ∝ ≤ 1.

Hyperplane

A set H = {x₁ , x₂,......,x_n} is called a hyperplane if c₁x₁ + c₂x₂ + ........ + c_nx_n = Z (Z ∈ R), c are scalar. Briefly we write H = {x/cx = Z}; Z ∈ Rand c is a scalar; as a hyperplane.

Convex Hull

The set Hc of all convex combinations of points in the set A (a vector subspace of X, where X is any set in the R) is a convex hull.

NOTE : If 'aff' shows the word 'affine' and 'aff(a)' denotes the 'affine set A' then 

(i) aff (aff A) = aff A

(ii) aff (A₁ + A₂) = aff (A₁) + aff (A₂)

Here 't' stand for union 'U' of sets.

Ex. Show that intersection of two convex sets is convex.

Soln. Let S₁ and S₂ be two convex sets.

        ∴ x₁, x₂ ∈ (S₁ ⋂ S₂), any two elements.

    ⇒ x₁, x₂ ∈ S₁ and x₁, x₁ ∈ S₂

    ⇒[λx₁ + (1 - λ) x₂] ∈ S₁ and [λx₂ + (1 - λ) x₂] ∈ S₂     [∵ S₁ & S₂ are convex]

    ⇒ [λx1 + (1 - λ) x₂] ∈ S₁ ⋂ S₂     [λ is a scalar ; λ ∈ R ]

    Hence, (S₁ ⋂ S₂) is also convex.

Note : Intersection of finite (n ∈ N) convex sets is also a convex set.

Ex. Show taht a hyperplan is a convex set.

Soln. Let H = {x| cx = z ; c is scalar ; z ∈ R} be a hyperplane.

    Suppose  x₁, x₂ ∈ H, any two elements.

    ∴ cx₁ = z -----------(1)

    and cx₂ = z --------(2),

by property of H ( as definition & supposition ) Let the convex combination of x₁, x₂ ∈ H be

        x₃ = λx₁ + (1 - λ) x₂    [λ is a scalar ; λ ∈ R]

    ∴ cx₃ = c [λx₁ + (1 - λ) x₂]

    ⇒ cx₃ = cλx₁ + c(1 - λ) x₂

    ⇒ cx₃ = λcx₁ + (1 - λ) cx₂

    ⇒ cx₃ = λz + (1 - λ)z (from 1. & 2.)

    ⇒ cx₃ = λz

∴ x₃ = λx₁ + (1 - λ) x₂ ∈ H (also)

Hence, the hyperplane H is a convex set.

Ex. Show that the set of all feasible solutions to a linear programming problem is a convex set.

Soln. For convenience, let us consider a l.p.p 

        optimize z = cx

        s.t. Ax = b

Here Q is the set of x ≥ 0 (A ∈ R; b ∈ Q) relation numbers. Suppose that x₁, x₂ (x₁, x₂ ≥ 0) be two feasible solutions (taken arbitrarily) in the set of feasible solutions to the above l.p.p.

        ∴ Ax₁ = b ------------(1)

        and Ax₂ = b ----------(2),

by property (constraint) of x₁ and x₂ be given as

        x₃ = λx₁ + (1 - λ) x₂    [λ is a scalar ; λ ∈ R]

Now we have

        A.x₃ = A . [λx₁ + (1 - λ) x₂]

    ⇒ A.x₃ = Aλx₁ + A(1 - λ) x₂

    ⇒ A.x₃ = λ . Ax₁ + (1 - λ) .Ax₂

    ⇒ A.x₃ = λb +  (1 - λ)b    (from 1. & 2.)

    ⇒ A.x₃ = b

    ∴ x3 = λx₁ + (1 - λ) x₂ is also a feasible solution to the l.p.p. and thus belongs to the set of feasible solution to the l.p.p.

Hence, the set of all feasible solutions to a linear programming problem is a convex set.

Ex. Prove that a line-segment is a convex set.

Soln. Let us consider a line-segment P ₁ P₂ given as

                    ax + by = c --------- (1)

where a, b are scalars.

Suppose that P₁ (x₁, y₁) and P₂ (x₂, y₂) be two end-points of the line-segment P₁P₂. the convex combination of P₁ and P₂ is given as (suppose)

                    ∝ = λx₁ + (1 - λ) x₂ ---------- (1)

                    β = λy₁ + (1 - λ) y₂ -----------(2)

where λ is a scalar ; λ ∈ R

Now, 

            a∝ + bβ = a[λx₁ + (1 - λ) x₂] + b[λy₁ + (1 - λ) y₂]

            a∝ + bβ = λa x₁ + λb y₂ + (1 - λ) ax₂ + (1 - λ) by₂   [since P₁ & P₂ are on the line-segment, therefore ax₁ + by₁ = c & ax₂ + by₂ = c ]

            ⇒ a∝ + bβ = λ(ax₁  + by₁) + (1 - λ)(ax₂  + by₂)

            ⇒ a∝ + bβ = λc + (1 - λ)c

            ⇒ a∝ + bβ = c

Hence, the convex combination of P₁ and P₂ is also belonging to the line-segment.

Hence a line-segment is a convex set.

Ex. Show that a circle is a convex set.

Soln.  For convenience, let us consider a circle of radius '⍴' and center at the origin O (0, 0) and thus its equation is

                x² + y² = ⍴² ---------- (1)

let (x₁, y₁) and (x₂, y₂) be two points in the circle.

            ∴ x₁² +y₁² ≤ ⍴² -------- (2)

            and x₂² + y₂² ≤ ⍴² -------- (3)

The convex  combination of these two points is given as

            u = λx₁ + (1 - λ) x₂

            v = λy₁ + (1 - λ) y₂

Where λ is a scalar ; λ ∈ R.

Now, 

            u² + v² = [λx₁ + (1 - λ) x₂]² + [λy₁ + (1 - λ) y₂]²

    ⇒ u² + v² = λ² (x₁² + y₁²) + (1 - λ)² (x₂² + y₂²) + 2λ (1 - λ) (x₁x₂ + y₁y₂)

    ⇒ u² + v²  ≤  λ²⍴² + (1 - λ)² ⍴²+ 2λ (1 - λ) (x₁x₂ + y₁y₂) ----------(4) (by using 2. & 3.)

Now, from cauch's inequality

x₁x₂ + y₁y₂ < √x₁² + y₁² . √x₂² + y₂² = √⍴²√⍴²

∴ from (4),

    ⇒ u² + v²  <  λ²⍴² + (1 - λ)² ⍴²+ 2λ (1 - λ) √⍴²√⍴²

    ⇒ u² + v²  < [ λ² + (1 - λ)² + 2λ (1 - λ) ] ⍴²

    ⇒ u² + v²  < [ λ + (1 - λ)]² ⍴² = ⍴²

    ⇒ u² + v²  < ⍴²  ⇒Convex combination of (x₁, y₁) and (x₂, y₂) is also in the circle.

Hence, a circle a convex set.

General from of linear Programming problem

A linear programming problem may be written in generalized from as

Optimize z = c₁x₁ + c₂x₂ + _ _ _ _ +c_nx_n

s.t. a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + _ _ _ _ _ + a_1nx_n  ≤ or = or ≥ b₁

    a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + _ _ _ _ _ + a_2nx_n  ≤ or = or ≥ b₂

    _{-------        ------        ------                           --------                -------}      

    -------        ------        ------                           --------                -------      

    a_m1x₁ + a_m2x₂ + a_m3x₃ + _ _ _ _ _ + a_mnx_n  ≤ or = or ≥ b_m

        x_1, x_2, x_{3, ------ ,} x_n  ≥  0.

Where (i) optimize may be maximize or minimize 

            (ii) the matrix

                        c = [c₁ c₂ c₃ -- -- -- -- c_n] or c = [c_i]_1✕2 is the matrix of coefficients of the decision-variable x_1, x_2, x_{3, ------ ,} x_n in the objective function z.