## Module Handbook

• Dynamischer Default-Fachbereich geändert auf MAT

# Module MAT-14-13-M-3

## Module Identification

Module Number Module Name CP (Effort)
MAT-14-13-M-3 Linear and Network Programming 9.0 CP (270 h)

## Basedata

CP, Effort 9.0 CP = 270 h 1 Sem. in SuSe  Bachelor (Core) [DE] German Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Kämmerer, Florentine, Dr. (WMA | DEPT: MAT) Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Ruzika, Stefan, Prof. Dr. (PROF | DEPT: MAT) Schöbel, Anita, Prof. Dr. (PROF | DEPT: MAT) [MAT-GRU] Mathematics (B.Sc. year 1 and 2) [MAT-82.276-SG] B.Sc. Business Mathematics [NORM] Active

## Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U MAT-14-13-K-3
Linear and Network Programming
P 84 h 186 h
U-Schein
- PL1 9.0 SuSe
• About [MAT-14-13-K-3]: Title: "Linear and Network Programming"; Presence-Time: 84 h; Self-Study: 186 h
• About [MAT-14-13-K-3]: The study achievement [U-Schein] proof of successful participation in the exercise classes (ungraded) must be obtained.

## Examination achievement PL1

• Form of examination: oral examination (20-30 Min.)
• Examination Frequency: each semester
• Examination number: 82046 ("Module Exam Measure Linear and Network Programming")

## Contents

• simplex method,
• linear programs in standard form,
• fundamental theorem of linear optimization,
• degeneracy,
• variants of the simplex method,
• duality theorem and complementary slackness,
• interior point methods,
• basic concepts of graph theory,
• minimal spanning trees,
• shortest path problems,
• maximum flows,
• minimum-cost flows.

## Competencies / intended learning achievements

Building on the knowledge acquired in the first year of their mathematical studies, the students have acquired basic theoretical and practical knowledge in an area of practical/applied mathematics.

They know and understand the basic methods and algorithms for dealing with linear optimisation problems and optimisation problems on networks. They are able to translate simple practical problems into the language of mathematics and develop solution methods using the modelling techniques of mathematical optimisation. They can prove the correctness of optimisation algorithms and analyse the complexity of the procedures. They are able to critically assess the possibilities and limits of the application of these solution methods.

In the exercise classes the students have acquired a confident, precise and independent handling of the terms, propositions and methods from the lecture. They are able to understand, comprehend and explain the proofs and algorithms from the lecture.

The practical implementation of the algorithms could be learned in parallel within the framework of programming projects (see module [MAT-14-02-M-3]).

## Literature

• H.W. Hamacher, K. Klamroth: Lineare und Netzwerkoptimierung - Linear and Network Optimization (ein bilinguales Lehrbuch),
• M.S. Bazaraa, J.J. Jarvis, H.D. Sherali: Linear Programming and Network Flows, 2nd edition,
• V. Chvátal: Linear Programming,
• S.O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Anwendungen.

## Registration

Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de).

## Requirements for attendance (formal)

For students of the (Bachelor's) study programmes of the Department of Mathematics, the proof of successful participation in the exercise classes of "Fundamentals of Mathematics I" or "Fundamentals of Mathematics II" (e.g. from the module [MAT-10-1-M-2] Fundamentals of Mathematics) is prerequisite for participation in the module examination.

## References to Module / Module Number [MAT-14-13-M-3]

Course of Study Section Choice/Obligation