Zero One Programming by D R Zanwar

zanwardr RKNEC www.youtube.com

Brief Summary

This lecture explains the zero-one programming problem and the Balas implicit enumeration algorithm for solving it. It highlights the importance of zero-one programming in decision-making, where variables can only take values of zero or one. The lecture contrasts explicit enumeration (trying all possible solutions) with implicit enumeration (intelligently filtering solutions). It details the pre-processing steps required for the Balas algorithm, including converting the objective function to minimise type with positive coefficients and transforming constraints to a "greater than or equal to zero" form. The lecture walks through an example problem, demonstrating how to apply the algorithm, including concepts like free variables, fixed sets, distance from feasibility, and backtracking.

  • Zero-one programming involves variables with values of 0 or 1 for decision-making.
  • Balas implicit enumeration algorithm efficiently solves zero-one programming problems.
  • Pre-processing steps are crucial for applying the Balas algorithm.
  • The algorithm uses concepts like free variables, fixed sets, and distance from feasibility.
  • Backtracking is used to explore different solution paths.

Introduction to Zero-One Programming and the Balas Algorithm

The lecture introduces the concept of zero-one programming, a critical area in decision-making where variables can only assume the values of zero or one, representing choices like "yes/no" or "true/false". These decisions are crucial as they often lead to a final decision. The lecture uses the example of selecting a cricket team's batting order, where each player's position is determined by a series of zero-one variables. The lecture contrasts two approaches to solving such problems: explicit enumeration, which involves trying all possible combinations, and implicit enumeration, which intelligently filters out combinations that won't lead to an optimal solution. The lecture focuses on the Balas implicit enumeration algorithm.

Problem Statement and the Inefficiency of Explicit Enumeration

The lecture presents a specific zero-one programming problem with five variables, an objective function to maximise, and three constraints. It explains that solving this problem using explicit enumeration would require testing 2 to the power of 5 (32) combinations. While this is manageable for a small number of variables, the lecture points out that real-world problems often involve thousands of variables, making explicit enumeration impractical due to the enormous number of combinations (2 to the power of 1000 or more) that would need to be evaluated. This highlights the need for more efficient methods like implicit enumeration.

Pre-processing Steps for the Balas Algorithm

To prepare the problem for the Balas implicit enumeration algorithm, several pre-processing steps are necessary. First, the objective function must be of the minimise type. Second, all terms in the objective function must have positive coefficients. Third, all constraints must be transformed to a "greater than or equal to zero" form. The lecture emphasises that these steps are not arbitrary but have specific reasons that will become clear as the algorithm is applied.

Transforming the Objective Function

The lecture details the process of converting the objective function from maximise to minimise by multiplying it by -1. It then addresses the requirement for positive coefficients. To achieve this, variables with negative coefficients (e.g., x1) are substituted using the formula x1 = 1 - y1. This ensures that the new variable (y1) also takes values of 0 or 1. The lecture explains why simply substituting x1 with -y1 is not suitable, as it could lead to y1 having a value of -1 when x1 is 1, violating the zero-one constraint. To maintain homogeneity, all x variables are converted to y variables, even those with positive coefficients. The constant term resulting from these substitutions can be kept or eliminated from the objective function.

Transforming the Constraints

The lecture explains how to transform the constraints to a "greater than or equal to zero" form. This involves substituting the x variables with their corresponding y variables (or 1-y variables where applicable) in each constraint. If a constraint is initially in a "less than or equal to zero" form, all signs are changed to convert it to the desired form. The lecture encourages viewers to perform these transformations themselves to verify the results.

Rationale Behind the Pre-processing Steps

The lecture explains the reasons for the pre-processing steps. Having a minimise-type objective function with positive coefficients allows for a clear starting point: a solution of zero (all variables set to zero). If the constraints permit this solution, it is immediately optimal. Converting constraints to a "greater than or equal to zero" form simplifies the evaluation of constraint satisfaction. A positive or zero value indicates satisfaction, while a negative value indicates violation, eliminating the need to compare left-hand and right-hand sides.

Applying the Balas Algorithm: Initial Setup

With the pre-processed problem at hand, the lecture begins demonstrating the Balas implicit enumeration algorithm. Initially, all variables are considered "free variables" and are collected in a "free set". The "fixed set" is initially empty, as no variables have been assigned specific values. The algorithm aims to set as many variables as possible to zero, given the minimisation objective.

