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.

Short Answer

Expert verified

The aim of a linear programming is to optimize the operations according to the constraints. In our question, we need to optimize the revenue.

Step by step solution

01

Defining the variables of constraints

Let the first material given be: x1 and corresponding revenue=1000$/m3. So total revenue for x1will be=1000x1.

Let the second material given be: x2 and corresponding revenue=1200$/m3. So total revenue for x2will be=1200x2.

Let the third material given be: x3 and corresponding revenue=12000$/m3. So total revenue for x3will be=12000x3.

Now in the question, we have given ‘A cargo plane can carry a maximum weight of 100 tons’. So the constraint according it can be represented as:

2x1+x2+3x3100.

Also it is mention that, ‘: A cargo plane can carry and a maximum volume of 60 cubic meters’. This can be represented as:

x1+x2+x360.

02

Linear Programming

According to the given constraints, we have to maximize(optimize) our revenue:

Maximun:1000x1+1200x2+12000x32x1+x2+3x3100x140x230x320x1,x2,x30

This is our required linear program.

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

In a particular network G = (V, E) whose edges have integer capacities ce, we have already found the maximum flow f from node to node t. However, we now find out that one of the capacity values we used was wrong: for edge (u, v) we used cuv whereas it should have been cuv. -1 This is unfortunate because the flow f uses that particular edge at full capacity: f = c.

We could redo the flow computation from scratch, but there’s a faster way. Show how a new optimal flow can be computed inO(|V|+|E|) time.

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.

You are given the following points in the plane:

(1,3),(2,5),(3,7),(5,11),(7,14),(8,15),(10,19)

.You want to find a lineax+by=c that approximately passes through these points (no line is a perfect fit). Write a linear program (you don’t need to solve it) to find the line that minimizes the maximum absolute error,max1i7|axi+byic|

For the linear program

maxx12x3x1x212x2x31x1,x2,x30

Prove that the solution(x1,x2,x3)=(3/2,1/2,0) is optimal

Show that the change-making problem (Exercise) can be formulated as an integer linear program. Can we solve this program as an LP, in the certainty that the solution will turn out to be integral (as in the case of bipartite matching)? Either prove it or give a counterexample.

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