Simplex Method Intro

📌 Problem Setup

Minimize:

Subject to:

We begin with basic variables $x_3,x_4$, and non-basic $x_1=0,x_2=0$

🔹 Initial Basic Feasible Solution

Set:

• $x_1=0$, $x_2=0$
• Then $x_3=1700$, $x_4=1600$
• So:$$f=-2(0)-4(0)=0$$

✅ Feasible, but not optimal because $x_1,x_2$ have negative coefficients.

🔹 Step 1: Bring $x_2$ into the basis

We choose $x_2$ because its coefficient in $f$ is more negative (–4).

Let’s determine how far we can increase $x_2$:

From constraint 1:

From constraint 2:

🔎 Tightest bound: $x_2=320$

So let’s set:

• $x_2=320$
• $x_1=0$
• Then:
  • $x_3=1700-4(320)=420$
  • $x_4=1600-5(320)=0$

New basic variables: $x_2,x_3$
New non-basic variables: $x_1=0,x_4=0$

New function value:

🧠 Now express $f-(-1280)$ by removing $x_2$

We solve constraint 2 for $x_2$, since $x_2$ just entered the basis via constraint 2.

From:

Now substitute into $f=-2x_1-4x_2$:

Distribute:

Combine like terms:

✅ After Step 1:

This means:

• Increasing $x_1$ can still decrease $f$ (good),
• But we must check feasibility.

🔹 Step 2: Try to bring $x_1$ into the basis

We now ask: how much can $x_1$ increase while keeping everything feasible?

Use updated values ($x_2=320$):

From constraint 1:

From constraint 2:

🔒 $x_1$ is blocked — can't increase without violating $x_4\ge 0$

So we’re at an optimal solution.

✅ Final Result

Optimal solution:

• $x_1=0$
• $x_2=320$
• $x_3=420$
• $x_4=0$

Minimum value of the objective:

Objective expressed in non-basic variables: