Nutritional Requirements A rancher has determined that the minimum weekly nutritional requirements for an average-sized horse include 40lb of protein, 20 lb of carbohydrates, and 45 lb o froughage. These are obtained from the following sources in varying amounts at the prices indicated:
| Requirement | Protein (lb) | Carbohydrate (lb) | Roughage (lb) | Cost |
|---|---|---|---|---|
| Hay (per bale) | 0.5 | 2.0 | 5.0 | $1.80 |
| Oats(per sack) | 1.0 | 4.0 | 2.0 | 3.50 |
| Feeding blocks (per block) | 2.0 | 0.5 | 1.0 | 0.40 |
| High-protein | 6.0 | 1.0 | 2.5 | 1.00 |
| Requirements | 40.0 | 20.0 | 45.0 |
Decision Variables
\(x_1 = \text{Hay (per table)}\)
\(x_2 = \text{Oats(per sack)}\)
\(x_3 = \text{Feeding blocks (per block)}\)
\(x_4 = \text{High-protein concentrate (per sack)}\)
Problem
Minimize the cost function given by the objective function:
\(Cost = 1.80x_1 + 3.50x_2 + 0.40x_3 + 1.00x_4\)
Constraints
\(Protein = 0.5x_1 + 1.0x_2 + 2.0x_3 + 6.0x_4 \leq 40\)
\(Carbohydrate = 2.0x_1 + 4.0x_2 + 0.5x_3 + 1.0x_4 \leq 20\)
\(Roughage = 5.0x_1 + 2.0x_2 + 1.0x_3 + 2.5x_4 \leq 45.0\)
\(\text{where } x_1, x_2, x_3, x_4 \geq 0\)
Maximize \(10x + 35y\) subject to:
\[8x + 6y \leq 48 \text{ (board-feet of lumber)}\]
\[4x + y \leq 20 \text{ (hours of carpentry)}\]
\[y \geq 5 \text{ (demand)}\]
\[x,y \geq 0 \text{ (non-negativity)}\]
Plot the lines using x, y values that satisfy the equations
x <- seq(0, 6, by=0.1)
data <- data.frame(x = x, board_feet = (48-8*x)/6, hours = 20-4*x, demand = 5)
tidy <- gather(data, variable, "y", -x)
ggplotly(ggplot(tidy, aes(x=x, y=y, color=variable)) + geom_line())Looking at the resulting plot, we see that the feasible region is defined by the points (0, 5), (0, 8), (2.2, 5)
Plug the extreme points into the objective function to maximize the value:
obj_f <- function(x, y) return (10*x + 35*y)
df <- data.frame(x = c(0, 0, 2.2),
y = c(5, 8, 5))
df$value <- obj_f(df$x, df$y)
df <- arrange(df, desc(value))The maximum value \(z = 280\) is given by \(x = 0\) and \(y = 8\)
| x | y | value |
|---|---|---|
| 0.0 | 8 | 280 |
| 2.2 | 5 | 197 |
| 0.0 | 5 | 175 |
Maximize \(10x + 35y\) subject to:
\[8x + 6y \leq 48 \text{ (board-feet of lumber)}\]
\[4x + y \leq 20 \text{ (hours of carpentry)}\]
\[y \geq 5 \text{ (demand)}\]
\[x,y \geq 0 \text{ (non-negativity)}\]
Convert the inequalities to equations and add slack variables \(y_1, y_2, y_3\)
\(8x_1 + 6x_2 + y_1 = 48\)
\(4x_1 + 1x_2 + y_2 = 20\)
\(x_2 = 5 + y_3\)
Constraints:
\(x1,x2, y1, y2, y3 \geq 0\)
1- Set \(x_1, x_2 = 0\)
\(0 + 0 + y_1 = 48\)
\(0 + 0 + y_2 = 20\)
\(0 - y_3 = 5\)
\(y_1 = 48\) \(y_2 = 20\)
\(y_3 = -5\)
We get \(y_1 = 48, y_2 = 20, y_3 =-5\)
This system satisfies the nonnegative constraint for all variables.
2 Next assign \(x_1 = 0\) and \(y_1 = 0\)
\(0 + 6x_2 + 0 = 48\)
\(0 + x_2 + y_2 = 20\)
\(x_2 - y_3 = 5\)
\(x_2 = 8\) \(y_2 = 12\) \(y_3 = 3\)
This system satisfies the nonnegative constraint for all variables which gives us point A
Point A: A(0, 8)
3 Next assign \(x_1 = 0\) and \(y_2 = 0\)
\(0 + 6x_2 + y_1 = 48\)
\(0 + x_2 + 0 = 20\) \(x_2 - y_3 = 5\)
\(x_2 = 20\)
\(y_1 = 48 - 120 = -72\) \(y_3 = 5\)
Since \(y_1 \leq 0\) the results will be in the infeasible region. This system does not satisfy the nonnegative constraint for all variables.
4 Next assign \(y_1 = 0\) and \(y_3 = 0\)
\(8x_1 + 6x_2 + 0 = 48\)
\(4x_1 + x_2 + y_2 = 20\)
\(x_2 - 0 = 5\)
\(x_2 = 5\)
\(x_1 = (48 - 30)/8 = 2.25\) \(y_2 = 20 - 9 - 5 = 6\)
This system satisfies the nonnegative constraint for all variables which gives us point B
Point B: B(2.25, 5)
5 Next assign \(y_2 = 0\) and \(y_3 = 0\)
\(8x_1 + 6x_2 + y_1 = 48\)
\(4x_1 + x_2 + 0 = 20\)
\(x_2 - 0 = 5\)
\(x_2 = 5\) \(x_1 = (20-5)/4 = 3.75\)
\(y_1 = 48 - 30 - 8*(3.75) = -12\)
This system fails the nonnegative constraint for all variables.
6 Next assign \(x_1 = 0\) and \(y_3 = 0\)
\(0 + 6x_2 + y_1 = 48\)
\(0 + x_2 + y_2 = 20\)
\(x_2 - 0 = 5\)
\(x_2 = 5\)
\(y_2 = 20 - 5 - 15\)
\(y_1 = 48 - 30 = 18\)
This system satisfies the nonnegative constraint for all variables which gives us point C
Point C: C(0, 5)
| Extreme Point | Feasible | Value of z |
|---|---|---|
| A(0, 8) | Yes | 280 |
| B(2.25, 5) | Yes | 197.50 |
| C(0, 5) | Yes | 175 |
The optimal solution is \(x_1 = 0, x_2 = 8, z = 280\)
Solve using the linprog package in R.
https://cran.r-project.org/web/packages/linprog/linprog.pdf
suppressWarnings(suppressMessages(library(linprog)))Objective Fuction: \(10x + 35y\)
\[8x + 6y \leq 48 \text{ (board-feet of lumber)}\]
\[4x + y \leq 20 \text{ (hours of carpentry)}\]
\[y \geq 5 \text{ (demand)}\]
cvec <- c(10, 35) # objective function; c vector
bvec <- c(48, 20, 5) # b vector
Amat <- rbind(c(8, 6), c(4, 1), c(0, 1)) # matrix A
# note. const.dir needs to be set correctly for each inequality above -- in particular, y >= 5
res = solveLP(cvec, bvec, Amat, const.dir = c("<=", "<=", ">=" ), maximum=TRUE)
print(res)##
##
## Results of Linear Programming / Linear Optimization
##
## Objective function (Maximum): 280
##
## Iterations in phase 1: 1
## Iterations in phase 2: 1
## Solution
## opt
## 1 0
## 2 8
##
## Basic Variables
## opt
## 2 8
## S 2 12
## S 3 3
##
## Constraints
## actual dir bvec free dual dual.reg
## 1 48 <= 48 0 5.83333 18
## 2 8 <= 20 12 0.00000 12
## 3 8 >= 5 3 0.00000 3
##
## All Variables (including slack variables)
## opt cvec min.c max.c marg marg.reg
## 1 0 10 -Inf 46.66667 -36.66667 2.25
## 2 8 35 7.50 Inf NA NA
## S 1 0 0 -Inf 5.83333 -5.83333 18.00
## S 2 12 0 -13.75 35.00000 0.00000 NA
## S 3 3 0 -27.50 Inf 0.00000 NAFor the example problem in this section, determine the sensitivity of the optimal solution to a change in \(c_2\) using the objective function \(25x_1 + c_2x_2\).
\(z = 25x_1 + c_2x_2\)
Use the slope method on coefficent \(c\)
\[x_2 = -\frac{25}{c}x_1\]
We know from the problem that the:
Therefore the range of values for which the current extreme point remains optimal is given by:
\[-\frac{2}{3} \leq -\frac{25}{c} \leq -\frac{5}{4}\]
\[\frac{2}{3} \geq \frac{25}{c} \geq \frac{5}{4}\]
\[ 20 \leq c \leq 37.5 \]