Separable Programming - Example

In this section, we provide an example of separable programming.

exampleExample

Maximize f0 (x1, x2) = 5x1 - x12 + 3x2 - x22

subject to

f1 (x1, x2) = 2x14 + x2 ≤ 32
f2 (x1, x2) = x1 + 2x22 ≤ 32

x1, x2 ≥ 0
The break points of x1 are 0, 1, 2 and x2 are 0, 1, 2, 3, 4.

Solution.

f01 (x1) = 5x1 - x12
f11 (x1) = 2x14
f21 (x1) = x1

f02 (x2) = 3x2 - x22
f12 (x2) = x2
f22 (x2) = 2x22

a1k f01(a1k) f11(a1k) f21(a1k) Weight
0 0 0 0 W11
1 4 2 1 W12
2 6 32 2 W13

a2k f02(a2k) f12(a2k) f22(a2k) Weight
0 0 0 0 W21
1 2 1 2 W22
2 2 2 8 W23
3 0 3 18 W24
4 -4 4 32 W25

The linear model can be written as:

Maximize 0W11 + 4W12 + 6W13 + 0W21 + 2W22 + 2W23 + 0W24 - 4W25

subject to

0W11 + 2W12 + 32W13 + 0W21 + W22 + 2W23 + 3W24 + 4W25 + S1 = 32
0W11 + W12 + 2W13 + 0W21 + 2W22 + 8W23 + 18W24 + 32W25 + S2 = 32
W11 + W12 + W13 = 1
W21 + W22 + W23 + W24 + W25 = 1

Wjk ≥ 0.

Recall that for any j not two Wjk can be positive; and if two are positive they must be adjacent. The successive simplex tables are given below:

Table 1

On small screens, scroll horizontally to view full calculation

  cj 0 4 6 0 2 2 0 -4 0 0  
cB Basic Variables B W11 W12 W13 W21 W22 W23 W24 W25 S1 S2 Solution Values
b=( XB)
0 S1 0 2 32 0 1 2 3 4 1 0 32
0 S2 0 1 2 0 2 8 18 32 0 1 32
0 W11 1 1 1 0 0 0 0 0 0 0 1
0 W21 0 0 0 1 1 1 1 1 0 0 1
zj-cj   0 -4 -6 0 -2 -2 0 4 0 0  

W11 departs and W13 enters.

Table 2

  cj 0 4 6 0 2 2 0 -4 0 0  
cB Basic Variables B W11 W12 W13 W21 W22 W23 W24 W25 S1 S2 Solution Values
b=( XB)
0 S1 -32 -30 0 0 1 2 3 4 1 0 0
0 S2 -2 -1 0 0 2 8 18 32 0 1 30
6 W13 1 1 1 0 0 0 0 0 0 0 1
0 W21 0 0 0 1 1 1 1 1 0 0 1
zj-cj   6 2 0 0 -2 -2 0 4 0 0  

S1 is replaced by W22. This is possible since W21 is a basic variable.

If one weight Wjk is in the current basis, then only the adjacent weights Wjk - 1 and Wjk + 1 are to be considered for entry into the solution.

Table 3

Use Horizontal Scrollbar to View Full Table Calculation

  cj 0 4 6 0 2 2 0 -4 0 0  
cB Basic Variables B W11 W12 W13 W21 W22 W23 W24 W25 S1 S2 Solution Values
b=( XB)
2 W22 -32 -30 0 0 1 2 3 4 1 0 0
0 S2 62 59 0 0 0 4 12 24 -2 1 30
6 W13 1 1 1 0 0 0 0 0 0 0 1
0 W21 32 30 0 1 0 -1 -2 -3 -1 0 1
zj-cj   -58 -58 0 0 0 2 6 12 2 0  

W21 departs and W12 enters.

Table 4

  cj 0 4 6 0 2 2 0 -4 0 0  
cB Basic Variables
B		 W11 W12 W13 W21 W22 W23 W24 W25 S1 S2 Solution Values
b=( XB)
2 W22 0 0 0 1 1 1 1 1 0 0 1
0 S2 -14/15 0 0 -59/30 0 179/30 239/15 299/10 -1/30 1 841/30
6 W13 -1/15 0 1 -1/30 0 1/30 1/15 1/10 1/30 0 29/30
4 W12 16/15 1 0 1/30 0 -1/30 -1/15 -1/10 -1/30 0 1/30
zj-cj   58/15 0 0 29/15 0 1/15 32/15 31/5 1/15 0  

Thus, the optimum values of the weights are:
W12 = 1/30, W13 = 29/30 & W22 = 1

The optimum values of the decision variables are:

x1 = a1k W1k = a13 W13 = 2 X 29/30 = 1.9333 = 1.93 (approx.)

x2 = a2k W2k = a22 W22 = 1 X 1 = 1

The maximum value of the objective function is
5 X 1.93 - (1.93)2 + 3 X 1 - (1)2 = 7.9251

The term nonlinear programming refers to a situation where either the objective function or the constraints or both are nonlinear functions of decision variables. The simplest nonlinear extension of a linear programming model is the quadratic programming model. This chapter discussed how a quadratic programming problem can be solved by a little modification of the simplex technique. Further, you learned separable programming technique for solving nonlinear problems.

Share This Article

Menu

Transportation Problem Linear programming Simplex Method Assignment Problem