Share
Explore BrainMass

Linear Programming

Linear programming is a way to determine the best outcome in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is specific case of mathematical programming. Linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. A linear programming algorithm finds a point in the polyhedron where this function has the smallest value if such point exists.

Linear programming can be applied to various fields of study. It is used in business and economics but is also utilized in engineering applications. Some industries that utilize linear programming models include transportation energy telecommunications and manufacturing. Many practical problems in operation research can be expressed as linear programming problems.

Standard form is the typical form of describing a linear programming problem. This form consists of three parts that are shown below:

A linear function to be maximized

F(x1, x2) = c1x1 + c2x2

Problem constraints

A11x1 + a12x2 <= b1

A21x1 + a22x2 <= b2

A31x1 + a32x2 <= b3

Non negative variables

X1>= 0

X2>= 0

The problem is usually expressed in matrix form and therefor becomes:

Ma{cTx| Ax <= b ^ x >= 0}

Categories within Linear Programming

Optimization

Postings: 404

Optimization is the selection of a best element from some set of available alternatives.

Investment Strategy Case Problem

Investment advisory firm WJI manages over $120 million in funds. Their asset allocation model recommends the portions of each client's portfolio to be invested in a growth stock fund, an income fund, and a money market fund. The firm caps the portion of each portfolio that may be invested in each of the funds. The amount investe

Network Optimization Problem

A utility company serves three cities from its three power plants. The power plant capacities and energy delivery costs per unit (in $) from each plant to each city are as follows in the attached document. 1. Draw the network representation for this problem. 2. Formulate the linear program to minimize total cost of energy

Linear Programming - Cyclic Algorithm (The Cutting Plane)

Please see the attachment for full details of the question. (a) Use the Cyclic (i.e. the cutting plane) algorithm to solve the attached integer linear programming problem. (b) Draw a graph to illustrate your solution form (a). Show all cuts generated and the solution obtained at each iteration. (c) Explain how the Cycl

Linear programming using two-phase simplex and graphical method

a) When solving linear programming problems a number of problem cases can arise. Explain, with the aid of diagrams where appropriate, how you would identify each of the following cases when solving a two-variable problem using the graphical method and when using the two-phase Simplex method. i) A non-unique solution ii) An

Linear Programming Using the M-technique

a) Describe the purpose of using the 2-phase method or the M-technique and highlight the pluses and minuses of these two approaches. b) Let the linear programming problem (S) be defined as follows: Minimise Z = 6x1 + 3x2 + 4x3 Such that: x1 + 6x2 + x3 = 10 2x1 + 3x2 + x3 = 15 x1,x2,x3 >=0 i) Use the M-technique

LP Scheduling problem

A nursing home employs attendants who are needed around the clock. Each attendant is paid the same, regardless of when his or her shift begins. Each shift is 8 consecutive hours. Shift begin at 6 a.m., 10 am, 2 pm, 6 pm, 10 pm and 2 am. The following table shows the nursing home's requirements for the numbers of attendants to be

Using Excel Solver to Maximize Profit for a Cargo Ship

The load master for a freighter wants to determine the mix of cargo to be carried on the next trip. The ship's volume limit for cargo is 100,000 cubic meters, and its weight capacity is 2,310 tons. The master has five different types of cargo from which to select and wishes to maximize the value of the selected shipment. Howeve

Integer Programming - Linear Programming

A photocopy machine company produces three types of laser printers—the Print Jet, the Print Desk, and the Print Pro—the sale of which earn profits of $60, $90, and $73, respectively. The Print Jet requires 2.9 hours of assembly time and 1.4 hours of testing time. The Print Desk requires 3.7 hours of assembly time and 2.1 hou

Linear Integer Programming: Integer Values

Is integer values a general property of Linear Programming problems? Explain why rounding or truncating non-integer values for the solutions is not an appropriate method for obtaining integer solutions.

Solving Linear Programming in Excel Solver-Maximization

1. You are the recently hired Chief Operations Officer at ABC Inc, a regional firm which produces specialized circuit boards used in the production of various makes and models of automobiles. The company currently owns three production plants, one much newer than the other two. Once the circuit boards are produced, the firm sh

Linear Transformation - Sensitivity Analysis

Please help with the following problem. In a linear programming problem, the binding constraints for the optimal solution are: 6X + 10Y >= (greater than or equal to) 30 3X + 15Y >= (greater than or equal to) 30 Fill in the blanks: As long as the slope of the objective function stays between _____ and _____, the current o

Lawn Trimmers: Optimal production, storage and distribution plan

XYZ Lawn Trimmer Company produces two types of lawn trimmers - a gas model and an electric model. The company has two manufacturing facilities: san Diego and Atlanta. Both plants have the capability to produce both of the models but the manufacturing and transportation costs are different.

Linear Programming Formulation Problem

The demands of circuit boards in 4 warehouses have to be met from 3 production plants. Each plant has their own capacity and production cost per unit, each warehouse has their own demand and the transportation cost is different from different plants to different warehouses. Each circuit board is sold at the same unit price regar