First Iteration: Evaluating Constraints and Feasibility

Assuming all free variables are zero, the lecture calculates the values of the left-hand sides of the constraints (C1, C2, C3). If any constraint is violated (i.e., the value is negative), the algorithm checks the possibility of satisfying that constraint. This involves substituting the free variables with positive coefficients in the violated constraint with a value of one. If, even with these substitutions, the constraint remains violated, the problem has no feasible solution.

Fixing Variables and Calculating Distance from Feasibility

If it's possible to satisfy the violated constraints, the algorithm proceeds to fix one of the free variables to one. The lecture introduces the concept of "distance from feasibility," which quantifies how much a constraint is violated. If a constraint is satisfied, the distance is zero; if violated, it's the absolute value of the negative result. The algorithm calculates the total distance from feasibility for each variable fixed to one.

Second Iteration and Backtracking

The algorithm selects the variable that results in the minimum total distance from feasibility and fixes it to one. This variable is moved from the free set to the fixed set. The process is repeated: constraints are evaluated, and if violations occur, the possibility of feasibility is checked. Once a feasible solution is found, the value of the objective function (z) is calculated. To find the optimal solution, the algorithm uses backtracking. This involves going back to a previous node and trying a different path (i.e., setting a previously considered variable to zero instead of one).

Modified Preset and Termination of Branches

During backtracking, the lecture introduces the concept of a "modified preset". This is a subset of the free set, excluding variables that, if set to one, would cause the objective function to exceed the current minimum known value of z. This helps to prune the search tree. If, at any point, the test for possibility of feasibility indicates that no feasible solution can be obtained along a particular path, that branch is terminated.

Finding the Optimal Solution and Final Substitutions

The algorithm continues to explore different branches through backtracking and variable fixing until all possibilities have been exhausted. The feasible solution with the lowest value of z is the optimal solution. Finally, the values of the original x variables are determined by substituting the values of the y variables back into the equations used during pre-processing. The lecture concludes by verifying that the optimal z value obtained using the Balas algorithm matches the z value calculated using the original problem formulation. The lecture encourages viewers to work through the problem themselves to solidify their understanding.

Summarize any YouTube video in seconds

Get summaries like this one for any video, in your language, with the free Summ app.

Download on the App Store
Get it on Google Play

Transcript

YouTube Transcript Generator

0:03 in this lecture we'll be seeing zero one programming problem and balance implicit enumeration algorithm for solving zero one programming problem zero one programming is a very critical area in decision making in zero one programming problem a value any variable can take is either zero or one yes or no true or false such decisions are very important as the choice is from only two values sometimes series of answers to many such questions lead to decision to be executed finally

0:50 for example which player should play at which of 11 batting position is answered by collection of questions whether a player i will bat at position j or not like in cricket team there are 11 players and 11 batting positions [Music] so there will be 11 into 11 variable that is 121 variables and these variables will be taking value 0 or 1 and finally this will be answering this collection of question will be answering which player will be betting at which position such problem can be solved by using explicit enumeration algorithm that is

1:36 trying all possible combinations of solution another approach is implicit enumeration algorithm that is intelligently intelligently filtering out those combinations which do not lead to optimal solution in this lecture we'll be learning ballas implicit enumeration algorithm here we go the problem maximize z equal to 5x1 minus 7x2 minus 10 x 3 plus 3 x 4 minus x bar u subject to x 1 plus 3 x 2 minus 5 x 3 plus x 4 plus 4 x 5 u less than equal to 0 is the first constraint second constraint is 2 x 1 plus 6 x 2 minus 3 x 3

2:24 plus 2 x 4 plus 2 x 5 greater than equal to 4 and third constraint x 2 minus 2 x 3 minus x 4 plus x 5 u less than equal to minus 2 and all the variables right from x 1 to x 4 u are 0 or 1 if we were required to solve this problem by explicit enumeration algorithm then as we know that each of the variable can take value 0 or 1 and there are 5 variables so the common number of combinations of the solution string will be our solution set will be 2 to the power 5 that is 32 some combinations out of this 32

3:09 combination will be violating some or um some of the constraints some of the three constrained right those combinations will be discarded out and the combinations which satisfy all the constraint for those combinations only value of z will be found and lastly by comparing the value of z to point the maximum value of z will help you in getting the optimal solution that's a very simple approach but it consumes lot of time of the computer getting you the optimal solution for five variables it won't take that much of the time but unfortunately

3:54 or [Music] the number of variables involved in search problem are thousands okay so using explicit enumeration algorithm is not a wise proposition for solving zero one programming problem because in that case the number of combinations you will have you will have to try will be two to the power thousand or more so that becomes very enormous number so therefore we will be seeing how to solve such problems by implicit enumeration algorithm so for for solving the problem by implicit enumeration algorithm some

4:41 pre-processing of the problem needs to be done that requires you to have your objective function of minimize type and second requirement with all the terms in the objective function must have positive coefficient and the third requirement is that all the constraints are to be transformed to type greater than equal to zero right this is very normal and we are not doing anything unreasonably the everything we are doing has some some reason behind it we are not just doing it okay and as we go through the process you will understand

5:27 why at all we are having the objective function minimize we are converting the objective function to minimize type why all the terms in the objective function we are converting to positive and y all the constraints um are transformed to have their right hand side of the form greater than equal to zero so first of all for converting our objective function from maximize to minimize if it is already minimized then you don't have to do anything with that as far as conversion is concerned but here the objective function is maximized so for converting it to minimize we will be multiplying this objective function by minus 1 so i get equivalent

6:16 of equivalent minimized type of objective function in the form of minimize z dash is equal to minus phi x 1 plus 7 x 2 plus 10 x 3 minus 3 x 4 plus x 5 u but now second condition if we look at we are having our objective function minimized but the terms in the objective function are not all positive some of the coefficients are negative right so for converting this coefficients to positive i will need to make a substitution of the form um like here x1 because the coefficient

7:01 of x 1 is minus 5 for converting that minus pi u to plus pi u i will be substituting x 1 as 1 minus y 1 now you may ask the question why not simply minus y1 if you substitute x1 as minus y1 then if x1 takes value 0 minus y1 y1 will be taking back to 0 it's fine but if x 1 is 1 then y 1 will be minus 1 that i don't want i want a substitution of a kind wherein i am sure that variable i am using in my substitution will also be taking value 0 r1 so in this

7:47 substitution when i am substituting x1 by 1 minus y1 what is happening just look uh if x1 is 0 if i [Music] suppose if y1 is 0 x1 will be 1 and if y1 is 1 x1 will be 0 that's good because um my variable x1 is taking that 0 r1 y1 also is taking value 0 or 1 okay so the variable which has negative coefficient is to be substituted by 1 minus y i here in this case y1

8:35 now there is another variable which has negative coefficient here x4 so i'll be substituting that by 1 minus y for x4 i will be substituting it by 1 minus y4 now for avoiding a situation wherein some variables are in form of y's and some variable are in form of x i am substituting other x variables to y variables like um even though that is not required to be done but to have homogeneity homogeneous base variable i'll be substituting x 2 as y 2 x 3 as y 3 and x 5 u as y pi so that i have my objective function in terms of y's only all right

9:21 so now the objective function becomes 5y1 plus 7y2 plus 10y3 plus 3y4 plus y prime and that one part minus 5u from here and minus 3 from here is coming here in the form of minus 8 that you may continue to have it in your objective function or you may eliminate it okay you can have this whole as your objective function or you can have your objective function till y pi right i hope you have understood that now that i have transformed my objective function

10:06 to a minimized type and to have all the coefficient with to have all the positive coefficients in the objective function i now have to see that all my constraints are transformed to greater than equal to zero form all right so i will be doing this substitution in the constraints also x1 substituted by 1 minus y 1 all right so just look at it x 1 substituted by 1 minus y 1 plus 3 y 2 minus 5 y 3 x 4 substituted by 1 minus y 4 plus 4 x 5 u substituted by 4 y pi less than equal to 0

10:54 right this is simplified to this form again less than equal to 0 here but i want the constant in the form greater than equal to 0 so i have changed all the signs here for example minus y 1 to y 1 plus 3 y 2 to minus 3 y 2 minus pi by 3 to plus pi y 3 and so on all the coefficients have changed thereby i have converted this less than equal to 0 type constraint to greater than equal to 0 type constraint again by substituting um these things x 1 as 1 minus y 1 and x 4 as 1 minus y 4 and rest other at x 2 equal to y 2 x 3

