Уравнения в целых числах. Решение задач целочисленного программирования: методы и примеры

В ряде экономических задач, относящихся к задачам линейного программирования, элементы решения должны выражаться в целых числах. В этих задачах переменные означают количество единиц неделимой продукции.

Задача целочисленного программирования формулируется следующим образом:

Найти такое решение план Х=(х 1 , х 2 ,…, х n ) , при котором линейная функция принимает максимальное или минимальное значение при ограничениях

задача решается методами линейного программирования. В случае если переменные оптимального решения оказываются нецелочисленными, то, применяя методы отсечения или метод перебора целочисленных решений.

Понятия о методе ветвей и границ .

Метод ветвей и границ заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор. Пока не получено оптимальное целочисленное решение исходной задачи.

Название метода ветвей и границ исходит из того, что в процессе решения задача последовательно «ветвится», заменяясь более простыми. Процесс решения можно продолжать в виде дерева, цифры в узлах (вершинах) которого обозначают план решения задачи (искомые переменные).

5. 2 Графический метод решения задач целочисленного программирования.

При наличии в задаче линейного программирования двух переменных, а в системе ограничения – неравенств, она может быть решена графическим методом без требований целочисленных переменных.

Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.

Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:

Оно должно быть линейным;

Должно отсекать найденный оптимальный не целочисленный план;

Не должно отсекать ни одного целочисленного плана.

Алгоритм графического решения задачи

целочисленного программирования.

Построить систему координат x 1 0х 2 и выбрать масштаб.

Найти область допустимых решений (ОДР) системы ограничений задачи.

Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

Переместить линию целевой функции по направлению нормали через ОДР, чтобы она из секущей стала касательной к ОДР и проходила через наиболее удаленную от начала координат точку. Эта точка будет являться точкой экстремума, т.е. решением задачи.

Если окажется, что линия целевой функции параллельна одной из сторон ОДР, то в этом случае экстремум достигается во всех точках соответствующей стороны, а задача линейного программирования будет иметь бесчисленное множество решений.

Найти координаты, точки экстремума и значение целевой функции в ней. Если полученные значения не целочисленные, то перейти к следующему шагу.

Выделить у этих координат область с целочисленными значениями.

Определить новые координаты и построить граф.

Найти точки с целыми значениями искомых переменных, подставить в уравнение целевой функции и найти её значение. Максимальное из полученных значений целевой функции и будет решением задачи.

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми , в честь древнегреческого математика , который исследовал некоторые типы таких уравнений ещё до нашей эры.

Современной постановкой диофантовых задач мы обязаны французскому математику . Именно он поставил перед европейскими математиками вопрос о решении неопределённых уравнений только в целых числах. Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

не имеет ненулевых рациональных решений для всех натуральных n > 2.

Теоретический интерес к уравнениям в целых числах достаточно велик, так как эти уравнения тесно связаны со многими проблемами теории чисел.

В 1970 году ленинградский математик Юрий Владимирович Матиясевич доказал, что общего способа, позволяющего за конечное число шагов решать в целых числах произвольные диофантовы уравнения, не существует и быть не может. Поэтому следует для разных типов уравнений выбирать собственные методы решения.

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

способ перебора вариантов;

применение алгоритма Евклида;

представление чисел в виде непрерывных (цепных) дробей;

разложения на множители;

решение уравнений в целых числах как квадратных (или иных) относительно какой-либо переменной;

метод остатков;

метод бесконечного спуска.

Задачи с решениями

1. Решить в целых числах уравнение x 2 – xy – 2y 2 = 7.

Запишем уравнение в виде (x – 2y)(x + y) = 7.

Так как х, у – целые числа, то находим решения исходного уравнения, как решения следующих четырёх систем:

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.

Решив эти системы, получаем решения уравнения: (3; –2), (5; 2), (–3; 2) и (–5; –2).

Ответ: (3; –2), (5; 2), (–3; 2), (–5; –2).

а) 20х + 12у = 2013;

б) 5х + 7у = 19;

в) 201х – 1999у = 12.

а) Поскольку при любых целых значениях х и у левая часть уравнения делится на два, а правая является нечётным числом, то уравнение не имеет решений в целых числах.

Ответ: решений нет.

б) Подберём сначала некоторое конкретное решение. В данном случае, это просто, например,

x 0 = 1, y 0 = 2.

5x 0 + 7y 0 = 19,

