Linear Programming and Optimization: Very Difficult Problems with Solutions

Solution:
Pieces cut beyond the order are simply waste, so we count only the ordered pieces. Their total length (in inches) is
[tex]320\times 560+260\times 480+120\times 780=179200+124800+93600=397600[/tex]
Lower bound. Since [tex]2\times 320=640\gt 600[/tex], the [tex]560[/tex] pieces of [tex]320[/tex] in are cut from [tex]560[/tex] different bars. In such a bar the remaining [tex]280[/tex] in hold either one piece of [tex]260[/tex] in and nothing else (as [tex]260+120\gt 280[/tex]), or at most two pieces of [tex]120[/tex] in (as [tex]3\times 120=360\gt 280[/tex]). So a bar with a [tex]320[/tex] in piece contains at most [tex]580[/tex] in of ordered pieces if it also has a [tex]260[/tex] in piece, and at most [tex]560[/tex] in otherwise.
Let [tex]k[/tex] be the number of bars containing both a [tex]320[/tex] in and a [tex]260[/tex] in piece; then [tex]k\le 480[/tex]. If [tex]N[/tex] bars are used, the total length of the ordered pieces is at most
[tex]580k+560(560-k)+600(N-560)=600N-40\times 560+20k\le 600N-22400+9600=600N-12800[/tex]
It must be at least [tex]397600[/tex], hence
[tex]600N\ge 410400\Rightarrow N\ge 684[/tex]
Construction: cut [tex]480[/tex] bars as [tex]320+260[/tex] (waste [tex]20[/tex] in each), [tex]80[/tex] bars as [tex]320+120+120[/tex] (waste [tex]40[/tex] in each) and [tex]124[/tex] bars as [tex]5\times 120[/tex] (no waste). This gives [tex]480+80=560[/tex] pieces of [tex]320[/tex] in, [tex]480[/tex] pieces of [tex]260[/tex] in and [tex]2\times 80+5\times 124=780[/tex] pieces of [tex]120[/tex] in, using [tex]480+80+124=684[/tex] bars; the total waste [tex]684\times 600-397600=12800[/tex] in is the smallest possible. The minimum number of standard bars is [tex]684[/tex].

Solution:
From the equation, [tex]x_3=10-2x_1+x_2[/tex], which is an integer whenever [tex]x_1, x_2[/tex] are integers. Substituting it into [tex]z[/tex]:
[tex]z=3x_1-5x_2+30-6x_1+3x_2=30-3x_1-2x_2[/tex]
The two inequality constraints and the condition [tex]x_3\ge 0[/tex] become:
[tex]x_1-2x_2+x_3\ge 3\Leftrightarrow 10-x_1-x_2\ge 3\Leftrightarrow x_1+x_2\le 7[/tex]
[tex]5x_1-4x_2+2x_3\ge 16\Leftrightarrow x_1-2x_2+20\ge 16\Leftrightarrow x_1-2x_2\ge -4[/tex]
[tex]x_3\ge 0\Leftrightarrow 2x_1-x_2\le 10[/tex]
So we must maximize [tex]w=3x_1+2x_2[/tex] (then [tex]z=30-w[/tex]) over the integer points with [tex]x_1, x_2\ge 0[/tex] satisfying these three constraints. Without the integrality condition the optimum is at the intersection of [tex]x_1+x_2=7[/tex] and [tex]2x_1-x_2=10[/tex], i.e. at [tex]\left(\frac{17}{3}, \frac{4}{3}\right)[/tex] with [tex]w=\frac{59}{3}[/tex], which is not an integer point. Indeed, for every admissible point
[tex]w=\frac{7}{3}(x_1+x_2)+\frac{1}{3}(2x_1-x_2)\le\frac{49}{3}+\frac{10}{3}=\frac{59}{3}\lt 20[/tex]
Since [tex]w[/tex] is an integer at integer points, [tex]w\le 19[/tex]. The point [tex]x_1=5,\ x_2=2[/tex] gives [tex]w=19[/tex] and satisfies [tex]5+2=7\le 7[/tex], [tex]5-4=1\ge -4[/tex], [tex]10-2=8\le 10[/tex]; then [tex]x_3=10-10+2=2[/tex]. Check in the original problem:
[tex]5-4+2=3\ge 3,\quad 25-8+4=21\ge 16,\quad 10-2+2=10,\quad z=15-10+6=11[/tex]
The minimum is [tex]z_{\min}=30-19=11[/tex], attained at [tex](5, 2, 2)[/tex].

