一个盒子的最大体积

Question

尝试编写一个简单的网络应用程序来解决 JavaScript 中的以下常见微积分问题。

Suppose you wanted to make an open-topped box out of a flat piece of cardboard that is L long by W wide by cutting the same size square (h × h) out of each corner and then folding the flaps to form the box, as illustrated below:

You want to find out how big to make the cut-out squares in order to maximize the volume of the box.

理想情况下，我想避免使用任何微积分库来解决这个问题。

我最初的幼稚解决方案：

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

function findMaxVol(l, w) {
  const STEP_SIZE = 0.0001;

  let ideal_h = 0;
  let max_vol = 0;

  for (h = 0; h <= Math.min(l, w) / 2; h = h + STEP_SIZE) {
    const newVol = getBoxVolume(l, w, h);
    if (max_vol <= newVol) {
      ideal_h = h;
      max_vol = newVol;
    } else {
      break;
    }
  }

  return {
    ideal_h,
    max_vol
  }
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237000000038558,
//   max_vol: 1056.3058953402121
// }

这个天真的解决方案的问题是它只给出了一个估计，因为你必须提供 STEP_SIZE 并且它严重限制了这个可以解决的问题的规模。

Answer 1

意识到体积函数的导数是second degree polynomial you can apply a quadratic formula求解x后

Using calculus, the vertex point, being a maximum or minimum of the function, can be obtained by finding the roots of the derivative

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

// ax^2 + bx + c = 0
function solveQuad(a, b, c) {
  var x1 = (-1 * b + Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  var x2 = (-1 * b - Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  return { x1, x2 };
}

function findMaxVol(l, w) {    
  // V'(h) = 12h^2-4(l+w)h+l*w - second degree polynomial
  // solve to get the critical numbers
  const result = solveQuad(12, -4*(l + w), l*w)

  const vol1 = getBoxVolume(l, w, result.x1);
  const vol2 = getBoxVolume(l, w, result.x2);

  let ideal_h = 0;
  let max_vol = 0;

  // check for max
  if (vol1 > vol2) {
    ideal_h = result.x1;
    max_vol = vol1;
  } else {
    ideal_h = result.x2;
    max_vol = vol2;
  }

  return {
    ideal_h,
    max_vol
  } 
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237478148923493,
//   max_vol: 1056.30589546119
// }

Answer 2

您有一个 objective 函数：getBoxVolume()。您的目标是最大化此函数的值。

目前，您正在使用等同于采样的方法最大化它：您正在检查每个 STEP_SIZE，看看是否获得了更好的结果。您已经确定了主要问题：无法保证 STEP_SIZE 区间的边缘落在最大值附近的任何位置。

观察一下您的 objective 函数：它是凸函数。即，它从上升开始（当 h = 0，交易量为零，然后像 h 一样增长），它达到最大值，然后下降，最终达到零（当 h = min(l,w)/2 ]).

这意味着保证有一个个最大值，你只需要找到它。这使得这个问题成为 binary search 的一个很好的案例，因为给定函数的性质，您可以在函数上采样两个点并知道最大值相对于那些方向两点。您可以使用它，一次使用三个点（左、右、中）来确定最大值是在左和中之间，还是在中和右之间。一旦这些值足够接近（它们在彼此的某个固定数量 e 内），您可以 return 那里的函数值。您甚至可以证明您 return 的值在最大可能值的某个值 e' 范围内。

这是伪代码：

max(double lowerEnd, upperEnd) {

    double midPoint = (upperEnd + lowerEnd) / 2

    double midValue = getBoxVolume(l, w, midpoint)

    double slope = (getBoxVolume(l, w, midpoint + epsilon) - midValue) / epsilon

    if (Math.abs(slope) < epsilon2) { // or, if you choose, if (upperEnd - lowerEnd < epsilon3)
        return midpoint
    }

    if (slope < 0) { // we're on the downslope
        return max(lowerEnd, midPoint)
    }

    else { // we're on the up-slope
        return max(midpoint, upperEnd)
    }
}

一个盒子的最大体积

The maximum volume of a box

javascript

optimization

mathematical-optimization

calculus