Normal form Example

Let us look at a power station.

To generate electricity the station can use heating oil, coal or heavy fuel oil.

The calorific values and the costs are $($per unit of quantity$)$

heavy fuel oil

heating oil

coal

$24$ kilojoule

$28$ kilojoule

$16$ kilojoule

$30$

$40$

$24$

Each month, at least $48,000$ kilojoule should be generated. In addition, $800$ units of quantity

must be used.

What energy$-$mix leads to minimal costs?

Decision variables

$x_1$:$=$ units of quantity of heavy fuel oil used each month

$x_2$:$=$ units of quantity of heating oil used each month

$x_3$:$=$ units of quantity of coal used each month

Objective function

We have to minimize monthly costs $=>G(x_1,x_2,x_3)$:$=30x_1+40x_2+24x_3=$Min $!$

Constraints

$(1)24x_1+28x_2+16x_{3}48,000$

$(2)x_1+x_2+x_{3}800$

Sign restrictions $x_1,x_2,x_{3}0$

To solve the minimization problem we transfer it into the normal form of a

maximization problem

by multiplying the objective function by $(-1)$ and

by multiplying both constraints by $(-1)$

$=>,-G(x_1,x_2,x_3)=-30x_1-40x_2-24x_3=$ Max!

$-24x_1-28x_2-16x_3-48,000$

$-x_1-x_2-x_3-800$

With $,A=([-24,-28,-16],[-1,-1,-1]),$vec$(x)=([x1],[x2],[x3]),$vec$(c{)}^T=(-30,-40,-24),$vec$(b)=(\frac{-48,000}{-800})$

we get vec$(c{)}^{TT}*vec(x)=$ Max! with $A*vec(x)$vec$(b)$ and vec$(x)$vec$(0)$

Corresponding LES

Introducing the slack variables $s_1,s_2,$ with $s_1,s_{2}0$ leads to the LES

$(1)-24x_1-28x_2-16x_3+s_1+0=-48,000$

$(2)-x_1-x_2-x_3+0+s_2=-800$

$(3)30x_1+40x_2+24x_3+0+0=z$

Basic feasible solution

Setting $x_1=0,x_2=0,x_3=0$ leads to $s_1=-48,000,s_2=-800$ and $z=0.$

This is a not basic feasible solution

$=>$ we use the phase I of the Simplex$-$Algorithm to reach the feasible region.

Simplex $-$ phase I

pivot row $r$ and pivot column $p$ : we choose $r=1$ and $p=1$

$(=>s_1$ becomes non$-$basic, $x_1$ becomes basic$)$

actual non$-$basic variables: $s_1,x_2,x_3$ this is a part of my lecture from mix constrains in simplex algorithm $,$ i dont undestand why my prof chose $-24$ rather than $-28?$also is there any rule on which negative value to choose in phase $1?$