We talk about functions, talked about constraints and for some reasons we need to tell you there are two kinds of constraints. They are sign constraints and they are functional constraints. Basically, if you have a constraint saying that there is a single variable which should be non-negative or which should be non-positive, you are talking about let's sign of a specific variable. In that case we say this is a sign constraint, we will very quickly see why we want to separate them. If have any function where the right-hand side value is not zero or the left hand side combination of variables is not just a single one then there's the other cases we say this is a functional constraint.. When you look at the constraints either it is assigned constraint or it is a functional constraint. When you are having some sign constraints, if you are x cannot be negative we say it is non-negative variable. If it is the case that it cannot be greater than 0, we say it is non positive. If your x has no sign constraint, we say it is unrestricted in sign. Abbreviated as urs. or we say it is free that basically means there is no restriction on its sign, so it maybe positive it may be negative, it may be zero, is only restricted by other functional constraints. If we have constraints very quickly we may talk about feasible solution. Any value combination of all your decision variable form a solution but some are feasible some are not. A feasible solution satisfies all the constraints, so it is an executable plan. On the other hand if you have a solution that violates at least one constraint, it is an infeasible solution, is still called a solution but it is infeasible. Example is here, we have three functional constraints and the two sine constraints and we have several candidate solutions. For example x_1 which is 2,3. If you plugging 2,3 into these functions, you may see that 2 is less than or equal to 10 this is fine. 2 plus 2 times, in this particular case it is still feasible. For the last one 2 minus 2 times 3 this is still again feasible. Basically we can say that the solution x_1 is a feasible solution because if you're plugging 2,3 into these particular set of constraints, it satisfies everything. Very quickly you may check the others candidate solutions for example, x_3 is 6,6. You may very quickly see that it violates the second constraint because 6 plus 12 is greater than 12. This is not allowed, this guy is infeasible. Combining all those feasible solutions, we get a feasible region or sometimes we call it a feasible set. Of Course It may be empty. If you have a random if you have any specific mathematical program, is always possible that some constraints are conflicting with each other and that there is no way to satisfy all constraints at the same time. In that case you don't have any feasible solution and your feasible region is empty. Inside the set of all the feasible solutions, we want to look for an optimal solution. Pretty much that's the meaning for solving a program. Optimal solution is a feasible solution that is optimal, that is the best. Technically it means if you are talking about a maximization problem, then that feasible solution gives you the largest possible objective value. If this is a minimization problem, that feasible solution gives you the smallest possible objective value or intuitively when you say one thing is optimal, there is no feasible thing that can be even better than that. Here when we say better we mean strictly better, so they cannot have a tie they can not be equally good. When you say one thing is optimal and if I want to challenge you, I wanted to say no you are wrong. I need to give you a solution a feasible solution that is strictly better, then I can say your solution is not optimal. That's somehow suggest you wants fact. An optimal solution may actually be unique or not unique, so sometimes we have a linear program with multiple optimal solutions that's possible, or is also possible that there is no optimal solution at all. For example if your feasible region is empty, you don't have any feasible solution then you don't have any optimal solution. Or it's also possible that you have a mathematical program there are feasible solutions, but that there is no optimal solution. Very quickly we will show you why it is possible. Next we need to talk about very important concept which is called binding constraints. It is a property for a constraints, when you are talking about a specific solution. Let's take a look at this definition. Suppose we have g of something less than or equal to b as an inequality constraint and the x bar is a specific solution then this particular inequality constraint is said to be binding at x. It's binding at x bar when you plug in x bar you get inequality constraint. Pretty much that says when you have an inequality constraint and there is a solution once you plug in that becomes equality. If that's the case, then we say this constraint is binding at x bar. Inequality may also be nonbinding at a point and a solution if it is strict instead of equality at that point. If you plugin and you see there is indeed a positive gap between the two sides then that inequality is nonbinding. If you have that definition and you look back at inequality constraint, if you have a feasible solution it must be some binding thing happening on that inequality. Any equality constraints must be binding at any feasible solution because if you're plugging that becomes inequality. Here are some numerical examples, I have an inequality constraint which is x_1 plus x_2 less than or equal to 10. This constraint is binding at 2, 8 because if you plugin 2, 8 that becomes an equality. On the contrary, this constraint 2x_1 plus x_2 greater than or equal to 6, this is nonbinding at 2, 8 because once you plug in 2,8 you may see the left-hand side is switched strictly better than strictly greater than the right-hand side. This means the constraints is nonbinding. The last one is inequality constraint, as this is a feasible solution, you plugin you get the equality, again this is binding. The definition of a binding constraint applies to both inequality and equality constraints but typically we focus more on inequality constraints when we are talking about binding or not because we basically always care about feasible solution, and then equality constraint is always binding at any feasible solution. Intuitively or geometrically, if you have a constraint saying that your feasible region is this part then, if a point lies at the boundary then you know these constraint is binding at that point. If another point lies in the interior of that feasible region then you know this constraint is not binding at that interior point. Lastly, binding, nonbinding are sometimes called active, inactive constraints by some other scholars. They are pretty much the same thing, whether a constraint is binding at one point basically means whether a constraint is active at that point. We mentioned about equalities, inequalities, and we all know that inequality may be strict or weak, so you may have a strict inequality or a weak inequality. A strict inequality means that tool size cannot be equal like x_1 plus x_2 should be greater than 5, if that's the case then 2, 3 does not satisfy this inequality because 2 plus 3 equals 5 this is not allowed. It is a weak inequality if the two sides are allowed to be equal. The thing that we want to remind you is that in mathematics both are possible but in OR, if we are talking about practical applications inequalities are always weak. We only work on weak inequalities in this course, why is that? Because with strict inequality sometimes an optimal solution actually does not exist which is very weird I would say. For example, there is a very simple formulation here, there is a real line I want to try to push x to the left as small as possible, but there is a constraint saying that your x must be greater than 0. In that case, you don't have optimal solution, if you say 0.1 is optimal I give you 0.01, if you say 0.01 is optimal I give you 0.001. You also cannot say that is optimal because zero is not feasible. If we allow strict inequalities, the feasible set technically may not be closed. You would see some boundaries that you cannot reach and then that may result in the case that your optimal solution does not exist. Mathematically is weird enough, practically it can be even more weird because practically in most cases the constraints by nature are weak. Why is that? Think about your budget constraints, suppose you have $500 you want to use that $500 to buy 0 things also that is a decision problem. That typically means you cannot spend more than 500, so 501 not allowed 500 and 50 cents not allowed. But you are allowed to spend exactly 500, so I hope this small example shows you or convince you that in practice most of the decision problems face inequality constraints, and we face weak inequality constraints where you have budget constraints you are allowed to spend all your budget. Where you have capacity constraints, you are allowed to use all your capacities. Where you'll have demand fulfillment constraints, you are allowed to just meet the demand, so we will always focus on weak inequalities in the whole course.