5(х – x 0) + 7(у – y 0) = 0,

5(х – x 0) = –7(у – y 0).

Поскольку числа 5 и 7 взаимно простые, то

х – x 0 = 7k, у – y 0 = –5k.

Значит, общее решение:

х = 1 + 7k, у = 2 – 5k,

где k – произвольное целое число.

Ответ: (1+7k; 2–5k), где k – целое число.

в) Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201:

НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1.

Запишем этот процесс в обратном порядке:

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.

Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел

x 0 = 1273·12 = 15276, y 0 = 128·12 = 1536

является решением уравнения 201х – 1999у = 12.

Общее решение этого уравнения запишется в виде

х = 15276 + 1999k, у = 1536 + 201k, где k – целое число,

или, после переобозначения (используем, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201),

х = 1283 + 1999n, у = 129 + 201n, где n – целое число.

Ответ: (1283+1999n, 129+201n), где n – целое число.

3. Решить в целых числах уравнение:

а) x 3 + y 3 = 3333333;

б) x 3 + y 3 = 4(x 2 y + xy 2 + 1).

а) Так как x 3 и y 3 при делении на 9 могут давать только остатки 0, 1 и 8 (смотрите таблицу в разделе ), то x 3 + y 3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

б) Перепишем исходное уравнение в виде (x + y) 3 = 7(x 2 y + xy 2) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

а) в простых числах уравнение х 2 – 7х – 144 = у 2 – 25у;

б) в целых числах уравнение x + y = x 2 – xy + y 2 .

а) Решим данное уравнение как квадратное относительно переменной у. Получим

у = х + 9 или у = 16 – х.

Поскольку при нечётном х число х + 9 является чётным, то единственной парой простых чисел, которая удовлетворяет первому равенству, является (2; 11).

Так как х, у – простые, то из равенства у = 16 – х имеем

2 х 16, 2 у 16.

С помощью перебора вариантов находим остальные решения: (3; 13), (5; 11), (11; 5), (13; 3).

Ответ: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

б) Рассмотрим данное уравнение как квадратное уравнение относительно x:

x 2 – (y + 1)x + y 2 – y = 0.

Дискриминант этого уравнения равен –3y 2 + 6y + 1. Он положителен лишь для следующих значений у: 0, 1, 2. Для каждого из этих значений из исходного уравнения получаем квадратное уравнение относительно х, которое легко решается.

Ответ: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Существует ли бесконечное число троек целых чисел x, y, z таких, что x 2 + y 2 + z 2 = x 3 + y 3 + z 3 ?

Попробуем подбирать такие тройки, где у = –z. Тогда y 3 и z 3 будут всегда взаимно уничтожаться, и наше уравнение будет иметь вид

x 2 + 2y 2 = x 3

или, иначе,

x 2 (x–1) = 2y 2 .

Чтобы пара целых чисел (x; y) удовлетворяла этому условию, достаточно, чтобы число x–1 было удвоенным квадратом целого числа. Таких чисел бесконечно много, а именно, это все числа вида 2n 2 +1. Подставляя в x 2 (x–1) = 2y 2 такое число, после несложных преобразований получаем:

y = xn = n(2n 2 +1) = 2n 3 +n.

Все тройки, полученные таким образом, имеют вид (2n 2 +1; 2n 3 +n; –2n 3 – n).

Ответ: существует.

6. Найдите такие целые числа x, y, z, u, что x 2 + y 2 + z 2 + u 2 = 2xyzu.

Число x 2 + y 2 + z 2 + u 2 чётно, поэтому среди чисел x, y, z, u чётное число нечётных чисел.

Если все четыре числа x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 делится на 4, но при этом 2xyzu не делится на 4 – несоответствие.

Если ровно два из чисел x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 не делится на 4, а 2xyzu делится на 4 – опять несоответствие.

Поэтому все числа x, y, z, u чётны. Тогда можно записать, что

x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,

и исходное уравнение примет вид

x 1 2 + y 1 2 + z 1 2 + u 1 2 = 8x 1 y 1 z 1 u 1 .

Теперь заметим, что (2k + 1) 2 = 4k(k + 1) + 1 при делении на 8 даёт остаток 1. Поэтому если все числа x 1 , y 1 , z 1 , u 1 нечётны, то x 1 2 + y 1 2 + z 1 2 + u 1 2 не делится на 8. А если ровно два из этих чисел нечётно, то x 1 2 + y 1 2 + z 1 2 + u 1 2 не делится даже на 4. Значит,

x 1 = 2x 2 , y 1 = 2y 2 , z 1 = 2z 2 , u 1 = 2u 2 ,

и мы получаем уравнение

x 2 2 + y 2 2 + z 2 2 + u 2 2 = 32x 2 y 2 z 2 u 2 .

Снова повторив те же самые рассуждения, получим, что x, y, z, u делятся на 2 n при всех натуральных n, что возможно лишь при x = y = z = u = 0.

Ответ: (0; 0; 0; 0).

7. Докажите, что уравнение

(х – у) 3 + (y – z) 3 + (z – x) 3 = 30

не имеет решений в целых числах.

Воспользуемся следующим тождеством:

(х – у) 3 + (y – z) 3 + (z – x) 3 = 3(х – у)(y – z)(z – x).

Тогда исходное уравнение можно записать в виде

(х – у)(y – z)(z – x) = 10.

Обозначим a = x – y, b = y – z, c = z – x и запишем полученное равенство в виде

Кроме того очевидно, a + b + c = 0. Легко убедиться, что с точностью до перестановки из равенства abc = 10 следует, что числа |a|, |b|, |c| равны либо 1, 2, 5, либо 1, 1, 10. Но во всех этих случаях при любом выборе знаков a, b, c сумма a + b + c отлична от нуля. Таким образом, исходное уравнение не имеет решений в целых числах.

8. Решить в целых числах уравнение 1! + 2! + . . . + х! = у 2 .

Очевидно, что

если х = 1, то у 2 = 1,

если х = 3, то у 2 = 9.

Этим случаям соответствуют следующие пары чисел:

х 1 = 1, у 1 = 1;

х 2 = 1, у 2 = –1;

х 3 = 3, у 3 = 3;

х 4 = 3, у 4 = –3.

Заметим, что при х = 2 имеем 1! + 2! = 3, при х = 4 имеем 1! + 2! + 3! + 4! = 33 и ни 3, ни 33 не являются квадратами целых чисел. Если же х > 5, то, так как

5! + 6! + . . . + х! = 10n,

можем записать, что

1! + 2! + 3! + 4! + 5! + . . . + х! = 33 + 10n.

Так как 33 + 10n – число, оканчивающееся цифрой 3, то оно не является квадратом целого числа.

Ответ: (1; 1), (1; –1), (3; 3), (3; –3).

9. Решите следующую систему уравнений в натуральных числах:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0, то a 3 > b 3 + c 3 ;

таким образом имеем

Складывая эти неравенства, получим, что

С учётом последнего неравенства, из второго уравнения системы получаем, что

Но второе уравнение системы также показывает, что а – чётное число. Таким образом, а = 2, b = c = 1.

Ответ: (2; 1; 1)

10. Найти все пары целых чисел х и у, удовлетворяющих уравнению х 2 + х = у 4 + у 3 + у 2 + у.

Разложив на множители обе части данного уравнения, получим:

х(х + 1) = у(у + 1)(у 2 + 1),

х(х + 1) = (у 2 + у)(у 2 + 1)

Такое равенство возможно, если левая и правая части равны нулю, или представляют собой произведение двух последовательных целых чисел. Поэтому, приравнивая к нулю те или иные множители, получим 4 пары искомых значений переменных:

х 1 = 0, у 1 = 0;

х 2 = 0, у 2 = –1;

х 3 = –1, у 3 = 0;

х 4 = –1, у 4 = –1.

Произведение (у 2 + у)(у 2 + 1) можно рассматривать как произведение двух последовательных целых чисел, отличных от нуля, только при у = 2. Поэтому х(х + 1) = 30, откуда х 5 = 5, х 6 = –6. Значит, существуют ещё две пары целых чисел, удовлетворяющих исходному уравнению:

х 5 = 5, у 5 = 2;

х 6 = –6, у 6 = 2.

Ответ: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Задачи без решений

1. Решить в целых числах уравнение:

а) ху = х + у + 3;

б) х 2 + у 2 = х + у + 2.

2. Решить в целых числах уравнение:

а) х 3 + 21у 2 + 5 = 0;

б) 15х 2 – 7у 2 = 9.

3. Решить в натуральных числах уравнение:

а) 2 х + 1 = у 2 ;

б) 3·2 х + 1 = у 2 .

