Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Moe is deciding how much Regular Duff beer and how much Duff Strong beer to order each week. Regular Duff costs Moe \(1 per pint and he sells it at \)2 per pint; Duff Strong costs Moe $1.50 per pint and he sells it at per pint. However, as part of a complicated marketing scam, the Duff company will only sell a pint of Duff Strong for each two pints or more of Regular Duff that Moe buys. Furthermore, due to past events that are better left untold, Duff will not sell Moe more than 3,000 pints per week. Moe knows that he can sell however much beer he has. Formulate a linear program for deciding how much Regular Duff and how much Duff Strong to buy, so as to maximize Moe’s profit. Solve the program geometrically.

Short Answer

Expert verified

In this, we will first define the constraints variables then define constraints mathematically, and then solve it graphically.

Step by step solution

01

Defining constraint variable

Let Moe order ‘R ’ regular duff beer per week.

It is given that Cost Price of Beer per Pint is=1$ and Selling Price of Beer per Pint is=2$

So profit obtain in regular duff beer per pints=2$-1$=1$

Let Moe order ‘’ Strong duff beer per week.

It is given that Cost Price of Beer per Pint is=1.5$ and Selling Price of Beer per Pint is=3$

So profit obtain in regular duff beer per pints=3$-1.5$=1.5$ .

This means that Moe earns profit by selling regular and strong duff beer=R+1.5S

02

Defining Constraints

It is said that, ‘Duff company will only sell a pint of Duff Strong for each two pints or more of Regular Duff that Moe buys’. This can be represented as: R2S.

Also, ‘Duff will not sell Moe more than 3,000 pints per week’. This can be express as:.

R+S3000.

As we know that quantity can never be negative. So R,S0.

So, our objective is to maximize the profit i.e.,

MaximizeR+1.5S.

Constraints:R2S

role="math" localid="1657275042140" R+S3000R,S0

03

Graph of Constraints

Constraints:

1R+S30002R2S3R,S0

From graph we can clearly see by interaction of constraints [1] and [2] at point R,S=1000,2000we will get our MAX revenue.

On, putting value of R,Sinrole="math" localid="1657275260361" R+1.55, we have:

1000+1.5x2000=1000+3000=4000$

Thus our maximunrevenue=4000$.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

The dual of maximum flow. Consider the following network with edge capacities

(a) Write the problem of finding the maximum flow from StoTas a linear program.

(b) Write down the dual of this linear program. There should be a dual variable for each edge of the network and for each vertex other than S,T.

Now we’ll solve the same problem in full generality. Recall the linear program for a general maximum flow problem (Section 7.2).

(c) Write down the dual of this general flow LP, using a variableyefor each edge and xufor each vertexus,t.

(d) Show that any solution to the general dual LP must satisfy the following property: for any directed path from in the network, the sum of the yevalues along the path must be at least 1.

(e) What are the intuitive meanings of the dual variables? Show that anystcut in the network can be translated into a dual feasible solution whose cost is exactly the capacity of that cut.

Give an example of a linear program in two variables whose feasible region is infinite, but such that there is an optimum solution of bounded cost.

A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.

  • Material 1 has density 2tons/cubicmeters, maximum available amount 40 cubic meters, and revenue \(1,000 per cubic meter.
  • Material 2 has density 1ton/cubicmeters,maximum available amount 30 cubic meters, and revenue \)1,200 per cubic meter.
  • Material 3 has density 3tons/cubicmeters, maximum available amount 20 cubic meters, and revenue $12,000 per cubic meter.

Write a linear program that optimizes revenue within the constraints.

Direct bipartite matching. We’ve seen how to find a maximum matching in a bipartite graph via reduction to the maximum flow problem. We now develop a direct algorithm.

Let G=(V1V2,E)be a bipartite graph (so each edge has one endpoint in V1and one endpoint in V2), and letMEbe a matching in the graph (that is, a set of edges that don’t touch). A vertex is said to be covered byMif it is the endpoint of one of the edges in M. An alternating path is a path of odd length that starts and ends with a non-covered vertex, and whose edges alternate between Mand E-M.

(a) In the bipartite graph below, a matching Mis shown in bold. Find an alternating path.


(b) Prove that a matchingMis maximal if and only if there does not exist an alternating path with respect to it.

(c) Design an algorithm that finds an alternating path inO(|V|+|E|)time using a variant of breadth-first search.

(d) Give a directO(|V|-|E|)algorithm for finding a maximal matching in a bipartite graph.

Hall’s theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartite graph with boys on the left and an equal number of girls on the right. Hall’s theorem says that there is a perfect matching if and only if the following condition holds: any subset sof boys is connected to at least |s|girls.

Prove this theorem. (Hint: The max-flow min-cut theorem should be helpful.)

See all solutions

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free