# What method will work for this linear programming problem?

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for help with methods on how to solve them.

The problem I'm working on is this:

A factory director of an airplane company needs to optimise production. The types of airplanes, the profit per airplane as well as the starting production cost are given below:

$$\begin{array}{llll}\text{Variable}&\text{Type}&\text{Profit}\ (\times100,000)&\text{Starting Cost}\ (\times100,000)\\\hline x_1&\text{A-300}&30&35\\x_2&\text{B-310}&30&20\\x_3&\text{C-320}&24&60\\x_4&\text{D-330}&26&70\\x_5&\text{E-340}&24&75\\x_6&\text{F-350}&30&30\end{array}$$

Each airplane is produced using 6 basic materials with requirements and availability as shown on table 2:

$$\begin{array}{l|ccccccl}&\text{A-300}&\text{B-310}&\text{C-320}&\text{D-330}&\text{E-340}&\text{F-350}&\text{Availability}\\\hline\text{Steel}&1&4&0&4&2&1&800\\\text{Copper}&4&5&3&0&1&0&1160\\\text{Plastic}&0&3&8&0&1&0&1780\\\text{Rubber}&2&0&1&2&1&5&1050\\\text{Glass}&2&4&2&2&2&4&1360\\\text{Paint}&1&4&1&4&3&4&1240\end{array}$$

As I see it we have to maximise the profit given by: $p=30x_1+45x_2+24x_3+26x_4+24x_5+30x_6-35y_1-20y_2-60y_3-70y_4-75y_5-30y_6$ Where $x_i$ is the amount of airplanes of type "i" produced and $y_i=1$ if $x_i>0$ and $y_i=0$ if $x_i=0$ That is if a plane is produced the starting cost is payed for else it isn't.

Then we have the following restrictions based on materials as well as the fact that airplanes are whole physical units, therefore our $x_i$s must be natural numbers.

$x_1+4x_2+4x_4+2x_5+x_6 \le 800$

$4x_1+5x_2+3x_3+x_5\le1160$

$3x_2+8x_3+x_6\le1780$

$2x_1+x_3+2x_4+x_5+x_6\le1050$

$2x_1+4x_2+2x_3+2x_4+2x_5+4x_6\le1360$

$x_1+4x_2+x_3+4x_4+3x_5+4x_6+\le1240$

Now, I'm stuck on how to work onwards. Will a simplex method work here? Where could I read more on this and what is the name of the method used for this type of problem?

I would appreciate a step-by-step solution, or even some guidance on where to look for some examples to teach me how to work.

# Corrections to the model

First, the model you wrote is missing a few constraints to link the $x_i$ and $y_i$ variables. You want to force the variable $y_i$ to take the value 1 if $x_i \geq 1$. Forcing $y_i$ to take value 0 when $x_i = 0$ is useless since this case is clearly suboptimal and will never yield an optimal solution. The constraints you must add are :

$$x_i \leq M y_i$$

Where $M$ should be a number bigger or equal to the maximum $x_i$ can ever take, but as small as possible (for example, you can take the maximum number of airplane $i$ you can build with the materials).

# Solving the problem

To solve this problem, you will need a MIP solver, unless there is some trick that makes that particular example easy (I could not find any). This problem seems hard to solve by hand.

## Softwares

Here is a list of software that could do the trick.

• Excel It has a built-in solver, and it is relatively to use, even for someone without programming experience. You can find a tutorial here. HOwever, the solver is not very good with large problems. It should do the job here, however.
• Xpress Maybe for more computer litterate people. This solver allows you to create and solve problems via a very simple and intuitive syntax. It is definetly a good tool if you plan on using an optimisation software for bigger problems. You can download the student version here for free.
• Cplex, gurobi SCIP, etc There are tons of other solvers out there, and most offer free student versions. Honestly, I have not tested them all.

## Manually solving the problem

If you choose to do it by hand, you have to create a Branch and bound tree. Here is a description of how it works.

However, this method may take a long time and is prone to errors, meaning that the slightest mistake may give you a wrong result.

• Thanks for the reply and the info provided! I had time to give it a swift read before going off for Christmas and I'm going to try and solve it using an MIP solver as well as trying the Branch and bound tree you suggested... Thanks a lot! – Basil Dec 27 '15 at 17:09

The simplex method is for Linear Programming (LP) problems. Linear programming problems deal with continuous variables.

A MIP solver (typically using some form of a branch-and-bound algorithm) can handle Mixed Integer Programming problems. These are problems like LP but with the additional restriction that some or all of variables can only assume integer (or often just zero-one) values. A MIP solver typically uses an LP solver as "subroutine".

A MIP solver can solve LPs but an LP solver cannot solve MIPs.

For your problem it looks like you need a MIP solver.

• An MIP solver is a program that handles Integral Programming problems right? Aside from an automated solution, what method should I look for to solve it by hand, as we don't use computers on our LP course... – Basil Dec 21 '15 at 10:15
• Branch & Bound algorithm – Erwin Kalvelagen Dec 21 '15 at 14:28