Solution:
For [tex]x[/tex] trips a company makes the profit
[tex]\pi(x)=100x-25x-0.01x^2=75x-0.01x^2[/tex]
With [tex]x_A[/tex] trips of [tex]A[/tex] and [tex]x_B[/tex] trips of [tex]B[/tex] we maximize [tex]\Pi=\pi(x_A)+\pi(x_B)[/tex] subject to [tex]x_A+2x_B\le 3000[/tex], [tex]x_A, x_B\ge 0[/tex]. Since [tex]\pi'(x)=75-0.02x\gt 0[/tex] for [tex]x\lt 3750[/tex] and always [tex]x_A\le 3000[/tex], any leftover points could be used for more trips of [tex]A[/tex], increasing the profit. Hence at the optimum all points are used: [tex]x_A=3000-2x_B[/tex], [tex]0\le x_B\le 1500[/tex], and for [tex]f(x_B)=\pi(3000-2x_B)+\pi(x_B)[/tex] we get
[tex]f'(x_B)=-2\left(75-0.02(3000-2x_B)\right)+75-0.02x_B=45-0.1x_B[/tex]
The derivative vanishes at [tex]x_B=450[/tex], and [tex]f''=-0.1\lt 0[/tex], so this is the maximum on the interval; then [tex]x_A=3000-900=2100[/tex]. (Equivalently, the Lagrange conditions [tex]75-0.02x_A=\lambda[/tex], [tex]75-0.02x_B=2\lambda[/tex] give [tex]\lambda=33[/tex] dollars, the marginal value of one eco-point.) The profits are
[tex]\pi(2100)=157500-44100=113400,\qquad \pi(450)=33750-2025=31725[/tex]
[tex]\Pi_{\max}=113400+31725=145125[/tex]
For comparison, without cooperation ([tex]x_A=1500[/tex], [tex]x_B=750[/tex]) the total profit is [tex]90000+50625=140625[/tex], and using only the new trucks ([tex]x_A=3000[/tex]) gives [tex]135000[/tex]. The maximum joint profit is [tex]145125[/tex] dollars.

Solution:
The vertices of [tex]S[/tex] are the feasible points where three of the six bounding planes with linearly independent normals meet. Solving all such systems and keeping the feasible solutions gives [tex]7[/tex] vertices:
[tex]O(0, 0, 0),\ \ (11, 0, 0),\ \ (0, 9, 0),\ \ (0, 0, 8),\ \ (4, 7, 0),\ \ (9, 0, 2),\ \ (0, 3, 8)[/tex]
For example, [tex]x+y+z=11[/tex], [tex]2x+3z=24[/tex] and [tex]y=0[/tex] give [tex](9, 0, 2)[/tex], while the point [tex](12, 0, 0)[/tex] obtained from [tex]2x+3z=24[/tex], [tex]y=z=0[/tex] is rejected since [tex]12\gt 11[/tex]. The vertex [tex](0, 3, 8)[/tex] is degenerate: four of the planes pass through it, namely [tex]x=0[/tex], [tex]x+y+z=11[/tex], [tex]2x+4y+3z=36[/tex] and [tex]2x+3z=24[/tex]. Each of the six planes contains a face with the following vertices:
[tex]x=0:\quad O,\ (0, 9, 0),\ (0, 3, 8),\ (0, 0, 8)[/tex]
[tex]y=0:\quad O,\ (11, 0, 0),\ (9, 0, 2),\ (0, 0, 8)[/tex]
[tex]z=0:\quad O,\ (11, 0, 0),\ (4, 7, 0),\ (0, 9, 0)[/tex]
[tex]x+y+z=11:\quad (11, 0, 0),\ (9, 0, 2),\ (0, 3, 8),\ (4, 7, 0)[/tex]
[tex]2x+4y+3z=36:\quad (0, 9, 0),\ (4, 7, 0),\ (0, 3, 8)[/tex]
[tex]2x+3z=24:\quad (0, 0, 8),\ (9, 0, 2),\ (0, 3, 8)[/tex]
So four faces are quadrilaterals and two are triangles. Every edge belongs to exactly two faces, hence
[tex]E=\frac{4\times 4+2\times 3}{2}=11[/tex]
Check with Euler's formula: [tex]V-E+F=7-11+6=2[/tex]. Also by degrees: the vertex [tex](0, 3, 8)[/tex] is joined to [tex]4[/tex] vertices ([tex](0, 9, 0)[/tex], [tex](0, 0, 8)[/tex], [tex](9, 0, 2)[/tex], [tex](4, 7, 0)[/tex]) and each of the other [tex]6[/tex] vertices to [tex]3[/tex], so [tex]E=\frac{4+6\times 3}{2}=11[/tex] (assuming that every vertex has degree [tex]3[/tex] would give the impossible [tex]\frac{21}{2}[/tex]). The polyhedron has [tex]11[/tex] edges.