11:40 equal to y 3 and x 5 equal to y 5 in the second and third constraint and doing necessary transformations to get the constraint converted to type greater than equal to 0 i convert the constraint as i am saying okay you can do it yourself and confirm whether your transformation is leading to get your constraint transform to this form and this form right finally if i compile my problem together this is the objective function till this which is to be in the form of minimize

12:27 and the cons first constraint taken from here greater than equal to zero form second constraint again greater than equal to zero form and third constant greater than equal to zero form so all these pre-processing conditions three conditions i have taken care now the question is why at all i want minimize type of objective function why i am not interested in having my objective function maximize type so if it is maximized type i don't know what is the best value of this objective function or it will be varying value okay if my objective function is maximized type then the value

13:15 best value of objective function will be a varying value depending upon the problem but if i have my objective function minimize type and if i make sure that all the terms in the objective function have positive coefficient the best solution will be zero all the variables involved in the problem will be taking zero value and z value is zero so if i get zero solution value of z equal to zero that itself is the optimal solution but the problem is my constraint may not get satisfied with that kind of solution if that happens if my constraint gets satisfied fine okay i get the solution before i do much

14:01 in the um much of the processing right so the constraints now why i why i have converted the constraint to greater than equal to zero form because soon this value comes positive it will be very sure for sure to me that the constraint is satisfied if this value is [Music] and then it will be very sure for sure to me that the constraint is violated otherwise i will have to come compare the left hand side with the right hand side to to assess whether the constraint is satisfied or violated now simply by

14:48 seeing if the constraint has positive or zero value then it is satisfied um right and if it is uh if it is [Music] would you say negative value then it is violated right so um now that we are having the pre-process problem available to us we will we are in we are ready for applying implicit information algorithm balance implicit enumeration algorithm so let's move on to the next transparency

15:37 all right now we are here the problem is written for our ready reference right now we don't know which variable will be taking which value of 0 and 1 so all the variables for us at the beginning are pre variables and we we collect them in preset and here i have written one two three four five that means y one y two y three y four and y for you are free variable they are free to take any value and in fixate i have not fixed any variable to some specific value all right

16:22 so in fixed it there is no variable it is a null state if objective is minimization then um if the constraint permit we will like to have as many variables as possible set equal to 0 this is this we are saying because our objective function is minimized so as many variables um from this objective function [Music] uh take value 0 it will be better solution right so assuming that all three variables are 0 because we have not fixed any value for

17:09 any of the pre variables and that's why they are free so assuming that all three variables are equal to 0 we will be finding the value of c1 c2 c3 c1 is the first constraint left hand side c2 is the second constant left hand side and c3 is the third constraint left hand side so c1's value by putting all three variables equal to zero is minus two c two's value it comes out to be zero and c three's value comes out to be minus one so we are seeing that uh because c1 and c2 the value is c1 and c3's value is negative we we say that the constraint is

17:56 first and third constant is violated right so when they are violated we will have to look into the possibility that if it is at all possible to satisfy these first and third constraint second we are seeing that it is already satisfied so for um checking the possibility of feasibility of first and third constraint what we will be doing all the variables we will be substituting all the variables in post constraint for example here from preset

18:41 have positive coefficient in the first constraint will be substituting them as one but that is the only way of converting this minus sign to plus sign all right so we will be substituting y1 because it belongs to pre set then y3 and then y4 okay all these variables belong to preset we have substituted them equal to one because they have plus one coefficient rest which of negative coefficient we are not substituting them at one so what i am getting one plus five u six plus one seven am i right am i right yes uh see here i

19:29 am having a mistake but that is not affecting another part of the solution c1 turns out to be uh six uh seven so it is possible to satisfy the first constraint in place of five you read there seven now third constant which was violated we want to look into the possibility of satisfying the third constraint so for that what we do is from the preset which has all right now all the variables will be substituting only those variables equal to one which have positive coefficient in third constraint so y three only has positive coefficient in third constraint so we'll be substituting y three equal

20:15 to one and after that this becomes two minus 1 that gets you one value of c 3 and as it is possible to get the positive or 0 value of g 3 there is a possibility of satisfying the constraint so having um having known that it is possible to satisfy the constraint we will proceed ahead towards fixing one of the five variables from preset to one right now suppose say at this at this stage itself you would have found that it is not possible to satisfy the constraint here itself you would have got the solution that the problem doesn't have

