# Homework Help: Standard form of linear program

1. Jul 20, 2014

### Maylis

1. The problem statement, all variables and given/known data
To preface, I believe this question is equally applicable to either the math or engineering homework forum, but I am having more trouble with the math part than the actual programming. I can't do any programming (with the understanding that linear programming doesn't necessarily imply coding) until I have the math down.

In a first quiz you formulated a linear program with the goal of determining the cheapest meal consisting of four kinds of food that meets two nutritional requirements. We formulated this problem as shown below

$\underset{a \in \mathbb{R}^m} \min \hspace{0.05 in} p^Ta$

\begin{align*} \text{subject to} \hspace{0.1in} &Va \geq r \\ &a \geq 0 \end{align*}

where

$a$ is a column vector of the amount of each food,
$p$ is a column vector of the price if each food,
$V$ is an array of the nutritional contents of each food, and
$r$ is a column vector of the nutritional requirements.

Reformulate this problem into the standard for linear programs as shown below.

$\underset{c \in \mathbb{R}^m} \min \hspace{0.05 in} c^Tx$

\begin{align*} \text{subject to} \hspace{0.05in} &Ax \leq b \end{align*}

part 1
What will $c$ be in terms of $p$, $V$, and $r$?

part 2
What will $A$ be in terms of $p$, $V$, and $r$??

part 3
What will $b$ be in terms of $p$, $V$, and $r$??

2. Relevant equations

3. The attempt at a solution
part 1
well, it looks like just replace $c$ with $p$, simple enough.

part 2
I am trying to parse this question. I know that if I use the identity matrix times any vector, it will return the vector. So to get in the standard form, I have

$\begin{bmatrix} -V \\ -I_{m} \end{bmatrix} a \leq \begin{bmatrix} -r \\ 0 \end{bmatrix}$

Well, the options have the identiy matrix with either eye(4) or eye(2). I don't know what to choose as the dimensions of the identity matrix. It seems like you are putting a matrix inside a matrix by choosing an element of the matrix A to be a matrix itself, no?

Edit: I have discovered that the reason for the identity matrix is that it imposes even more constaints. When I set the second element of b to be zeros(n,1) and eye(n), then That will force my elements $x_{1}, x_{2},...,x_{n}$ to have a constraint that their value is greater than or equal to zero. Clearly, since the application of this problem is related to food and optimizing the calories and protein while spending the least amount of money, the amount of any particular food will have to be greater than or equal to zero.

The only thing that now troubles me is the fact that nowhere does the column vector $p$ show up in the matrix equation of the form $Ax \leq b$. How is it that I can minimize $p$ without using its affine function in my matrix? My best guess is that the matrix equation is only the constraints. $p$ is not a constraint, but is the ''object'' that we which to minimize. So how do I relate the two? Just writing ''subject to'' is not enough for me. Where is the relation between $p$ and the matrix equation?

Last edited: Jul 20, 2014