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

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 satisfiable system of linear inequalities

a11x1+···+a1nxnb1:am1x1+···+amnxnbm

we describe the inequality as forced-equal if it is satisfied with equality by every solution x = (x1,...,xn)of the system. Equivalently,Piajixibj is not forced-equal if there exists an x that satisfies the whole system and such that Piajixibj.

For example, in

x1+x22-x1-x2-2x11-x20

Consider the following network (the numbers are edge capacities).

(a)Find the maximum flow fand a minimum cut.

(b)Draw the residual graphGf (along with its edge capacities). In this residual network, mark the vertices reachable fromS and the vertices from whichT is reachable.

(c)An edge of a network is called a bottleneck edge if increasing its capacity results in an increase in the maximum flow. List all bottleneck edges in the above network.

(d)Give a very simple example (containing at most four nodes) of a network which has no bottleneck edges.

(e)Give an efficient algorithm to identify all bottleneck edges in a network.

Consider the following generalization of the maximum flow problem.

You are given a directed network G=(V,E)with edge capacities {ce}. Instead of a single (s,t)pair, you are given multiple pairs (s1,t1),(s2,t2),,(sk,tk), where the siare sources of Gand tithe are sinks of G. You are also given kdemands d1,,dk. The goal is to find kflows f(1),,f(k)with the following properties:

  • f(i)is a valid flow fromSi toti .
  • For each edge e, the total flowfe(1)+fe(2)++fe(k) does not exceed the capacityce .
  • The size of each flowf(i) is at least the demand di.
  • The size of the total flow (the sum of the flows) is as large as possible.

How would you solve this problem?

For the linear program

maxx12x3x1x212x2x31x1,x2,x30

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

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.

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