mirror of
https://github.com/HananoshikaYomaru/openfreebooks.git
synced 2026-11-12 20:45:52 +00:00
70 lines
3 KiB
HTML
70 lines
3 KiB
HTML
<div class="book-prose">
|
|
<h2 id="history" class="book-prose__heading">History</h2>
|
|
<p>
|
|
Linear programming developed in the 20th century for resource allocation and planning. George
|
|
Dantzig's simplex method made large optimization problems practical in economics and operations
|
|
research.
|
|
</p>
|
|
|
|
<h2 id="derivation" class="book-prose__heading">Derivation and reasoning</h2>
|
|
<h3 id="why-corners" class="book-prose__heading">Why corner points matter</h3>
|
|
<p>
|
|
Objective lines \(ax+by=c\) are parallel for different \(c\). Sliding this line across a polygonal
|
|
feasible region reaches the last contact at a vertex (or an entire edge in tie cases).
|
|
</p>
|
|
|
|
<h2 id="checkpoints" class="book-prose__heading">Checkpoints</h2>
|
|
<details class="book-question">
|
|
<summary class="book-question__prompt">
|
|
Plot \(x+y\le6,\ x\ge0,\ y\ge0\). List feasible vertices.
|
|
</summary>
|
|
<div class="book-question__solution">
|
|
<p><strong>Answer:</strong> Vertices: \((0,0)\), \((6,0)\), \((0,6)\).</p>
|
|
</div>
|
|
</details>
|
|
<details class="book-question">
|
|
<summary class="book-question__prompt">
|
|
Maximize \(P=2x+y\) on vertices \((0,0)\), \((4,0)\), \((1,3)\), \((0,3)\).
|
|
</summary>
|
|
<div class="book-question__solution">
|
|
<p><strong>Answer:</strong> Values \(0,8,5,3\). Maximum \(8\) at \((4,0)\).</p>
|
|
</div>
|
|
</details>
|
|
<details class="book-question">
|
|
<summary class="book-question__prompt">
|
|
Minimize \(C=5x+3y\) with feasible vertices \((0,2)\), \((2,1)\), \((3,4)\).
|
|
</summary>
|
|
<div class="book-question__solution">
|
|
<p><strong>Answer:</strong> \(C=6,13,27\). Minimum \(6\) at \((0,2)\).</p>
|
|
</div>
|
|
</details>
|
|
<details class="book-question">
|
|
<summary class="book-question__prompt">
|
|
In a model, why are \(x\ge0,\ y\ge0\) often included?
|
|
</summary>
|
|
<div class="book-question__solution">
|
|
<p><strong>Answer:</strong> Quantities like items, time, or material cannot be negative.</p>
|
|
</div>
|
|
</details>
|
|
<details class="book-question">
|
|
<summary class="book-question__prompt">
|
|
How can you detect possible multiple optimal solutions graphically?
|
|
</summary>
|
|
<div class="book-question__solution">
|
|
<p><strong>Answer:</strong> Objective line is parallel to a boundary edge where both edge endpoints give the same optimum value.</p>
|
|
</div>
|
|
</details>
|
|
|
|
<h2 id="applications" class="book-prose__heading">Applications</h2>
|
|
<ul>
|
|
<li><strong>Production planning:</strong> maximize profit under labor and material limits.</li>
|
|
<li><strong>Transport/logistics:</strong> minimize cost with capacity constraints.</li>
|
|
<li><strong>Scheduling:</strong> optimize time allocation under availability rules.</li>
|
|
</ul>
|
|
|
|
<h2 id="references" class="book-prose__heading">References</h2>
|
|
<ul>
|
|
<li>Standard high-school extension units on graphical linear programming.</li>
|
|
<li>Introductory operations research texts on feasible regions and corner-point optimization.</li>
|
|
</ul>
|
|
</div>
|