4. Доказать, что уравнение х 3 + 3у 3 + 9z 3 = 9xyz в рациональных числах имеет единственное решение

5. Доказать, что уравнение х 2 + 5 = у 3 в целых числах не имеет решений.

Обычно в задачах линейного программирования не требуется, чтобы координаты плана были целыми числами. Однако в практике часто приходится сталкиваться с задачами, в которых координаты оптимальных планов должны быть целыми числами, и такие задачи называются задачами . При решении задач линейного программирования графическим методом и симплекс-методом нет гарантий, что координаты оптимального плана будут целыми числами.

В некоторых случаях допускается округление результатов. Например, если в оптимальном плане предусмотрено, что следует произвести 499683,3 автомашины, то экономически обосновано округление результата до 499683 или даже до 500000.

Существуют однако задачи, в которых подобное округление может создать большую ошибку. Например, если в оптимальном плане предусмотрено, что следует построить 0,67 заводов, то формальное округление до 0 или 1 недопустимо.

Поэтому большое практическое значение имеют методы решения задач линейного программирования, с помощью которых можно найти оптимальный план, координаты которого - целые числа. Задачи целочисленного программирования решаются именно такими методами.

Если задача целочисленного программирования задана в канонической форме, она формулируется следующим образом:

найти максимум функции цели (линейной формы)

при системе ограничений

Таким образом, задача целочисленного программирования и соответствующая задача линейного программирования отличаются только условием целочисленности неизвестных.

Как и в задачах линейного программирования, в задачах целочисленного программирования требуется, чтобы оптимальный план максимизировал функцию цели (линейную форму).

Метод Гомори решения задач целочисленного программирования

Метод Гомори является универсальным методом решения задач целочисленного программирования, с помощью которого после конечного числа итераций можно найти оптимальный план или убедиться в том, что задача не имеет решений. Однако практическая ценность метода Гомори весьма ограничена, так как при решении задач нужно выполнить довольно много итераций.

При решении задач целочисленного программирования методом Гомори из множества оптимальных планов задачи линейного программирования постепенно удаляются подмножества, которые не содержат целочисленных планов.

На первой итерации симплекс-методом нужно решить задачу линейного программирования. Если найденные неизвестные удовлетворяют требованию целочисленности, то задача целочисленного программирования решена. Если же среди найденных неизвестных хотя бы одна является дробным числом, то тогда следует составить дополнительное условие (как его составлять - об этом чуть ниже) и присоединить его к системе ограничений задачи целочисленного программирования. Таким образом, из множества планов удаляется подмножество, не содержащее целочисленных планов. Если оптимальный план дополненной таким образом задачи является целочисленным, то задача целочисленного программирования решена. Процесс решения продолжается то тех пор, пока на какой-либо итерации не будет найден целочисленный оптимальный план или можно убедиться, что задача не имеет решения.

Теперь о том, как составлять упомянутое дополнительное условие. Оно, дополнительное условие, получается из одного из уравений системы ограничений из коэффициентов при неизвестных и самих неизвестных по формуле

, где в фигурных скобках - дробные части соответственно свободного члена и коэффициентов при неизвестных.

Например, из симплексной таблицы получаем такое уравнение:

.

Дробную часть свободного члена получаем, вычитая из самого числа его целую часть следующим образом:

Аналогично получаем дробные части коэффициентов при неизвестных:

(при x 3 ),

(при x 4 ).

А общее правило нахождения дробных частей таково: целой частью вещественного числа a называется самое большое целое число [a ] , не превыщающее a ; дробной частью вещественного числа a называется разность {a } = a - [a ] самого числа a и его целой части [a ] .

.

В нашем примере по приведённой выше формуле получается следующее уравнение:

.

Пример 1. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Решаем задачу симплекс-методом. Поскольку у нас есть урок по решению задач линейного программирования симплекс-методом , сам метод объясняться здесь не будет, а будут приведены лишь симплексные таблицы.

Дополнительные неизвестные x 3 и x 4 примем за базисные. Выразим базисные неизвестные и функцию цели через неосновные переменные:

Из коэффициентов составим симплексную таблицу:

Составляем следующие таблицы до получения оптимального плана:

Таблица 3
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
С	65/7	10/7	1/7	1/2

Из таблицы 3 находим оптимальный план . Поскольку этот оптимальный план не удовлетворяет условию целочисленности, нам нужно составить дополнительное условие. Дробной частью координаты является число , а дробной частью координаты - число .

