Question 1

Which of the following best describes a polyhedron in the context of linear optimization?

Accepted Answer

A set defined by the intersection of finitely many halfspaces.

Question 2

Given the standard form of a linear program: $$\min \{ c^T x : Ax = b, x \geq 0 \}$$, which of the following is NOT a characteristic of this form?

Accepted Answer

It is a maximization problem.

Question 3

Which geometric object is defined by $$\{ x : a^T x = b \}$$?

Accepted Answer

A hyperplane

Question 4

In the context of linear programming, what is a basic feasible solution (BFS)?

Accepted Answer

A solution that satisfies all constraints and is a vertex of the feasible region.

Question 5

Consider the feasible region defined by $$x_1$$ + $$x_2$$ \leq 4$$, x_1$ \geq 0$$, $$x_2$$ \geq 0$$. What is the geometric shape of this region?

Accepted Answer

A polyhedron

Question 6

Which of the following statements about extreme points of a polyhedron is correct?

Accepted Answer

Every extreme point is a basic feasible solution.

Question 7

If a linear program has multiple optimal solutions, what can be said about the set of optimal solutions?

Accepted Answer

It forms a line segment or a higher-dimensional face of the feasible region.

Question 8

Which transformation is used to convert an inequality constraint $$a^T x \leq b$$ into an equality in standard form?

Accepted Answer

Introduce a slack variable $$s \geq 0$$ such that $$a^T x + s = b$$

Question 9

What is the implication of the theorem: 'If $$P is a $$bounded polyhedron, then $$P$$ has a basic feasible solution'?

Accepted Answer

There exists at least one vertex in the feasible region.

Question 10

In the conceptual algorithm for linear programming, what is the main idea behind moving from one corner to another?

Accepted Answer

To visit a neighboring corner that improves the objective value.

Question 11

Which of the following is true about degeneracy in linear programming?

Accepted Answer

Degeneracy occurs when more than $$n$$ constraints are tight at a solution in $$n-$$dimensional space.

Question 12

Suppose you have the following constraints: $$x_1$$ + $$x_2$$ \leq 2$$, x_1$ \geq 0$$, $$x_2$$ \geq 0$$. What is the set of feasible solutions?

Accepted Answer

All points in the first quadrant below the line $$x_1$$ + $$x_2 = 2$

Question 13

Which of the following is NOT a property of a basic feasible solution?

Accepted Answer

It is always an interior point of the feasible region.

Question 14

What is the geometric intuition behind the simplex method in linear programming?

Accepted Answer

It moves along the edges of the polyhedron from one vertex to another to improve the objective value.

Question 15

If the feasible region of a linear program is empty, what does this imply about the problem?

Accepted Answer

There are no solutions that satisfy all constraints.

Question 16

Which of the following is a correct definition of a halfspace?

Accepted Answer

The set $$\{ x : a^T x \leq b \}$$

Question 17

In the context of optimization, what does the term 'vertex' refer to?

Accepted Answer

A point where $$n$$ constraints are tight and linearly independent in $$n-$$dimensional space.

Question 18

Which of the following is true about the optimality of basic feasible solutions (BFS) in bounded polyhedra?

Accepted Answer

At least one BFS is optimal if the polyhedron is bounded.

Question 19

What is the main purpose of constructing basic columns in the context of BFS?

Accepted Answer

To identify linearly independent constraints that define a vertex.

Question 20

Suppose you are solving a real-world resource allocation problem using linear programming. Why is it important to identify the vertices of the feasible region?

Accepted Answer

Because optimal solutions are found at the vertices.

Geometry of Linear Optimization: Polyhedra, Vertices, and Basic Feasible Solutions

스터디 가이드 - 연습 문제

학습 가이드 - 플래시카드