Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If you are not familiar with Linear Programming, start here: <a href="http://en.wikipedia.org/wiki/Linear_programming">http://en.wikipedia.org/wiki/Linear_programming</a></p> <p>Also have a look at the part about Mixed-Integer Programming <a href="http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns">http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns</a>. That's when the variables you are trying to solve are not all continuous, but also include booleans or integers.</p> <hr> <p>To all aspects, your problem is a mixed-integer programming (to be exact, an integer programming) as you are trying to solve for integers: the number of vehicles to produce for each model.</p> <p>There are known algorithms for solving these and thankfully, they are already wrapped into R packages for you. <code>Rglpk</code> is one of them, and I'll show you how to formulate your problem so you can use its <code>Rglpk_solve_LP</code> function.</p> <hr> <p>Let <code>x1, x2, x3, x4, x5</code> be the variables you are solving for: the number of vehicles to produce for each model.</p> <p>Your objective is:</p> <p><code>Profit = 2000 x1 + 2500 x2 + 3000 x3 + 5500 x4 + 7000 x5</code>.</p> <p>Your steel constraint is:</p> <p><code>1.5 x1 + 3 x2 + 5, x3 + 6 x4 + 8 x5 &lt;= 6500</code></p> <p>Your labor constraint is:</p> <p><code>30 x1 + 25 x2 + 40 x3 + 45 x4 + 55 x5 &lt;= 65000</code></p> <p>Now comes the hard part: modeling the minimum production requirements. Let's take the first one as an example: the minimum production requirement on <code>x1</code> requires that at least 1000 vehicles be produced (<code>x1 &gt;= 1000</code>) or that no vehicle be produced at all (<code>x1 = 0</code>). To model that requirement, we are going to introduce a boolean variables <code>z1</code>. By boolean, I mean <code>z1</code> can only take two values: <code>0</code> or <code>1</code>. The requirement can be modeled as follows:</p> <p><code>1000 z1 &lt;= x1 &lt;= 9999999 z1</code></p> <p>Why does this work? Consider the two possible values for <code>z1</code>:</p> <ol> <li>if <code>z1 = 0</code>, then <code>x1</code> is forced to <code>0</code></li> <li>if <code>z1 = 1</code> then <code>x1</code> is forced to be greater than <code>1000</code> (the minimum production requirement) and smaller than 9999999 which I picked as an arbitrarily big number.</li> </ol> <p>Repeating this for each model, you will have to introduce similar boolean variables (<code>z2, z3, z4, z5</code>). In the end, the solver will not only be solving for <code>x1, x2, x3, x4, x5</code> but also for <code>z1, z2, z3, z4, z5</code>.</p> <hr> <p>Putting all this into practice, here is the code for solving your problem. We are going to solve for the vector <code>x = (x1, x2, x3, x4, x5, z1, z2, z3, z4, z5)</code></p> <pre><code>library(Rglpk) num.models &lt;- nrow(Dorian) # only x1, x2, x3, x4, x5 contribute to the total profit objective &lt;- c(Dorian$Profit, rep(0, num.models)) constraints.mat &lt;- rbind( c(Dorian$SteelReq, rep(0, num.models)), # total steel used c(Dorian$LabReq, rep(0, num.models)), # total labor used cbind(-diag(num.models), +diag(Dorian$MinProd)), # MinProd_i * z_i cbind(+diag(num.models), -diag(rep(9999999, num.models)))) # x_i - 9999999 x_i constraints.dir &lt;- c("&lt;=", "&lt;=", rep("&lt;=", num.models), rep("&lt;=", num.models)) constraints.rhs &lt;- c(Materials$Steel, Materials$Labor, rep(0, num.models), rep(0, num.models)) var.types &lt;- c(rep("I", num.models), # x1, x2, x3, x4, x5 are integers rep("B", num.models)) # z1, z2, z3, z4, z5 are booleans Rglpk_solve_LP(obj = objective, mat = constraints.mat, dir = constraints.dir, rhs = constraints.rhs, types = var.types, max = TRUE) # $optimum # [1] 6408000 # # $solution # [1] 1000 0 0 202 471 1 0 0 1 1 # # $status # [1] 0 </code></pre> <p>So the optimal solution is to create (1000, 0, 0, 202, 471) vehicles of each respective model, for a total profit of 6,408,000.</p>
    singulars
    1. This table or related slice is empty.
    1. POOptimization with minimum order quantities using R
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USflodel
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POOptimization with minimum order quantities using R
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is spectacular! I was assuming that treating the values as continuous and just rounding the solution to the nearest integer at the end would be sufficient because I read somewhere that integer programming was more complicated than for example the simplex algorithm, but of course the R gods have endowed us with a package that makes this a non-issue. For the sake of knowledge however, is it possible/practical to introduce the boolean variables to an algorithm such as the simplex?
      singulars
      1. PO
      1. USrnorberg
    2. COYou are correct that solving a mixed-integer programming is a lot harder than a linear programming. But the number of integer variables in your problem is small enough that the free solver provided through Rglpk can solve it easily.
      singulars
      1. PO
      1. USflodel
    3. COThe simplex method is for solving linear programmings. The trick I showed you requires the introduction of boolean variables, so your problems shifts to a mixed-integer programming where the simplex method cannot (unfortunately) apply. I'm not sure there is a way around it.
      singulars
      1. PO
      1. USflodel
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload