Целочисленные задачи линейного программирования

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

Правильное отсечение
x1
Правильным отсечением называется гиперплоскость, которая отсекает решение нецелочисленной задачи от ОДР, не отсекая при этом ни одной точки с целыми координатами.

Метод отсечений
Метод отсечений был разработан в конце 1950-х годов Гомори для решения целочисленных линейных задач с помощью симплекс-метода.
Целой частью числа называется число, которое является максимальным из целых чисел не больше .
Примеры:
Дробной частью числа называется число , которое находится по формуле
Примеры:

Отсечение Гомори
Если получена симплекс-таблица нецелочисленного решения, то по отсечению Гомори определяется строка вида:
,
где максимально по всем строкам и
После этого в симплекс-таблицу добавляется строка вида:
.
Эта строка и определяет уровень правильного отсечения Гомори. После этого ищется оптимальный план. Если некоторые переменные будут дробными, то процедура повторяется.

Задача о раскрое
Имеются бревна длиной 3 метра. Из них требуется сделать не менее 50 заготовок длиной 1,2 метра и не менее 81 заготовки длиной 0,9 метра.
Какое наименьшее число бревен потребуется и какими способами их надо для этого распилить?
Рассмотрим способы распила бревен:
1,2 м и 1,2 м;
1,2 м, 0,9 м и 0,9 м;
0,9 м, 0,9 м и 0,9 м.

Задача о раскрое
Обозначим - количество бревен, распиливаемых -м
способом, Тогда задача примет вид

Запишем симплекс-таблицу.
Находим разрешающий элемент. В данной таблице он находится на пересечении строки и столбца .
Задача о раскрое

Задача о раскрое

Задача о раскрое

Задача о раскрое

Задача о раскрое

Задача о раскрое

Задача о раскрое
Оптимальный план целочисленной задачи найден.
Ответ:

Найдем другие решения этой задачи. Так как в первой строке L симплекс-таблицы при и коэффициенты равные 0, эти переменные в L не входят и могут быть больше 0.
Из последней строки конечной таблицы, учитывая условие получаем Далее рассмотрим 2 возможных случая
и При из предпоследней строки таблицы с учётом условия получаем Следовательно, или
При из этого же условия получаем
Таким образом, получаем еще пять решений.
Задача о раскрое

Следовательно, задача имеет 6 решений.
1) при решение
2) при решение
3) при решение
4) при решение
5) при решение
6) при решение
Задача о раскрое

Можно принять во внимание дополнительные соображения по поводу лучшего решения:
Минимальные отходы.
Так как второй способ распила - безотходный, лучшее решение - то, при котором максимальное число бревен распиливается этим способом.
Таким образом, лучшее решение − третье.
Задача о раскрое
Наименьшее число распилов.
При первом способе - 2 распила , при втором - 2 распила, при третьем - 3 распила.
Лучшее решение первое и третье, так как они не используют третьего способа распила.

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

Метод ветвей и границ
L = x1+ 2x2 → max

Метод ветвей и границ

Метод ветвей и границ

Метод ветвей и границ

Метод ветвей и границ
Решение в точке Е (5;4).
Ответ: L max=L (5;4)=13.

1. Целочисленной задачей линейного программирования называется задача линейного программирования, в которой дополнительно требуются, чтобы...
все коэффициенты целевой функции были целыми;
все коэффициенты ограничений были целыми;
все переменные были целыми;
все коэффициенты целевой функции, ограничений и переменные были целыми.
Задания для самоконтроля

2. Целой частью числа x называется…
максимальное целое число, которое не меньше x;
максимальное целое число, которое не больше x;
минимальное целое число, которое не больше x;
минимальное целое число, которое не меньше x.
Задания для самоконтроля

3. В методе отсечений Гомори в симплекс-таблицу оптимального нецелочисленного решения добавляется строка, для которой...
коэффициент в первом столбце максимальный;
коэффициент в первом столбце имеет максимальную целую часть;
коэффициент в первом столбце минимальный;
коэффициент в первом столбце имеет максимальную дробную часть.
Задания для самоконтроля