21:02 solution all right so now that we have got the positive result for the test for possibility of feasibility we will be moving towards fixing one of the variable out of this pi u two equal to one so we will be doing it one by one i will be fixing y one equal to one uh while i fix y one equal to one rest other i am free to assume them equal to zero okay now here i am using a term called a distance from feasibility what does that mean it means how how far you are from how much away you are from visibility

21:48 if you are already you are getting a feasible um you are satisfying certain constraint you are dealing with then your distance from visibility will be zero but if it is coming negative if your constraint is getting violated adding how much quantity to eat will satisfy the constraint is the distance from visibility right so distance from feasibility for c1 for c2 and for c3 will be finding and then lastly we'll be finding total distance from feasibility right so y 1 equal to 1 i am substituting y 1 equal to 1 in first constraint and rest other are 0 so 1 minus 2 is

22:36 getting me minus 1 so the constant is violated but if i add one to it it will get satisfied right so their distance from feasibility is one now let us look at distance from possibility per second constant if y1 is substituted equal to 1 so this is becoming minus 2 and there is no other addition so minus 2 all other are 0 so minus 2 the distance from feasibility for this constraint in that case is 2 because the constraint is violated and if i add 2 to 8 the constraint will become satisfied so distance from visibility for second

23:21 constraint is 2 and for third constraint y1 is not there term is not there and others i am assuming all of them equal to 0 and minus 1 is there so if i am able if i add 1 to this then only it will be possible for me to satisfy third constraint right if the value of left hand side comes negative then the absolute of that is the distance from possibility if it comes positive then the distance from visibility is zero because the constant is already satisfied now if i take y 2 equal to 0 and rest

24:07 all other equal to y 2 equal to 1 rest all other equal to 0 so here i get minus 3 minus 2 minus 5 that means pi distance away c1 is pi distance away and c2 now y2 i am taking equal to 1 and rest of that 0 6 so left c2 will become equal to 6 so distance from feasibility in that case is 0 because the constant is already satisfied right then third one y 2 equal to 1 i am substituting so this term will become minus 1 our rest all variables are 0 minus 1 minus 1 minus 2

24:53 over so distance from probability is 2. so total distance from probability is 7 it is addition of the distances from visibility likewise by substituting y 3 equal to 1 y 4 equal to 1 y phi equal to 1 while i substitute this substitution rest other variables i am assuming 0 so you can yourself find this values and the total distance from visibility now i'll be comparing total distances from feasibility to find the minimum total distance from probability and that is 3 so i'll be fixing y 3 equal to 1

25:40 okay now i'll be going on to the second iteration okay my iteration ends here second iterations okay now in my fixed set i have one value which was null here now i have one value 3 because i have fixed y 3 equal to 1 and that value will not be there now in preset so my appreciate says 1 2 4 5 values right now once again i'll be substituting or i'll be assuming all three variables equal to 0 y 3 equal to 1 because it is fixed and i will be finding out

26:26 the values of c1 c2 and c3 just look here y 3 i have fixed equal to 1 and rest all other are 0 so 5 minus 2 is 3 so that means that constant c 1 equal to 3 when c 1 comes positive it is indicative of constant getting satisfied now second constraint now y 3 equal to 1 and rest of the 0 all right so 6 it is 6. [Music]

27:12 it is six it is six [Music] just a minute uh y1 6 sorry sorry sorry sorry y 3 is 1 so it is minus 3 and rest all other are 0 so minus 3 um c 2 value is coming out to be minus 3 and having that value negative is indicative of violation of the constraint and then let's go on to the third constraint y 3 is equal to 1 rest all other are 0 so i

27:58 am getting the value of c 3 equal to c3 equal to 2 minus this 1 2 minus this 1 [Music] makes it 1 okay here it should be 1 but if it is zero or one if both are indicative of satisfying and both are indicative of satisfaction of third constraint so all in all considering this mistake also we are seeing that second constraint is violated now the question is is it at all possible to satisfy second constraint right for that what we will be doing from this preset whichever variable have

28:46 positive coefficient in the second constraint because second constant y because we are concerned with it being violated constraint in the second constraint i am finding that coefficient of y2 is positive and y5 is positive both of them are uh in presets so i can i can substitute their coefficient equal their value equal to 1 so 6 plus 2 8 okay minus 3 because y 3 is fixed equal to 1 so it is coming out to be pi u so as this is phi u the constraint can be satisfied now having

