# Week 9

## Topics

This is the first of two weeks devoted to Linear Programming. This week, we
will cover the first three sections of chapter 5 and the first section of chapter
6.

**Chapter 5-1**: Inequalities
in Two Variables
**Chapter 5-2**: Systems
of Linear Inequalities in Two Variables
**Chapter 5-3**: Linear
Programming in Two Dimensions: Geometric Approach
**Chapter 6-1**: Table Method: An Introduction to the Simplex Method

## What is Linear Programming?

A linear programming problem consists of several linear inequalities called **constraints**,
and a linear **objective function** which is to be maximized or minimized. The
objective function is often a profit (to be maximized), or a cost (to be minimized).

For the case of two variables, we can represent the problem graphically. Each
constraint corresponds to a half-plane on one side of a straight line. The
intersection of all the half-planes forms the **feasible region**. This
region is either empty, or it is a **polygon**, that is, something bordered
by straight line segments.

We
want to find the maximum or minimum of the objective function among all the
points in the feasible region. The objective function is constant along lines
in a certain direction. The maximum and minimum will always occur along a line
that just barely touches the region.

For the standard problems that we do, the feasible region is always in the
first quadrant, and the slope of the line representing the objective function
is negative. This implies that if the region is bounded (that is, it does not
extend all the way out to infinity), there is always a minimum and a maximum,
and both of them are at corner points of the feasible region. If the region
is unbounded, there will be a minimum, but no maximum.

It is possible that the maximum or minimum occurs at *two* corner points
simultaneously. In this case, any point on the boundary between the two corners
is also a solution.

**Left:** Single solution (the usual case).

**Right:** Multiple solution. Any point between B and C is a solution

## Assignments

- Read the textbook and do the homework assignment HW 7.
- Take the quiz, which covers Sections 3.1, 3.2, 5.1, 5.2

Last Updated:
Monday, July 13, 2015