Linear programming Definition and 101 Threads

Homework Statement Minimize |2x1-3x2| subject to x1+x2≤5 -x1+x2≥-1 x1≥0, x2≥0 (a) Solve the problem graphically. (b) Formulate a linear program that could be used to solve the problem. Use software to solve your LP and show how to reconstruct a solution to the original problem...

If a linear Program (P) has a feasible solution x_{o}, ( x_{o} not necessarily optimal),does it follow that there exists a feasible solution to the dual problem (D) as well? If yes, why? I know that the Strong Duality Theorem guarantees an optimal finite solution to the dual problem if the...

Homework Statement Let C be the set of all points (x,y) in the plane satisfying x≥0, y≥0, -x-2y≤-8. a. Show that C is nonempty and unbounded. b. Prove that the LP problem: Max M=2x+3y subject to the constraint that (x,y) lie in C has no feasible, optimal solution. c. Show that the LP...

Homework Statement The shaded area on graph represents the feasible region of a linear programmin problem whose objective function is to be maximized. Label each of the following statements as True or False, and then justify your answer based on the graphical method. In each case, give an...

Homework Statement I'm trying to learn the Branch and Bound method. For that, I need to master the Dual Simplex Method (DSA). I have tried and tried and tried to google examples but can't find any. Does anyone know where I can find any? How do you know the LPP has become infeasible with...

This semester while taking Linear Programming (Linear Optimization Models), we talked about using a linear program to separate two sets of points A and B. The general program is: Max d s.t. yA ≥ axA+b+d yB ≤ axB+b-d It can be expanded into finding a polynomial that passes between the...

Homework Statement I made this problem up as an example for a bigger problem I have to do. P = {(-2,4),(1,3)} and Q = {(-1,1),(0,0)}. I need to use linear programming to find the best line to go between them. Homework Equations Max d subject to: y_{i}≥ax_{i}+b+d (for all points above...

Homework Statement Blacktop refining extracts minerals from ore mined at two different sites in Montana. Each ton of ore type 1 contains 20% copper, 20% zinc, and 15% magnesium. Each ton of ore type 2 contains 30% copper, 25% zinc, and 10% magnesium. Ore type 1 costs 90$ per ton, while ore...

I am taking Linear Programming and I haven't completed the course yet, but here is my question. I've notice that all these problems could have been solved just as easily with Lagrange multipliers. We got a bunch of linear inequality constraints and an obj function, we can use Lagrange...

Homework Statement Choose the number \omega so that the following program has a solution. Then write down the optimal solution. \begin{bmatrix} -1 & 2 & 3 \\ 2 & 3 & 1 \\ -5 & -4 & 1 \end{bmatrix} x = \begin{bmatrix} 1 \\ 5 \\ \omega \end{bmatrix} min=x_2 x\geq 0 Homework...

Homework Statement Suppose we have a maximum LOP P max z = c^t x s.t. Ax \leq b x \geq 0 and the dual to P is min w = b^t y A^t y \geq c y \leq 0 Then the bounds are z = c^t x \leq y^t Ax \leq y^t b = b^t y = w question Okay where the heck did y^t Ax came...

Homework Statement A small cargo ship leaving Hawaii for London has three holds for cargo. The forward hold has a capacity of 140 tons, and volume of 6,000 cubic feet; the central hold has a capacity of 800 tons, and a volume of 15,000 cubic feet; the aft hold has a capacity of 450tons and...

Homework Statement Consider the following LOP P: Max z = 3x_1 + x_2 -\frac{1}{2}x_3 s.t. 2x_1 + x_2 + x_3 \leq 8 4x_1 + x_2 - x_3 \leq 10 x_1, x_2, x_3 \geq 0 1) Find a primal solution x and its objective value z = z(x) 2) What is the LOP D that is Dual to P? 3) Find a dual feasible...

Homework Statement Consider the following LOP K: Max z = 4x_1 + 3x_2 s.t 7x_1 + 6x_2 \leq 42 2x_1 - 3x_2 \geq -6 x_1 \geq 2, x_1 \leq 5, x_2 \geq \frac{1}{2} (a) Decide whether the solution sets are feasible i) x = (3.5, 2.5)^t ii) x = (2.1, 4)^t iii) x = (5,1/2)^t (b) Graph the...