29:32 um having signaled that um the it is possible to satisfy second constraint violated constraint we will move on to fix one more variable equal to one we already fixed y three equal to one now we are moving towards fixing y some other variable equal to 1 all right now feasible solution is obtained but it is not optimal i don't know whether it is optimal or not but feasible solution definitely yes so by now if i track the process post i peak so i have fixed y 3 equal to 1

30:20 and then i'll fix y2 equal to 1 and there i have got a feasible solution and soon i get the feasible solution i'll be finding the value of z so by substituting y 2 equal to 1 and y 3 equal to 1 i get z equal to 17 okay for getting the optimal solution now um i have the standard our minimum known value of z is available with me if i get any other value of z which is less than 17 then [Music] i will be referring to that value of z as being a minimum value for any letter um

31:06 in diverse i will then be trying to get the value of z lesser than that that minimum value of z that's what is the idea now that i have tried y2 equal to 1 i would like to go back to this node and will i would like to try another part another part means y2 equal to 0 so what i am this this process is called as backtracking so i am trying i am going back and taking another part so i now have the fixations of the variable as y 3 equal to 1 and y 2 equal to 0 so my pix8 is indicated as y 3 equal

31:52 as 3 and minus 2 now this minus 2 is used for signifying that the variable corresponding to that minus sign is taking value 0 okay y 3 is 1 and y 2 is fixed equal to 0 not assumed equal to y 3 is fixed equal to 1 y 2 is fixed equal to 0 because it is minus sign right and now my preset is having the variables which are not there in fixed set one four and five now here when i was going along this part

32:39 i know that i am not going to get a feasible solution at this point but still what i am doing i will be finding the value of z tentative which gets built till this point by taking y 3 equal to 1 and y 2 equal to 0 right y 3 equal to 1 and y 2 y 3 equal to 1 and y 2 equal to 0 and rest of them safely at them to be 0 so value tentative value of z so far built is 10 now i would not like to have any other variable fixed equal to 1 which has the coefficient greater than 7 because

33:24 when i know that value of z i have built so far by fixing these two variables the way i have fixed is coming out to be 10 minimum known standard of z is 17 so i have the scope of 7 right 17 minus 10 i won't allow any variable to be fixed equal to 1 if that if it has a coefficient greater than 7 so from my preset i will eliminate those variables which has coefficient greater than 7 so i will be checking the coefficients of y 1 y 4 and y 5 in objective function are they greater than

34:10 7 and if they are i will omit them from being the member of preset and that's how i build what is called as modified preset so y1's coefficient is 5 less than 7 y 4's coefficient is 3 less than 7 by point coefficient is 1 less than 7 so my modified preset is preset itself sometimes you may have all the all the elements from the preset we which will be having value of z which will be having the coefficients in objective function greater than scope in that case modified preset will become

34:57 null state right now uh um i will be finding out concern now the iterations are same except for this addition thing here constant state i'll be finding um by setting three variables um from modified preset equal to zero right so and y three fixed equal to one y two fixed equal to 0 and y 1 y 4 and y 5 assumed equal to 0 i get c 1 c 2 and c 3 as 3 minus 3 and 0 okay

35:43 right 3 minus 3 and 0 so second constraint is violated so again i'll be carrying out the test for possibility of feasibility on the second constraint now now just look at this right i'll just look at this just a second [Music] just look at this uh what i am having [Music] c2 is violated and um

36:28 i will be fixing i know that y 3 is 1 so minus 3 is fixed okay y 2 is equal to 0 okay i don't have option of putting that y 2 equal to 1 so by this two terms i am having value minus 3 built so far right and now from preset which includes modified preset y1 y4 and y5 i need to find if any of the variables have positive coefficient okay so y5 has positive coefficient all right 2

37:14 right minus 3 plus 2 gets you minus 1 so what does that mean it means that it is not possible to satisfy second constraint okay feasible solution cannot be obtained by combination in which y 3 is 1 and y 2 is 0 okay so um this node means if i am trying to investigate this path for optimal solution that path gets terminated here itself because along this path if i go i'm not going to get a feasible solution that is confirmed by the test for possibility of feasibility okay

