Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MH6503 Mathematical Programming and Optimisation

2025/26 Trimester 1

Project 1: Modelling and code development

Due: 28 October 2025

Project 1A: Modeling and Solving a Real-World Problem Objectives

● Formulate a real-world problem as a linear program.

● Solve it using both manual simplex iterations and a coded solver.

● Interpret the solution and analyze the dual problem.

Tasks

1. Formulate the LP: define decision variables, objective, and constraints.

2.  Perform at least one full simplex tableau pivot by hand.

3. Implement a simplex solver in code.

4.  Solve the LP using your code.

5. Write down the dual problem and interpret dual variables.

Sample Dataset: Blending Problem (Oil Refinery)

A refinery blends four crude oils into three types of gasoline (Regular, Premium, Diesel).

● Crudes available: A (500 barrels), B (400), C (300), D (200).

● Product requirements:

Product	Octane ≥	Sulfur ≤	Max Demand	Price
Regular	85	1.0%	400	$50
Premium	95	0.7%	300	$70
Diesel	75	1.2%	250	$60

Crude	Octane	Sulfur	Cost
A	80	1.2%	$35
B	90	0.8%	$45
C	100	0.6%	$55
D	70	1.5%	$30

Deliverables

● Report (6—10 pages): formulation, manual step, solver output, dual analysis.

●  Source code.

Grading Rubric (100 pts)

● Formulation:  15

● Manual iteration: 20

●  Code correctness:  30

●  Solver comparison:  10

● Dual analysis:  15

● Report clarity & teamwork: 10

Project 1B: Simplex vs. Revised Simplex

Objectives

● Implement both the tableau and revised simplex methods.

● Compare efficiency experimentally.

Tasks

1. Implement two solvers: tableau simplex and revised simplex.

2.  Solve the test problems below.

3.  Record iterations, operations, and runtime.

4.  Discuss efficiency and practical implications.

Sample Datasets

Problem A (Production Planning, 6 variables, 3 constraints):

Max Z = 5x1 + 4x2 + 3x3 + 7x4 + 6x5 + 8x6

2x1 + 3x2 + x3 + 4x4 + 2x5 + x6  ≤ 60

x1 + 4x2 + 2x3 + x4 + 3x5 + 2x6  ≤ 70

3x1 + x2 + 4x3 + 2x4 + x5 + 3x6  ≤ 80

                                              xi  ≥ 0

Problem B (Transportation, 20 variables, 9 constraints):

Source \ Dest	D1	D2	D3	D4	D5
S1 (50)	8	6	10	9	7
S2 (60)	6	7	11	8	9
S3 (40)	7	5	8	6	9
S4 (30)	9	8	7	10	6

Demands: D1=30, D2=40, D3=50, D4=30, D5=30. Objective: Minimize total shipping cost.

Deliverables

● Report (5—8 pages): methods, sample iterations, comparison, discussion.

●  Code for both solvers.

Grading Rubric (100 pts)

● Tableau implementation: 20

● Revised simplex implementation: 25

●  Correctness:  20

●  Comparison analysis:  15

● Degeneracy/cycling discussion:  10

● Report clarity: 10

Project 1C: Duality and Sensitivity Analysis

Objectives

● Generate duals automatically.

● Explore strong duality computationally.

Tasks

1. Write a program to generate the dual given a primal LP.

2.  Test your program with at least three different examples by:

● Solve both primal and the generated dual by hand.

● Verify strong duality.

Sample Dataset: Resource Allocation

Max Z = 10x1 + 8x2 + 6x3 + 7x4 + 9x5

2x1 + x2 + 3x3 + x4 + 2x5  ≤ 100

x1 + 2x2 + 2x3 + 3x4 + x5  ≤ 80

2x1 + 2x2 + x3 + 2x4 + 3x5  ≤ 120

xi  ≥ 0

Deliverables

● Report (6—9 pages): dual generation, primal-dual results.

● Code for dual generation.

Grading Rubric (100 pts)

● Dual generation and code correctness: 35

● Primal-dual solutions: 30

● Analysis: 20

● Report clarity: 15