Recover an additive constant from a vertex optimum
Recover an additive constant from a vertex optimum
All vertices of a nonempty, bounded, closed convex polygon are listed. Let F(x,y)=ax+by+k. In two separate cases, find k if its minimum is T and if its maximum is T. The constant k is additive and is not a coefficient of x or y.
- 91 bytes
- COMP mode
Worked examples
Example 1
Original exercise 1. All vertices of a nonempty, bounded, closed convex polygon are listed. Let F(x,y)=ax+by+k. In two separate cases, find k if its minimum is T and if its maximum is T. The constant k is additive and is not a coefficient of x or y. Data: A=a = 4; B=b = -1; C=N, vertex count = 4; vertex 1: x = 1; vertex 1: y = 2; vertex 2: x = 3; vertex 2: y = 2; vertex 3: x = 3; vertex 3: y = 5; vertex 4: x = 1; vertex 4: y = 5; D=T = 22.
- (a)Calculate all requested quantities in the stated order. Output order: k: minimum=T; k: maximum=T.
Answer
Standard solution (without a calculator)
- Build the mathematical model and substitute the data. P=ΣⱼλⱼVⱼ; λⱼ≥0; Σⱼλⱼ=1 ⇒ f(P)=Σⱼλⱼf(Vⱼ).
- Written solution: f(V1)=(4)(1)+(-1)(2)=2; f(V2)=(4)(3)+(-1)(2)=10; f(V3)=(4)(3)+(-1)(5)=7; f(V4)=(4)(1)+(-1)(5)=-1.
- minimum=-1, V4; maximum=10, V2.
- -1+k=22 ⇒ k=23; 10+k=22 ⇒ k=12.
- Retain exact fractions in written work; round only the final answer.
Example 2
Original exercise 2. All vertices of a nonempty, bounded, closed convex polygon are listed. Let F(x,y)=ax+by+k. In two separate cases, find k if its minimum is T and if its maximum is T. The constant k is additive and is not a coefficient of x or y. Data: A=a = 2; B=b = 1; C=N, vertex count = 3; vertex 1: x = 0; vertex 1: y = 1; vertex 2: x = 4; vertex 2: y = 1; vertex 3: x = 1; vertex 3: y = 3; D=T = 20.
- (a)Calculate all requested quantities in the stated order. Output order: k: minimum=T; k: maximum=T.
Answer
Standard solution (without a calculator)
- Build the mathematical model and substitute the data. P=ΣⱼλⱼVⱼ; λⱼ≥0; Σⱼλⱼ=1 ⇒ f(P)=Σⱼλⱼf(Vⱼ).
- Written solution: f(V1)=(2)(0)+(1)(1)=1; f(V2)=(2)(4)+(1)(1)=9; f(V3)=(2)(1)+(1)(3)=5.
- minimum=1, V1; maximum=9, V2.
- 1+k=20 ⇒ k=19; 9+k=20 ⇒ k=11.
- Retain exact fractions in written work; round only the final answer.
Example 3
Original exercise 3. All vertices of a nonempty, bounded, closed convex polygon are listed. Let F(x,y)=ax+by+k. In two separate cases, find k if its minimum is T and if its maximum is T. The constant k is additive and is not a coefficient of x or y. Data: A=a = -3; B=b = 2; C=N, vertex count = 4; vertex 1: x = -2; vertex 1: y = 1; vertex 2: x = 1; vertex 2: y = -1; vertex 3: x = 4; vertex 3: y = 0; vertex 4: x = 0; vertex 4: y = 3; D=T = -5.
- (a)Calculate all requested quantities in the stated order. Output order: k: minimum=T; k: maximum=T.
Answer
Standard solution (without a calculator)
- Build the mathematical model and substitute the data. P=ΣⱼλⱼVⱼ; λⱼ≥0; Σⱼλⱼ=1 ⇒ f(P)=Σⱼλⱼf(Vⱼ).
- Written solution: f(V1)=(-3)(-2)+(2)(1)=8; f(V2)=(-3)(1)+(2)(-1)=-5; f(V3)=(-3)(4)+(2)(0)=-12; f(V4)=(-3)(0)+(2)(3)=6.
- minimum=-12, V3; maximum=8, V1.
- -12+k=-5 ⇒ k=7; 8+k=-5 ⇒ k=-13.
- Retain exact fractions in written work; round only the final answer.
When to use it
All vertices of a nonempty, bounded, closed convex polygon are listed. Let F(x,y)=ax+by+k. In two separate cases, find k if its minimum is T and if its maximum is T. The constant k is additive and is not a coefficient of x or y.
Input order
- A=a
- B=b
- C=N, vertex count
- j=1,…,N: xⱼ, yⱼ
- D=T
- Every displayed input is required unless a blank is explicitly specified. Empty EXE keeps a stored value, whereas typing 0 replaces it with zero. The listed domain conditions must be checked even when the program does not test all of them.
Output order
- k: minimum=T
- k: maximum=T
- Record the value and press EXE.
- The program has ended. Press AC to leave; EXE runs it again.
Conditions and limitations
- N∈ℤ; 1≤N≤69; a,b,xⱼ,yⱼ,T∈ℝ.
- F(x,y)=ax+by+k; k∈ℝ.
- Math ERROR: N∉ℤ / N<1 / N>69.
- For the additive-constant calculation a segment or a single point is also allowed as a degenerate convex region; list all endpoints or the point.
- Supply all actual vertices of the stated feasible region yourself. The program does not find boundary intersections or verify feasibility, boundedness or convexity. Only a linear objective is covered; curved or empty regions require another method.
- Every displayed input is required unless a blank is explicitly specified. Empty EXE keeps a stored value, whereas typing 0 replaces it with zero. The listed domain conditions must be checked even when the program does not test all of them.
- Use consistent units throughout.
- Finite precision can lose small differences between large numbers or probabilities extremely near 0 or 1. An error marker is never a valid answer.
Checking access…