Целочисленное программирование

Метод Гомори

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

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

при ограничениях:

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

Наиболее распространенным методом решения задач целочисленного программирования является метод Гомори, основанный на симплексном методе.

Напомним, что целой частью числа а называется наибольшее целое число, не превышающее . Дробной частью числа а называется разность между числом и его целой частью. Целую часть числа обозначают [ ], а дробную часть — , т.е. .

Алгоритм метода Гомори

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

2. Если в оптимальном решении не все переменные целочисленные, составить дополнительное ограничение (сечение Гомори). Сечение строится по базисной переменной, имеющей наибольшую дробную часть. Пусть в оптимальном решении базисная переменная, имеющая наибольшую дробную часть

где — множество индексов свободных переменных.

Разбить все коэффициенты и свободный член (2.2) на два слагаемых — целую и дробную часть. Неравенство

называется сечением Гомори. Дополнительное ограничение имеет вид

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

Пример задачи №17

Найти наибольшее значение функции

при ограничениях:

Решим задачу симплексным методом без учета целочисленности Для этого приведем ее к каноническому виду

Решение нецелочисленное, поэтому строим сечение Гомори. Возьмем первое уравнение из последней симплексной таблицы, так как у переменной наибольшая дробная часть :

Сечение примет вид

или

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

Решим задачу симплексным методом.

Данное решение целочисленное, значит, исходная задача решена.

Дадим геометрическую иллюстрацию метода Гомори по задаче из предыдущего примера. Областью допустимых решений является четырехугольник (Рис.2.4). Оптимальное решение задачи совпадает с точкой . Наибольшую дробную часть имеет переменная , ее целая часть равна 5.

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

Транспортная задача

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

Имеется пунктов производства однородного продукта с объемами производства и пунктов потребления с объемами потребления . Известна стоимость перевозки единицы продукта от каждого пункта производства до каждого пункта потребления:

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

Различают два типа транспортных задач. Если суммарные запасы продукта поставщиков равны суммарным объемам потребления

то это задача закрытого типа. В противном случае задачу называют задачей открытого типа.

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

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

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

1. Найти первоначальное опорное решение (распределение поставок), например, методом «минимального тарифа».

2. Проверить решение на оптимальность методом потенциалов. Для этого найти потенциалы для каждой строки и столбца из условия

справедливого для занятых клеток. Первоначально положить .

· Для всех свободных клеток рассчитать оценки

Если все , то найденное решение оптимально.

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

· Если решение не оптимально, необходимо перейти к новому опорному решению (новому плану поставок), которое ближе к оптимальному, чем предыдущее. Необходимо ввести в базис свободную переменную имеющую наибольшую положительную оценку. Для этого построить цикл для соответствующей этой переменной клетки. Цикл строится по занятым клеткам и имеет прямоугольную конфигурацию. Вершины цикла занумеровать, начиная со свободной клетки. Среди клеток с четными номерами найти наименьший объем поставок X и перераспределить его по циклу: в клетки с нечетными номерами его надо прибавить к поставке, в клетки с четными номерами вычесть. Выписать новое решение и значение целевой функции.

· Переход в п. 2.

Пример задачи №18

Найдем исходное опорное решение по методу «наименьшего тарифа» и оценим это решение на оптимальность.

По занятым клеткам составим систему уравнений:

Получим 7 уравнений и 8 неизвестных.

Если

Находим оценки свободных клеток по формуле

Найденное решение не оптимально, так как

Построим цикл для клетки (1; 5). В таблице в клетку (1; 5) даем поставку величиной , тогда нарушится баланс в первой строке и в пятом столбце. Это же количество поставок вычтем из поставок клеток (1; 4) и (2; 5) и прибавим к (2; 4).

Цикл построен.

Определим

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

Составим систему уравнений и, полагая , найдем значения всех остальных потенциалов:

Находим оценки свободных клеток:

Решение не оптимально, возьмем свободную клетку с наибольшей положительной оценкой и построим для нее цикл. Определим

Строим третью таблицу.

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

Находим оценки свободных клеток:

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

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

Если суммарные поставки меньше суммарных потребностей, т.е.

то вводят фиктивный пункт производства с объемом

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

Если суммарные поставки больше суммарных потребностей, т.е.

то вводят фиктивный пункт потребления с объемом

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

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

Вырожденность и альтернативный оптимум в транспортных задачах

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

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

Если два решения и являются оптимальными, то множество всех оптимальных решений имеет вид:

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