Homework Statement . . . . (c) Find a feasible solution that is not basic. (d) Find a feasible solution that is not an extreme point: justify your answer by using the definition of extreme point. Homework Equations The Attempt at a Solution The whole question is not that...

Homework Statement Find the dual of -d \leq Ax-b \leq d x \geq 0; c \cdot x = min where A is mxn matrix and x,d,b \in \mathbb{R}^n Homework Equations dual of canonical is of the form maximize b \cdot y A^{T}y \leq where y \in \mathbb{R}^m The Attempt at a Solution I tried...

Homework Statement State the linear system Ax = b as a canonical minimum problem. What is the dual program? Homework Equations The canonical minimum problem is Ax = b, x\geq0, c\bulletx=min.The Attempt at a Solution I'm confused here, in part because there is no objective function...

Ok, so the title didn't allow me to be too descriptive. Basically, I'm trying to formulate a variant of the time constrained traveling salesman problem. I read a paper "An Exact Algorithm for the Time-Constrained Traveling Salesman Problem" by Edward Baker which formulated this problem of a...

Linear Programming "Possibility Restaurant" Homework Statement Angela Fox and Zooey Caulfield were food and nutrition majors at State University, as well as close friends and roommates. Upon graduation Angela and Zooey decided to open a French restaurant in Draperton, the small town where the...

Homework Statement Homework Statement Omega Manufacturing Company has excess manufacturing capacity and is considering devoting its excess capacity to product 1,2, and 3. The production process uses three types of machines and the available capacity on the machines is as follows: Milling...

Homework Statement Omega Manufacturing Company has excess manufacturing capacity and is considering devoting its excess capacity to product 1,2, and 3. The production process uses three types of machines and the available capacity on the machines is as follows: Milling Machine: 550...

I'm trying to minimize a function over a rather complicated surface. I'm using an algorithm that takes an initial guess, finds the tangent plane at that point, minimizes using a linear programming algorithm, then (tries to) project back onto the complicated surface. More specifically, if \xi...

Homework Statement I can do most the question, but just get stuck on the final question. Here is the whole question 1. Gordon Ltd makes 2 products, Tennis racquets and badminton racquets, each using the same materials and the same skilled labour. The costs of the products per unit...

I have absolutely no ides where to go from here, I am horrible at this, If you could help me I would appreciate it, I want help doing it, not just answers. Homework Statement You are the owner of a manufacturing plant. We've been hired by Apple to produce iPhone and iPods. Apples pays us $50...

Homework Statement A feasible dictionary whose last row reads z = z* + ∑ cjxjdescribes an optimal solution if and only if cj ≤ 0 for all j. Prove or disprove. Homework Equations The Attempt at a Solution It is clear that if all c's are ≤ 0, then the solution is optimal since increasing any of...

Homework Statement Sketch the area that fulfills : x + y ≥ 1 3y ≥ 2x - 1 2y ≤ 3x and find the range of x and y that are restricted. Find the maximum value of y – 2x that satisfies the area above and find also the value of xHomework Equations Line equationThe Attempt at a Solution I've drawn...

Homework Statement Under current legislation, a company involved in a noxious chemical industry has a permit to pass into the atmosphere a maximum of 1500 units of sulfur dioxide, and a maximum of 1200 units of carbon monoxide each day. A new plant just installed releases 150 units of sulfur...

Homework Statement AutoIgnite produces electronic ignition systems for automobiles at a plant in Cleveland, Ohio. Each ignition system is assembled from two components produced at AutoIgnite’s plants in Buffalo, New York, and Dayton, Ohio. The Buffalo plant can produce 2000 units of...

Homework Statement Eva, senior analyst, is determining the optimal investment policy for her reality company, 4-Closure Associative. She has a budget of $6 million for year 1 and $5 million for year 2, and each project can be undertaken as a fraction, up to 100%. Her investment...

The admissions office at State University wants to develop a planning model for next year's entering freshman class. The university has 4500 available openings for freshmen. Tuition is $8600 for a local student, and $19200 for an overseas student. The university wants to maximize the tuition...

A furniture manufacturer makes chairs and sofas. Each chair can be sold for a profit of £15 and each sofa for a profit of £5. It takes 4 hours to make the chair and 5 hours to make the sofa. The manufacturer has enough workers to provide 200 hours per week producing the furniture. Customer...

