LINEAR PROGRAMMING

Linear Programming deals with the problem of minimizing or maximizing a linear function in the presence of linear equality and/or inequality constraints. Since the development of the simplex method by George B. Dantzig in 1947, linear programming has been extensively used in the military, industrial, governmental, and urban planning fields, among others. The popularity of linear programming can be attributed to many factors including its ability to model large and complex problems, and the ability of the users to solve such problems in a reasonable amount of time by the use of effective algorithms and modern computers.
In this course, we address linear programming and network flows, including the general theory, characteristics of these optimization problems, as well as effective solution algorithms. The simplex algorithm provides considerable insight into the theory of linear programming and yields an efficient algorithm in practice. Hence, we study this method in detail. Whenever possible, the simplex algorithm is specialized to take advantage of the problem structure, such as in network flow problems. We also introduce Khachian's and Karmarkar's polynomial-time algorithms for linear programming problems. The latter algorithm compares favorably with the simplex method, particularly for general large-scale problems.

INSTRUCTOR: Zhuangyi Liu

OFFICE HOUR: 1:00-2:30 MWF, SCC 140

LECTURE: 10:00-10:50 MWF, Engr 177

TEXTBOOK: Linear Programming and Network Flows (Fourth Edition) by M. Bazaraa and et al

CONTENT:

  • Chapter 1, Introduction (section 1.1-1.4)
  • Chapter 2, Review of Linear Algebra, Convex Analysis, and Polyhedral Sets (section 2.1-2.7)
  • Chapter 3, The Simplex Method (section 3.1-3.8)
  • Chapter 4, Starting Solution and Convergence (section 4.1-4.2,4.5-4.6)
  • Chapter 5, Special Implementation and Optimality Condition (section 5.2-5.4)
  • Chapter 6, Duality and Sensitivity (section 6.1-6.8)
  • Chapter 9, Minimal-cost Network Flows (section 9.1-9.9)
  • Chapter 10, The Transportation and Assignment Problems (section 10.1-10.7)
  • Chapter 8, Interior Methods (section 8.3-8.5)

    MIDEXAMS:

  • 6th week 20%, will be given in an evening of that week
  • 12th week 20%, will be given in an evening of that week

    HOMEWORK: due every Wed. 40%

    FINAL: TBA 20%

    GRADING SCALE:

  • 360-400 A
  • 320-359 B
  • 280-319 C
  • 240-279 D

    REMARKS:

    (1) Tests must be taken at scheduled times. If a test is missed for a valid reason, then a make-up test can be arranged. Midexams will be scheduled at evening so that we have a two-hour period to work on the exam problems.
    (2) As a student you may experience a range of issues that can cause barriers to learning, such as strained relationships, increased anxiety, alcohol/drug problems, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may lead to diminished academic performance or reduce a student's ability to participate in daily activities. University of Minnesota services are available to assist you with addressing these and other concerns you may be experiencing. You can learn more about the broad range of confidential mental health services available on campus via the UMD Health Service Counseling website at www.d.umn.edu/hlthserv/counseling
    (3) Academic dishonesty tarnishes UMD's reputation and discredits the accomplishments of students. UMD is committed to providing students every possible opportunity to grow in mind and spirit. This pledge can only be redeemed in an environment of trust, honesty, and fairness. As a result, academic dishonesty is regarded as a serious offense by all members of the academic community. In keeping with this ideal, this course will adhere to UMD's Student Academic Integrity Policy, which can be found at http://www.d.umn.edu/conduct/integrity/Academic_Integrity_Policy.htm. This policy sanctions students engaging in academic dishonesty with penalties up to and including expulsion from the University for repeat offenders.

    Email comments and questions to zliu@d.umn.edu