MATH 340 Introduction to Linear Programming 2015 spring

 

Term

Day

Start Time

End Time

Building

Room

2

Tue Thu

11:00

12:30

Buchanan

B213

 

Instructor: Jozsef Solymosi

Office: MATH 220

Office hours: Wednesdays 4:00-5:30 pm. 

 

MATH 340 (3) Introduction to Linear Programming:

Linear programming problems, dual problems, the simplex algorithm, solution of primal and dual problems, sensitivity analysis. 

Additional topics chosen from: Karmarkar's algorithm, non-linear programming, game theory, applications.
Prerequisite: One of MATH 152, MATH 221, MATH 223.

Course book: 

We follow the textbook, "Linear Programming" by Vanderbei, 4th edition; it is available to anyone with a CWL account.

Grading

Policies

Notes

·       We are going to use the optimization software Classic LINDO. You have to download it. Here is the User's Manual.

o   LINDO runs on Widows based PCs. There are two basic approaches to running Windows on a Mac:

§  Setting up Apple's Boot Camp

§  Running Windows in a "virtual machine"

Which route you take depends on your needs, particularly how often or permanently you need Windows. The first option sets aside a partition on your Mac's hard drive that you can boot into and run Windows directly on the Apple hardware.

If you have no access to computers then write me to set up an account to the computer lab.

·       Joel Friedman’s notes about poker and game theory.

·       Applications of network optimization

·       Graph theory and applications a book by Bondy and Murty. We cover the Shortest Path Problem (1.8) the Chinese Postman Problem (4.3) the Traveling Salesman Problem (4.4) and parts of Chapters  5, 10, and 11.

Notes from class

·       Introduction (1/6/15)

·       A simplex example (1/8/15)

o   Max 4x1+6x2

o   Subject to

§  -x1+x2<=11

§  x1+x2<=27

§  2x1+5x2<=90

o   After completing two more iteration (what we did in class) the optimum is 132, when x1=15 and x2=12.

·       An unfeasible LP problem.(1/22/15)

·       A LINDO example.(1/29/15)

Syllabus

·       Scroll down for the details

Problem Sets

In addition to the questions covered in the problem sets there might be a sensitivity analysis question based on a LINDO output. Check the LINDO example we analyzed in class and try to answer the sample question below. We will discuss the answers in class after the break.

In the following example you want to minimize the cost of transportation while satisfying the demands of the four costumers and the supply constraints of the three warehouses. You will find the questions after the LINDO output.

 

Dates:

Withdrawal Dates

·       Last day to withdraw without a W standing: January 19, 2015

·       Last day to withdraw with a W standing (course cannot be dropped after this date): February 13, 2015

Term 2 (Jan 05, 2015 to Apr 10, 2015)

Midterm break: February 16-20

Midterm exam: Feb 26 Thursday (in class)

Final: April 20 Monday at 12 noon, location: GEOG 100

http://photo.elsoar.com/wp-content/images/Spring-2015-calendar.jpg

Syllabus MATH 340

2015 spring

 

Part 1.  Basic Theory: The Simplex Method and Duality

 

Week 1-2 (Jan 6- 18)

 

Chapter 1.   Introduction

1.         Managing a Production Facility

2.         The Linear Programming Problem

 

Chapter 2.   The Simplex Method

1.   An Example

2.   The Simplex Method

 

Week 3 (Jan 19-25)

 

3.   Initialization

4.   Unboundedness

5.   Geometry

 

Week 4 (Jan 26-31)

Chapter 3.   Degeneracy

1.         Definition of Degeneracy

2.         Two Examples of Degenerate Problems

3.         The Perturbation/Lexicographic Method

4.         Bland’s Rule

5.         Fundamental Theorem of Linear Programming

6.         Geometry

 

Week 5-6 (Feb 1-16)

 

Chapter 5.   Duality Theory

1.         Motivation: Finding Upper Bounds

2.         The Dual Problem

3.         The Weak Duality Theorem

4.         The Strong Duality Theorem

5.         Complementary Slackness

6.         The Dual Simplex Method

7.         A Dual-Based Phase I Algorithm

8.         The Dual of a Problem in General Form

 

Reading break

 

Week 8 (Feb 23-28)

Review and Midterm exam

 

Week 9-10 (March 1-7)

LINDO + sensitivity analysis

 

Week 10-11 (March 8-21)

 

Chapter 10.  Convex Analysis

1.         Convex Sets

2.         Carathe΄odory’s Theorem

3.         The Separation Theorem

4.         Farkas’ Lemma

 

Chapter 11.   Game Theory

1.         Matrix Games

2.         Optimal Strategies

3.         The Minimax Theorem

4.         Poker

 

Week 12(March 25-31)

 

Part 2 (Network Flows and Applications)

 

Week 12+ (April)

 

Review

 

Final

 

 

 

Note: This is the plan; however we might change the schedule if needed. The indicated chapters and sections are from the course’s book. Our treatment some of the listed topics will be slightly different then in the book.