CHAPTER-4 INTEGER PROGRAMMING aad Introduction : A special cl ass of linear programming plem where all or some of ¢1 i = re : he decision variables are pi strained to assume non-negative integer values is called an 0 ser Programming Problem (IPP). This type of problem ts of Les! | nicular importance in business and industry where, quite Pp are unrealistic because the units ‘ten. the fractional solutions wa not divisible. For example it is often necessary to assign ple machines, vehicles etc. to activities in integer quantities. he integer solution to a problem can, however, be obtained by rounding off the optimum values of the variables to the nearest integer values. But it is generally inaccurate to obtain an integer solution by rounding off in this manner, for there is no guarantee that the deviation from the, exact, integer solution will not be too large to retain the feasibility, There are three types of integer programming problem. (i) If all variables are required to take integer values then it is called the all (or pure) integer programming problem (AIPP). (ii) If some of the variables are restricted to integer values, whereas others can assume any real value, the problem is mixed- integer programming problem (MIPP). (iii) If all variables are allowed to take values either O or I (which is integer also) then the problem is called 0 - 1.(zero- one) programming problem or standard discrete programming problem. 4.2. Gomory’s all integer Programming Problem method : An optimum solution to an integer programming problem is first obtained by usual simplex method ignoring the restriction of integer values. In the optimum solution if all the variables have integer values, the current solution will be desired optimum integer solution otherwise we add a new constraint to the problem such that the new set of feasible solutions includes all the original feasible integer solutions but does not include the optimum non-integer solution initially found. This new constraint is called a fractional cut or Gomorian constraint. We then solve the revised problem using dual simplex method and see if we can get. an integer solution. If not, we add another326 Operation Research fractional cut and repeat the process until an integer Solution jg found. Since we never eliminate any feasible integer Solution from consideration when we add fractional cuts, the inteper solution ultimately found must be optimum. Determination of Fractional cut : Let us consider an L, P, p Maximize, z = cx Subject to Ax = b, x20 for which an optimum non-integer basic feasible solution hag been attained by simplex method. Let this solution be displayeq in the following final simplex table : Gp es | basic y yo Y3 Ya. variables Xe yu Yi = Yia Yia c yo Cg y3 X3 4S ~. The optimum basic feasible solution is given by bj} x Xp= (22) -( C -(%e] > ") (327) and Max. z = yog X3 by Yoo X3 Y20 Since xp is a non-integer feasible solution we assume yjq is fractional. i. e. the value of x2 is fractional. Now the constraint equation from final table Yur X1 + Yi2 X2 + Via Xs + Via X4 = Yio Since x, and x; are basic variables y)2 = 1 and y;3=0 Yin X1 +X + Via X4=Yi0-~ (1) Since the solution is feasible, y;o 2 0, the fractional part of yo must be non-negative, we split over each of yy (j = 1, 2, 3, 4) in (1) into an integer part I, and a non-negative fractional part fy for j= 0. 2, 2, 3, 4. After this decomposition, (1) can be written as (1) = (iy + fin) x1 +X + (ig + fia) X4 = hho + fo => Nyy xy + Xe + Sq Xq— Lio = fo- fii X1 — fig X4 + (2) By comparing (1) and (2) we conclude that if we add an additional constraint in such a way that the R. H. S of (2) is an integer, then we shall be forcing the non-integer y,, towards an integer. The fractional cut or Gomorian constraint is flo- fir Xi — fia Xq 2 O-- (3) Const. b or Solution XsInteger Programming 327 i possible let ha = fy x1 ~ fia xq <0 then let Cio - fii X1 fig xy =h where h> 0 is an integer. then fo= fin Xi + haxy+h> 1 This is contradicts the fact that 0 < fy <1 forj=0, 1,2,3.4 Thus the fractional cut is _— fio~ fir X1 ~ fia X20 = fy x1 + fig xy 2 fig o 2% x2ho by are non-basic variables] jel = fy x4 S-fip>- f, IN) ee fi = aap Ja 1%) ia y+ GE =~ fio (4) Qo; *. Where Gj, is a slack variable in the above first Gomory constraint or fractional cut. This additional constraint is to be included in the final table of the original problem in order to move farther towards obtaining, an optimum all-integer solution. After the addition of this constraint, the last optimum simplex table looks like (oO SO dC 2 X2 ya Yu Miz Vis) Ya 0 x3 ys | Yar Yoo Yas You O Ss} co | -fi 0 O -f4 1 BiG Yo. Yor _Yos Yos Since -f\o is negative i. e. s; = - fo, the optimum solution is infeasible and all z; - ¢ 2 0 and thus the dual simplex method is to be applied for obtaining an optimum feasible solution. If the solution is not all integer, we introduce 2nd fractional cut in same way. The process is continue until all-integer solution has not been obtaining. Yio Y20 -fio Yo Yoo 4.3. All-Integer cutting plane Algorithm : The iterative procedure for the solution of an all-integer programming problem ts as follows : Step-1. Convert minimization problem in to maximiza-tion problem (if need) form. Step-2. Solve the problem by simplex method ignoring the condition of all integer soluticn.328 Operation Research Step-3. (i) If all xy 20 for i= 1,2, +.m and are integer then the current solution is an optimum all-Integer solution. (ii) [fall xy, 2 0 (= 1, 2, +, m) but some of them are not integers goto the next step-4. Step-4. Choose the largest fraction of xpj's. Let it be found from Xp (= fko Say) Step-5. Express each of the negative fraction if any, in the kth row of the optimum simplex table as the sum of a negative integer and a non-negative fraction. Step-6. Find the fractional cut or Gomorian constraint in the form n - >. “fy 4) S— fo [xj are non-basic] j=l n =>- >. fig Xj + $1 =— feo j=l where s, is the Gomorian slack variable. Step-7. Add the additional constraint found in step-6 at the bottom of the last optimum simplex table found in step-2. Find the optimum solution using dual simplex method. Step-8. Go to step-3 and repeat the procedure until all Xt 2 0, (i = 1, 2, +, m) and are integers. Example-1. Find the optimum integer solution to the following all IPP. Maximize, z = xX; + 2x9 Subject to x; + x2 $7 2x, <11 2X_ <7 X), Xp 2 0 and are integers. Solution : Introducing slack variables x3 2 0, x4 > 0 and Xs 2 O and are integers one to each constraint, we have Maximize, z = x, + 2x9 + Oxy + Ox, + Oxs, Sulject to x) + X2 + Xg + Oxy + Oxs = 7 2x, + OX2 + OXg +X, + Oxs = 11 9x, + 2X + Oxy + Oxy + X5 = 7 x, = O and are integers.Integer Programming Since all 2 - c¢ 2 0, the optimality conditions are satisfied. The optimum solution is ] i X= 39. %2= 35 and Max. z= 103. x 3 Here optimum solution xp = = Nile Xq Xe cS 3 dlr which is not integer valued. we consider only the fractional parts f; € Xp, (i= 1, 2, 3) th, fab = 1. 2° 3/ Xa 1] i Maximum ({f;, fg) = Maximum {3 ' 4 =3 both f, and f, are ‘qual. So, we select orbitrarily ony one of them. Let us choose fy Le. fap =5330 Operation Research The fractional cut or Gomorian constraint - > fey X, +8; =-fy9 [for non-hasic variables xg and xs] j=35 1 1 1 1 7B X5 +S) = 7H = OX + Oxy + Oxy + OX4 ~ aX tS1=-9 Inserting this additional constraint in the optimum simplex table and use dual simplex method to find next optimum solution. 57G This shows that the optimum solution has been attained in integers. Hence the integer optimum solution is x, = 4. x2 = 3 and max. z= 10. Example-2. Solve the following L. P. P. Maximize, z = x; + Xz Subject to 3x; + 2x9 <5 X_ <2 X). X2 2 O and are integers Solution : Introducing slack variables x3 = 0, x4 2 0 and are Integers in 1st and 2nd constraint respectively, Max. z = x; + Xq + OXg + OXy Subject to 3x; + 2x + Xg + Ox, = 5 Ox, + X2 + Oxg +X, =2 xj, 20,j= 1, 2, 3, 4 and all are integersInteger Programming 331 1 Since all 2; - ¢ 2 0 and x, = 3 + X2 = 2 are not integers valued. Thus the optimum solution is not integer solution. 1 Here largest fraction is fg = 3 which is unique. «. Fractional cutis - >. fy x +8, =-fho =34 3-4m-R 4812-3 [since 0 « fiy< 1; 2 =-1 +4] Introducing this constrain in the optimum table. by dual simplex method find optimum solution. Xq Sy b 1/3 -2/3 Oo 1 0 0 x, 0 Since all xp = [:)-(3 are integer valued. Thus the Xg °pimum integer solution is x; = 0, x2 = 2 and max. z = 2.332 Operation Research Example-3. Solve the following L. P. P. Manimize, 2 = X; - Xp Subject lo x; + 2x2 <4 6X, + 2x). $9 Xj, Xy 2 0 and are integers Solution : Introducing slack variables x3 2 0, x4 2 0 and are integers one to cach constraint we have Max, x1 = Xq + OXy + OX4 S. tx) + 2x2 +5 + OXY =4 Gx) + 2X + Oxg +X =9 x, 2 0, and are integer: j = 1, 2, 3, 4 Since all z, - c, > 0. the optimality conditions are satisfied. But the solution is not integral valued. x 2 1) Here optimum solution xp = ( | = P Xp . 2 x 2/3 f I Fractional part of the solution is {f;, f)} = 3 . aN 1 ~. Maximum {fy, {|} = Max. {i ' 3 = rs 2 which occurs for Xpa = 1»: fao = 3 .. Fractional cut or Gomorian constraint is - > fy X) + $1 = — foo jo24 Nn 2 1 1 73% GX +81 = 3 +9 OX; 7B ¥a+ OX3- § xy +8) =-3Integer Programming 333 Introducing this constraint i n the opti dual simplex method find optima puimum table and using im solution, X3 4 Since Xp = [:) -(3) integer valued thus the optimum integer Xq solution is x; = 0, x = 0 and max. z= 0. Example-4. Solve the following L. P. P. Maximize, z = x, + 4x» Subject to 2x) + 4x9 <7 5x) +X_.S15 X), X2 2 0 and integers Solution : Introducing slack variables x3 > 0, x, > 0 and integers in 1st and 2nd constraint, we have Max. z= X, + 4x» + Ox3 + Oxy S. t. 2x) + 4x9 + X3 + Ox, =7 5X) + 3xX_ + Ox3 + X4 = 15 X1, Xg. Xj, Xq4 2 O and integers.334 Operation Research fractional part of x3. (fy. + Max. {f. 1) = Max. is : aI “4 3 both f and fy are equal. Choose arbitrarily let f = foo = a Fractional cui or Gomorian constraint is = >. fa) X) +S, = - bo J=h3 1 1 3 1 1 3 ST ONT gat $1 => 4 7g Ni + ON. — 4 Xp + ON +8, =—- 7 Inserting this constraint in the bottom of the optimum table and use dual simplex method to obtain next optimum solution.Integer Programming olf Let {f2. fab € Xu 1 42 which is not all integers. wo Vato 1 2° a/=9- let =5 = fp .. Second fractional cut or Gomorian constraint is + Max. (fo, fyb = qe 1 +, OX, + OX2 ~ 2X3 + ON + 0x; + =— _. 1 é 2 {95 82 hho m9 05, #5) =- 4 [- 5 = 335 Inserting this constraint in the last optimum table and use dual simplex method. 1 Since all xy = Xa/ a ; are integers , 1 *. The optimum integer solution is x, = 1, xX) = 1 and Max. z= 5.336 Operation Research Example-5. Solve the following L. P. P. Maximize, z = 11x, + 4x2 Subject to - x; + 2x,<4 5x; + 2x9 < 16 2x, -X)S4 X1. X2 2 0 and integers. Solution : Introducing slack variables x3 2 0. x4 2 0, x5 2 O and integers one to each constraint, we have Max. z = 11x; + 4x2 + Oxy + Ox, + Ox5 S. t. =X) + 2X9 + Xg + Oxy + Ox5 = 4 5x) + 2xX_ + Oxy + X3 + Oxs = 16 . 2X) — Xq + Oxg + Oxy + X5=4 X1, Xo. Xg, X4, X5 2 O and integers x3 12 Here optimum solution Xp = | Xp | =| 4/3 x1 1 which is not all integers. Here only one fraction 3 € XmInteger Programming 337 1 1 1 ©. Max. {5} =3>fo=3 .. First fractional cut or Gomorian constraint is 3 2 4 1 = > fy % + 81 =~ fo9 > -F xy - 2x5 +58, =-4 4s 4 20> 9 4-H XS +S 2 4 £- OR + Ore + Oxy ~ § 4-5 5 +8 =-F Introducing this constrain in the last optimum table and use dual simplex method to get optimum solution. Xs 10 Here x3 = 2 ~ Ae 2 which is not integers. 3/4 Fractional pert of the solution is Let ff =| Sh ea ms 11 3\].3 2. Max. ff. fg, fj =Max {}.3.3} 23 which occurs for fy i. e. i= 4 = fe=3 Oneratinn Resenrch-2?338 Operation Research -. second fractional c¥t is -1,,-3 3 ee git as Inserting this constraint in last optimum table and use dual simplex method. 0 Xp 1 Here Xp = | X; | = aoe has fractional parts X, xe} (3/2 11 i (hi, fs, w={b-4-3} . Max. thy. fy, fs) = Max. {b + chose fs = 3 = fo .. Fractional. cut is 1 5 bey Na omni din ih 1 = 0X) + OX2 + Oxy + OX + OXs — 5 8) + OS2 + S3=- 5Integer Programming 339 inserting this constraint in the last optim ju ai simplex method to get optimum sélittion, m table and use Since optimality conditions are satisfied and solution is integral values. Thus the optimum integer solution is X) = 18, xX) = 3 and max. z = 210. Example-6. Solve the following L. P. P. Maximize, z = 3x, + Xp + 3x3 Subject to —x, + 2x2 + x3 <4 4X - 3x3 52 X1 — 3x2 + 2x3<53 X, Xp, Xz 2 O and integers. Solution : Introducing slack variables x, < 0, x5 2 0, x, 2 0 and integers one to each constraint, we have Max. z = 3x; + X_ + 3x3 + Oxq + Oxs + Ox, S. t. Ky + 2x + Xg + Xq + OXs + OXe = 4 Ox; + 4X9 - 3X3 + OX4 + X5 + OX = 2 X1 ~ 3Xq + 2X3 + OX + Oxs + X6=3 x, 2 O and integers, j = 1, 2, --.6340 Operation Research 4/9 1/9 4/9 1/3 /3 1/3 1/9 7/9 10/9 16 _ 10 All z - ¢, 2 0, the optimum solution is x, = B+ %2=3,%3= 3 max. Z = 29, which is not integers. X3 10/3) Here xp=|X,/=| 3 x,} (16/3 Let f, € Xpj, the fractional part of xp, 11 1 -. Max. {f;, fg} = Max. i , 4| =3 which occurs for i = 1, (choose arbitrarily) 1 “ho =3 -. Fractional cut or Gomorian constraint is ~ 2 fy xy +81 =- fio j=45.6 4 1 4 1 "9X1 9%" OXStS/=—G 4 1 4 *+ OX] + Ox + OX3~ 9 X4- G X59 X6 +S) =-4Integer Programming 341 Introducing this constraint in the eptimum table. Dual simplex table : 4/9 1/9 4/9 1/3 1/8 1/3 1/9 7/9 1/9 Solution obtained is optimum but not integer let fractional part fle xy S.8 S oy fas fal -{2 “a 3 Select for i = 2 i.e. f= 2 ~ 2 yx + 82=- 1 3 3 =>- | X5 + Ox6- 4 Sit S=—] j=£8.7 4 qr eee 4 1 Ox, + Ox, + Ons + Oy = N5 + OG 35) +5y=-8 Inserting this additional constraint in the last optimum table, we have342 Operation Research -1/4 0-3/4" 6 This gives all integer optimum solution x, = 5, X2 = 2, x3 = 2 and max. z = 23. Example-7. Solve the following L. P. P. Maximize, z = 4x, + 5x2 Subject to -3x, + 3x, <6 2x, + 4x9 < 12 Xj, Xq 2 0 and integers. Solution : Introducing. slack variables x3 2 0, x4 > 0 and integer one to each constraint, we have Max. z =— 4x) + 5x» + Oxg + Oxy S. t. -3xX, + 3x2 + X3 + Oxy =6 2x, + 4x + OX3 + X4 = 12 X1, Xo, X3, X42 O and integers. Simplex table, ignoring the condition of integer valued solution.Integer Programming 343 Allzy-% 2 0. Thus the solution is optimum but not integer X2)_(8/3 / 220" ( x2) = (5/3) Let the fractional part f, € xp, = {f,, fo} , both are equal 2 Max. {f}, fo} = Max. B : | =2 Choose arbitrarily f; = 2 2 «fio =3 :. Fractional cut or Gomorian constraint is 2 7 Zs fy x +5) =- fio =>- 3% xy +5) =- 3 lol 2 1 OX, + OX - 9 Xs ~ G Xa + 81 =— 3 Inserting this constraint in the optimum simplex table and use dual weep he mets to ee next optimum este solution. i = -2/9 1/6 -1/9__-1/6* 13/9 1/6T “. The all integers optimum solution is x; = 0, x2 = 2 and max. z = 10. Example-8. Solve the following L. P. P. Maximize, z = 9x, + 10x Subject to x; + x3=3 2x, + 5X_ +X4=15 X1, Xp, Xg, Xq 2 O and integers.344 Operation Research Solution : The problem can be written us Max. z = 9x; + 10x2 + Ox3 + Oxy S. t. X1 + Oxy + X3 + Ox, = 3 2x) + SX + Oxg + Xy = 15 X1, Xo, Xg, X4 are non-negative integers. Now we solve the problem by simplex method ignoring integer condition. Const. | Min. Ratio 0 : x The solution xp = () =(0%3): which is optimum but not integer. 4.4 Fractional part of x. = 1+ == 5.5 which corresponds 2nd row i. e. Max. {fp} = 3 4 bo = 3 «. Ffactional cutis - >. fy x; +s) =~ fo 4 3,1 4 [2 3 ~ 5X87 Bt = 5 [vr Ber 1+s Introducing this constraint in the optimum simplex table and use dual simplex method to get an optimum solution.Integer Programming 345 Dual simplex table. " + OA WIN Win W N + lo wie wits | Xi 5/3 The solution xp = | x2 |=| 7/3] is optimum but not integers. x3) 4/3 Fractional parts 2 f € Xpi= ff, a-2-4-4 21 + Max thy ff) = Max 2-45. 3} 22 iC} =f,= 3° hich corresponds Ist row. 2 fo=3 ~. Fractional cut is = > fi 4 + S2 =— fio ja45 2,2 3 [1 i 2angda1+2] Tg gS tS="3 [.--h=-143 ana$=1+3] 3 2 2 = 0x, + Ox, + 0x3 — 3 %4— 3 S1 + $2=7-3 Inserting this constraint in the last optimum table.346 Operation Research which is integers -, Optimum integer solution is x, = 2, x2 = 2, x3 = 1, Xy = land max. z = 38. Application of all integer programming : Example-9. The owner of a ready-made garments store makes two types of shirts A and B. He makes a profit of taka 1.00 and taka 4.00 per shirts of A and B respectively. He has two tailors T, and T, at his disposal to stitch these shirts. Tailor T; and T, can devote at the most 7 hours and 15 hours per day respectively. Both these shirts are to be stitched by both the tailors. Tailor T, and T, spend two hours and five haurs respectively in stitching a A shirt and four hours and three hours respectively in stitching a B shirt. How many shirts of both the types should be stitched in order to maximize daily profits? (S95 TSH TS A 6 BER eats “HT COR Sea A ST CD CT ATS FA 1.00 BF © B SA So IE ATS Ba 4.00 TH | OIA WAKA T, 6 T, Baer wf oTeR | ere T, HA 7 VT 6 T, HA 15 WH ore ata | Bou TRE BR ora ID OTR ea | A tata GE HIT Cea aS T, HfRa mH AIA 2 TO 6 T, Hsia FT AA 5 WB B esta aeld IS ore saw T, aie A A! 4 WS 6 T, Aiea TN AIC 3 WOT | afeihA caTA stones ME sO wal Sara ars Fao AN Ae BI ify sa |)Integer Programming 347 Solution : Data of the problem can be write in the tabular farm | nm | Profit per shirt (Formulation) : Let x, units of A shirt and x2 units of | g shirt to be made to maximize the profit, where x; = O and x22 0 and integers. Total profit = X, + 4X, Objective function of the problem is z = x; + 4x» which will be maximized. Time restriction of T, tailor is 2x, + 4x, <7 Time restriction of Tp tailor is 5x, + 3x, < 15 .. Linear programming problem of the given problem is Maximize, z = x, + 4x9 Subject to 2x; + 4x, <7 5x, + 3x2 $15 X, X2 2 O and integers. Now we solve the problem by simplex method ignoring the condition of integers. Introducing slack variables xg 2 0. x, = 0 and integers one to each constraint, we have Max. Z =X) + 4X2 + OX3 + Oxy S. t. 2x) + 4x9 +X + 0K =7 5x, + 3X_ + Oxg+x4=15 X), Xg. X3, X4 are non-negative integers Obtained solution [Link] but not integers fraction of shirt can never be made.348 Operation Research Here xX = ( 2) =(30//') Let the fraction part f, € xpi = (30/4) =(64374) - (fh. fo -{. 3| both are equal 2 Max. tf, fo) = Max. {2 : 3 as choos arbitrarily f, = 3 which corresponds Ist row 3 ~- fo =4 -. Fractional cut or first Gomorian constraint is 1 1 3 - > fy x) +81 =-ho=-9%1- 4 %3t+S1=-| j=13 1 1 3 737g Xi + OX2 4X3 + OX4 +S) =- | Inserting this constraint in the optimum table and use dual simplex method to get optimum solution.Integer Programming 349 1 racenan( 3173 tts) -4) sot ar cau 2. Max Uf, fg) = Max. {s | =4 choose arbitrarily f, = 3 = foo =} .. fractional cut or 2nd Gomorian constraint {s = >, fy x; + Sp =~ f j=3.5 mi ° NI~ 1 1 2— 9 Xa + 82575 =9 0K, + Ong} 5 + OX, + 05, +59 =— Inserting this constraint in the last optimum table. X2 1 Here solution xg = be } which is optimum arid integers. 1 X3 1 i Thus the optimum integer solution is X, = 1, x,.= 1 and max.z=5.0 Operation Research Example-10. A manufacturer of baby-dolls makes two types | of dolls; Doll X and Doll Y. Processing of these two dolls is done | on two department A and B, Doll X requires two hours an | deportment A and six hours on department B. Doll Y requires five | hours on department A and B also, there are sixteen hours of | labor time per day available on department A and thirty hours on | department B, profit gained on both the dolls is same i. e. 1.00 | taka per doll. What should be the daily production of each of the two dolls to maximize the profit. (ef Prema aya teats AAA Ao | B af Rent xy Ba der Aga WOR Bea X ear AEA teh A Frere FAA ACA 2 WS B ASI TM AM G TB Y Aaa AWA ACS A @ B Bey Fron AH aI 5 HBL A front afoiR 16 Te @ B Frere afefin 30 THOT Se A Boy saa ale awa cars ATS I 1.00 Bra aftr CHR ASH yt Sols Coa sara ars wracHTH CaN Aa Fifa a 1) | Solution : Tabular form of the given problem is Profit per doll (Formulation) : Lei x, units of X doll and x, units of Y doll to | be made to maximize the profit. Where x, 2 0, x2 2 O and are integers. Total profit = x, + x2. The objective function of the given ; problem is z = x, + X2, which will be maximized. Restriction of labour hours on Dept. A is 2x, + 5x, < 16 Restriction of labour hours on Dept. B is 6x, + 5x2 < 30 ~. The linear programming problem of the given problem is Maximize, z = x; + Xp Subject to 2x; + 5x9< 16 | 6x, + 5x2 < 30 i X1, X92 O and are integers Now we solve the problem ignoring the integer restriction by simplex method. Introducing slack variables xz 2 0, x4 = 0 and integers one to each constraint, we have Max. z = X, + X2 + Oxg + Oxy Subject to 2x, + 5x2 + x3 + Ox, = 16 6x) + Sx_ + Ox3 + X4=30 X1, Xa, Xg, X4 2 O and integers.Intege: i ‘er Programming - lee 1 3/10 -1/10 | 9/5 0 -1/4 1/4 7/2 0 0 1/20 3/20 = [* 9 The solution xg = (>) =(3/3). which is optimum but not integers. Lntsexa=(5%4/5) +. Max. {fy, {a} = Max. {s : | =4 4 of =5 which corresponds Ist row 4 “ho=5 -. Fractional cut or Gomorian constraint is - D> fyxytsi=-f joa 95 10 3, See ee* Ilposeeeanes =~ joxs ost =75 [10> * 10. 3 9 4 = Ox, + OX. — 7g X3~ 19 *4- 81 = 75 Inserting this constraint in the optimum table and use dual simplex method to get optimum solution. Pr 1000] Const b 3/10 -1/10 -1/4 1/4 -3/10__-9/10*Operation Research - -1/6 -1/6r = Xo 17/9 The solution xp = | x, | =|59/18| which is optimum but not / x4 8/9 integers ‘ 9 7 Wem a sage ‘ 1+8/9 8 5 8|_8 Let fe xp, =|34+5/8] = Max. ff. fe f -max.{8. 5.8] 28 Hes 1» fa. fo) 9° 18'9]"9 8 -. Let & = 9 Which corresponds 3rd row 8 “fo = 9 ~. Fractional cut is JE Inserting this constraint in the last optimum table. 1 8 8 -10 8 4 5 st 2 =— foo —3% gS t+S2=—9 [:--y2--2+8]Integer Programming 353 | 25/6 0 8/8 The solution x; = which is optimum but not integer. 25 31 Lex = @ Xg= 1, maxz=— 1 waiiexa= 4+1/6 24+2/3 +. Max (ff) = Max, {A 2 which corresponds 4th row 2 «. fag = 3 Fractional cut is 5 2 gta beo 7-381 +082 +S3=-3 Inserting this constraint in the last optimum table. 2 2 xy 3 The solution xp = | x4 | = 2 . which is optimum and integers. x3 3; 1 Thus the optimum integer solution is x, = 3, x2 = 2 and Max z= 5, -354 Operation Research Example-11. Maximize, 7 = 2x, + 20X_ - 10x Subject to 2x; + 20x» + 4X3 $ 15 Ox) + 20x2 + 4X3 = 20 X). Xp, Xy.2 0 and integers Solve the problem as a linear program, the show that it is impossible to obtain feasible integer solution by using simple rounding. Solve the problem using all integer Program algorithm. Solution : Now we solve the problem by simplex method ignoring the integral constraint. Introducing slack variable x, 2 0 and an artificial variable a, in 1st and 2nd constraint respectively, we have. Max. z = 2x, + 20X_ — 10x3 + Ox4 - May Subject to 2x; + 20x» + 4x3 + 4 + Oa, = 15 6X, + 2OX_ + 4Xy + OX4 + a; = 20 -4M+10 1/10 1/5 120 «(OO 3/4 4* 0 =], 1 ~4M-21 14 M+l_0 0 1/5 3/40 - 1 Oo. -1/4 - All z, - c, 2 0, the optimum solution x, = 3 XQ= 3 + X3 =O and max. z = 15. Simple rounding to get integer solution : Let x) = 1, X2 =0,x3=0 This does not satisfy the 2nd constraint Let x) = 2, x2 = 0, x3=0 This does not satisfy the 2nd constraint Let x; = 2, x2 = 1,x3=0 This does not satisfy both the constraints. Hence by simple rounding we can not obtain a integral solution of the given problem.Integer Programming 355 Now we apply G somory's all integer problem method to get integer solution, We have from the optimum simplex table two variables are not integer. 5 1 5 N= gl tqandx=9=0+9 8 ‘ = {*2 5/8 ie-so=(%7)=(,5/8,) The largest fractional part of the solution is 3 which corresponds Ist row. So we choose first row as source row for secondary constraint. From the ist row of spa simplex table 5 3 5 Ox; + XQ + s8r40% 8 Ext X= g> Xe 1 pS 3 = 5% a X28 =~ 5%" 1905-8 1 3 5 “5% 1OM*SI=g Introducing this constraint in the above optimum table. 3/40 0 -1/4 -1/5__-3/40" PEL ec ee 40/8 Here the solution xy = not integers.356 Operation Research 1 Since both the fractional part are 3 (equal) We take 3rd row as a source row for secondary constraint. From 8rd row of the last optimum table 8 40 25 2 2 1 gst gS =(2 + 3 )xote(-14 + 3) =84+5 2 4 = 3x94 81 =3 +8- 2% xy + 4s, os zy eee os} 2 2y 2, <] mage guess ge ges 2-2 4 “7B X7 BSF SH=—3 Introducing this constraint in the last optimum table. X2 3 Here solution xp = 2 = s , which is optimum but not all 4 x3) \1/2 integers. 1 only fractional part = 5 which corresponds 4th row. So we take 4th row as a source row " 1 1_ it -. Fractional cut is xg + $) +(2 + 3) 79237 y-Xe- 81 ! 2 1 1 85-9 17g S2tS3=7 oe 1 1 3922597Integer Py rogramming Oo 2 Xo 0 xy x Here the solution xp =|x,/=|3|, which is optimum and x3 2 Se 1 integers. Thus the optimum integers solution is X1 = 2, X_ = 0, x3 = 2 and Max. 2=- 16. Example-12. Solve the following L. P. P. Maximize, z = 3x, + 2X» + 5x3 Subject to 5x; + 3x2 + 7x3 < 28 4X, + 5x2 + 5x3 $30 Xj, Xg, X3 2 O and are integers. Solution : First we solve the L. P. P. by simplex method ignoring integer constraint. Introducing slack variables x, > 0. x5 > 0 and integers in Ist and 2nd constraint respectively we have Max. 2 = 3x, + 2xXy + 5x3 + Oxy + Oxs, S. (. 5X) + 3xy + 7X3 + Xq + Oxs = 28 4x, + 5x2 + 5x3 + OXy + X5 = 30 X|. Xq. X3, X4q. X5 20358 Operation Research 5 5/7 3/7 1 0 3/7 20/7_—0—-5/7_ I 4/7 1/7 0 5/7 0 Since all 4 ~ ¢ 2 0, the optimality conditions are saltsfled, The optimum solution ts x; = 0. x, = 0. xy = 4 and max, z = 20, which ts all Integers so farther compilation [s nol required, «. Thus the all integer optimum solution ts X) =X, =0, x, = 4 and max, z = 20. 4.4. Gomory’s Mixed-Integer Method : In a linear programming problem, if some of the vartables are restricted to integer values, whereas others can be any real value, the problem is known as mixed integer programming problem : Mixed Integer cutting plane Algorithm : The iterative procedure for the solution of mixed-integer . Programming problem is as fallows : Step-1. Solve the given L. P. P. by using usual simplex method as a maximization problem. Stop-2. (i) If all x, 2 0, (1 = 1, 2, -, m) and are integers or integer restricted variables are integers, then the current solution is an optimum solution. (ii) If all xy, 20, (i = 1, 2, +, m) but the integer restricted variables are nol integers, go to next step. Step-3. Choose the largest fraction among those xj's which are restricted to Integers. Let it be found at xj, (= {xo Say). Step-4. Find the fractional cut (Gomorian constraint) in the form JER, where 0 < {ko < 1. Rt =: fy > O), Ro = Gj: Syj < O) and R={(R,, R}= (1, 2. +, n- m) is the set of indices corresponding to non-basic variables. f - 2 63%-( fa"? x) D>. fy S- ho je RInteger Programming —fxo -2 65% ~( als) 2 fs) +81=~fo je Re je R 359 where S; is the Gomorian slack variable. step-5. Add the additional constraint found in step-4 : at the bottom of the optimum simplex table. Find the new optimum solution using dual simplex method. Step-6. Go to step-2 and repeat the procedure until all xp 20 (i= 1, 2, ++, m) and all integer restricted variables are integers. Example-13. Solve the following mixed integer programming problem Maximize, z = 4x, + 6x2 + 2x3 Subject to 4x; - 4x2 <5 -X, + 6x,<5 -X) +X +XgS5 X), Xg, Xg3 2 O and Xj, Xg are integers Solution : Now we solve the problem by simplex method ignoring the integer restriction. 1 : Introducing slack variables x4 > 0, x5 2 O X62 O one to each constraint, we have Max. z = 4x, + 6Xq + 2X3 + OXy + Oxs + OX s. t. 4X) — 4Xp + OXg + Xq + OXs + OX6 = 5 -x; + 6X2 + Oxy + OX4 + X5 + Oxg = 5 -X] + X_ + Xg + Oxy + OX5 + XG =5 X1, Xa, Xgr Xqe X5, Xp 2 O and xj, xy are integers. 25/3 | 5/2* 5/6 | - z=5Operation Research 0 3/10 1/5 5/2 a 0 1/20 1/5 5/4 = 0 25/4 | 25/4 11/5 3/10 1/5 5/2 1/20 1/5 5/4 Oo Since all z, — ¢; > 0, the optimality conditions are satisfied. xX 5/2 The solution xp = Xo 5/4 |, which is optimum but Xg 25/4 5 3 1 =9.+X3= q are not integers. 1 xX 2245 .%=644 Largest fractional part = 4 ,which corresponds 1st row. So we take first row as a source row for secondary constraint. 2. fps (ra i, 2 Austere =~ ho Je Rage 4g? 3 1 1 3 1 ] 37719 475 StS =-g SOX + OX + OKs 19 M4 5S FST =H Introducing this constraint in the last optimum table. 3/10 V/s 1/20 1/4 0 ~-3/10* -1/5Integer Programming 361 2) 35 Here optimum solution x, = aes . where x3 ="% which is 43 not integer. 3s ; 5 “. Fraction part = @, which correspond 3rd row. So we select 5 83rd row as a Source row for secondary constraint here fo = 6° Fractional cut is Eon je Ry 2, fy +52=- foo je R Se 5 5/6_\/(-1 5 5 5 5 =~ 6 S1-\ 576-1) 6 )%+S2=- GG 81 G+ = G 5 S) 5 => 0x, + Oxy + Ox3 + OX4-§ XS § S1 + 2=7-G Introducing this constraint in the last optimal table. The obtained optimum solution is integers 2. X) = 2, x2 = 1, X3 = 6 and max. z = 26.362 Operation Research Example-14. Solve the following mixed integer programining problem using Gomory’s cutting plane method. Maximize, z = x, +X Subject to 3x, + 2x) <5 X_ <2 X1, Xg 2 0 and x, an integer First we solve the problem by usual simplex method ignoring integer constraint. Introducing slack variables x, > 0, x, >0 in Ist and 2nd constraint, we have Solution : Max. z = x, + Xq + Ox3 + Oxy S. L 3x) + 2x) + x3 + Oxy =5 . OX) + Xy + Oxy +X, =2 X1. Xa. Xg. X42 0 Since all z - c 2 0. the ppumaltty condi tions are ened The optimum solution is x)= Zi o X2 = 2, Max. 2= 8. Butx, = 4 is not an integer-and is only fractional part of the optimum solution, so we take first row for source row 1 fo “3 \ Fractional cut or Gomorian constraint is F . fio v - WX Fg< 1) D. fy%+s1=~fy je Ry JER V us. _2 iw og i SUBS T] 3) 44812" 3 9-3 35- 3x 45) =-4Integer Programming 363 introducing this constraint in the optimum table and use dual | ginplex method to get next optimum solution. x1 1 Obtained solution xp = | x2 -(}} which is optimum and x, is Xq 1 }) integer. -. The mixed integer optimum solutions is X, = 1, x2 =1 and max. z=2 \ Since z3 - C3 = O, there is an alternative solution. If we introduce xs in the basis then we get The optimum integer solution is x, = 0, x, = 2 and : max. z= 2. Example-15. Solve the following mixed integer programming problem Maximize, z = 6x, + 9X Subject to -x, + 3x2 <6 7x, + X2_ 235 X 1, X2 2 O and x, is an integer.364 Operation Research Solution : First we solve the problem by simplex methog ignoring the integer constraint. Introducing slack variable x3 2 0. x4 2 [Link] to each constraint, we have + OX» + OX; + OX, Xy + 3xz + Xy + Oxy =6 TX, + Xo + OXy + Xy = 35 = Xg. Xg. X4 2 O and x, integer. Since all z - c, = 0. the eptinaltty conditions are satisfied, 7 The optimum solution is x, = 2, x= 9 and max. z = 63. 9 Here x, = 3 - is not an integer and fractional part of x, is (u=$ te =4+ 3)" 3. which corresponds 2nd row. So we take 2nd 1 Tow as a source row for secondary‘constraint. Here fog = 3- - Fractional cut or Gomorian constraint is oe fo, %- lin), Ze ae ~ foo Ry 3 1/2 _\ (-1 mel =" 92%"\ 172-1): Bp )%o+ 51 = a 3 A eof ells x coal > 99% a9 %FSI="Q 99 XB 9D MISE H Introducing this constraint in the optimum simplex table and use dual simplex method to find next optimum solution.Integer Programming 365 7/22 1/22 -1/22 3/22 Xx, 10 Here solution is xp = | =| -( 4 3) Xq i eget aie =4and =i gl mur3 which is optimum and x, = 4 is an integer. Thus the solution of the given problem is x; = 4, xX, = » and max. z = 58. Example-16. Solve the following mixed integer programming problem. Maximize, z = 6x, + 4x9 + X3 Subject to 3x, + 2x9 + x3 $ 20 6X, + 5x2 + Xy S25 X, + 3X_q + 3x35 :10 X}. Xg. Xg 2 O and x, is integer. Solution : First we solve the problem by simplex method ignoring integer restriction. Introducing slack variables x, 2 0, x5 2 0, x 2 0 one to each constraint, we have | Max. z = 6x, + 4X9 + Xg + OX4 + OXs + OxG | S. L. 3x, + 2x + Xg + Xq + OXs + Oxg = 20 | 6x) + 5X2 + Xq + OX4 + X5 + OXe = 25 | X) + 3Xq + 3xq + Oxy + OXs + Xg = 10 | Xs Xye Xan Xgy X5r Xp ZO366 Operation Research : b 20 25 10 5/6 1/6 13/6 17/6 _0 o 1 0 0 | = 25] Since all z, — ¢, 2 0, the optimality conditions are satisfied. Bui 25 X1 = 6 =4 + is not an integers. which corresponds 2nd row, so Wwe -1/2 1/2 take 2nd row as a source row for secondary constraint. Here foo = & - also 2nd row has no negative fraction. Thus fractional cut or Gomorian constraint is fon = 2 fy ( 5 i) Dd. %yx+81=- bo jeR, jeR. 5 ] 1 1 2" 6% GBH TSIA"G Introducing this constraint in the optimum table we get -1/2 1/2 1 -1/2 0 5/6 1/6 0 1/6 13/6 17/6 -5/6_ -1/6" 0Hateger Proving 7 al 7 Obtaed ONION yy» xn - { WHET by ptt nid iy Se xy Integer: Thun the OpUMUn mixed titeger solution tts KP Aka 0, xy Land mix, 24 Ys, Examplee17. Solve the mixed jnteyer problem Maxhinize, 4 © 2X) 1 AXy 4 xy 4 xq Subpeet to xy OXy 4 xy 4 YX) Xy Ry AK A Ky ‘ Hi Kae Ki Ky ot OWN Ky Ky re legen, Solutions litroductig alack varlubles xp 2 0. xy 2 0, %y 2 One to cach constraint we have MIX. % 2X) + AK Key te Ky OX 4 OX + Oy WoL Xp OX ob OX A XY HX OKG OK, A DK) Xy tb OX OXG + Oy ob Key OXy OR) yt AKG A Ky ob OX OK G Ky el/3 -2/3 0 it i 4/8 73 1 0 I 1/38 0 5/3* 0 0 =1/38 -1/38 1 “1/120 41 1/6 -1/12_ 0 -3/4T_ 0 0 1/2 6/4__—O. 1 0 2/5 2/5. 0 0 -1/6 -I/5 3/5 0 1 3/20 -1/10 ww _ ya | 1/2 00 7/20 11/10 ww in Since all 4 - ¢ 2 O and x) = 1. xy, = 1 are Integer. Thus the required inlxed Integer opUmum solution xe xe 1 xg +X 2 Oand max. 2 me