Conference rusure::math

> If the LP is setup and executed on an individual, one-by-one basis all the 
> inexpensive materials will be used up from the start.

I'm not sure what you mean by this. 

In LP your objective is to minimize a linear combination of the costs
involved in your problem. The coefficients for resources used will be
positive, but the coeff's. for outputs from the process are negative - you
sell the product, you make money, so your cost is negative. So the cost
function generally looks like 

	c0*x0+c1*x1+...+cn*xn - Cp*Xp

Where cn is the unit cost of resource n and xn is the amount used (subject
to the *constraint* inequalities), and Cp is the return by selling each unit
of product, of which Xp can be made out of the resources used.

As has been suggested in several other contexts in this conference, the book
"Numerical Recipes" is a treasure trove of theory, advice, and codes for a 
wide variety of problems, including this one.

I agree with .1: this needs more clarification.  If you could describe an
actual example in detail, and tell us what you're trying to minimize (or
maximize), as well as examples of the constraints, that will help us suggest 
the expressions you need.  The grid will follow pretty much automatically from
there.

Looking forward to seeing more detail; I enjoy these problems.

    
    
    							Mark


							Mark

 Background : 

 Part of the steel and aluminum product making process is to melt
 (via electric, oxygen , or gas fired furnaces) scrap material in
 order to be formed into a final product. This process is termed
 melting. The product is a tub of molten metal. These are termed 
 'heats' or  'melts'. The defined characteristic is the physical 
 chemistry of the molten metal. The scrap going into
 the melt has a chemistry defining it as well as a price per lb.
 The product specification is that for the required elements,  the
 element perecentages fall within a range ( e.g. Carbon be greater
 than .05 % and less than .10 % of liquid tonnage).
 

 A linear program is used to derive the least cost mix of materials
 to make a specific tonnage of molten material. The attached describes 
 the LP setup to make a tub of this molten material. This example has one 
 element ; usually ten elements are involved.

 
 The problem I am trying to resolve is how to set up a LP matrix for
 a schedule of 'heats' of varying product specifications. For example,
 in February make 10 heats ( 5 of specification A and 5 of specification B).
 If I 'ran' 10 LP calculations in serial sequence all the inexpensive 
 material would be used up first. A 'global' LP matrix will solve 
 for all.

 Any questions call Peter Moulder DTN 422-7818.

 

======================================================================
\
\  BLEND PROBLEM =  MINIMIZE COST OF AVAILABLE MATERIALS TO 
\                   ATTAIN PRODUCT OF CERTAIN QUALITY FORMULA
\                   WITHIN CERTAIN CAPACITY
\

MINIMIZE                / OBJECTIVE FUNCTION

     P_MTRLA *  A_MTRL1 +  
     P_MTRL2 *  A_MTRL2 +
     P_MTRL3 *  A_MTRL3  / PRICE OF EACH MATERIAL * AMOUNT OF EACH MATERIAL

ST                       / CONSTRAINTS

AMOUNT: A_MTRL1 + A_MTRL2 + A_MTRL3  + A_HEEL <=  140000  / CAPACITY

C1  : 

\ LOWER ALLOWABLE PERCENTAGE OF EACH ELEMENT * CAPACITY  (MIN) LESS THAN SUM
\ OF PERCENTAGES OF ELEMENT IN EACH MATERIAL ACCOUNTING FOR ELEMENT RECOVERY 

          MIN  < SI_%_MTRL1 * A_MTRL1  * SI_R_MTRL1  +  
                 SI_%_MTRL2 * A_MTRL2  * SI_R_MTRL2  +  
                 SI_%_MTRL3 * A_MTRL3  * SI_R_MTRL3  +
                 SI_%_HEEL  * A_HEEL
       
C2  :
 
\ UPPER ALLOWABLE PERCENTAGE OF EACH ELEMENT * CAPACITY ( MAX) LESS THAN SUM 
\ OF PERCANTAGES OF ELEMENT IN EACH MATERIAL  ACCOUNTING FOR ELEMENT RECOVERY


          MAX  > SI_%_MTRL1 * A_MTRL1  * SI_R_MTRL1  +  
                 SI_%_MTRL2 * A_MTRL2  * SI_R_MTRL2  +  
                 SI_%_MTRL3 * A_MTRL3  * SI_R_MTRL3  +
                 SI_%_HEEL  * A_HEEL

C3 :

\ SPECIFIC VOLUME : ALL MATERIAL WILL FIT INTO FURNACE

          S_V_FRN - S_V_HEEL =>  S_V_MTRL1 + S_V_MTRL2 + S_V_MTRL3

