Linear Programming with Examples. C Code and Octave Script
.
1. Introduction
.
1.1 Setting the Task
The linear programming problem consists of minimizing a linear objective function z:
Notes
-
To solve the problem, we will often write the objective function in the form:
In this case, z is the variable to be minimized. -
In the case of a maximization problem, we will change the sign of the objective function to reduce it to a minimization problem:
In a linear programming problem, constraints are imposed on the variables x in the form of m equations:
Let us express (1) and (3) in matrix form:
Note
Typically, a linear programming problem involves m constraints in the form of inequalities and equalities:
In this case, it is necessary to introduce new variables for the inequalities to bring the problem into the standard form (3) (or (5)), while simultaneously creating an initial basis (for more details, see below).
For the inequality:
a supplementary variable is introduced, which is called a slack variable:
For the inequality:
two additional variables are introduced: one to compensate for the surplus, called a surplus variable, and another to form an initial basis, called an artificial variable, which takes a value of zero at the end of the calculations if a solution exists.
For the equality:
a variable is introduced to form an initial basis, called an artificial variable, which takes a value of zero at the end of the calculations if a solution exists:
.
1.2 Graphical Solution of the Problem
I use an example from [2] to illustrate the graphical solution of a linear programming problem:
To solve the problem, all inequalities are converted into equalities, and the lines corresponding to each equation are plotted:
The solution to each inequality will lie either above or below the corresponding line. Next, we shade only those regions that satisfy all the inequalities.
Now, let us plot the line for the objective function:
By choosing different constants, it is easy to determine in which direction this line should move to minimize the objective function. We shift the plot of the objective function toward smaller values z until it reaches the boundary of the feasible region. This very point will be the solution to the problem.
Figure 1-1: Graphical Solution of a Linear Programming Problem
.
The solution corresponds to point A with coordinates (4,2), which yields:
Notes:
-
It is easy to see that a graphical solution is readily obtained for systems with two variables or two-dimensional problems.
-
The graphical solution does not require the introduction of additional variables to bring the linear programming problem into the form (3).
.
2. Simplex Algorithm
Using simple transformations, (1) and (3) can be represented in the form:
Such a representation of equations is called the canonical form, and the variables
are called the basis.
By setting all variables except for the basic ones to zero, we obtain a basic solution for this canonical form:
If all values in (11) are:
then the basic solution of this canonical form (12) is the optimal solution that provides the required minimum.
If there are values:
then there is an opportunity to improve the current result. To do this, a variable is selected to be entered into the basis:
corresponding:
By assigning a certain positive value to (15), we obtain the following changes:
.
2.1 Simplex Algorithm with Сonstraints Ax ≤ b
If the linear programming problem has only constraints of the form:
or in matrix form:
With the objective function:
or in matrix form:
By introducing slack variables, as shown in (7), we obtain the canonical form:
The initial basic variables are:
Figure 2-1 shows the Simplex algorithm for this case:
Figure 2-1: Simplex algorithm with the constraints Ax ≤ b
.
To illustrate this case, let us use example (10) again and introduce the slack basic variables:
Table 2-1: Initial Simplex Tableau for Example (10)
.
Note:
Empty cells in the table imply zero values.
From (16), the minimum is:
According to formula (20), we find:
Table 2-2: Simplex Method. Iteration 1 for Example (10)
.
From (16), the minimum is:
According to formula (20), we find:
Table 2-3: Simplex Method. Iteration 2 for Example (10)
.
From (16), the minimum is:
According to formula (20), we find:
According to formula (20), we find:
Table 2-4: Simplex Method. Iteration 3 for Example (10)
.
Since all values in the objective row are non-negative:
Therefore, the optimal solution has been found. By setting all non-basic variables to zero, we obtain the optimal values for the basic variables and the objective function:
Notes
-
This algorithm is implemented in C in SimplexProgramWithVsCopilot.c. The C code was generated by artificial intelligence (AI): Copilot and the Claude 3.5 Sonnet model. Subsequently, bugs were fixed, and the code was optimized for performance.
Below is the output of the solution for problem (10) generated by the program:
Starting simplex method solution (minimization):
Iteration 1:
Pivot element: row=4, column=1
Current simplex table (iteration 1):
x3 => 9.500000 = (0.000000)x1 + (4.000000)x2 + (1.000000)x3 + (0.000000)x4 + (0.000000)x5 + (-0.500000)x6
x4 => 4.500000 = (0.000000)x1 + (3.000000)x2 + (0.000000)x3 + (1.000000)x4 + (0.000000)x5 + (-0.500000)x6
x5 => 0.500000 = (0.000000)x1 + (1.000000)x2 + (0.000000)x3 + (0.000000)x4 + (1.000000)x5 + (-0.500000)x6
x1 => 1.500000 = (1.000000)x1 + (-2.000000)x2 + (0.000000)x3 + (0.000000)x4 + (0.000000)x5 + (0.500000)x6
Current objective value: -3.000000
Iteration 2:
Pivot element: row=3, column=2
Current simplex table (iteration 2):
x3 => 7.500000 = (0.000000)x1 + (0.000000)x2 + (1.000000)x3 + (0.000000)x4 + (-4.000000)x5 + (1.500000)x6
x4 => 3.000000 = (0.000000)x1 + (0.000000)x2 + (0.000000)x3 + (1.000000)x4 + (-3.000000)x5 + (1.000000)x6
x2 => 0.500000 = (0.000000)x1 + (1.000000)x2 + (0.000000)x3 + (0.000000)x4 + (1.000000)x5 + (-0.500000)x6
x1 => 2.500000 = (1.000000)x1 + (0.000000)x2 + (0.000000)x3 + (0.000000)x4 + (2.000000)x5 + (-0.500000)x6
Current objective value: -5.500000
Iteration 3:
Pivot element: row=2, column=6
Current simplex table (iteration 3):
x3 => 3.000000 = (0.000000)x1 + (0.000000)x2 + (1.000000)x3 + (-1.500000)x4 + (0.500000)x5 + (0.000000)x6
x6 => 3.000000 = (0.000000)x1 + (0.000000)x2 + (0.000000)x3 + (1.000000)x4 + (-3.000000)x5 + (1.000000)x6
x2 => 2.000000 = (0.000000)x1 + (1.000000)x2 + (0.000000)x3 + (0.500000)x4 + (-0.500000)x5 + (0.000000)x6
x1 => 4.000000 = (1.000000)x1 + (0.000000)x2 + (0.000000)x3 + (0.500000)x4 + (0.500000)x5 + (0.000000)x6
Current objective value: -10.000000
Iteration 4:
Optimal solution found!
Optimal solution:
x3 = 3.000000
x6 = 3.000000
x2 = 2.000000
x1 = 4.000000
Objective function value: -10.000000
-
In some degenerate cases, linear programming problems solved by the simplex method can lead to cycling. This can occur if formula (20) yields more than one equal minimum. Cycling can be avoided by correctly choosing one minimum from the available options using the Lexicographic Rule (see below). Here is an example of a problem with such cycling from [2]:
To solve this problem, I use the C code SimplexProgramWithVsCopilot.c, which, for example (27), detects the stall in progress, stops the computation process, and warns about cycling.
Iteration 1:
Pivot element: row=1, column=1
Current simplex table (iteration 1):
x1 => 2.000000 = (1.000000)x1 + (-2.000000)x2 + (1.000000)x3 + (0.000000)x4 + (0.000000)x5
x4 => 0.000000 = (0.000000)x1 + (3.000000)x2 + (-2.000000)x3 + (1.000000)x4 + (0.000000)x5
x5 => 3.000000 = (0.000000)x1 + (3.000000)x2 + (-1.000000)x3 + (0.000000)x4 + (1.000000)x5
Current objective value: -6.000000
Iteration 2:
Pivot element: row=2, column=2
Warning: Solution might be cycling. Stopping.
Optimal solution:
x1 = 2.000000
x2 = 0.000000
x5 = 3.000000
Objective function value: -6.000000
.
2.2 Simplex Algorithm with Сonstraints Ax ≤ (=, ≥) b
When artificial variables are introduced to solve the problem (see (8), (9)), the solution process is divided into two phases. In the first phase, an auxiliary objective function w is introduced, which is the sum of all artificial variables. Since these variables are part of the initial basis, they are eliminated from w using the constraints.
Thus, the auxiliary function w is formed as follows:
In the first phase, we minimize the auxiliary function w using the simplex method. As mentioned above, the minimum value of w must be zero (w=0), since all artificial variables are introduced into the equalities solely to obtain an initial valid basis. If the minimum w>0, it indicates that no feasible solution exists, and the process is terminated. If the minimum w=0, we proceed to the second phase, after first excluding variables x that have positive non-zero coefficients d in the final modified equation for w. Typically, these are the artificial variables that have been driven out of the basis.
Example.
Let the constraints be given in the form of equalities:
By introducing artificial variables, we obtain:
Next, we formulate the auxiliary function w:
Using (30) and eliminating the basic variables in (31):
we get:
Next, the first phase is launched, which is the simplex method for w:
If the optimization of the first phase results in w=0, we proceed to the second phase. In the second phase, the simplex method is applied to the feasible canonical form obtained at the end of phase one to minimize the original objective function z. The subsequent steps of the second phase are identical to those demonstrated in the previous section.
.
2.3 Simplex Method Using Multipliers
As mentioned above, in some cases, the classical simplex method can lead to cycling. The Simplex Method Using Multipliers is free from this drawback. It utilizes the Lexicographic Rule mentioned earlier. Below is a brief description of this algorithm. I will present the basic formulas from [1] used by this method without proof, and then demonstrate their application through an example:
Here, I use an example from [1] to illustrate the method.
Rewriting the objective function in the form (1a) and introducing two new variables, as shown in (9), to obtain the initial basis:
as well as the auxiliary function w:
Next, by eliminating the basic variables from w, we obtain:
Then the initial table (Table 2-5) takes the following form:
Table 2-5: Initial calculation table for Example (57)
.
Now, we will modify and store only a portion of the table (see Table 2-6), while using the initial table (Table 2-5) without changes. This approach will save the memory required for the program to operate:
Table 2-6: The modified portion of the calculation table for Example (57)
.
We find the minimum negative coefficient d for the function w (see Table 2-5):
Now, we find the pivot element ‘a’ using the formula:
Thus, there will be a replacement in the basis:
Now, we calculate the new values of β in the modified portion of the table using formulas (37), (36), (42), (44), (49), (53), and (54):
Values of b:
Values of π:
Values of σ, z, w, d:
We find the minimum negative coefficient d for the function w:
We enter the results of the calculations into the modified table as the result of the first iteration:
Table 2-7: Iteration 1 of the modified calculation table for Example (57)
.
Now, we find the new pivot element ‘a’ using the formula:
Thus, there will be a replacement in the basis:
Now, we repeat all calculations for the new iteration of the modified portion of the table:
Values of b:
Values of π:
Values of σ, z, w, d:
Values of c:
Table 2-8: Iteration 2 of the modified calculation table for Example (57)
.
Now, we find the pivot element ‘a’ using the formula:
Thus, there will be a replacement in the basis:
Now, we calculate the new values of β in the modified portion of the table:
Values of b:
Values of π:
Values of z:
Values of c:
We record the final 3rd iteration into the modified table:
Table 2-9: Iteration 3 of the modified calculation table for Example (57)
.
Solution to the problem:
This method prevents cycling and, in the case of example (27), produces the correct result:
minimize z = -3*x1 + x2
subject to:
x1 – 2*x2 <= 2
2*x1 – x2 <= 4
x1 + x2 <= 5
x >= 0
— Phase 1 (revised simplex) —
Optimal (revised) after 1 iterations
— Phase 2 (revised simplex) —
Pivot(rev): enter x1, leave row 2 (basic s2)
Pivot(rev): enter x2, leave row 3 (basic s3)
Optimal (revised) after 3 iterations
Optimal solution found:
x1 = 3
x2 = 2
Objective value: -7
.
3. Travelling Salesman Problem and Linear Programming
The Travelling Salesman Problem (see the articles:“Branch and Bound Method for Travelling Salesman Problem Using Octave GNU Tool”, “Dynamic Programming and Travelling Salesman Problem. C Code and Octave Script“, “Greedy Algorithm and Travelling Salesman Problem Using Octave GNU Tool”) can also be solved using Integer Linear Programming (specifically, the Cutting-Plane Method by Ralph E. Gomory). This approach is discussed in [1] and [3].
The solution becomes quite complex because additional constraints are introduced in the process:
– objective function:
– the departure city occurs only once:
– the arrival city occurs only once:
– to eliminate subtours, i.e., non-Hamiltonian cycles:
Miller–Tucker–Zemlin (MTZ) formulation:
Dantzig–Fulkerson–Johnson (DFJ) formulation:
– constraints to ensure an integer solution, which enable the implementation of the Cutting-Plane Method
.
4. C Language SimplexProgramWithVsCopilot.c/h
The C Code implements: The Simplex Algorithm with constraints Ax ≤ b. The code was generated by artificial intelligence (AI): Copilot and the Claude 3.5 Sonnet model. Subsequently, bugs were fixed, and the code was optimized.
/* Function to find the pivot column (using the most negative coefficient rule) */
sint8 find_pivot_column(LinearProgram_t *lp, float *z)
/* Function to find the pivot row (using minimum ratio rule) */
sint8 find_pivot_row(LinearProgram_t *lp, sint8 pivot_col)
/* Function to calculate values c[j] – z[j] */
void calculate_c_minus_z(LinearProgram_t *lp, float *z)
/* Function to perform one iteration of the simplex method */
void pivot_operation(LinearProgram_t *lp, sint8 pivot_row, sint8 pivot_col)
/* Function to add slack variables to the problem */
void add_slack_variables(LinearProgram_t *lp)
/* Main simplex method function */
void simplex_method(LinearProgram_t *lp)
/* Input Data – Add Slack Variables – Simplex Method – Result Output */
int main()
.
5. Octave GNU files SimplexMethodUsingMultipliers.m and run_simplex_tests.m
The script SimplexMethodUsingMultipliers.m solves the linear programming problem using the Simplex Method Using Multipliers. The code was generated by artificial intelligence (AI): Copilot and the GPT-5 mini model.
% Modified two-phase simplex method (Octave/MATLAB)
% Usage:
% [x, z] = SimplexMethodUsingMultipliers(A, b, c, constr_types)
% where constr_types is a cell array of ‘<=’, ‘>=’, or ‘=’ for each row.
% If called without arguments, a sample problem will be solved.
function [x, z] = SimplexMethodUsingMultipliers(A, b, c, constr_types)
% Build expanded coefficient matrix Afull (m x nv) with slack/surplus/artificial
% columns and initial basic_vars indices. This is used by the revised
% simplex implementation which keeps B and B^{-1} explicitly.
function [Afull, bvec, basic_vars, var_names, art_cols] = build_phase1_matrix(A, b, c, constr_types)
% Prepare data for Phase 2 by removing artificial columns and
% constructing the Phase 2 objective vector c_phase2.
% Inputs:
% Afull – full coefficient matrix from Phase 1
% var_names – cell array of variable names corresponding to Afull columns
% basic_vars – current basic variable indices (relative to Afull)
% art_cols – indices of artificial columns in the Phase 1 Afull
% c – original objective vector (for x variables)
% Outputs:
% Afull – Afull with artificial columns removed
% var_names – var_names with artificials removed
% basic_vars – adjusted basic variable indices
% c_phase2 – objective vector for Phase 2 (length matches new Afull)
function [Afull, var_names, basic_vars, c_phase2] = build_phase2_matrix(Afull, var_names, basic_vars, art_cols, c)
% Revised simplex (Dantzig) implementation using pure incremental
% updates of B^{-1} via the user’s k/kbar formulas.
% Afull: m x nvars matrix of coefficients (no Right-Hand Side column)
% b: Right-Hand Side vector is passed as second argument
function [basic_vars, xB, B_inv, success, iter, redcosts, y, k, kbar] = simplex_revised(Afull, b, cfull, basic_vars, var_names, art_cols, phase1)
The script run_simplex_tests.m automatically runs tests for SimplexMethodUsingMultipliers.m. The code was generated by artificial intelligence (AI): Copilot and the GPT-5 mini model. The tests (examples) themselves are taken from [1] and [2].
% run_simplex_tests.m
% Automatic test runner for SimplexMethodUsingMultipliers
% Usage: run_simplex_tests; or run_simplex_tests(1) to run single test
function run_simplex_tests(which_test, quitOnFinish)
.
6. Download the SimplexProgramWithVsCopilot.c/h, SimplexMethodUsingMultipliers.m and run_simplex_tests.m
You can download the files:
SimplexProgramWithVsCopilot.c/h
SimplexMethodUsingMultipliers.m and run_simplex_tests.m
with the button:
.