167Mathematics · Linear programming

Linear Programming: Vertex Extremes

Linear Programming: Vertex Extremes

Linear Programming: Vertex Extremes. Linear Programming: Vertex Extremes. Use CMPLX/Deg. Enter p+qi for F=px+qy+r, then four pairs (a+bi,c) for ax+by≤c, and finally r: ten inputs. Convert ≥ by reversing every sign. For three constraints, repeat the third. Require nonzero normals and (p,q)≠(0,0). The region must already be known nonempty with a vertex. Empty regions, parallel strips and the whole plane are outside the contract. General memory is cleared.

  • 242 bytes
  • CMPLX mode
01

Worked examples

Example 1

Original exercise. Data: x,y∈ℝ; x≥0; y≥0; 2x+3y≤18; F=4x+5y+7. Find: minimum F; maximum F. Calculate all requested quantities in the stated order.

Answer
min F=7; max F=43
Standard solution (without a calculator)
  1. Build the mathematical model and substitute the data.
  2. x≥0,y≥0⇒−x≤0,−y≤0; 2x+3y≤18
  3. V={(0,0),(9,0),(0,6)}
  4. F(0,0)=7; F(9,0)=43; F(0,6)=37
  5. 7≤F≤43; F(0,0)=7; F(9,0)=43
  6. Combine the preceding results to obtain the answer.
Do it on the calculator

Example 2

Original exercise. Data: x,y∈ℝ; x≥0; y≥0; 4x+3y≤120; 2x+5y≤100; F=30x+28y−40. Find: minimum F; maximum F; max F>900?. Calculate all requested quantities in the stated order.

Answer
min F=−40; max F=6460/7≈922.8571429>900
Standard solution (without a calculator)
  1. Build the mathematical model and substitute the data.
  2. x≥0,y≥0⇒−x≤0,−y≤0; 4x+3y≤120; 2x+5y≤100
  3. 4x+3y=120; 2x+5y=100⇒(x,y)=(150/7,80/7)
  4. V={(0,0),(30,0),(150/7,80/7),(0,20)}
  5. F(V)={−40,860,6460/7,520}
  6. 6460/7≈922.8571429; 6460/7>900
  7. Combine the preceding results to obtain the answer.
Do it on the calculator

Example 3

Original exercise. Data: x,y∈ℝ; x≤5; x+y≥4; x−y≤2; F=2x−3y+10. Find: minimum F; maximum F. Calculate all requested quantities in the stated order.

Answer
inf F=−∞; max F=13; (x,y)=(3,1)
Standard solution (without a calculator)
  1. Build the mathematical model and substitute the data.
  2. x≤5; x+y≥4⇒−x−y≤−4; x−y≤2
  3. y≥max(4−x,x−2)
  4. x≤3⇒F=2x−3y+10≤5x−2≤13
  5. 3≤x≤5⇒F≤16−x≤13; F(3,1)=13
  6. x=3,y≥1⇒F=16−3y→−∞
  7. Combine the preceding results to obtain the answer.
Do it on the calculator
02

When to use it

Linear Programming: Vertex Extremes. Linear Programming: Vertex Extremes. Use CMPLX/Deg. Enter p+qi for F=px+qy+r, then four pairs (a+bi,c) for ax+by≤c, and finally r: ten inputs. Convert ≥ by reversing every sign. For three constraints, repeat the third. Require nonzero normals and (p,q)≠(0,0). The region must already be known nonempty with a vertex. Empty regions, parallel strips and the whole plane are outside the contract. General memory is cleared.

Input order

  • X=p+qi
  • (a₁+b₁i,c₁),…,(a₄+b₄i,c₄)
  • X=r
  • Enter every required value again, including 0. Blank EXE retains memory; it is not zero. Used registers and Ans are overwritten.

Output order

  • min F
  • max F
  • Record the value and press EXE.
  • The program has ended. Press AC to leave; EXE runs it again.

Conditions and limitations

  • 3≤N≤4; (aⱼ,bⱼ)≠(0,0); (p,q)≠(0,0)
  • F=px+qy+r; ax+by≤c; x,y∈ℝ
  • Use CMPLX/Deg. Enter p+qi for F=px+qy+r, then four pairs (a+bi,c) for ax+by≤c, and finally r: ten inputs. Convert ≥ by reversing every sign. For three constraints, repeat the third. Require nonzero normals and (p,q)≠(0,0). The region must already be known nonempty with a vertex. Empty regions, parallel strips and the whole plane are outside the contract. General memory is cleared.
  • Read minimum then maximum. −1E99 and +1E99 are flags for no finite lower or upper extreme, not attained objective values. The variables are continuous; integer optimisation, all vertices, optimal edges and parameter ranges require written analysis. Extreme scales and cancellation can corrupt results. The program cannot certify model feasibility.
  • Enter every required value again, including 0. Blank EXE retains memory; it is not zero. Used registers and Ans are overwritten.
  • Finite precision can lose small differences between large numbers or probabilities extremely near 0 or 1. An error marker is never a valid answer.

Sign in to unlock the full programme

Checking access…

The programme code and appendix unlock together.

Checking access…

Sign in to unlock the full programme

Checking access…

The programme code and appendix unlock together.