MATH 340 Introduction to Linear Programming 2015 spring




Start Time

End Time




Tue Thu






Instructor: Jozsef Solymosi

Office: MATH 220

Office hours:          Apr. 17, 3-4:30 pm.  Room: MATH 104 (most likely)

Apr. 18, 3-4:30 pm.  Room: MATH 104 (most likely)


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


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.

Here is a book you might find very useful when you review what we’ve learned: Practical Optimization: A Gentle Introduction, by John W. Chinneck. (up to Chapter 9.)




·       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.

·       Wikipedia has nice descriptions of the network algorithms we’ve learned.

o   The Ford-Fulkerson Algorithm

o   Dijkstra's Algorithm

o   Minimum Spanning Tree

o   The Chinese Postman Problem

o   Maximum Matching

o   The Traveling Salesman’s Problem

·       Here is a book you might find very useful when you review what we’ve learned: Practical Optimization: A Gentle Introduction, by John W. Chinneck. (up to Chapter 9.)



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)


·       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.



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

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

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 11.   Game Theory

1.         Matrix Games

2.         Optimal Strategies

3.         The Minimax Theorem


Week 12+(March 25-31-)


Part 2 Network Flows and Applications

Graph Algorithms

1.      The Ford-Fulkerson Algorith

2.      Dijkstra's Algorithm

3.      Minimum Spanning Tree

4.      The Chinese Postman Problem

5.      Maximum Matching

6.      The Traveling Salesman’s Problem


Week 12+ (April)








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.