1. Introduction
1-1. Problem. Obtain maximum profit, when crop A and B are cultivated as under conditions as next table.
Conditions are, 1) available land is 10 ha, 2) available labor is 1,600 man * h , 3) available fertilizer is 2,400 kg annually, for two crops A and B.
Maximize the total profit of crops (A, B), which gives annual profit of 30,000 $ / ha and 20,000 $ / ha respectively. The profits are essentially linear with use, if 10ha land or less is cultivated each year. Labor required for crop A and B are 200 and 100 man * h / ha, and fertilizer required are 100 and 300 kg / ha respectively.
Crop
Available
amount
A
B
Land (ha)
Labor required (man * h / ha)
Fertilizer required (kg / ha)
X1
200
100
X2
100
300
10
1,600
2,400
Profit (100$ / ha)
300
200
LP-vb.xls (with lpd-ex02) An algebraic statement of above relationships is the next three constraints of equations 1, 2, 3, and a objective function of equation 4, which shows the total profit.
X1 + X2 < = 10 (ha) Eq. 1 2 * X1 + X2 < = 16 (100 * man * h / ha) Eq. 2X1 + 3 * X2 < = 24 (100 * kg / ha) Eq. 3
Z = 3 * X1 + 2 * X2 (10,000 * $) Eq. 4
The concepts of linear of programming may be easily understood from a graphical model. The sample problem is a two-dimension (two structural variable) problem that can be shown on a two-dimensional graph at Fig. 1.
Fig. 1 Graphical solution of LP: Land area and constraints 1-2. Graphical solution of LP
Area which satisfies the constraint equations 1, 2, 3 is the convex pentagon OABCD.Those five points are A (0 , 8), B (3, 7), C (6, 4), D (8, 0) and O (0, 0).
Objective function of equation is shown by paralel straight lines, which are shown as Z0 = 3 * X1 + 2 * X2, and shown by broken lines in Figure 1. And Z is maximum 26 at point C (X1 = 6, X2 = 4).
Generally, constraint area is shown by the convex polygon, and the optimal point is obtained at their edges. Therefore, at first we may obtaine the points which are edges of the polygon, and then compare the value of objective function at each edge point as followings:
ZA = 16, ZB = 23, ZC = 26, ZD = 24
Finally, we can find the optimal (maximum) Z is 26, at point C (X1 = 6, X2 = 4).
Maximum profit is 260,000$, when the crop A and B are grown 6 and 4 hectares respectively.
1-3. Mathematical solution
Inequality of Eq.1, 2, 3 will be modified to Eq.5, 6, 7 by using slack variables (X3, X4, X5) as followings.
X1 + X2 + X3 = 10 Eq. 5
2 * X1 + X2 + X4 = 16 Eq. 6
X1 + 3 * X2 + X5 = 24 Eq. 7
Objective of this linear programming is to make Z (equation 8) minimum, which equation is modified from equation 4 by changing sign.
Z = - 3X1 - 2X2 Eq. 8
Generally, these equations are expressed as followings:
Constraints are equations 9.
a11 * X1 + a12 * X2 + … + a1n * Xn = b1
a21 * X1 + a22 * X2 + … + a2n * Xn = b2
……
am1 * X1 + am2 * X2 + … + amn * Xn = bm Eq. 9
And objective function is equation 10, which is to be minimum.
Z = c1 * X1 + c2 * X2 + … + cn * Xn Eq. 10
Where m = 3，n = 5 in this example.
Feasible basic solution correspond to the edges of graphic solution is shown in Table 1.
Table 1 Feasible basic solution
X1
X2
X3
X4
X5
Edge
0
0
10
16
24
O
0
8
2
8
0
A
3
7
0
3
0
B
6
4
0
0
6
C
8
0
2
0
16
D
1-4. Simplex table method
From this Possible base solution, optimal solution is calculated sequentially by so-called Simplex table method.
Where, P1 =（a11，a21 … am1），Pj =（a1 j，a2 j … am j ），P0 =（b1，b2 … bm ） and P3，P4，P5 are called as basic vector in next table.
Table 2 Simplex tableau at point O
c j
-3
-2 0 0 0
ci
P0 P1 P2 P3 P4 P5
P3
0 10 1 1 1 0 0 (1) P4 0 16 2* 1 0 1 0 (2) P5 0 24 1 3 0 0 1 (3) Zj 0 0 0 0 0 0
Zj - cj
3
2 0 0 0
↑
Slack variables (X3, X4, X5) are shown as followings.
X3 = b1 - a11 * X1 - a12 * X2 Eq. 11
X4 = b2 - a21 * X1 - a22 * X2 Eq. 12
X5= b3 - a31 * X1 - a32 * X2 Eq. 13
In example,
X3 = 10 - 1 * X1 - 1 * X2 Eq. 14
X4 = 16 - 2 * X1 - 1 * X2 Eq. 15
X5 = 24 - 1 * X1 - 3 * X2 Eq. 16
By inserting equation 11, 12, 13 into equation.10,
Z = c1 * X1 + c2 * X2 + c3 *（b1-a11 * X1 - a12 * X2）+ c4 *（b2-a21 * X1 - a22 * X2） + c5 *（b3 - a31 * X3 - a32 * X2）
=［c3 * b1 + c4 * b2 + c5 * b3］ - ［（c3 * a11 * c4 * a21 + c5 * a31）-c 1］ * X1 - ［（c3 * a12 + c4 * a22 * c 5 * a32］ - c2］ * X2
= Z 0 - （Z1 - c1）* X1 - （Z2 - c2）* X2 Eq. 17
Where, Z 0 = c3 * b1 + c4 * b2 + c5 * b3， Z1 = c3 * a11 + c4 * a21 + c5 * a31， Z2 = c3 * a12 + c4 * a22 + c5 * a32 and [Z j = Σc i * a i j（i row, j column）].
In example,
Z = 0 - （0 + 3）* X1 - （0 + 2）* X2 Eq. 18
Objective function will be Z0 at the point of X1 = X2 = 0, and we can make the objection function less by increasing X1 or X2 if （Z1-c1）or（Z2-c2） is positive value. In this case we increase X1 because Z j-c j is maximum when j = 1. But there is limitation of X1 increase, because of X3，X4，X5 should be not negative and satisfy equations 11, 12, 13 therefore following equations 19 - 21 should be satisfied and minimum of θi will be adopted.
Example X1 ≦ b1 / a11 = θ1 Eq. 19
θ1 = 10 / 1 = 10 X1 ≦ b2 / a21 = θ2 Eq. 20
θ2 = 16 / 2 = 8 X1 ≦ b3 / a31 = θ3 Eq. 21
θ3 = 24 / 1 = 24 Minimum (θ1,θ2,θ3)
So, θ2=8 is minimum and X1 = 8.
From equation 15, X4 = 0 and move to point D; that is, we exchange P4 vector to new basic vector P1 by using * mark in table 2 pivot.
New simplex tableau (table 3) will be obtained by using pivot alk（l = 2，k = 1） and following procedure.
Example
bl ' = bl / alk
b2 / a21 = 16 / 2 , that is, new b2: b2' = 8
bi' = bi - bl * aik / alk , (l = 2，k = 1, and i = 1, 3)
new b1: b1' = b1 - b2 * a11 / a21 =10 - 16 * 1 / 2 = 2
new b3: b3' = b3 - b2 * a31 / a21 = 24 - 16・1/2 = 16
alj' = alj / alk , (l = 2 ,k = 1 and j = 1, 2, 3, 4, 5), new a2j: a2j' = a2j / 2, that is, (j = 1, 2, 3, 4, 5),
a21' = 2 / 2 = 1, a22' = 1 / 2, a23' = 0 / 2 = 0, a24' = 1 / 2 = 0.5, a25' = 0 / 2 = 0
new aij: aij' = aij - alj * aik / alk , (l = 2，k = 1, and i = 1, 3), new a1j: a1j' = a1j - a2j * 1 / 2, that is, (j = 1, 2, 3, 4, 5)
a11' = 1 - 2 / 2 = 0, a12' = 1 - 1 / 2 = 0.5, a13' = 1 - 0 = 1, a14' = 0 - 1 / 2 = -0.5, a15' = 0 - 0 = 0
new a3j: a3j' = a3j - a2j * 1 / 2, that is, (j = 1, 2, 3, 4, 5)
a31' = 1 - 2 / 2 = 0, a32' = 3 - 1 / 2 = 2.5, a33' = 0 - 0 = 0, a34' = 0 - 1 / 2 = -0.5, a35' = 1 - 0 = 1
Table 3 Simplex tableau at point D
c j
-3
-2
0
0
0
ci
P0
P1
P2
P3
P4
P5
P2
0
2
0
0.5*
1
-0.5
0
(1) '
(1)-(2) / 2
P1
-3
8
1
0.5
0
0.5
0
(2) '
(2) / 2
P5
0
16
0
2.5
0
-0.5
1
(3) '
(3) - (2) / 2
Zj
-24
-3
-1.5
0
-1.5
0
Zj - cj
0
0.5
0
-1.5
0
↑ In same procedure, X3 and X4 = 0 and move to point C; that is, we exchange P3 vector to new basic vector P2 by using * mark in table 2 pivot.
New simplex tableau (table 4) will be obtained by using pivot alk（l = 1，k = 2）.
Table 4 Simplex tableau at point C
c j
-3
-2
0
0
0
ci
P0
P1
P2
P3
P4
P5
P2
-2
4
0
1
2
-1
0
(1)' / 0.5
P1
-3
6
1
0
-1
1
0
(2)' - 1 * (1)'
P5
0
6
0
0
-5
2
1
(3)' - 5 * (1)'
Zj
-26
-3
-2
-1
-1
0
Zj - cj
0
0
-1
-1
0
In table 4, all Z j-c j are not positive and Z = -26 shows minimum value of objective function.
Shadow price of X3 and X4 (Z3 - c3，Z4 - c4) are -1 which means we may decrease objective function 10,000$, that is, profit of this farm increase 10,000$ and become 270,000$, if we increase 1 ha of total area or increase 100man*h/ha of laborer. This shadow price is the vector correspond to optimal solution, which is the value of change of the objective function when right side constant of constraint equation is increased 1 unit. [JIS (Z8121)]
Also, X2 = 4，X1 = 6 of P0 column show the solution of this LP, and X5 = 6 shows fertilizer will be remaining 6 ( * 100kg) at same time.
1-5. Technical terms in Linear Programming
The term linear programming is used to describe a procedure for optimum allocation where use of the resource has a linear effect; that is, if the use of resource A is doubled, the output from A is doubled also. There are programming procedures for other than linear resource-output relationships, but this presentation, only linear relations will be examined.
Definitions useful for linear programming follow.
Structural variables. Items subject to manipulation until an optimum is found: the system variables.
Objective function. The linear equation of structural variables.
Constraints. Equations limiting the values of the structural variables.
Feasible solution. A possible solution, not necessarily optimum.
Optimum solution. The solution to the problem, which satisfies the constraints and the given objective function. A problem may have more than one equally optimum solution.
Slack variable. Nonnegative, arbitrary variables added to constraints, which transform inequalities into equalities.
Linear programming (LP) software are commonly available at most computer centers. If one is able to write the objective function and the constraint equations, the software will automatically insert any needed artificial and slack variables.
See reference 1. LP-Hunt.doc
1-6. Exercise
Problem: Show the coverage of the following farm work series. (SEJICA3-2)
Farm work
Field capacity (ha/h)
Capacity(h/ha)
period
Available working hour
1
Puddling
C1 = 2
T1 = 0.5
8/1-8/7
S1 = 42, S11 = 12
2
Transplanting
C2 = 0.5
T2 = 2.0
8/6-8/10
S2 = 30, S = 60
<------- ------------------------------
--------S=60-------------
-------------------------------->
S
<-----------X1-----------------------
----------X2------------>
S1
<---------X3-------------
------X4---------------------->
S2
<------------------------>
S11
30 hour 12 hour 18 hour Total 60 hour <----------s1---------><---------------------------------s2------------------------------------>
Answer A
Total time required to both farm work is, T = T1 + T2 = 0.5 +2.0 =2.5 (h/ha)
If total period (S) is available to both farm work, coverage is, H' = S / T = 60 /2.5 =24 (ha)
And time required to puddling is, s1 = T1 * S / T = 0.5 * 24 =12 (h)
Time required to transplanting is, s2 = T2 * S / T = 2.0 * 24 =48 (h)
S1 = 42 > s1, that is, period for puddling is enough, but S2 = 30 < s2 means period for transplanting is not enough.
Therefore, coverage of both farm work is obtained by following equation.
H = min [ H', H1, H2 ] = min [ 24, 84, 15 ] = 15 (ha) Eq. 22
Where, H1 = S1 / T1 = 42 / 0.5 = 84
H2 = S2 / T2 = 30 / 2.0 = 15
Answer B by LP