COMPSCI 170 Lecture Notes - Feasible Region, Profit Maximization
31 Oct 2013
School
Department
Course
Professor
Document Summary
We are planting peas and carrots and we want to know how much of each in order to obtain the greatest pro t. Here is the information we have: // 1. Here are the resulting constraints where x1 is peas and x2 is carrots: money: max{4x1 + 2x2} sunny land: 3x1 60 shady land: 3x2 75 water: 3x1 + 2x2 100 non-negative: x1, x2 0. There are uncountably in nite points that it could possibly be though! In a convex graph (such as this one), any two points in a region connected by a line is still in a region. Optimal point? vertex of a region (intersection of two constraints). Though not all intersections are still inside the feasible region! Idea: try every vertex! m constraints with 2 variables o(m2) vertices. m constraints with n variables (cid:0)m (cid:1) which is nite but still exponential. n. No proof exists but in practice it works in polynomial time.
