/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q5E The Canine Products company offe... [FREE SOLUTION] | 91Ó°ÊÓ

91Ó°ÊÓ

The Canine Products company offers two dog foods, Frisky Pup and Husky Hound, that are made from a blend of cereal and meat. A package of Frisky Pup requires 1 pound of cereal and 1.5pounds of meat, and sells for \(7. A package of Husky Hound uses 2 pounds of cereal and 1 pound of meat, and sells for \)6. Raw cereal costs\(1per pound and raw meat costs\)2per pound. It also costslocalid="1658981348093" \(1.40to package the Frisky Pup and localid="1658981352345" \)0.60to package the Husky Hound. A total of localid="1658981356694" 240,000pounds of cereal and pounds of meat are available each month. The only production bottleneck is that the factory can only package 110,000bags of Frisky Pup per month. Needless to say, management would like to maximize profit.

(a) Formulate the problem as a linear program in two variables.

(b) Graph the feasible region, give the coordinates of every vertex, and circle the vertex maximizing profit. What is the maximum profit possible?

Short Answer

Expert verified

a)The problem as a linear program in two variables is given below.

b). The graph from above constraints is showing below of feasible region, give the coordinates of every vertex, and circle the vertex maximizing profit.

Step by step solution

01

Defining Maximum Profit

Let the packageproducebyFriskyPuppermonth=F.The package contains 1 pound of cereal and cost 1$/poundand 1.5 pound of meat and cost 2$/pound.

So,we will achieve maximum profit if we have:1.6F+1.4H

Here,

On solving above conditions in the question, maximum profit is:22.2×104

So total production cost include cost of production of cereal and meat and package cost(1.40$). This givelocalid="1658924309919" totalcostofproductionofapackage=1+2×1.5+1.40=5.4$..

Hence,localid="1658924239764" profitobtaininsellingapackage=Sellingprice-Costofproduction.

Profit=7-5.4=1.6$

So,maximumprofitofF=1.6F

Let thepackageproducebyHuskyHoundpermonth=H.The package contain 2 pound of cereal and cost 1$/poundand 1 pound of meat and costlocalid="1658981373747" 2$/pound.So total production cost include cost of production of cereal and meat and package cost (0.6$).This give localid="1658981380385" totalcostofproductionofapackage=2×1+2+0.6=4.6$.Hence, profitobtaininsellingapackage=Sellingprice-Costofproduction.1.6F+1.4H.

Profit=6-4.6=1.4$

So, max profitofH=1.4H

Therefore, max profitlocalid="1658923761946" =1.6F+1.4H

This is our optimal goal to achieve.

02

Define constraints

Total cereal available in a month F+2H≤240000pounds. Also, Frisky Pup and Husky Hound contain 1 pound and 2 pound cereal respectively.

So, the constraint is: F+2H≤240000

Total meat available in a monthH≤180000pounds. Also, Frisky Pup and Husky Hound contain 1.5 pound and 1 pound meat respectively. So,

the constraint is: H≤180000.

Frisky Pug can produce at the most localid="1658982614215" F≤110000package.

This can be expressed as:F≤110000 .

And the package quantity can never be negative.

Thus, our required linear program is:

Maximum:1.6H+1.4H

Constraints

[1]F+2H≤240000[2]1.5F+H≤180000[3]F≤110000[4]F≥0[5]H≥0

03

The graph is given as:

The graph from above constraints is:

In this graph,"denote power of 4 .

From the graph, it is clear that we will obtain maximum profit from

(F,H)=(6×104,9×104)

So, our maximum profit will be:

1.6F+1.4H=1.6×6×104+1.4×9×104=22.2×104

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 91Ó°ÊÓ!

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

Find necessary and sufficient conditions on the reals a and b under which the linear program

max x+yax+by≤1x,y≥0

(a) Is infeasible.

(b) Is unbounded.

(c) Has a unique optimal solution.

There are many common variations of the maximum flow problem. Here are four of them.

(a) There are many sources and many sinks, and we wish to maximize the total flow from all sources to all sinks.

(b) Each vertex also has a capacity on the maximum flow that can enter it.

(c) Each edge has not only a capacity, but also a lower bound on the flow it must carry.

(d) The outgoing flow from each node u is not the same as the incoming flow, but is smaller by a factor of (1-∈U), whererole="math" localid="1659789093525" ∈u is a loss coefficient associated with node u.

Each of these can be solved efficiently. Show this by reducing (a) and (b) to the original max-flow problem, and reducing (c) and (d) to linear programming.

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.

Question: Consider the following simple network with edge capacities as shown.

a) Show that, if the Ford-Fulkerson algorithm is run on this graph, a careless choice of updates might cause it to take 1000iterations. Imagine if the capacities were a million instead of 1000.

We will now find a strategy for choosing paths under which the algorithm is guaranteed to terminate in a reasonable number of iterations.

Consider an arbitrary directed network (G=V,E,s,t,ce)in which we want to find the maximum flow.Assume for simplicity that all edge capacities are at least 1, and define the capacity of an s - t path to be the smallest capacity of its constituent edges. The fattest path from s to t is the path with the most capacity.

b) Show that the fattest s - t path in a graph can be computed by a variant of Dijkstra’s algorithm.

c) Show that the maximum flow in Gis the sum of individual flows along at most|E|paths from s to t.

d) Now show that if we always increase flow along the fattest path in the residual graph, then the Ford-Fulkerson algorithm will terminate in at mostO(ElogF) iterations, where F is the size of the maximum flow. (Hint: It might help to recall the proof for the greedy set cover algorithm in Section 5.4.)

In fact, an even simpler rule—finding a path in the residual graph using breadth-first search— guarantees that atO(V.E)most iterations will be needed.

Matching pennies. In this simple two-player game, the players (call them Rand C) each choose an outcome, heads or tails. If both outcomes are equal, Cgives a dollar to R; if the outcomes are different, Rgives a dollar to C.

(a) Represent the payoffs by a2×2 matrix.

(b) What is the value of this game, and what are the optimal strategies for the two players?

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.