I see only one variable there. Could you help me with it? The answer involves several variables. How shall I solve it?

Hello, I'm studying operations research - linear programming maximization. minimization problems All tasks in my textbook seem to be very easy ( I've transportation, diet ... examples ) Please if anybody knows where I can find more complicated models where you'll need to think which...

Homework Statement Original question: The Cut-Right Company sells sets of kitchen knives. The Basic Set consists of 2 utility knives and 1 chef’s knife. The Regular Set consists of 2 utility knives, 1 chef’s knife, and 1 slicer. The Deluxe Set consists of 3 utility knives, 1 chef’s knife...

I've got this question to do: A bank is attempting to determine where its assets should be invested during the current year. At present $500 million is available for investment in bonds, home loans, car loans, and personal loans. The annual rate of return on each type of investment is known...

basically, let's say i have three linear equations, y1, y2, and y3. assume y1 = ax+b where a and b are constants assume y2 = mx+k where m and k are constants assume y3 = n where n is a constant also, now assume that they all intersect at y1=y1=y3=n. would the area between the...

I have been struggling with Part 3 of this question for some time: Computico Limited, currently operating in the UK, assembles electronic components at its two factories, located at Manchester and London, and sells these components to three major customers. Next month the customers, in units...

Linear Programming Theory, "Optimality Criterion" Question In a (theory oriented) linear programming class, I am studying the simplex method. The basic feasible solution represented by a tableau is said to be 'optimal' when it respects the Optimality Criterion: 'If the objective row of a...

Homework Statement Solve: http://www.rinconmatematico.com/latexrender/pictures/0399b7f0b179dcbf396e72f315e6d219.png Homework Equations The Attempt at a Solution http://www.rinconmatematico.com/latexrender/pictures/5a8e45f50b7d55e4c8ab2c5ce3b7d554.png...

what exactly is the point of the two phase method? I have in my notes that 'if you have a program (P) maximise xc_T x >= 0 , Ax<=b, but b not > 0, that we use the two phase method for to find a B.F.S to start the simplex algorithm. But then the notes go on to say that we use the method...

Please help: A manufacturer of biscuits is considering three types of gift packs containing three types of biscuits, Orange Cream (OC), Chocolate Cream(CC) and Wafers (W). Market research study conducted recently shows that three types of assortments A, B and C are in good demand...

Hi, I need a program for TI89 which can make the pivoting showing steps or which makes the pivoting but I can select the pivot element. It is needed to solve _minimum_ LP problem using Simplex method Phase #1 and Phase#2. Thanks.

This is really difficult, I have no idea how to go about this. A manufacturer of tennis rackets makes a profit of $15 on each oversized racket and $8 on each standard racket. To meet dealer demand, daily production of standard rackets should be between 30 and 80 (inclusive), and prdouction of...

i believe this type of question falls under linear programming but I am not sure. anyways, can someone help me out with this question: An office manager needs to buy new filing cabinets. Cabinet A costs $15, takes up 6 ft^2 of space and holds 8 ft^3 of files. Cabinet B costs $10, takes...

How do you resolve linear programming problems? I don't like the way my math textbook and my teacher does. I think it's a bit innacurate, if I make me understand. They do it by displacing the objective function.

As an elective for undergraduate Chem Engineer, which would be better to have? Thanks. -A

Ok, I hope this is the right section. I have a problem that I can't even start. I have a set of points on a plane. I need to formulate a linear program so that the vertical distance between each point and a line is minimised. The line must have a positive gradient, positive y-intercept and...

My assignment is to formulate a LP and find the optimal solution for the following problem: Acme estimates it costs $1.50 per month for each unit of this appliance carried in inventory (estimated by averaging the beginning and ending inventory levels each month). Currently, Acme has 120 units...

I need someone to help me folumate a Linear Programming Problem based on the following story. The optimal solution should equal 26,740; however, I need to be able to outline the equation and graph it. The story is as follows: A farmer in Georgia has a 100-acre farm on which to plant...

All-Easy manufactures three products whose unit profits are $1, $9 and $5, respectively. The company has budgeted 70 hrs. of labor time and 45 hours of machine time for the production of three products. The labor requirements per unit of products A,B C are 2, 3 and 5 hours, respectively. The...