OPERATIONS RESEARCHMini-ProjectSolving a Real time problem using LPP, Simplex method and BIG M Method10BEC0025-Kandepi Prudhvi Raj10BEC0308- G Karthik Reddy10BEC0332- R Vamshidhar Reddy5/7/2013Prof. Rita. SOperations Research
Abstract:-
In this paper, we discuss the application of linear programming to solve the situation of handling the beams in cancer operation. Cancer treatment makes use of radiation beams to clear the tumour. Using LPP, we find the optimum number of waves to be used. Here we use a 2 phase method comprising of Big-M and simplex methods.
Introduction:-
Since Radiology has advanced a lot in the past decade, People have come up with an answer to treat initial stages of cancer by using laser beams of varying intensity. It is known as one of the best ways to treat cancer but it comes with a huge risk. Radiation is attractive because the repair mechanisms for cancer cells are less efficient than for normal cells. Recent advances in radiation therapy now make it possible tomap the cancerous region in greater detailaim a larger number of different beamlets with greater specificityThis has lead to the development of a new field called as tomotheraphy. High doses of radiation (energy/unit mass) can kill cells and/or prevent them from growing and dividing. True for cancer cells and normal cells. So in order to not destroy the healthy cells, we must concentrate the beams with enough intensity to destroy all the cancer cells and minimum number of normal cells.
Theory:-
To make use of LPP, we go for Conventional Radiotherapy. In conventional radiotherapy3 to 7 beams of radiation. Radiation oncologist and physicist work together to determine a set of beam angles and beam intensities. Determined by manual ” trial-and-error” process. Our goal is to maximize the dose to tumor while minimizing dose to the critical area. With a small number of beams, it is difficult to achieve this goal.
Problem Statement:-
For a given tumor and given critical areasFor a given set of possible beamlet origins and anglesDetermine the weight of each beamlet such that: Dosage over the tumor area will be at least a target level γL. Dosage over the critical area will be at most a target level γU. Create the beamlet data for each of p = 1, …, n possible beamlets. Dp is the matrix of unit doses delivered by beam p.= unit dose delivered to pixel (i, j) by beamlet p. The Linear program has the following conditionsDecision variables w = (w1, …, wp)wp = intensity weight assigned to beamlet p for p = 1 to n; Dij = dosage delivered to pixel (i, j)Here we minimizeOptimal Solution for the LPThere are further constrains to follow:-Minimize damage to critical tissueMaximize damage to tumor cellsMinimize time to carry out the dosageLP depends on the technology
Numerical Example:-
Consider a person about to undergo cancer operationObjective – Design and select the combination of beamlets to be used and the intensity of each one, to generate the best possible dose distribution (units: kilorads)Decision variables: x1 – dose at the entry point for beamlet 1×2 – dose at the entry point for beamlet 1Objective function: Z – total dosage reaching healthy anatomymin z = 0. 4 x1 + 0. 5 x2st 0. 3×1 + 0. 1×2 ≤ 2. 7 critical tissues0. 6×1 + 0. 4×2 = 6 tumor region0. 5×1 + 0. 5×2 ≥ 6 center of tumorx1, x2, > 0The above inequalities can be solved by using Big-M method directly. But for computational purpose, the Big-M method is quite complex. The optimal values are x1= 7. 5, x2= 4. 5To simplify the process for computational purpose, we use the two-phase method. Two phase method – streamlined procedure for performing the two-phases directly, without introducing M explicitly, Phase 1 – all the artificial variables are driven to 0 (because of the penalty M) in order to reach an initial BF solution to the real problem; Phase 2 – all the artificial variables are kept to 0 (because of the penalty M) while the simplex method generates a sequence of BF solutions for the real problem that leads to an optimal solution. So in the end we can solve without using the M. For two-phase method the functions are as follows:-Real problem’s objective function: min z = 0. 4 x1 + 0. 5 x2Big M method’s objective function: min z = 0. 4 x1 + 0. 5 x2 + M x4 + M x6Since the two first coefficients are negligible compared to M, the two phase method drops M by using the following objective functions: Phase 1: minimize z = x4 + x6 (until x4 = , x6 = 0)min z = x4 + x6st0. 3×1 + 0. 1×2 + x3 = 2. 70. 6×1 + 0. 4×2 + x4 = 60. 5×1 + 0. 5×2 – x5 + x6 = 6×1, x2, x3, x4 , x5, x6 >= 0The initial solution for phase 2 is the final solution of phase 1:- x1= 6; x3 = 0. 3; x2= 6, x4, x5, x6= 0Phase 2: min z = 0. 4 x1 + 0. 5 x2 (with x4 = , x6 = 0)min z = 0. 4×1 + 0. 5x2stc0. 3×1 + 0. 1×2 + x3 = 2. 70. 6×1 + 0. 4×2 = 60. 5×1 + 0. 5×2 – x5 = 6×1, x2, x3, x5 >= 0Using phase 1 solution, how do we get the 1st tableau for phase 2Preparing for Phase 2What variable leaves the basis and what variable enters the basis? Here also e obtain the same optimal result of x1= 7. 5, x2= 4. 5Graphical Visualization of phase 1 and phase 2:-C: DOCUME~1selmanLOCALS~1Temp\ msotw9_temp0. bmpThe two-phase method streamlines the Big M method by using only the multiplicative factors in phase 1 and by dropping the artificial variables in phase 2. Two-phase method is commonly used in computational implementations. From a computational view point this approach has the disadvantage of introducing new variables. If all the variables can have arbitrary values the transformed model will have twice as many variables. But nevertheless, we can avoid the usage of an arbitrary M value by creating artificial decision variables. If the original problem has no feasible solutions, then either the Big M method or the phase 1 of the two-phase method yields a final solution that has at least one artificial variable greater than zero.
RESULT:-
Thus we have seen the real time application of Linear programming in the curing of cancer by using 2 phase method for computational purpose.