BOUND


A_MTRL1 < 50000         \ AMOUNT OF MATERIAL 1 AVAILABLE
A_MTRL2 = 1000          \ PRESPECIFY AMOUNT OF MATERIAL 2
A_MTRL3 < 70000         \ AMOUNT OF MATERIAL 3 AVAILABLE
A_HEEL   = 25000        \ ASSUME 



END

Let me see if I understand the problem. I think what you are saying in:

> The product specification is that for the required elements,  the
> element perecentages fall within a range ( e.g. Carbon be greater
> than .05 % and less than .10 % of liquid tonnage).

is that in your 10 runs for February, the cheap carbon is used at .10% for 
each case and that the supply would be exhausted before all the melts are
done. 

I think it will not suffice simply to add another constraint to the existing
matrices: amount of carbon available for each melt = total available / no.
of melts. This will have the effect of fixing the amount of carbon used for
each melt, but what you want is for maximum use of carbon to be associated
with the most costly other ingredients. 

This implies that you must include separate constraints for the use of 
carbon with each of the melts, as well as one constraint for the total 
available carbon. So you need variables for carbon used in melt 1, carbon 
used in melt 2, etc. each with the .05-.10 constraints, and a constraint
describing their sum to be <= the amount available. In fact, it appears that 
you need such a set of variables for each ingredient, for each melt. Then 
the cost function must include a term for each of these variables, and you 
will then get a minimization over all the melts.

sounds like you want minimize cost of x1+...+xn subject to constraints for
x1,...,xn and subject to the composition of the scrap.  
the matrix will consist of the matrices of the problems for
the various heats, along the diagonal of a big matrix.
then you take a different portion of the solution for each heat.

it is likely that new scrap arrives between the first and last heats.
in that case set up the problem again.

how can the composition of the scrap be known accurately enough?

This is similar to the nutrition problem, which is described in a number
of LP texts.  The trick is to think of two subscripts: one for the heat,
and one for the component.

Let:
	. C(i) = unit cost of ingredient (carbon, tungsten, etc.) 'i'
	. A(i, j) = the amount of ingredient 'i' used in heat 'j'
	. H = total number of heats
	. I = total number of ingredients
	. S(j) = size (weight, volume, or whatever) of heat 'j'

Then the objective function is;
	
		 H       I
		----	----
		\	\
	minimize/	/	C(i) * A(i, j)
		----	----
		j=1	i=1


	The actual order of the sigmas doesn't matter, as will become
	clear when you expand this expression.

Constraints are:

	1. A(i, j) <= m(i, j) * S(j)  
	   A(i, j) >= n(i, j) * S(j)

		Where 'm' and 'n' are the minimum and maximum portions
		(fractions, percentages, etc.) of ingredient 'i' allowed
		in heat 'j'.  There will be i * j pairs of these constraints,
		assuming no ingredient can vary with complete freedom.

	2. A(1, j) + A(2, j) + ...A(I, j) = S(j)

		Reflecting that the sum of all the ingredients should
		equal the heat size.  It's often better to use inequality,
		so you may want to assign a tolerance to the size of the
		heat, e.g. + or - x%.  Then (2) becomes:

			A(1, j) + A(2, j) + ...A(I, j) <= S(j) * (100 + s)

			A(1, j) + A(2, j) + ...A(I, j) >= S(j) * (100 - s)

	        There will be 'H' pairs of these constraints.

I think these should cover it.


						Mark

.6 assumed that the size of each heat is predetermined, and that the goal is
to find an ingredient mixture for each heat while keeping the total cost (for
all heats) to a minimum.

Another version of the problem is: find a way to get the greatest output (total
volume, weight, or whatever) of the set of heats while not exceeding some 
fixed cost.

Let C(total) be the maximum total amount you can spend.

The objective function is then:
	
		 H       I
		----	----
		\	\
      maximize 	/	/     A(i, j)
		----	----
		j=1	i=1


Constraints are:

	1. A(i, j) <= m(i, j) * [A(1, j) + A(2, j) + ... + A(I, H)]
	   A(i, j) >= n(i, j) * [A(1, j) + A(2, j) + ... + A(I, H)]


    	   Ensures that percentage of each ingredient is within 
	   proper range.  (S(j) can no longer be used in this version).
	   As before, there will be 'H' pairs of these constraints.

		 H       I
		----	----
		\	\
        2.      /	/     A(i, j) * C(i) <= C(total)
		----	----
		j=1	i=1


	   Simply constrains you from not spending more than the total.