Solving integer programming problems: methods and examples
Equations in integers are algebraic equations with two or more unknown variables and integer coefficients. The solutions to such an equation are all integer (sometimes natural or rational) sets of values of unknown variables that satisfy this equation. Such equations are also called diophantine, in honor of the ancient Greek mathematician who studied some types of such equations before our era.
We owe the modern formulation of Diophantine problems to the French mathematician. It was he who raised the question of solving indefinite equations only in integers before European mathematicians. The most famous equation in integers is Fermat's last theorem: equation
has no non-zero rational solutions for all natural n > 2.
The theoretical interest in equations in integers is quite great, since these equations are closely related to many problems in number theory.
In 1970, Leningrad mathematician Yuri Vladimirovich Matiyasevich proved that a general method that allows solving arbitrary Diophantine equations in integers in a finite number of steps does not exist and cannot exist. Therefore it follows for different types equations, choose your own solution methods.
When solving equations in integers and natural numbers The following methods can be roughly distinguished:
way to sort through options;
application of the Euclidean algorithm;
representation of numbers in the form of continued (continued) fractions;
factorization;
solving equations in integers as square (or other) with respect to any variable;
residual method;
infinite descent method.
Problems with solutions
1. Solve the equation x 2 – xy – 2y 2 = 7 in integers.
Let's write the equation in the form (x – 2y)(x + y) = 7.
Since x, y are integers, we find solutions to the original equation as solutions to the following four systems:
1) x – 2y = 7, x + y = 1;
2) x – 2y = 1, x + y = 7;
3) x – 2y = –7, x + y = –1;
4) x – 2y = –1, x + y = –7.
Having solved these systems, we obtain solutions to the equation: (3; –2), (5; 2), (–3; 2) and (–5; –2).
Answer: (3; –2), (5; 2), (–3; 2), (–5; –2).
a) 20x + 12y = 2013;
b) 5x + 7y = 19;
c) 201x – 1999y = 12.
a) Since for any integer values of x and y left side equation is divisible by two, and the right hand is an odd number, then the equation has no solutions in integers.
Answer: there are no solutions.
b) Let’s first select some specific solution. IN in this case, it's simple, for example,
x 0 = 1, y 0 = 2.
5x 0 + 7y 0 = 19,
5(x – x 0) + 7(y – y 0) = 0,
5(x – x 0) = –7(y – y 0).
Since the numbers 5 and 7 are relatively prime, then
x – x 0 = 7k, y – y 0 = –5k.
So the general solution is:
x = 1 + 7k, y = 2 – 5k,
where k is an arbitrary integer.
Answer: (1+7k; 2–5k), where k is an integer.
c) Finding a specific solution by selection in this case is quite difficult. Let's use the Euclidean algorithm for the numbers 1999 and 201:
GCD(1999, 201) = GCD(201, 190) = GCD(190, 11) = GCD(11, 3) = GCD(3, 2) = GCD(2, 1) = 1.
Let's write this process in reverse order:
1 = 2 – 1 = 2 – (3 – 2) = 2 2 – 3 = 2 (11 – 3 3) – 3 = 2 11 – 7 3 = 2 11 – 7(190 – 11 17) =
121 11 – 7 190 = 121(201 – 190) – 7 190 = 121 201 – 128 190 =
121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.
This means that the pair (1273, 128) is a solution to the equation 201x – 1999y = 1. Then the pair of numbers
x 0 = 1273 12 = 15276, y 0 = 128 12 = 1536
is a solution to the equation 201x – 1999y = 12.
The general solution of this equation will be written in the form
x = 15276 + 1999k, y = 1536 + 201k, where k is an integer,
or, after redesignation (we use that 15276 = 1283 + 7 1999, 1536 = 129 + 7 201),
x = 1283 + 1999n, y = 129 + 201n, where n is an integer.
Answer: (1283+1999n, 129+201n), where n is an integer.
3. Solve the equation in integers:
a) x 3 + y 3 = 3333333;
b) x 3 + y 3 = 4(x 2 y + xy 2 + 1).
a) Since x 3 and y 3 when divided by 9 can only give remainders 0, 1 and 8 (see the table in the section), then x 3 + y 3 can only give remainders 0, 1, 2, 7 and 8. But the number 3333333 when divided by 9 gives a remainder of 3. Therefore, the original equation has no solutions in integers.
b) Let's rewrite the original equation in the form (x + y) 3 = 7(x 2 y + xy 2) + 4. Since cubes of integers when divided by 7 give remainders 0, 1 and 6, but not 4, then the equation is not has solutions in integers.
Answer: There are no integer solutions.
a) in prime numbers the equation x 2 – 7x – 144 = y 2 – 25y;
b) in integers the equation x + y = x 2 – xy + y 2.
a) Solve this equation as a quadratic equation with respect to the variable y. We get
y = x + 9 or y = 16 – x.
Since for odd x the number x + 9 is even, then the only pair prime numbers, which satisfies the first equality, is (2; 11).
Since x, y are simple, then from the equality y = 16 – x we have
2 x 16.2 at 16.
Using an enumeration of options, we find the remaining solutions: (3; 13), (5; 11), (11; 5), (13; 3).
Answer: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).
b) Consider this equation as a quadratic equation for x:
x 2 – (y + 1)x + y 2 – y = 0.
The discriminant of this equation is –3y 2 + 6y + 1. It is positive only for the following values of y: 0, 1, 2. For each of these values, from the original equation we obtain a quadratic equation for x, which is easily solved.
Answer: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).
5. Is there infinite number triples of integers x, y, z such that x 2 + y 2 + z 2 = x 3 + y 3 + z 3?
Let's try to select triples where y = –z. Then y 3 and z 3 will always cancel each other, and our equation will look like
x 2 + 2y 2 = x 3
or, otherwise,
x 2 (x–1) = 2y 2 .
For a pair of integers (x; y) to satisfy this condition, it is sufficient that the number x–1 be twice the square of the integer. There are infinitely many such numbers, namely, these are all numbers of the form 2n 2 +1. Substituting this number into x 2 (x–1) = 2y 2, after simple transformations we obtain:
y = xn = n(2n 2 +1) = 2n 3 +n.
All triplets obtained in this way have the form (2n 2 +1; 2n 3 +n; –2n 3 – n).
Answer: exists.
6. Find integers x, y, z, u such that x 2 + y 2 + z 2 + u 2 = 2xyzu.
The number x 2 + y 2 + z 2 + u 2 is even, therefore among the numbers x, y, z, u there is an even number of odd numbers.
If all four numbers x, y, z, u are odd, then x 2 + y 2 + z 2 + u 2 is divisible by 4, but 2xyzu is not divisible by 4 - a discrepancy.
If exactly two of the numbers x, y, z, u are odd, then x 2 + y 2 + z 2 + u 2 is not divisible by 4, but 2xyzu is divisible by 4 – again a discrepancy.
Therefore, all numbers x, y, z, u are even. Then we can write that
x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,
and the original equation will take the form
x 1 2 + y 1 2 + z 1 2 + u 1 2 = 8x 1 y 1 z 1 u 1 .
Now note that (2k + 1) 2 = 4k(k + 1) + 1 when divided by 8 gives a remainder of 1. Therefore, if all numbers x 1, y 1, z 1, u 1 are odd, then x 1 2 + y 1 2 + z 1 2 + u 1 2 is not divisible by 8. And if exactly two of these numbers are odd, then x 1 2 + y 1 2 + z 1 2 + u 1 2 is not even divisible by 4. This means
x 1 = 2x 2, y 1 = 2y 2, z 1 = 2z 2, u 1 = 2u 2,
and we get the equation
x 2 2 + y 2 2 + z 2 2 + u 2 2 = 32x 2 y 2 z 2 u 2 .
Repeating the same reasoning again, we find that x, y, z, u are divisible by 2 n for all natural n, which is possible only for x = y = z = u = 0.
Answer: (0; 0; 0; 0).
7. Prove that the equation
(x – y) 3 + (y – z) 3 + (z – x) 3 = 30
has no solutions in integers.
Let us use the following identity:
(x – y) 3 + (y – z) 3 + (z – x) 3 = 3(x – y)(y – z)(z – x).
Then the original equation can be written as
(x – y)(y – z)(z – x) = 10.
Let us denote a = x – y, b = y – z, c = z – x and write the resulting equality in the form
In addition, it is obvious that a + b + c = 0. It is easy to verify that, up to permutation, the equality abc = 10 implies that the numbers |a|, |b|, |c| are equal to either 1, 2, 5, or 1, 1, 10. But in all these cases, for any choice of signs a, b, c, the sum a + b + c is non-zero. Thus, the original equation has no integer solutions.
8. Solve equation 1 in whole numbers! + 2! + . . . +x! = y 2 .
It's obvious that
if x = 1, then y 2 = 1,
if x = 3, then y 2 = 9.
These cases correspond to next pairs numbers:
x 1 = 1, y 1 = 1;
x 2 = 1, y 2 = –1;
x 3 = 3, y 3 = 3;
x 4 = 3, y 4 = –3.
Note that for x = 2 we have 1! + 2! = 3, for x = 4 we have 1! + 2! + 3! + 4! = 33 and neither 3 nor 33 are squares of integers. If x > 5, then, since
5! + 6! + . . . + x! = 10n,
we can write that
1! + 2! + 3! + 4! + 5! + . . . +x! = 33 + 10n.
Since 33 + 10n is a number ending in 3, it is not the square of an integer.
Answer: (1; 1), (1; –1), (3; 3), (3; –3).
9. Decide the following system equations in natural numbers:
a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).
3abc > 0, then a 3 > b 3 + c 3 ;
thus we have
Adding these inequalities, we get that
Taking into account the last inequality, from the second equation of the system we obtain that
But the second equation of the system also shows that a is an even number. Thus, a = 2, b = c = 1.
Answer: (2; 1; 1)
10. Find all pairs of integers x and y satisfying the equation x 2 + x = y 4 + y 3 + y 2 + y.
Factoring both sides of this equation, we get:
x(x + 1) = y(y + 1)(y 2 + 1),
x(x + 1) = (y 2 + y)(y 2 + 1)
Such equality is possible if the left and right sides are equal to zero, or are the product of two consecutive integers. Therefore, equating certain factors to zero, we obtain 4 pairs of desired variable values:
x 1 = 0, y 1 = 0;
x 2 = 0, y 2 = –1;
x 3 = –1, y 3 = 0;
x 4 = –1, y 4 = –1.
The product (y 2 + y)(y 2 + 1) can be considered as the product of two consecutive non-zero integers only when y = 2. Therefore x(x + 1) = 30, whence x 5 = 5, x 6 = –6. This means that there are two more pairs of integers that satisfy the original equation:
x 5 = 5, y 5 = 2;
x 6 = –6, y 6 = 2.
Answer: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)
Problems without solutions
1. Solve the equation in integers:
a) xy = x + y + 3;
b) x 2 + y 2 = x + y + 2.
2. Solve the equation in integers:
a) x 3 + 21y 2 + 5 = 0;
b) 15x 2 – 7y 2 = 9.
3. Solve the equation in natural numbers:
a) 2 x + 1 = y 2;
b) 3 2 x + 1 = y 2.
4. Prove that the equation x 3 + 3y 3 + 9z 3 = 9xyz in rational numbers has a unique solution
5. Prove that the equation x 2 + 5 = y 3 in integers has no solutions.
Usually in tasks linear programming Plan coordinates are not required to be integers. However, in practice one often encounters problems in which the coordinates of optimal plans must be integers, and such problems are called problems . When solving linear programming problems using the graphical method and the simplex method, there is no guarantee that the coordinates of the optimal plan will be integers.
In some cases, results may be rounded. For example, if the optimal plan stipulates that 499683.3 cars should be produced, then it is economically justified to round the result to 499683 or even to 500000.
There are, however, problems in which such rounding can create a large error. For example, if the optimal plan stipulates that 0.67 plants should be built, then formal rounding to 0 or 1 is unacceptable.
Therefore, methods for solving linear programming problems are of great practical importance, with the help of which you can find the optimal plan, the coordinates of which are integers. Tasks integer programming are solved using exactly these methods.
If integer programming problem set in canonical form, it is formulated as follows:
find the maximum of the objective function (linear form)
under a system of restrictions
Thus, the task integer programming and the corresponding linear programming problem differ only in the condition that the unknowns are integer.
Like linear programming problems, integer programming problems require that the optimal plan maximize the objective function (linear form).
Gomori method for solving integer programming problems
Gomori method is universal method solving integer programming problems, with the help of which, after a finite number of iterations, you can find the optimal plan or make sure that the problem has no solutions. However, the practical value of Gomori's method is very limited, since quite a lot of iterations need to be performed when solving problems.
When solving integer programming problems using the Gomori method, subsets that do not contain integer plans are gradually removed from the set of optimal plans for a linear programming problem.
At the first iteration, you need to solve a linear programming problem using the simplex method. If the unknowns found satisfy the integer requirement, then the integer programming problem is solved. If among the unknown unknowns at least one is a fractional number, then one should compose additional condition(how to compose it - more on that below) and attach it to the system of constraints of the integer programming problem. Thus, from the set of plans, the subset that does not contain integer plans is removed. If the optimal plan of the problem augmented in this way is integer, then the integer programming problem is solved. The solution process continues until at some iteration an integer optimal plan is found or it can be verified that the problem has no solution.
Now let's talk about how to create the mentioned additional condition. It, an additional condition, is obtained from one of the equations of the system of restrictions from the coefficients of the unknowns and the unknowns themselves according to the formula
, where in curly brackets are the fractional parts of the free term and coefficients of the unknowns, respectively.
For example, from simplex table we get the following equation:
.
We obtain the fractional part of the free term by subtracting its integer part from the number itself as follows:
Similarly, we obtain the fractional parts of the coefficients for the unknowns:
(at x3 ),
(at x4
).
A general rule finding fractional parts is as follows: whole part real number a The largest integer is called [ a], not exceeding a; fractional part of a real number a called difference {a} = a - [a] the number itself a and its whole part [ a] .
.
In our example, using the above formula, the following equation is obtained:
.
Example 1. Solve the following integer programming problem using the Gomori method. Find the maximum objective function
under a system of restrictions
Solution. We solve the problem using the simplex method. Since we have lesson on solving linear programming problems using the simplex method, the method itself will not be explained here, but only simplex tables will be given.
Additional unknowns x3 And x4 Let's take it as basic. Let us express the basic unknowns and the goal function in terms of non-basic variables:
Let's create a simplex table from the coefficients:
We compile the following tables until we obtain the optimal plan:
| Table 3 | ||||
| Basic unknowns | Free members | Free unknowns | Auxiliary coefficients | |
| X3 | X4 | |||
| X1 | 19/7 | 4/7 | -1/7 | -1/2 |
| X2 | 4/7 | -1/7 | 2/7 | |
| WITH | 65/7 | 10/7 | 1/7 | 1/2 |
From Table 3 we find the optimal plan 
. Since this optimal plan does not satisfy the integer condition, we need to create an additional condition. Fractional part coordinates is a number, and the fractional part of a coordinate is a number.
The first equation based on the table will be written as follows:
.
Having determined the fractional parts of the coefficients for the unknowns and free terms, we obtain the following additional condition:
or, by introducing an additional variable,
.
We get new line in the simplex table obtained from Table 3 and adding the coefficients from the equation just obtained:
| Table 4 | ||||
| Basic unknowns | Free members | Free unknowns | Auxiliary coefficients | |
| X3 | X4 | |||
| X1 | 19/7 | 4/7 | -1/7 | -1/2 |
| X2 | 4/7 | -1/7 | 2/7 | |
| X5 | -5/7 | -4/7 | -6/7 | |
| WITH | 65/7 | 10/7 | 1/7 | 1/2 |
We complete the simplex method step and get the table:
| Table 5 | ||||
| Basic unknowns | Free members | Free unknowns | Auxiliary coefficients | |
| X3 | X4 | |||
| X1 | 17/6 | 2/3 | -1/6 | 1/7 |
| X2 | 1/3 | -1/3 | 1/3 | -2/7 |
| X4 | 5/6 | 2/3 | -7/6 | |
| WITH | 55/6 | 4/3 | 1/6 | -1/7 |
We received the optimal plan 
. This plan, like the previous one, does not satisfy the integer condition. Therefore, an additional condition is again required. In this case, you can use the first or third equation. We get the following additional condition:
.
Let's create the following table:
| Table 6 | ||||
| Basic unknowns | Free members | Free unknowns | Auxiliary coefficients | |
| X3 | X4 | |||
| X1 | 17/6 | 2/3 | -1/6 | 1/7 |
| X2 | 1/3 | -1/3 | 1/3 | -2/7 |
| X4 | 5/6 | 2/3 | -7/6 | |
| X6 | -5/6 | -2/3 | -5/6 | |
| WITH | 55/6 | 4/3 | 1/6 | -1/7 |
Optimal plan 
we get from the following final table:
| Table 7 | ||||
| Basic unknowns | Free members | Free unknowns | Auxiliary coefficients | |
| X3 | X6 | |||
| X1 | 3 | 4/5 | -1/5 | 1/6 |
| X2 | 0 | -3/5 | 2/5 | -1/3 |
| X4 | 2 | 8/5 | -7/5 | 7/6 |
| X5 | 1 | 4/5 | -6/5 | |
| WITH | 9 | 6/5 | 1/5 | -1/6 |
Since the found optimal plan satisfies the integer condition, the integer programming problem is solved. Coordinates x5 And x6 can be ignored, since the initial conditions of the problem contain only four unknowns. Therefore, the final optimal plan will be written as follows:
,
and the maximum of the goal function is 9.
Branch and bound method for solving integer programming problems
The branch and bound method is convenient for solving integer programming problems in which the number of unknowns is small or the integer requirements do not apply to all unknowns. The essence of the branch and bound method is that for those unknowns to which the integer requirement applies, it is necessary to determine the boundaries within which the values of these unknowns may lie. Then the corresponding linear programming problems are solved.
Specifying the boundaries within which the values of the unknowns must lie in an integer programming problem can be written as follows:
In practice, in many cases, the boundaries of the unknown values are already included in the system of constraints of the integer programming problem, or they can be determined based on the economic content of the problem. Otherwise, we can assume that the lower bound is , and the upper bound is , where M- a fairly large positive number.
How the branch and bound method allows you to refine boundaries acceptable values unknown?
First, a linear programming problem corresponding to an integer programming problem is solved, say, using the simplex method. Let the optimal plan in this problem be found and the value of any of its coordinates be a fractional number. Then you will need to create two new linear programming problems. How to do it?
Let us denote the integer part of the coordinate as . In one of the new linear programming problems lower limit the coordinate value will be a number, that is, the integer part of the coordinate value increased by one. It will be written as follows:
.
In another new task linear programming, the upper bound of the coordinate value will be the integer part of the coordinate value itself. It will be written like this:
Thus, two new problems “branched” from the first linear programming problem, in which the boundaries of the permissible values of one unknown changed. When solving each of these problems, three cases are possible:
- the optimal plan is not an integer,
- the optimal plan is integer,
- the problem has no solutions.
Only in the first case is it possible to “branch” new tasks in the manner shown above. In the second and third cases, the “branching” stops.
At each iteration of solving an integer programming problem, one problem is solved. Let's introduce the concept: a list of linear programming problems to be solved. From the list, select the problem to be solved at the corresponding iteration. At further iterations, the list changes, since solved problems are no longer included in it, and instead of them, new tasks that “branched off” from previous tasks are included in the list.
In order to limit the “branching”, that is, to reduce the number of problems to be solved, at each iteration it is necessary to determine the lower limit of the maximum value of the objective function. This is done as follows:
According to the algorithm for solving an integer programming problem using the branch-and-bound method, on each p The th iteration requires 4 steps.
Example 2. Solve the following integer programming problem using the branch and bound method. Find the maximum of the objective function
under a system of restrictions
Solution. Let us assume that the following boundaries of the optimal values of the unknowns are given or determined:
.
Since the task is given in normal form, it has an integer design and a lower bound on the maximum value of the objective function.
The list of tasks to be solved includes the 1st task:
Iteration 1.
Step 1. By using simplex method the solution to the 1st problem was obtained:
Since the found plan is not integer, step 4 follows.
Step 4. Since the optimal plan has a fractional coordinate of 1.2, then . Applying the bounds on the values of the unknowns of the 1st problem, we obtain new problems. In the 2nd problem, the lower bound for is , and in the 3rd problem, the upper bound for is .
6 answers
Follow this example: suppose the equations are:
7 = x + 3y + 4z + 9w 12 = 4x + 2y + 3z + 7w
There are 2 equations and 4 unknowns. You can set 2 of the unknowns as parameters, so the system will have as many equations as there are unknowns:
7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y
We will use x and y as unknowns. It can be solved and leave w and z as parameters in the linear solution:
X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10
Now you need to make the numerators divisible by 10, the denominator. If there is a solution, you can check all parameters from 1 to 10.
In general, you do this:
- Choose the parameters so that there are as many unknowns as the equations. Try to leave the unknowns that generate the smallest absolute value for the determinant (in the example it was 10, but choosing y and z would be better since it would be |det|=3)
- Decide linear system and create a response depending on the parameters
- Check the parameter values from 1 to absolute value det (if there is a solution, you will find it at this point) until there is an integer solution for all unknowns (which is why you choose the smallest determinant value before) and check if it is positive (this was not illustrated in the example).
Sorry if he is brute force on last step, but at least it is possible to minimize the test range. May be The best way solve the final system of Diophantine equations, but I don't know any method.
EDIT1
There is a method to avoid brute forcing the last part. Again, in the example you need to do:
22 = 3w + z (congruent, mod 10) 16 = 29w + 13z (congruent, mod 10)
Application of the module:
2 = 3w + z (congruent, mod 10) 6 = 9w + 3z (congruent, mod 10)
You can make the congruence system triangular (Gaussian elimination) by multiplying the congruence with its inverse modulo 10 and summing to others. The inverse of 9 modulo 10 is -1, so we multiply the last congruence:
2 = 3w + z (congruent, mod 10) -6 = -9w + -3z (congruent, mod 10)
Equivalent:
2 = 3w + z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)
Then multiply by -3 and add to the first:
2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)
Equivalent:
10 = -20z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)
Then you solve from top to bottom (this example seems to be true for any value of z). There might be a certain degree freedom if you have more parameters than congruences, but they are equivalent and you can set the redundant parameters to any value, preferably the smallest value of 1.
Let me know if there's anything else that's unclear!
If I understand the problem correctly, you have multiple packages, each with different postage. You want to pay this postage from the pool of stamps you have. You can solve the problem with whole programming. The solution below solves for all packages at once. You will have a number of variables equal to numPackages * numStampDenominations (probably inconvenient for large quantity packages).
The equality constraint looks like Aeqx = beq. The Aeq matrix for two packages with four brands (numVarsnumPackages) looks like this:
21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50
The first row is the constraint coefficients (stamp values) for batch 1. The non-zero coefficients are the stamp values. The null variable associated with other packages is not cared for.
The second set of constraints (inequality) concerns the pool of brands that I have. The inequality constraint looks like A * x = b. Matrix A for 4 stamps and 8 variables (numPackages * numStampDenominations) looks like this:
1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20
The cost function is f"*x, which represents the total number of dies. Its coefficients are simply units, specified as a column vector.
A script is executed in Matlab that solves the problem in the manner described. It will probably be formulated in much the same way in the octaves GNU offers, similar to Matlab. Matlab or Octave may not be the right solution for you, but they at least tell you what works and give you a sandbox to develop a solution.
% The value of each stamp available as a 4x1 matrix sv = [.21; .68; .47; .01]; % The number of each stamp available as a 4x1 matrix sq = ; % Number of demonstrations m = size(sv, 1); % The postage required for each package as a 4x1 matrix % -- probably read from a file postage = [.89;.50;1.01;.47;.47]; % Number of packages -- just a count of the postage rows packageCount = size(postage, 1); % Number of variables is m*packageCount numVar = m*packageCount; % lower bound -- zero stamps of a given denomination lb = zeros(numVar,1); % upper bound -- use constraints for upper bound ub = ; % The cost function -- minimize the number of stamps used % min(f"*x) f = ones(numVar,1); % integer constraints intcon = 1:numVar; % Construct postage constraint matrix Aeq = zeros(numVar, packageCount ); for i = 1:packageCount first = i*m - 3; last = first + 3; Aeq(first:last,i) = sv(:); end % Construct stamp count constraint matrix A = zeros(numVar, m ); for r = 1:m for j = 1:m c = (j-1)*m + 1; A(c,r) = 1; end end x = intlinprog(f, intcon, A", b, Aeq ", beq, lb, ub)
I'd try the following approach (note that I've never had to deal with this problem, so take this answer as an attempt to solve the problem with you instead of an actual analytical answer).
You simply find solutions as if it were a normal system, so you can find infinitely many solutions:
Example:
Y=x+3
then the real pair of numbers (2,5) is a possible real solution for this system, once you have infinitely many solutions, you simply limit the subset of solutions that are produced by integers.
Of course you have limitations, in our case the solution only has 1 free variable, so we can write all solutions like this:
(x, x+3)
Astonishment:
If there is an irrational number in there somewhere, there are no integer solutions:
(x, x+pi) => neither 1st or 2nd number here can be whole at the same time
So you can find integer solutions if and only if your "infinitely many solutions" are limited to integers or rational numbers.
Let's say you have the following vector:
(3x, (2/5)y, y, x, x+y)
Then the whole solution could be:
X=3 y=10/2
If you feel that the answer is not suitable for you, just say: I will delete it so as not to receive bonus points.
In a number of economic problems related to linear programming problems, the elements of the solution must be expressed in integers. In these problems, the variables mean the number of units of indivisible products.
The integer programming problem is formulated as follows:
Find such a solution plan X=(x 1 , X 2 ,…, X n ) , in which the linear function takes a maximum or minimum value subject to restrictions
the problem is solved using linear programming methods. If the variables of the optimal solution turn out to be non-integer, then using cutting methods or the method of enumerating integer solutions.
Branch and Bound Concepts .
The branch and bound method consists of an orderly search of options and consideration of only those that turn out to be promising according to certain criteria, and discarding unpromising options.
The branch and bound method consists of the following: the set of feasible solutions (plans) is divided in some way into subsets, each of which is again divided into subsets in the same way. The process continues until then. The optimal integer solution to the original problem has not yet been obtained.
The name of the branch and bound method comes from the fact that in the process of solving the problem is successively “branched”, replaced by simpler ones. The solution process can be continued in the form of a tree, the numbers in the nodes (vertices) of which indicate the plan for solving the problem (the desired variables).
5. 2 Graphical method for solving integer programming problems.
If there are two variables in a linear programming problem, and there are inequalities in the constraint system, it can be solved graphically without the requirement of integer variables.
If the optimal solution to this problem is integer, then it is optimal for the original problem.
If the resulting optimal solution is not integer, then an additional linear constraint is constructed. It has the following properties:
It should be linear;
Should cut off the found optimal non-integer plan;
Should not truncate any integer plan.
Algorithm for graphical solution of the problem
integer programming.
Construct a coordinate system x 1 0x 2 and select a scale.
Find the region of feasible solutions (ADS) of the system of constraints of the problem.
Construct an objective function that is a level line and indicate the normal direction on it.
Move the line of the objective function in the direction of the normal through the ODR so that it changes from a secant to becoming tangent to the ODF and passes through the point furthest from the origin. This point will be the extremum point, i.e. solving the problem.
If it turns out that the line of the objective function is parallel to one of the sides of the ODP, then in this case the extremum is reached at all points of the corresponding side, and the linear programming problem will have an infinite number of solutions.
Find the coordinates, extremum points and the value of the objective function in it. If the obtained values are not integer, then proceed to the next step.
Select an area with integer values at these coordinates.
Determine new coordinates and build a graph.
Find points with integer values of the desired variables, substitute them into the equation of the objective function and find its value. The maximum of the obtained values of the objective function will be the solution to the problem.
