Introduction to Optimization Study Guide Complete Questions Well Answered/2024.

set of feasible solutions - correct answer the set of points satisfying all constraints and the nonnegative restrictions, the feasible solution can be empty Fundamental theorem of linear programming - correct answer a. linear programming problems with bounded, nonempty set of feasible solutions always have optimal solutions b. if an LPP has optimal solutions, then at least one of these solutions occurs at a corner point of the set of feasible solutions shadow price, marginal worth - correct answer the coefficient of s1, s2,...,sn dual problem - correct answer minimization problem; for every variable xi in primal problem, there is a constraint in the dual problem; for every constraint in the primal, there is a variable yi in the dual; the coefficient matrix in the primal is "transposed" to form the coefficient matrix for the dual Theorem (dual-primal) - correct answer the dual of the dual is primal primal - correct answer maximize C^T(X) st AX=b, X=0 dual - correct answer minimize b^T(Y) st A^T(Y)=C, Y=0 Weak duality theorem - correct answer if X0 is a primal feasible solution and Y0 is dual feasible, then C^T(X0)= b^T(Y0) Corollary (Weak duality thm- optimal soln) - correct answer if X0 is primal feasible, Y0 is dual feasible, and C^T(X0)=b^T(Y0), then X0 and Y0 are the optimal solutions to the respective problems Corollary (Weak duality thm- unbounded/infeasible) - correct answer a. if the primal is unbounded above, then the dual problem is infeasible b. if the dual is unbounded below, then the primal problem is infeasible Strong duality theorem - correct answer a. if either the primal of the dual linear problem has a finite optimal solution, then so does the other and they achieve the same optimal objective value b. if either problem has an unbounded objective value, then the other has no feasible solution Theorem (Complementary slackness conditions) - correct answer a. if in the optimal table of a primal linear problem, the decision variable xi appears as a basic variable, then the ith dual constraint is satisfied as equality constraint (i.e.- slack or surplus variable associated with ith dual constraint assumes zero value b. if in the optimal table of a primal linear problem the slack or surplus variable si appears as basic variable, then the dual variable yi associated with the ith primal constraint assumes zero value in the optimal solution of the dual linear problem Complimentary slackness theorem - correct answer let X be a primal feasible solution and Y be a dual feasible solution to a pair of linear programs, then X and Y become an optimal solution pair iff a. either ri= (b-AX)i =0 or Yi=0, i=1,2,...,m AND b. either si=(A^T(Y)-C)j =0 or Xj=0, j=1,2,...,n are satisfied post-optimality analysis - correct answer analyzing the optimal table to review the problem parameters and solution this process included confirming or updating problem parameters (cost, resources,...), and assessing effects of changes of parameters on the optimality of the solution analyze: change in objective function coefficients; increases or decreases in the right-hand side of constraint; adding a new variable; adding a constraint; changes in constraint coefficient increases/decreases in right-hand side of a constraint - correct answer increase/decrease in (delta) (see in-class example) results in translation of graph: line has same slope but change in y-intercept change in the objective function coefficient - correct answer results in change of the s