Первое уравнение на основании таблицы запишется так:

.

Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие:

или, введя добавочную переменную ,

.

Получаем новую строку в симплексной таблице, полученной из таблицы 3 и добавления коэффициентов из только что полученного уравнения:

Таблица 4
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		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
С	65/7	10/7	1/7	1/2

Совершаем шаг симплекс-метода и получаем таблицу:

Таблица 5
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		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
С	55/6	4/3	1/6	-1/7

Получили оптимальный план . Этот план, как и предыдущий, не удовлетворяет условию целочисленности. Поэтому вновь требуется составить дополнительное условие. В данном случае можно использовать первое или третье уравнение. Получится следующее дополнительное условие:

.

Составляем следующую таблицу:

Таблица 6
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		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
С	55/6	4/3	1/6	-1/7

Оптимальный план получаем из следующей, завершающей таблицы:

Таблица 7
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		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
С	9	6/5	1/5	-1/6

Так как найденный оптимальный план удовлетворяет условию целочисленности, задача целочисленного программирования решена. Координаты x 5 и x 6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так:

,

а максимум функции цели равен 9.

Метод ветвей и границ решения задач целочисленного программирования

Методом ветвей и границ удобно решать такие задачи целочисленного программирования, в которых число неизвестных невелико либо требования целочисленности относятся не ко всем неизвестным. Суть метода ветвей и границ состоит в том, что для тех неизвестных, к которым относится требование целочисленности, нужно определить границы, в которых могут находиться значения этих неизвестных. Затем решаются соответствующие задачи линейного программирования.

Задание границ, в которых должны находиться значения неизвестных в задаче целочисленного программирования, можно записать так:

На практике во многих случаях границы значений неизвестных уже включены в систему ограничений задачи целочисленного программирования или же их можно определить исходя из экономического содержания задачи. Иначе можно принять, что нижняя граница , а верхняя граница , где M - достаточно большое положительное число.

Как метод ветвей и границ позволяет уточнить границы допустимых значений неизвестных?

Сначала решается, допустим, симплекс-методом задача линейного программирования, соответствующая задаче целочисленного программирования. Пусть найден оптимальный план в этой задаче и значением какой-либо его координаты является дробное число. Тогда потребуется составить две новые задачи линейного программирования. Как это сделать?

Обозначим целую часть координаты в виде . В одной из новых задач линейного программирования нижней границей значения координаты будет число , то есть целая часть значения координаты, увеличенная на единицу. Это запишется следующим образом:

.

В другой новой задаче линейного программирования верхней границей значения координаты будет сама целая часть значения координаты . Это запишется так:

Таким образом, от первой задачи линейного программирования "ответвились" две новые задачи, в которых в которых изменились границы допустимых значений одной неизвестной. При решении каждой из этих задач возможны три случая:

• оптимальный план не является целочисленным,
• оптимальный план является целочисленным,
• задача не имеет решений.

Лишь в первом случае возможно "ответвление" новых задач способом, показанным выше. Во втором и третьем случае "ветвление" прекращается.

На каждой итерации решения задачи целочисленного программирования решается одна задача. Введём понятие: список решаемых задач линейного программирования. Из списка следует выбрать задачу, решаемую на соответствующей итерации. На дальнейших итерациях список меняется, так как решённые задачи в него уже не входят, а вместо них в список включаются новые задачи, которые "ответвились" от предыдущих задач.

Для того, чтобы ограничить "ветвления", то есть уменьшить число решаемых задач, на каждой итерации следует определить нижнюю границу максимального значения целевой функции. Это делается следующим образом:

Согласно алгоритму решения задачи целочисленного программирования методом ветвей и границ, на каждой p -й итерации требуется сделать 4 шага.

Пример 2. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции

при системе ограничений

Решение. Допустим, что заданы или определены следующие границы оптимальных значений неизвестных:

.

Так как задача задана в нормальной форме, она имеет целочисленный план и нижнюю границу максимального значения целевой функции .

В списке решаемых задач - 1-я задача:

Итерация 1.

Шаг 1. С помощью симплекс-метода получено решение 1-й задачи:

Так как найденный план не является целочисленным, следует шаг 4.

Шаг 4. Так как оптимальный план имеет дробную координату 1,2, то и . Применяя границы значений неизвестных 1-й задачи, получаем новые задачи. Во 2-й задаче нижней границей для является , а в 3-й задаче верхней границей для является .