Optimization Problems in MS&E Course
"Explore various optimization problems in the field of Management Science and Engineering, including production scheduling, matrix rounding, and oil pipeline flow. Learn how to model these problems as min-cost flow problems for efficient solutions."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Problems using MCF/Max-flow 1.Production problem 2.MCF with non-matching supply/demand 3.Matrix rounding example 4.Probability of failure (modelling)
Production problem A small computer manufacturing company forecasts the demand over the next n months to be di, i = 1, 2, . . . , n. In any month it can produce r units, using regular production, at a cost of b dollars per unit. By using overtime, it can produce additional units at c dollars per unit, where c > b. The firm can store units from month to month at a cost of s dollars per unit per month. Formulate the problem of determining the production schedule that minimizes cost. Show how this problem can be solved as a min-cost flow problem.
Non-matching supply/demand Class question: What if the total demand is not zero? Eg. what if it is bigger than 0, i.e. the demand is smaller or bigger than the supply ? Formal question: Consider a variant of the min-cost flow problem where any excess supply can be discarded at no cost (free- disposal)? Or at the cost of L per unit? How can you model this case as the standard min-cost flow considered in class?
Matrix rounding example Given a matrix with noninteger entries, we would like to find another matrix with the same row and column sums but with integer entries. Find such a matrix in polynomial time, via a reduction to a max-flow problem. Assume that sums of rows and columns are integral. We are given an n n matrix A where each entry Aijis non-negative. Furthermore, the sum of each row or column of A is an integer. Goal: Find a rounding of A call it Bsuch that Bi,jis either floor of ceil of Ai,jsuch that its rows and columns have identical sums as that of A.
Steps Discussed : Can assume that each entry of A is between 0 and 1. Observe that the MCF graph shown on white board actually does the desired reduction.
Oil pipeline flow Consider the oil pipeline network in the figure above with the capacity of each pipeline and failure probability given in table. Find the most reliable path from A to B by modelling as min cost.