38:00 now that this this branch is not going to yield me anything constructive so i will be going further back where i have tried y 3 equal to 0 i want to try y 3 i have tried y 3 equal to 1 i want to try y 3 equal to 0 okay so my fixed set in this iteration now will be minus 3 because i am going along this part minus 3 and the pre variables for me now are 1 2 4 and 5 now look at this i have the idea of minimum value of z that is 17 and tentative value of z getting built

38:47 because of the variables i have picked so far um that is y three equal to zero and if i substitute here in the objective function what is happening uh z tentative is coming out to be zero the scope i am having of um uh increasing the value of z is 17 minus zero that is 17 scope is there so if any of the variable from preset is having coefficient greater than 17 i will be eliminating that variable from preset that's how i'll be getting modified preset all right and then going on to continuing that iteration i am going to

39:34 find c1 c2 and c3 but while doing that i need to keep in mind that y 3 is fixed equal to 0 and others are assumed equal to 0 so i am getting the value of c 1 as -2 c 2 as 0 and c c3 as minus 1 all right and they i'll be performing the test for possibility of feasibility all right on the first and second cons first and third constraint which are violated so just look here y3 i cannot take it as

40:21 i cannot take it as 1 because i have fixed equal to 0 so let's consider constraint number 1 for checking if at all it can be satisfied or not right so i have y one y two y four and y five in modified preset but only after those y one and y four has positive coefficient like i'll be substituting them as one i'll be substituting them as one all right so you plus 1

41:10 y 3 is 0 1 plus 1 2 minus 2 is equal to 0 all right third constraint right y 3 is 0 and i don't have any variable from modified preset which has positive coefficient in constraint number three um so i am going to get c3 as [Music] c3 y3 is fixed equal to 0 and c3 i am going to have

41:55 i am going to have is minus 1 by mistake here it is minus 2 it should be minus 1 only all right so all in all that means i am not able to satisfy third constraint it's not possible to get a feasible solution if y 3 is fixed equal to 0 that is sure so i don't have to try any combination wherein y 3 is equal to 0 because that is not leading me towards getting the optimal solution right so it's not possible for you to get a feasible solution if y 3 is equal to 0 so everything has been searched so far

42:41 so my solution is y 3 equal to 1 y 2 equal to 1 okay because amongst all the possibilities all the combinations i have tried so far this only has given me the optimal solution solution and that eventually happens to be optimal solution right um y 3 1 y 2 1 so y 1 y 4 and y pi equal to 0 right but you if you recall back to the substitutions you have made in the beginning y1 is 1 minus x1 is 1 minus y1 so as y1 is 0 x1 will be 1 y 2

43:27 is x 2 so as y 2 is 1 x 2 is 1 y 3 is x 3 y 3 1 x 3 1 y 4 is equal to 0 means x 4 is equal to 1 and y prime is x 5 so y phi 0 means x 5 is 0 and by substituting all these variables in the original problem i am getting z equal to minus 19. now you may question that when the problem is same then why in this case i am getting z minimum as 17 and uh z minimum as 17 and

44:12 uh here for the original problem z as minus 9 because if you recall i was subtracting minus 8 in the original problem which i have not done if i do that if i do that if i do that if i do that then z will come equal to nine and you you recall one more thing and that um

44:58 for converting your objective function from minima maximize to minimize we have taken um you we have used or we have multiplied the objective function by minus 1 so here we are getting it here minus 9 and there it is 17 minus 8 means 9 only both the answers are same right this is how we will be using balance implicit algorithm here the problem got easily finished but sometimes the problem may grow their branches on this side and that branches may have to be backtracked once again and further sub-branches may also

45:45 have to be backtracked and in that case the problem [Music] shows a little bit of complexity okay so here we finish our lecture you however you are supposed to take up the same problem and as um [Music] you will be moving through the solution you also [Music] do the solution yourself thank you so much

Share

YouTube Video Summaries

Pulses

Cereals

Beautiful Princess Pretended To Be Broke Village Girl To Find The Humble Hunter - African Movies

💎🦆🌊 THE GIANT DIAMOND DUCK HOUSE ADVENTURE! 🏡✨🚤😱 | They Found a Mysterious House Underwater! 🌊💎🦆

Bring them all - open challenge by Adam Seeker

ಗಾಂಧೀ ಯುಗ (1919 -1947) I ಪ್ರಮುಖ PYQ ಪ್ರಶ್ನೋತ್ತರಗಳ ಚರ್ಚೆ| Shivaraj Palled sir | #kea #vao

Browse all summaries →