Linear Programming Problems Solutions Class 12

[Channing Arther]

WhenI look at optimization problems I see a lot of options. One is linear programming. I understand in abstract terms how LP works, but I find it difficult to see whether a particular problem is suitable for LP or not. Are there any heuristics that can help guide this decision?

For example, the work described in Is there a good way to do this type of mining? took weeks before I saw how to structure the problem correctly. Is it possible to know "in advance" that problem could be solved by LP, without first seeing "how to phrase it"?

Commonly encountered LP's include: Resource allocation.: (Assignment, Transportation, Trans-shipment, knapsack) ,Portfolio Allocation, Job Scheduling, and network flow problems.Here's a good list of LP Applications for anyone new to LPs or IPs.That said, there are literally 1000s of different types of problems that can be formulated as LP/IP. The people I've worked with (researchers, colleagues) develop an intuition. They are good at recognizing that a problem is a certain type of an Integer Program, even if they don't remember the details, which they can then look up.

The following has always steered me in the right direction. I typically start by listing the Decision Variables, Constraints, and the Objective Function. I then usually iterate among these three to make sure that everything "fits."

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this problem near the end, but I'm interested in knowing if there is a proper and efficient algorithm or method for solving this kind of problem.

This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, An Algorithmic Theory of Lattice Points in Polyhedra, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)

Land and Doig (1960) proposed a method for solving discrete programming problems. You may be able to modify his algorithm so that instead of solving an optimization problem you are enumerating every possible feasible integer solution.

Optimization of resources (cost and time) is required in every aspect of our lives. We need the optimization because we have limited time and cost resources, and we need to take the maximum out of them. Every aspect of the business world today requires optimization, from manufacturing to resolving supply chain issues to stay competitive.

Linear programming offers the easiest way to do optimization as it simplifies the constraints and helps to reach a viable solution to a complex problem. In this article, we will solve some of the linear programming problems through the graphing method.

A transport company has two types of trucks, Type A and Type B. Type A has a refrigerated capacity of and a non-refrigerated capacity of . In contrast, Type B has the same overall volume with equal refrigerated and non-refrigerated stock sections. A grocer must hire trucks to transport of refrigerated stock and of non-refrigerated stock. The cost per kilometre of Type A is , and for Type B. How many trucks of each type should the grocer rent to achieve the minimum total cost?

A school is preparing a trip for 400 students. The transportation company has 10 buses of 50 seats each and 8 buses of 40 seats but only has 9 drivers available. The rental cost for a large bus is and for a small bus. Calculate how many buses of each type should be used for the trip for the least possible cost.

A store wants to liquidate 200 shirts and 100 pairs of pants from last season. They have decided to put together two offers, A and B. Offer A is a package of one shirt and a couple of pants which will sell for . Offer B is a package of three shirts and a pair of pants, which will sell for . The store does not want to sell less than 20 packages of Offer A and less than 10 of Offer B. How many boxes do they have to deal with to maximize the money generated from the promotion?

A school is preparing a trip for 400 students. The company who is providing the transportation has 10 buses of 50 seats each and 8 buses of 40 seats, but only has 9 drivers available. The rental cost for a large bus is and for a small bus. Calculate how many buses of each type should be used for the trip for the least possible cost.

A store wants to liquidate 200 shirts and 100 pairs of pants from last season. They have decided to put together two offers, A and B. Offer A is a package of one shirt and a pair of pants which will sell for . Offer B is a package of three shirts and a pair of pants, which will sell for . The store does not want to sell less than 20 packages of Offer A and less than 10 of Offer B. How many packages of each do they have to deal to maximize the money generated from the promotion?

I very much appreciate the exercises and solutions however, it seems that the answer to the third exercise has an issue. A couple of jeans refers to two pairs not one so the equation x + y = 100 is supposed to be 2x+ y = 100. Perhaps there was an issue with the wording because I just realized it is a pair in the solution but a couple in the question

An agricultural Research institute suggested to a farmer to spread out at least 4800kg of a special phosphate fertilizer and not less than 7200kg of a special nitrogen fertilizer to raise productivity of crops in his fields. There are two sources for obtaining these: Mixture A and B, both of these are available in bags weighting 100 kg each and they cost sh 40 and sh24 respectively. Mixture A contains phosphate and nitrogen equivalent of 20 kg and 80 kg respectively, while mixture B contains these ingredients equivalent of 50 kg each.

Required: Write this as a linear programming problem and determine how many bags of each type the farmer should buy in order to obtain the required fertilizer at a minimum cost

Please help to do under this question

A company produces two types of TVs, one of which is black and white, the

other colour. The company has the resources to make at most 200 sets a week. Creating a black

and white set includes Birr 2700 and Birr 3600 to create a colored set. The business should

spend no more than Birr 648,000 a week producing TV sets. If it benefits from Birr 525 per set

of black and white and Birr 675 per set of colours.

Construct the linear programing model.

How many sets of black/white and colored sets it should produce in order to get

maximum profit using

Graphical Method and Simplex Method

A company manufacture two types of product A1 and A2. Each product using milling and drilling machine. The process time per unit of A1 on the milling is 10 hours and the drilling is 8 hours, the process time per unit of A2 on the milling is 15 minute and on the drilling is 10 hours, the maximum number of hours available per week on the drilling and milling machine are 80 hours and 60 hours respectively also the profit per selling of A1 and A2 are 25 naira and 35 naira respectively. Formulate a LP model to determine the production volume of each of the product such that the total profit is maximized

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help from him either,Any help will be appreciated.Thank you

The other classics besides Winston are Hillier and Lieberman's Introduction to Operations Research and Chvtal's Linear Programmming. I learned linear programming out of Bob Vanderbei's Linear Programming: Foundations and Extensions, which is also a fine book. The last time I taught linear programming I used Dave Rader's new book, Deterministic Operations Research, and was happy with it.

As for a comparison, Winston focuses on how the different methods work and gives lots of examples but doesn't spend much time on theory. Hillier and Lieberman is at a slightly higher level than Winston, with a more leisurely pace and a little more theory but with fewer examples. Chvtal and Vanderbei have a more noticeable focus on the theory. Rader takes a different approach in that the simplex method does not appear until about halfway through the book. Instead, he spends a lot of time early on algorithm design and on what an algorithm for solving linear programs might look like so that when you finally do see the simplex method the reaction is closer to "Of course" than to "Where in the world did that come from?" He doesn't do the tableau form of the simplex method, which, while a plus in my opinion, may make it hard to understand his version of the simplex method if you're used to the tableau.

Many LP books spend little time on how to construct linear programming models (i.e, how to come up with variables, an objective function, and constraints that describe the problem you're trying to solve). Of these five, Winston and Rader discuss construction of LP models the most.

This is more a books of application ( with proofs ) full of algorithms using linear and integer programming, duality, also unimodularity, Chvatal-Gomory cuts and solving TSP with various methods. Both books are complementary ;) I recommend starting with first one and read few chapters of Combinatorial Optimization to get another look at things.

3a8082e126