Follow “Graduate Mathematics Emperor (ID: King_maths)“↑

Breakthroughs come from gradual accumulation~

Optimization Models

1.1 Mathematical Programming Models

Linear programming, integer linear programming, nonlinear programming, multi-objective programming, dynamic programming.

1.2 Differential Equation Models

Logistic growth model, SARS transmission model.

1.3 Graph Theory and Network Optimization Problems

Shortest path problem, maximum flow problem, minimum cost maximum flow problem, minimum spanning tree problem (MST), traveling salesman problem (TSP), graph coloring problem.

1.4 Probability Models

Decision models, stochastic storage models, stochastic population models, newsboy problem, Markov chain models.

1.5 Classic Problems in Combinatorial Optimization

1.5.1 Multi-dimensional Knapsack Problem (MKP)

Knapsack problem: Given items, with each item having a volume, and the knapsack having a capacity. How to pack as many items as possible into the knapsack. Multi-dimensional knapsack problem: Given items, with each item having a value and volume, and the knapsack having a capacity. How to select items to maximize the total value in the knapsack. Applications of the multi-dimensional knapsack problem include: resource allocation, cargo loading, and storage allocation issues. This problem is classified as NP-hard.

1.5.2 Quadratic Assignment Problem (QAP)

Job assignment problem: Given jobs that can be completed by workers. Each worker has a time to complete the job. How to arrange tasks to minimize total work time. Quadratic assignment problem (often exemplified by machine layout problem): Given machines to be arranged in locations, with logistics flow between machines and distances between locations, how to arrange them to minimize costs. Applications of the quadratic assignment problem include: campus building layout, hospital department arrangements, and grouping technology in processing center composition issues.

1.5.3 Traveling Salesman Problem (TSP)

Traveling salesman problem: Given cities, with distances between cities, find a route that visits each city exactly once and returns to the starting point, minimizing total distance.

1.5.4 Vehicle Routing Problem (VRP)

Vehicle routing problem (also known as vehicle scheduling): Given customer location coordinates and cargo demand, under constraints of available vehicle count and capacity, each vehicle departs from a start point, completes delivery tasks to several customer points, and returns to the start point, aiming to minimize the number of vehicles and total distance traveled. The TSP problem is a special case of the VRP problem.

1.5.5 Job Shop Scheduling Problem (JSP)

Job shop scheduling problem: There are jobs and machines, each job consists of a series of operations, and the execution order of operations follows a strict serial order. Each operation requires a specific machine to complete at a specific time, with no machine able to complete multiple jobs simultaneously, and operations of the same job cannot execute concurrently. How to determine the minimum time from the start of the first operation to the end of the last operation.

Classification Models

Discriminant analysis is based on known observational data of several types of samples, establishing a discriminative function to analyze unknown types of samples. Cluster analysis, on the other hand, does not predefine the types to be classified, but determines the types through internal analysis.

2.1 Discriminant Analysis

2.1.1 Distance Discriminant Method

Basic idea: Firstly, calculate the centroid (mean) of each category based on known classification data. The discriminative criterion is that for any given observation, if it is closest to the centroid of a certain category, it is assumed to belong to that category. The distance can be measured using Euclidean distance, Mahalanobis distance, Minkowski distance, etc., as needed.

2.1.2 Fisher’s Discriminant Method

Basic idea: Extract samples with indicators from two populations, constructing a discriminant function based on variance analysis principles. The coefficients are determined to maximize the differences between groups while minimizing the deviations within each group. For a new sample, substitute its indicator values into the discriminant function to obtain a y value, and compare it with the discriminant threshold to determine its population. Under the assumption of equal prior probabilities for the two populations, the discriminant threshold is generally taken as:Finally, use statistical measures to test the effectiveness of the discrimination; if effective, it is considered valid, otherwise invalid. The above describes two-population discrimination, while multi-population discrimination methods need to be expanded. As the number of populations increases, the complexity of the established discriminant functions also increases, making calculations more complex.

2.1.3 Bayes Discriminant Method

Basic idea: Assume knowledge of the studied objects, i.e., the prior probabilities and probability density functions of each population. Use Bayes’ theorem to calculate the posterior probability of the observed sample belonging to each population, classifying it accordingly.

2.1.4 Stepwise Discriminant Method

Similar to stepwise regression, this method employs an