22 Consider the following puzzle. You are to pick out 4 three-letter \"words\" f

Question

22 Consider the following puzzle. You are to pick out 4 three-letter "words" from the following list: DBA DEG ADI FFD GHI BCD FDF BAI For each word, you earn a score equal to the position that the word's third letter appears in the alphabet. For example, DBA earns a score of 1, DEG earns a score of 7, and so on. Your goal is to choose the four words that maximize your total score, subject to the following constraint: The sum of the positions in the alphabet for the first letter of each word chosen must be at least as large as the sum of the positions in the alphabet for the second letter of each word chosen. Fonnulate an IP to solve this problem.

Explanation / Answer

It is a problem of integer programming:

Let U= {DBA, DEG, ADI, FFD, GHI, BCD, FDF, BAI}

Assume a variable ai for every i belong to U

ai = 1 if word I is chosen

      = 0 otherwise

Let bij be the position of the alphabet of the jth letter of word I for all j belongs to {1,2,3} and for all I belongs to U. In this case linear programming equation will be

Maximize: sigma (bi3 ai) where I belong to U

Such that ( or constraint)

Sigma (bi2 ai) <= Sigma (bi1 ai) where I belong to U

Ai belongs to (0,1)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.