There are 14 food ingredients available. They can be classified into seven groups. it is required to mix them into a minimum cost diet satisfying the following constraints:

(i) Protein content should be at least 20%;

(ii) fat content should be at least 3%;

(iii) fiber content should be at most 12%;

(iv) Ca content should be between 1% and 2%;

(v) Ph content should be between 0.6% and 2%;

(vi) Ca content should be greater than or equal to the Ph content. Data and other constraints are given below.

			Percent of Nutrient Content
Group		Food Ingredient	Protein	Fat	Fiber	Ca	Ph	Cost per Ton	Range of Ingredient (%)	Range of Group (%)
1	1	Dried beet pulp	9	0.5	20	0.7	0.05	64	4 to 20	5 to 20
	2	Dried citrus pulp	6	3	16	2	0.1	35	1 to 20
2	3	Ground yellow corn	8.5	4	2.5	0.02	0.25	55	1 to 25	20 to 35
	4	Ground oats	12	4.5	12	0.1	0.4	54	1 to 25
3	5	Corn molasses	3.5			0.6	0.1	19	5 to 14	5 to 14
4	6	Wheat middling's	16	4	8	0.1	0.9	64	5 to 30	10 to 30
	7	Wheat bran	16	4	10.5	0.1	1.2	62	5 to 30
5	8	Distiller grains	26	8.5	9	0.15	0.6	77	5 to 15	2 to 25
	9	Corn gluten feed	24	2	8	0.3	0.65	66	1 to 25
6	10	Cottonseed meal	41	1.5	13	0.1	1.2	74	1 to 35	3 to 35
	11	Linseed oil meal	34	1	8	0.35	0.8	85	1 to 35
	12	Soybean oil meal	45	0.5	6.5	0.2	0.6	108	1 to 35
7	13	Ground limestone				36	0.5	10	0 to 2
	14	Ground phosphate				32	14	66	1 to 2

Write a code in any language to solve the following LP problem based on the following guidelines using simplex method:

1.If your LP model is not in the standard form, you can just manually convert them into the standard form before inputting to computers. For larger problems, however, you may need to design a routine to do the conversion in your code.

2. Your code needs to be able to detect if the LP at hand is feasible or not.

3. (Regardless if your problem matrix has redundancy or not) Your code needs to be able to detect if the coefficient matrix associated with the standard form of the LP has full row rank; and if not, how to remove the redundant constraints. (Note just checking if the coefficient matrix has full rank or not, such as using the MATLAB function “rref”, is not sufficient. Your code needs to be able to reduce redundant constraints regardless if the specific LP problem you chose has redundant constraints or not.)

4. How to start the simplex method if an initial basis is not readily available. (Your code needs to check if a basic feasible solution (BFS) with the identity matrix as the corresponding basis is readily available. If yes, you can just go ahead to use the BFS to start your simplex method; otherwise, it is strongly recommended for you to use the methods we learned in class to start your simplex with an identity matrix as the initial basis.

5. Your code needs to implement one rule to prevent the simplex method from cycling.

6. Termination: your code needs to be able to handle both cases at termination – a finite optimal solution or unbounded (since you don’t know before hand if the LP at hand has an optimal solution or is unbounded).