Problem 45500. Maximize the production in a plant within equipment capacity

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The goal of a certain manufacturing company is to maximize its production of goods per day. In the production flow, there is a single source of raw materials, denoted by</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point 1</w:t></w:r><w:r><w:t>, and a single point where all the finished goods are collected, denoted by</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point N</w:t></w:r><w:r><w:t>. Between them are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>(N-2)</w:t></w:r><w:r><w:t> other</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Points</w:t></w:r><w:r><w:t> where the materials are flowing.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The details of the production flow is given as a matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> of size [</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>K</w:t></w:r><w:r><w:t> x 3]. Each row in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> represents a piece of processing equipment between two</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Points</w:t></w:r><w:r><w:t>. The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>-th row in this matrix is read as follows: \"Goods are processed from</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>P</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>(i, 1)</w:t></w:r><w:r><w:t> to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>P</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>(i, 2)</w:t></w:r><w:r><w:t> through an equipment with a maximum capacity of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 3) goods per day.\"</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Although it is desired to produce as many goods as possible, we are limited by the capacity of each equipment in the production. Some equipment can process more goods than others. Given the maximum capacities of all the equipment, can you determine the maximum number of finished goods that can be produced per day?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that takes matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> as input. Output the required maximum number of goods that can be produced for a day such that none of the equipment capacities from</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point 1</w:t></w:r><w:r><w:t> to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Point N</w:t></w:r><w:r><w:t> are exceeded. You are ensured that:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>3 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> &lt;= 50 and 2 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>K</w:t></w:r><w:r><w:t> &lt;= 200</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>For all</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 1) &lt;</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 2).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>All</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N Points</w:t></w:r><w:r><w:t> are mentioned at least once in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>. Hence,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> can be inferred from</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>All elements of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> are integers, and 1 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 3) &lt;= 100.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>See sample test case:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> P = [1 2 10;\n 1 3 6 ;\n 2 3 15;\n 2 4 5 ;\n 3 4 10;\n 3 5 3 ; \n 4 5 8];\n>> max_production(P)\nans = \n 11]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This test case is illustrated in:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://drive.google.com/open?id=13yoze4dLKlK__NAkialQmvjtjcs66aDr\"><w:r><w:t>&lt;https://drive.google.com/open?id=13yoze4dLKlK__NAkialQmvjtjcs66aDr</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

The goal of a certain manufacturing company is to maximize its production of goods per day. In the production flow, there is a single source of raw materials, denoted by Point 1, and a single point where all the finished goods are collected, denoted by Point N. Between them are (N-2) other Points where the materials are flowing.The details of the production flow is given as a matrix P of size [ K x 3]. Each row in P represents a piece of processing equipment between two Points. The i-th row in this matrix is read as follows: "Goods are processed from Point P(i, 1) to Point P(i, 2) through an equipment with a maximum capacity of P( i, 3) goods per day."Although it is desired to produce as many goods as possible, we are limited by the capacity of each equipment in the production. Some equipment can process more goods than others. Given the maximum capacities of all the equipment, can you determine the maximum number of finished goods that can be produced per day?Write a function that takes matrix P as input. Output the required maximum number of goods that can be produced for a day such that none of the equipment capacities from Point 1 to Point N are exceeded. You are ensured that:<ul><li>3 &lt;= N &lt;= 50 and 2 &lt;= K &lt;= 200</li><li>For all i, P( i, 1) &lt; P( i, 2).</li><li>All N Points are mentioned at least once in P. Hence, N can be inferred from P.</li><li>All elements of P are integers, and 1 &lt;= P( i, 3) &lt;= 100.</li></ul>See sample test case:<pre class="language-matlab">&gt;&gt; P = [1 2 10;
 1 3 6 ;
 2 3 15;
 2 4 5 ;
 3 4 10;
 3 5 3 ; 
 4 5 8];
&gt;&gt; max_production(P)
ans = 
 11
</pre>This test case is illustrated in: <a href = "https://drive.google.com/open?id=13yoze4dLKlK__NAkialQmvjtjcs66aDr">https://drive.google.com/open?id=13yoze4dLKlK__NAkialQmvjtjcs66aDr</a>

Solve

Solution Stats

55 Solutions
7 Solvers

Last Solution submitted on Aug 05, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

William on 17 May 2020

I'm confused! Two successful solutions have been submitted, but I would swear that the test suite answers for problems 6 and 15 are incorrect. In problem 15, it is easy to see that there is no way to get a production rate higher than 43; yet the answer given is 44.

Karl Ezra Pilario on 28 May 2020

To clarify, here is a possible breakdown for Test Case 15: [34 goods can flow along path 1-2-10-11] + [2 goods can flow along path 1-3-4-8-11] + [8 goods can flow along path 1-3-7-9-11] = 34 + 2 + 8 = 44. Take note that we can flow 34 goods from Point 10 to Point 11.

Solution Comments

Solution 2290704

1 Comment

1 Comment

Karl Ezra Pilario on 28 May 2020

This solution can be improved if line 6 becomes: a(P(j,1),P(j,2)) = a(P(j,1),P(j,2)) + P(j,3); I'm sorry for the confusion. You see, there can be more than 1 path between two points.

Problem Recent Solvers7

Problem Tags

chemical engineering digraph max flow

Problem 45500. Maximize the production in a plant within equipment capacity

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author19

Problem Tags

Problem 45500. Maximize the production in a plant within equipment capacity

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author19

Problem Tags

Players