Operations Research Simplified produced by www.universalteacher.com

Nonlinear Programming

Separable Programming-Example

Example

Maximize f₀ (x₁, x₂) = 5x₁ - x₁² + 3x₂ - x₂²

subject to

f₁ (x₁, x₂) = 2x₁⁴ + x₂ £ 32
f₂ (x₁, x₂) = x₁ + 2x₂² £ 32

x₁, x₂ ³ 0
The break points of x₁ are 0, 1, 2 and x₂ are 0, 1, 2, 3, 4.

Solution.

f₀₁ (x₁) = 5x₁ - x₁²
f₁₁ (x₁) = 2x₁⁴
f₂₁ (x₁) = x₁

f₀₂ (x₂) = 3x₂ - x₂²
f₁₂ (x₂) = x₂
f₂₂ (x₂) = 2x₂²

a₁^k	f₀₁(a₁^k)	f₁₁(a₁^k)	f₂₁(a₁^k)	Weight
0	0	0	0	W₁¹
1	4	2	1	W₁²
2	6	32	2	W₁³

a₂^k	f₀₂(a₂^k)	f₁₂(a₂^k)	f₂₂(a₂^k)	Weight
0	0	0	0	W₂¹
1	2	1	2	W₂²
2	2	2	8	W₂³
3	0	3	18	W₂⁴
4	-4	4	32	W₂⁵

The linear model can be written as:

Maximize 0W₁¹ + 4W₁² + 6W₁³ + 0W₂¹ + 2W₂² + 2W₂³ + 0W₂⁴ - 4W₂⁵

subject to

0W₁¹ + 2W₁² + 32W₁³ + 0W₂¹ + W₂² + 2W₂³ + 3W₂⁴ + 4W₂⁵ + S₁ = 32
0W₁¹ + W₁² + 2W₁³ + 0W₂¹ + 2W₂² + 8W₂³ + 18W₂⁴ + 32W₂⁵ + S₂ = 32
W₁¹ + W₁² + W₁³ = 1
W₂¹ + W₂² + W₂³ + W₂⁴ + W₂⁵ = 1

W_j^k ³ 0.

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

Table 1

	c_j	0	4	6	0	2	2	0	-4	0	0
c_B	Basic Variables B	W₁¹	W₁²	W₁³	W₂¹	W₂²	W₂³	W₂⁴	W₂⁵	S₁	S₂	Solution Values b=( X_B)
0	S₁	0	2	32	0	1	2	3	4	1	0	32
0	S₂	0	1	2	0	2	8	18	32	0	1	32
0	W₁¹	1	1	1	0	0	0	0	0	0	0	1
0	W₂1	0	0	0	1	1	1	1	1	0	0	1
z_j-c_j		0	-4	-6	0	-2	-2	0	4	0	0

W₁¹ departs and W₁³ enters.

Table 2

	c_j	0	4	6	0	2	2	0	-4	0	0
c_B	Basic Variables B	W₁¹	W₁²	W₁³	W₂¹	W₂²	W₂³	W₂⁴	W₂⁵	S₁	S₂	Solution Values b=( X_B)
0	S₁	-32	-30	0	0	1	2	3	4	1	0	0
0	S₂	-2	-1	0	0	2	8	18	32	0	1	30
6	W₁³	1	1	1	0	0	0	0	0	0	0	1
0	W₂¹	0	0	0	1	1	1	1	1	0	0	1
z_j-c_j		6	2	0	0	-2	-2	0	4	0	0

S₁ is replaced by W₂². This is possible since W₂¹ is a basic variable.

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

Table 3

	c_j	0	4	6	0	2	2	0	-4	0	0
c_B	Basic Variables B	W₁¹	W₁²	W₁³	W₂¹	W₂²	W₂³	W₂⁴	W₂⁵	S₁	S₂	Solution Values b=( X_B)
2	W₂²	-32	-30	0	0	1	2	3	4	1	0	0
0	S₂	62	59	0	0	0	4	12	24	-2	1	30
6	W₁³	1	1	1	0	0	0	0	0	0	0	1
0	W₂¹	32	30	0	1	0	-1	-2	-3	-1	0	1
z_j-c_j		-58	-58	0	0	0	2	6	12	2	0

W₂¹ departs and W₁² enters.

Table 4

	c_j	0	4	6	0	2	2	0	-4	0	0
c_B	Basic Variables B	W₁¹	W₁²	W₁³	W₂¹	W₂²	W₂³	W₂⁴	W₂⁵	S₁	S₂	Solution Values b=( X_B)
2	W₂²	0	0	0	1	1	1	1	1	0	0	1
0	S₂	-14/15	0	0	-59/30	0	179/30	239/15	299/10	-1/30	1	841/30
6	W₁³	-1/15	0	1	-1/30	0	1/30	1/15	1/10	1/30	0	29/30
4	W₁²	16/15	1	0	1/30	0	-1/30	-1/15	-1/10	-1/30	0	1/30
z_j-c_j		58/15	0	0	29/15	0	1/15	32/15	31/5	1/15	0

Thus, the optimum values of the weights are:
W₁² = 1/30, W₁³ = 29/30 & W₂² = 1

The optimum values of the decision variables are:

x₁ = a₁^k W₁^k = a₁³ W₁³ = 2 X 29/30 = 1.9333 = 1.93 (approx.)

x₂ = a₂^k W₂^k = a₂² W₂² = 1 X 1 = 1

The maximum value of the objective function is
5 X 1.93 - (1.93)² + 3 X 1 - (1)² = 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.

Operations Research Contents