Building a composite function with multivariate

Discuss composite and multivariate functions What do you think the application of composite or multivariate function could be ? Here's an example of how a simple composite function is constructed The area of A of a circle is given by A=(pi)*r^2 The volume of V of a container with a cylindrical cross-section A and height h

Integer Programming Problem: Transportation and Transshipment

Part 1 Transportation The following network describes a transportation scenario in which there are four sources A, B, C, and D; and there are three destinations P, Q, and R. (The numbers next to each arrow represents the cost of transporting one unit from that particular source to the destination located at the other end of th

Applications of Linear Programming

Linear Programming Scenario # 1 A new woodworking company is going to manufacture and sell dining room tables and chairs. The company's owner has assumed that his customers are interested in buying tables and chairs individually, rather than having to buy them in predetermined sets, as is the case with his competitors. T

Linear Programs and Inequalities

Please see the attached spreadsheet that goes along with the following problem: One way to solve a linear program is to graph the inequalities to find the feasible region. Next, find the value of the objective function at each of the corner points (i.e., enumerating the corner points).

Linear Programming - Transportation Problem, North West corner

3. Emily Alice PLC is a printing company which specializes in the design and production of special effect booklets for marketing promotions. A new client orders 60,000 booklets which are to be sent to their offices in London, Manchester and Newcastle. These offices require 15000, 21000 and 24000 copies respectively. Each of

Transformation Algorithms - Linear Programming Models

Problem: This question involves formulating a linear programming model a transportation problem where demand exceeds supply. The question has four parts: (a) to (d). Please see the attachment for full details of the question. a) Write down a linear programming model of the transportation problem in the case when demand ex

Determining Optimal Ranges

Decision Theory Question An organization uses a spam filtering software to block potentially spam messages. The spam filter can be set to one of three security modes: High-Security-Mode (H), Moderate-Security-Mode (M), or Low-Security-Mode (L). Extensive experimentation using a benchmark corpus of spam messages yields the

Linear Programming Model to Determine Amount of Projects For Texmart To Undertake

Texmart is a locally owned "big-box" retail store chain in Texas with 75 stores, primarily located in the Dallas-Fort worth area. In order to compete with national big-box store chains, Texmart is planning to undertake several "sustainability" projects at its stores. The national chains have been heavily publicizing their sustai

Model Linear Program for a car manufacturer

A car manufacturer wants to reduce the weight of a car by at least 400 pounds. Design engineers have identified ten potential design changes that may be used to reduce the vehicle weight, shown in the table below. Changes 4 and 7 are engine block modifications and thus cannot both be selected. Formulate an integer linear program

Linear Programming: The Lancaster Decor Company

The Lancaster Decor Company (LDC) makes wallpaper. One of its factories makes two types of wallpaper, pasted and unpasted. Both types of wallpaper are printed by a high quality gravure process and both are packed at the same Packaging plant. The difference is that the pasted wallpaper must pass through a pasting process before i

Linear Programming: Toasties by Ajax Corp

A new cereal called Toasties is to be marketed by the Ajax Corp. The required ingredients show that to each box of Toasties must be added at leaset 16 units of vitamin A and at least 20 units of vitiamin B. These vitamins are available in two commercial supplements. The cost per pound for supplement one is $60.00 and the cost p

Formulate a Mathematical Program to Maximize Profit

An oil refinery owns two plants that can produce the same product. It costs 20x^(1/2) to produce x barrels at Plant 1 and 40x^(1/3)to produce x barrels at Plant 2. Each plant can produce up to 70 barrels and each unit produced can sell for $10. At most 120 units can be sold. a) Formulate a mathematical program to determine t

Linear Programming for Weinberger Electronics

The Weinberger Electronics Corporation manufactures four highly technical products that it supplies to aerospace firms that hold NASA contracts. Each of the products must pass through the following departments before they are shipped: wiring, drilling, assembly, and inspection. The time requirement in hours for each unit prod

Nonlinear Programming Model

Widgetco produces widgets at plants 1 and 2. It costs 20x^(1/2) dollars to produce x units at plant 1 and 40x^(1/3) dollars to produce x units at plant 2. Each plant can produce up to 70 units. Each unit produced can be sold for $10. There is demand for at most 120 widgets. A) Formulate a mathematical model to help Widget

Linear Programming: Hart Manufacturing

Hart Manufacturing makes three products. Each product requires manufacturing operations in three departments: A, B, and C. The labor-hour requirements, by department, are as follows: Department Product 1 Product 2 Product 3 A 1.5 3 2 B 2 1 2.5 C 0.25 0.25

Linear programming model for revenue management application

Problem 30 Hanson Inn is a 96-room hotel located near the airport and convention center in Louisville, Kentucky. When a convention or a special event is in town, Hanson increases its normal room rates and takes reservations based on a revenue management system. The Classic Corvette Owners Association scheduled its annual conven