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

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:

  • 3 <= N <= 50 and 2 <= K <= 200
  • For all i, P( i, 1) < P( i, 2).
  • All N Points are mentioned at least once in P. Hence, N can be inferred from P.
  • All elements of P are integers, and 1 <= P( i, 3) <= 100.

See sample test case:

>> P = [1 2 10;
        1 3 6 ;
        2 3 15;
        2 4 5 ;
        3 4 10;
        3 5 3 ; 
        4 5 8];
>> max_production(P)
ans = 

This test case is illustrated in:

Solution Stats

11.11% Correct | 88.89% Incorrect
Last Solution submitted on Jun 28, 2020

Problem Comments

Solution Comments