Linear Programming by the Corner-Point Method

Doing the best with what you have#

A fac­tory has only so many work­ers and so much mate­r­ial, and wants the biggest profit it can get. A diet has to sup­ply enough nutri­ents while cost­ing as lit­tle as pos­si­ble. When the goal and all the lim­its are lin­ear, some­thing remark­able hap­pens: the best choice always sits at a cor­ner of the region the lim­its allow. We will learn to set up such lin­ear pro­gram­ming prob­lems, solve them by check­ing the cor­ners, and prac­tise on the kinds of prob­lems you will meet in exams.

Set­ting up the prob­lem#

Every lin­ear pro­gram­ming prob­lem has three parts:

• deci­sion vari­ables $x, y \ge 0$;
• a lin­ear objec­tive func­tion $Z = ax + by$ to max­imise or min­imise;
• lin­ear con­straints (inequal­i­ties).

The points that sat­isfy every con­straint form the fea­si­ble region. Each of those points is a fea­si­ble solu­tion, and the best of them is the opti­mal solu­tion.

Cor­ner-point the­o­rem. If an opti­mal value exists at all, it occurs at a cor­ner (ver­tex) of the fea­si­ble region. And if the region is bounded, you are guar­an­teed both a max­i­mum and a min­i­mum.

The cor­ner-point method, step by step#

1. Graph the con­straints and shade the fea­si­ble region.
2. Find its cor­ner points.
3. Eval­u­ate $Z$ at each cor­ner.
4. For a bounded region, the largest value is the max­i­mum and the small­est the min­i­mum. An unbounded region needs one extra check: a can­di­date value $M$ is truly the max­i­mum only if the half-plane $ax + by > M$ does not meet the fea­si­ble region (and sim­i­larly for a min­i­mum with $<$).

Try these your­self#

1. Max­imise $Z = 3x + 2y$ sub­ject to $x + 2y \le 10$, $3x + y \le 15$, $x, y \ge 0$.
2. Min­imise $Z = 2x + 3y$ sub­ject to $x + y \ge 5$, $x \le 4$, $y \le 4$, $x, y \ge 0$.
3. Max­imise $Z = 5x + 4y$ sub­ject to $x + y \le 7$, $x - y \le 1$, $y \le 5$, $x, y \ge 0$.
4. Show that $Z = x + y$ has no max­i­mum sub­ject to $x - y \le 1$, $x + y \ge 2$, $x, y \ge 0$.
5. A dealer has ₹$50{,}000$ and room for $40$ items. Fans cost ₹$1{,}000$ (profit ₹$250$) and lamps ₹$1{,}500$ (profit ₹$300$). How many of each should she buy to max­imise profit?
6. A farmer has $30$ hectares for wheat and gram. Wheat earns ₹$20{,}000$ and gram ₹$15{,}000$ per hectare; wheat needs $4$ work­ers per hectare and gram $2$, and $100$ work­ers are avail­able. Find the best allo­ca­tion.
7. A mix­ture must con­tain at least $10$ units of vit­a­min A and $12$ of vit­a­min B. Food P has $2$ and $3$ units per packet (₹$5$), food Q has $2$ and $2$ (₹$4$). Find the cheap­est mix­ture.
8. Why must the opti­mum of a lin­ear objec­tive over a bounded poly­gon occur at a cor­ner?

Answers to check against#